Simple and fast approximate counting and leader election in populations

DOI10.1016/J.IC.2021.104698OpenAlexW3119807236MaRDI QIDQ2139094FDOQ2139094

Michail Theofilatos, Othon Michail, P. G. Spirakis

Publication date: 17 May 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2021.104698

Recommendations

• Simple and fast approximate counting and leader election in populations
• Brief announcement: Fast approximate counting and leader election in populations
• Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
• Polylogarithmic-time leader election in population protocols
• Simple and Efficient Leader Election

zbMATH Keywords

epidemicapproximate countingcountingleader electionpopulation protocolpolylogarithmic time protocol

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Computation in networks of passively mobile finite-state sensors
• Computing on an anonymous ring
• Computation with finite stochastic chemical reaction networks
• The computational power of population protocols
• Fast computation by population protocols with a leader
• Deterministic function computation with chemical reaction networks
• Title not available (Why is that?)
• Stably computable predicates are semilinear
• Distributed computation in dynamic networks
• Mediated population protocols
• Simple and efficient local codes for distributed stable network construction
• Self-stabilizing Counting in Mobile Sensor Networks with a Base Station
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• Passively mobile communicating machines that use restricted space
• Naming and Counting in Anonymous Unknown Dynamic Networks
• Timing in chemical reaction networks
• Space-optimal counting in population protocols
• Title not available (Why is that?)
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks
• Population protocols with faulty interactions: the impact of a leader
• Mediated Population Protocols: Leader Election and Applications
• Polylogarithmic-Time Leader Election in Population Protocols
• Terminating distributed construction of shapes and patterns in a fair solution of automata
• Stable leader election in population protocols requires linear time
• Brief announcement: fast approximate counting and leader election in populations
• On space complexity of self-stabilizing leader election in mediated population protocol
• Time-Space Trade-offs in Population Protocols
• Title not available (Why is that?)
• Title not available (Why is that?)
• How many cooks spoil the soup?

Cited In (1)

• Simple and fast approximate counting and leader election in populations

This page was built for publication: Simple and fast approximate counting and leader election in populations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2139094)