Expressive Power of Broadcast Consensus Protocols

DOI10.4230/LIPIcs.CONCUR.2019.31OpenAlexW2970698689MaRDI QIDQ5875393

Michael Blondin, Javier Esparza, Stefan Jaax

Publication date: 3 February 2023

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

zbMATH Keywords

distributed computingcomplexity theorycounter machinespopulation protocols

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Fast and succinct population protocols for Presburger arithmetic ⋮ Protocols with constant local storage and unreliable communication ⋮ Unnamed Item ⋮ The complexity of verifying population protocols

Cites Work

• Verification of population protocols
• The method of forced enumeration for nondeterministic automata
• The computational power of population protocols
• Computation in networks of passively mobile finite-state sensors
• Context-free commutative grammars with integer counters and resets
• The Power of Well-Structured Systems
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• Nondeterministic Space is Closed under Complementation
• Time-Space Trade-offs in Population Protocols
• Clocked Population Protocols
• Testing finite-state machines: state identification and verification
• Computation in networks of passively mobile finite-state sensors
• Counter machines and counter languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item