How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
Population protocols is one of the distributed computing models where a number of mobile agents change their states by pairwise interactions. A self-stabilizing protocol ensures that the system converges to the desired behavior regardless its initial configuration. A leader election allows to distinguish a single agent with the final state ELECTED, the state of the other agents is NON-ELECTED. Global fairness guarantees the occurrence of any possible transition. This paper proves that under the assumption of global fairness, no protocol using only \(n-1\) states (where \(n\) is the number of agents) can solve the self-stabilizing leader election in complete interaction graphs.
- A Simple Population Protocol for Fast Robust Approximate Majority
- Computation in networks of passively mobile finite-state sensors
- scientific article; zbMATH DE number 5605125 (Why is no real title available?)
- Self-stabilizing Counting in Mobile Sensor Networks with a Base Station
- Stably computable predicates are semilinear
- The computational power of population protocols
- On space complexity of self-stabilizing leader election in mediated population protocol
- On the power of oracle \(\varOmega ?\) for self-stabilizing leader election in population protocols
- Constructing self-stabilizing oscillators in population protocols
- Fault-tolerant simulation of population protocols
- Loosely-stabilizing leader election with polylogarithmic convergence time
- A combinatorial characterization of self-stabilizing population protocols
- Mediated population protocols: leader election and applications
- Constant-space population protocols for uniform bipartition
- Space complexity of self-stabilizing leader election in passively-mobile anonymous agents
- On space and time complexity of loosely-stabilizing leader election
- scientific article; zbMATH DE number 7561458 (Why is no real title available?)
- The Power of Global Knowledge on Self-stabilizing Population Protocols
- scientific article; zbMATH DE number 7204593 (Why is no real title available?)
- Brief announcement: Space-optimal naming in population protocols
- Constructing Self-stabilizing Oscillators in Population Protocols
- Self-stabilizing systems in spite of high dynamics
- A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States
- Brief Announcement: Population Protocols Decide Double-exponential Thresholds
- A Combinatorial Characterization of Self-stabilizing Population Protocols
- Deterministic self-stabilising leader election for programmable matter with constant memory
- Efficient assignment of identities in anonymous populations
- Sublinear-time collision detection in population protocols with polynomially many states
- Self-stabilizing mutual exclusion in dynamic networks with bounded temporal diameter
- Time-optimal self-stabilizing leader election in population protocols
- Anonymous self-stabilising localisation via spatial population protocols
- Space-efficient self-stabilizing counting population protocols on mobile sensor networks
This page was built for publication: How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692907)
