A simple population protocol for fast robust approximate majority
From MaRDI portal
Publication:352239
DOI10.1007/s00446-008-0059-zzbMath1267.68055OpenAlexW2059505795MaRDI QIDQ352239
David Eisenstat, Dana Angluin, James Aspnes
Publication date: 4 July 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.828
Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)
Related Items (45)
Modular verification of chemical reaction network encodings via serializability analysis ⋮ Population protocols with faulty interactions: the impact of a leader ⋮ On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols ⋮ Polylogarithmic-Time Leader Election in Population Protocols ⋮ Fast computation by population protocols with a leader ⋮ ppsim: a software package for efficiently simulating and visualizing population protocols ⋮ Data Collection in Population Protocols with Non-uniformly Random Scheduler ⋮ TTLed Random Walks for Collaborative Monitoring in Mobile and Social Networks ⋮ On convergence and threshold properties of discrete Lotka-Volterra population protocols ⋮ Simple dynamics for plurality consensus ⋮ Constant-Space Population Protocols for Uniform Bipartition ⋮ Synthesizing and Tuning Chemical Reaction Networks with Specified Behaviours ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions ⋮ Computing with biological switches and clocks ⋮ Unnamed Item ⋮ Chemical reaction network designs for asynchronous logic circuits ⋮ Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication ⋮ Speed faults in computation by chemical reaction networks ⋮ Verifying chemical reaction network implementations: a bisimulation approach ⋮ Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ Approximate majority analyses using tri-molecular chemical reaction networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Distributed Averaging in Opinion Dynamics ⋮ Loosely-stabilizing leader election in a population protocol model ⋮ Step-by-step community detection in volume-regular graphs ⋮ Unnamed Item ⋮ Passively mobile communicating machines that use restricted space ⋮ Fault-tolerant simulation of population protocols ⋮ Uniform bipartition in the population protocol model with arbitrary graphs ⋮ Determining majority in networks with local interactions and very small local memory ⋮ Modular Verification of DNA Strand Displacement Networks via Serializability Analysis ⋮ Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits ⋮ Mediated population protocols ⋮ Verifying polymer reaction networks using bisimulation ⋮ Stable leader election in population protocols requires linear time ⋮ Time-space trade-offs in population protocols for the majority problem ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ Robust biomolecular finite automata ⋮ Noisy rumor spreading and plurality consensus ⋮ Chemical Reaction Network Designs for Asynchronous Logic Circuits ⋮ Verifying Chemical Reaction Network Implementations: A Bisimulation Approach ⋮ Distributed computation with continual population growth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- From binary consensus to multivalued consensus in asynchronous message-passing systems
- Differential equations for random processes and random graphs
- The computational power of population protocols
- Computation in networks of passively mobile finite-state sensors
- Fast Computation by Population Protocols with a Leader
This page was built for publication: A simple population protocol for fast robust approximate majority
