개체군 프로토콜의 최적 시간 자가 안정 리더 선출

본 연구는 표준 개체군 프로토콜 모델에서 자가 안정 리더 선출 문제의 시간 복잡도를 최초로 탐구한다. 이 모델은 구별 불가능하고 익명인 에이전트들이 균일 무작위 스케줄링에 따라 쌍으로 상호작용하며, 프로토콜은 어떤 초기 구성에서도 단일 리더 에이전트로 수렴해야 한다. 기존의 유일한 프로토콜은 예상 병렬 시간 Θ(n²)이 소요되며 n개의 상태를 사용한다. 기존 프로토콜은 에이전트 상태 변화가 멈추는 '사일런트(silent)' 특성을 가지는데, 사일런트 프로토콜은 Ω(n)의 예상 병렬 시간을 요구한다. 본 연구는 최적의 O(n) 병렬 시간과 상태를 사용하는 새로운 사일런트 프로토콜을 제안한다. 이는 기존 프로토콜보다 효율적이다. 사일런트 제약이 없을 경우, 본 연구는 점근적으로 최적인 O(log n)의 예상 병렬 시간으로 자가 안정 리더 선출 문제를 해결할 수 있음을 보인다. 다만, 이 경우 최소한 지수적인 상태(준 다항식 비트 수)가 필요하다. 이 모든 프로토콜은 더 어려운 랭킹 문제, 즉 에이전트에 1부터 n까지 순위를 할당하는 문제를 해결함으로써 작동한다. 본 연구의 결과는 개체군 프로토콜에서 자가 안정 리더 선출 문제의 시간 복잡도에 대한 이해를 심화시키고, 특히 사일런트 제약 여부에 따른 성능 한계를 명확히 제시한다. 이는 분산 시스템 및 자가 조직화 시스템 설계에 중요한 이론적 기반을 제공한다.