In this paper, we present the first leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of the population size n such that m ≥ log_2 n and m = O(log n), the proposed protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter.
展开▼