Message complexity of population protocols

DOI10.4230/LIPICS.DISC.2020.6zbMATH Open1543.68027MaRDI QIDQ6535003FDOQ6535003

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

Publication date: 2 November 2023

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

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)

Cites Work

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

Cited In (3)

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

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)