Space-efficient population protocols for exact majority on general graphs
Abstract
We study exact majority consensus in the population protocol model. In this model, the system is described by a graph \(G = (V,E)\) with n nodes, and in each time step, a scheduler samples uniformly at random a pair of adjacent nodes to interact. In the exact majority consensus task, each node is given a binary input, and the goal is to design a protocol that almost surely reaches a stable configuration, where all nodes output the majority input value.
Fields of Study & Subjects
Distributed systems and fault tolerance
Opportunistic and Delay-Tolerant Networks
Distributed Control Multi-Agent Systems
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 574–612
- Publication date
- 1 January 2026
- Language
- EN