개체군 프로토콜의 최적 시간 자가 안정 리더 선출
Time-optimal self-stabilizing leader election in population protocols
본 연구는 표준 개체군 프로토콜 모델에서 자가 안정 리더 선출 문제의 시간 복잡도를 최초로 탐구한다. 이 모델은 구별 불가능하고 익명인 에이전트들이 균일 무작위 스케줄링에 따라 쌍으로 상호작용하며, 프로토콜은 어떤 초기 구성에서도 단일 리더 에이전트로 수렴해야 한다. 기존의 유일한 프로토콜은 예상 병렬 시간 Θ(n²)이 소요되며 n개의 상태를 사용한다. 기존 프로토콜은 에이전트 상태 변화가 멈추는 '사일런트(silent)' 특성을 가지는데, 사일런트 프로토콜은 Ω(n)의 예상 병렬 시간을 요구한다. 본 연구는 최적의 O(n) 병렬…