AnO(log3/2n) Parallel Time Population Protocol for Majority withO(logn) States
Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, Ely Porat · 2020
In population protocols, the underlying distributed network consists of n nodes (or agents), denoted by V, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by applying a state transition function that depends only on the states of the two nodes prior to the interaction. The efficiency of a population protocol is measured in terms of both time (which is the number of interactions until the nodes collectively have a valid output) and the number of possible states of nodes used by the protocol. By convention, we consider the parallel time cost, which is the time divided by n.