A simple population protocol for fast robust approximate majority
From MaRDI portal
Publication:352239
DOI10.1007/s00446-008-0059-zzbMath1267.68055MaRDI 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
68M14: Distributed systems
68M15: Reliability, testing and fault tolerance of networks and computer systems
Related Items
Unnamed Item, Unnamed Item, Data Collection in Population Protocols with Non-uniformly Random Scheduler, Find Your Place: Simple Distributed Algorithms for Community Detection, Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions, Modular Verification of DNA Strand Displacement Networks via Serializability Analysis, Unnamed Item, Stable leader election in population protocols requires linear time, Unnamed Item, Phase transition of the \(k\)-majority dynamics in biased communication models, Modular verification of chemical reaction network encodings via serializability analysis, Loosely-stabilizing leader election in a population protocol model, Determining majority in networks with local interactions and very small local memory, Mediated population protocols, Passively mobile communicating machines that use restricted space, Population protocols with faulty interactions: the impact of a leader, Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication, Speed faults in computation by chemical reaction networks, Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits, Verifying polymer reaction networks using bisimulation, Time-space trade-offs in population protocols for the majority problem, Distributed computation with continual population growth, ppsim: a software package for efficiently simulating and visualizing population protocols, On convergence and threshold properties of discrete Lotka-Volterra population protocols, Step-by-step community detection in volume-regular graphs, Fault-tolerant simulation of population protocols, Uniform bipartition in the population protocol model with arbitrary graphs, Data collection in population protocols with non-uniformly random scheduler, Robust biomolecular finite automata, Noisy rumor spreading and plurality consensus, Fast computation by population protocols with a leader, Simple dynamics for plurality consensus, Verifying chemical reaction network implementations: a bisimulation approach, Chemical Reaction Network Designs for Asynchronous Logic Circuits, Verifying Chemical Reaction Network Implementations: A Bisimulation Approach, TTLed Random Walks for Collaborative Monitoring in Mobile and Social Networks, Synthesizing and Tuning Chemical Reaction Networks with Specified Behaviours, On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols, Polylogarithmic-Time Leader Election in Population Protocols, Constant-Space Population Protocols for Uniform Bipartition
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item