2018/08/27 by David Doty, Doty, David, Mahsa Eftekhari +1
Computer Science · #Computational Complexity (cs.CC) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1808.08913
openalex publication_date 2018/08/27 · openalex created_date 2022/08/03 · openalex updated_date 2026/07/28
We study uniform population protocols: networks of anonymous agents whose\npairwise interactions are chosen at random, where each agent uses an identical\ntransition algorithm that does not depend on the population size n. Many\nexisting polylog(n) time protocols for leader election and majority\ncomputation are nonuniform: to operate correctly, they require all agents to be\ninitialized with an approximate estimate of n (specifically, the exact value\n lfloor \log n rfloor). Our first main result is a uniform protocol for\ncalculating \log(n) \± O(1) with high probability in O(\log2 n) time and\nO(\log4 n) states (O(\log \log n) bits of memory). The protocol is\nconverging but not terminating: it does not signal when the estimate is close\nto the true value of \log n. If it could be made terminating, this would\nallow composition with protocols, such as those for leader election or\nmajority, that require a size estimate initially, to make them uniform (though\nwith a small probability of failure). We do show how our main protocol can be\nindirectly composed with others in a simple and elegant way, based on the\nleaderless phase clock, demonstrating that those protocols can in fact be made\nuniform. However, our second main result implies that the protocol cannot be\nmade terminating, a consequence of a much stronger result: a uniform protocol\nfor any task requiring more than constant time cannot be terminating even with\nprobability bounded above 0, if infinitely many initial configurations are\ndense: any state present initially occupies \Ω(n) agents. (In particular,\nno leader is allowed.) Crucially, the result holds no matter the memory or time\npermitted. Finally, we show that with an initial leader, our size-estimation\nprotocol can be made terminating with high probability, with the same\nasymptotic time and space bounds.\n