A simple population protocol for fast robust approximate majority
From MaRDI portal
Publication:352239
DOI10.1007/S00446-008-0059-ZzbMATH Open1267.68055OpenAlexW2059505795MaRDI QIDQ352239FDOQ352239
Authors: Dana Angluin, James Aspnes, David Eisenstat 
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
Recommendations
- A Simple Population Protocol for Fast Robust Approximate Majority
- Fast and exact majority in population protocols
- scientific article; zbMATH DE number 6850453
- A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
- Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)
Cites Work
- Computation in networks of passively mobile finite-state sensors
- Title not available (Why is that?)
- Title not available (Why is that?)
- The computational power of population protocols
- Title not available (Why is that?)
- From binary consensus to multivalued consensus in asynchronous message-passing systems
- Differential equations for random processes and random graphs
- Fast Computation by Population Protocols with a Leader
- Title not available (Why is that?)
Cited In (54)
- Asynchronous opinion dynamics in social networks
- Early adapting to trends: self-stabilizing information spread using passive communication
- Distributed computation with continual population growth
- Noisy rumor spreading and plurality consensus
- Synthesizing and tuning chemical reaction networks with specified behaviours
- Distributed computation with continual population growth
- Passively mobile communicating machines that use restricted space
- Title not available (Why is that?)
- Fault-tolerant simulation of population protocols
- Approximate majority analyses using tri-molecular chemical reaction networks
- Constant-space population protocols for uniform bipartition
- Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
- Verifying polymer reaction networks using bisimulation
- Data Collection in Population Protocols with Non-uniformly Random Scheduler
- Step-by-step community detection in volume-regular graphs
- Uniform bipartition in the population protocol model with arbitrary graphs
- Mediated population protocols
- Population protocols with faulty interactions: the impact of a leader
- Modular verification of chemical reaction network encodings via serializability analysis
- Polylogarithmic-time leader election in population protocols
- A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
- Loosely-stabilizing leader election in a population protocol model
- ppsim: a software package for efficiently simulating and visualizing population protocols
- Title not available (Why is that?)
- Fast and exact majority in population protocols
- Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions
- Robust biomolecular finite automata
- Stable leader election in population protocols requires linear time
- Simple dynamics for plurality consensus
- Space-optimal proportion consensus with population protocols
- Modular verification of DNA strand displacement networks via serializability analysis
- Fast computation by population protocols with a leader
- Message complexity of population protocols
- Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
- Distributed Averaging in Opinion Dynamics
- Verifying chemical reaction network implementations: a bisimulation approach
- Verifying chemical reaction network implementations: a bisimulation approach
- Find Your Place: Simple Distributed Algorithms for Community Detection
- Data collection in population protocols with non-uniformly random scheduler
- Chemical reaction network designs for asynchronous logic circuits
- A Simple Population Protocol for Fast Robust Approximate Majority
- Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
- Speed faults in computation by chemical reaction networks
- Simplifying analyses of chemical reaction networks for approximate majority
- Chemical reaction network designs for asynchronous logic circuits
- Phase transition of the \(k\)-majority dynamics in biased communication models
- On convergence and threshold properties of discrete Lotka-Volterra population protocols
- On convergence and threshold properties of discrete Lotka-Volterra population protocols
- Limits for rumor spreading in stochastic populations
- Time-space trade-offs in population protocols for the majority problem
- Computing with biological switches and clocks
- Determining majority in networks with local interactions and very small local memory
- A tight analysis of the parallel undecided-state dynamics with two colors
- TTLed random walks for collaborative monitoring in mobile and social networks
This page was built for publication: A simple population protocol for fast robust approximate majority
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q352239)
