Dana Angluin, James Aspnes, and Dongqu Chen. A population protocol for binary signaling consensus. Available as YALEU/DCS/TR-1527, August 2016.
We study the convergence properties of a simple population protocol for consensus using binary signaling, where the communication in each interaction is limited to a single bit transmitted from the initiator to the responder. We consider a population which consists of n agents, where pairs of individuals are drawn uniformly at random to interact. Each agent has a confidence level for a binary preference and a more confident agent supports the preference with higher probability. An agent increases its confidence level when interacting with another agent supporting the preference, and decreases its confidence level otherwise. We prove that with high probability a three-state binary signaling population protocol reaches consensus after Θ(n log n) interactions in the worst case, regardless of the initial configuration. In the general case, a continuous-time binary signaling process in the limit will converge within O(r log nr) time (corresponding to O(nr log nr) interactions in expectation) if the initial configuration is monotone, where r is the number of confidence levels. In the other direction, we also show a convergence lower bound Ω(nr+ n log n) on the number of interactions when r is large. Experimental results are presented to support our theoretical results and to provide evidence for some conjectures.
@techreport{AngluinAC2016,
author = {Dana Angluin and James Aspnes and Dongqu Chen},
title = {A population protocol for binary signaling consensus},
mon = aug,
year = {2016},
institution="Yale University Department of Computer Science",
number="YALEU/DCS/TR-1527"
}