2018/10/24 by Dan Alistarh, Rati Gelashvili · 2 citations
paper · doi:10.1145/3289137.3289150
crossref issued 2018/10/24 · crossref published 2018/10/24 · crossref published-online 2018/10/24 · crossref published-print 2018/10/24 · crossref created 2018/10/25 · crossref deposited 2025/06/18 · crossref indexed 2026/08/03
Population protocols are a popular model of distributed computing, introduced by Angluin, Aspnes, Diamadi, Fischer, and Peralta [6] a little over a decade ago. In the meantime, the model has proved a useful abstraction for modeling various settings, from wireless sensor networks [35, 26], to gene regulatory networks [17], and chemical reaction networks [21]. In a nutshell, a population protocol consists of n agents with limited local state that interact randomly in pairs, according to an underlying communication graph, and cooperate to collectively compute global predicates. From a theoretical prospective, population protocols, with the restricted communication and computational power, are probably one of the simplest distributed model one can imagine. Perhaps surprisingly though, solutions to many classical distributed tasks are still possible. Moreover, these solutions often rely on interesting algorithmic ideas for design and interesting probabilistic techniques for analysis, while known lower bound results revolve around complex combinatorial arguments.