검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Loosely Stabilizing Leader Election on Arbitrary Graphs in Population Protocols without Identifiers or Random Numbers 식별자나 난수가 없는 인구 프로토콜의 임의 그래프에서 리더 선택을 느슨하게 안정화

Yuichi SUDO, Fukuhito OOSHITA, Hirotsugu KAKUGAWA, Toshimitsu MASUZAWA

  • 조회수

    0

  • 이것을 인용

요약 :

우리는 Angluin et al.이 제안한 인구 프로토콜 모델의 리더 선택 문제를 고려합니다. 프로토콜이 노드의 정확한 수를 알지 못하면 완전한 그래프, 임의 그래프, 트리, 선, 차수 제한 그래프 등에 대해 자체 안정화 리더 선택이 불가능합니다. 2004년에는 불가능함을 극복하기 위해 우리는 다음과 같은 개념을 도입했습니다. 느슨한 안정화, 이는 자체 안정화에 대한 폐쇄 요구 사항을 완화합니다. 느슨하게 안정화된 프로토콜은 초기 구성부터 시작하여 시스템이 안전한 구성에 도달하고 그 후에 시스템이 해당 사양(e.g., 독특한 리더) 영원히는 아니지만 충분히 오랫동안 (e.g., 노드 수에 비해 기하급수적으로 긴 시간입니다). 이전 연구에서는 임의 그래프에 대해 느슨하게 안정화된 두 가지 리더 선택 프로토콜을 제시했습니다. 하나는 에이전트 식별자를 사용하고 다른 하나는 난수를 사용하여 고유한 리더를 선출합니다. 본 논문에서는 에이전트 식별자나 난수 없이 임의의 그래프에서 리더 선택을 해결하는 느슨하게 안정화된 프로토콜을 제시합니다. 주어진 상한 N 및 노드 수의 Δ n 및 노드의 최대 수준 δ는 각각 제안된 프로토콜이 안전한 구성에 도달합니다. O(mn2d 기록 n+mNΔ2 기록 N) 예상 단계를 수행하고 Ω(NeN) 예상 단계, 여기서 m 는 모서리의 수이고 d 그래프의 직경입니다.

발행
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.489-499
발행일
2020/03/01
공개일
2019/11/27
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2019FCP0003
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
범주

작성자

Yuichi SUDO
  Osaka University
Fukuhito OOSHITA
  Nara Institute of Science and Technology
Hirotsugu KAKUGAWA
  Ryukoku University
Toshimitsu MASUZAWA
  Osaka University

키워드