scientific article; zbMATH DE number 7204593

DOI10.4230/LIPICS.ICALP.2017.141zbMATH Open1442.68014arXiv1811.01235MaRDI QIDQ5111475FDOQ5111475

David Soloveichik, David Doty, Amanda Belleville

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1811.01235

Title of this publication is not available (Why is that?)

Recommendations

• Fast Computation by Population Protocols with a Leader
• Fast computation by population protocols with a leader
• The complexity of verifying population protocols
• The computational power of population protocols
• Polylogarithmic-time leader election in population protocols
• How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
• Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
• On the power of oracle \(\varOmega ?\) for self-stabilizing leader election in population protocols
• On the bit complexity of distributed computations in a ring with a leader

zbMATH Keywords

population protocolstable computationtime lower bound

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Distributed systems (68M14)

Cited In (13)

• A survey of size counting in population protocols
• Distributed computation with continual population growth
• Fast and succinct population protocols for Presburger arithmetic
• Finding cut-offs in leaderless rendez-vous protocols is easy
• Running time analysis of broadcast consensus protocols
• Automatic Analysis of Expected Termination Time for Population Protocols
• Composable computation in discrete chemical reaction networks
• Fast Computation by Population Protocols with a Leader
• Simple and fast approximate counting and leader election in populations
• Constant-Space Population Protocols for Uniform Bipartition
• Message complexity of population protocols
• Data collection in population protocols with non-uniformly random scheduler
• Computing with chemical reaction networks: a tutorial

This page was built for publication:

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