Message complexity of population protocols

DOI10.4230/LIPICS.DISC.2020.6MaRDI QIDQ6535003zbMATHFDO

Authors James Aspnes, David Doty, Mahsa Eftekhari, Eric E. Severson

Publication date 2 November 2023

zbMATH Keywords

population protocolmessage complexityspace-optimality

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Distributed systems (68M14) Communication complexity, information complexity (68Q11)

Recommendations

• The computational power of population protocols
• Simple and fast approximate counting and leader election in populations
• Time-space trade-offs in population protocols
• Brief Announcement
• Simple and fast approximate counting and leader election in populations

Cites work

• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• scientific article; zbMATH DE number 7204593 (Why is no real title available?)
• A simple population protocol for fast robust approximate majority
• Brief Announcement
• Brief announcement: Fast approximate counting and leader election in populations
• Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
• Computation in networks of passively mobile finite-state sensors
• Computation with finite stochastic chemical reaction networks
• Deterministic function computation with chemical reaction networks
• Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols
• Efficient Turing-universal computation with DNA polymers
• Fast and exact majority in population protocols
• Fast computation by population protocols with a leader
• Fast space optimal leader election in population protocols
• Leaderless deterministic chemical reaction networks
• Logarithmic Expected-Time Leader Election in Population Protocol Model
• On Counting the Population Size
• Optimal time and space leader election in population protocols
• Passively mobile communicating machines that use restricted space
• Polylogarithmic-time leader election in population protocols
• Recent results in population protocols for exact majority and leader election
• Simple and Efficient Leader Election
• Stably computable predicates are semilinear
• Time and space optimal counting in population protocols
• Time-space trade-offs in population protocols
• Timing in chemical reaction networks

Cited in

(3)

• Privacy in population protocols with probabilistic scheduling
• The computational power of population protocols
• Protocols with constant local storage and unreliable communication

This page was built for publication: Message complexity of population protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535003)