Running time analysis of broadcast consensus protocols

DOI10.1007/978-3-030-71995-1_9OpenAlexW3140862071MaRDI QIDQ2233402

Philipp Czerner, Stefan Jaax

Publication date: 18 October 2021

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

zbMATH Keywords

distributed computingcomplexity theorybroadcast protocols

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mediated population protocols
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• On read-once vs. multiple access to randomness in logspace
• Tail bounds for sums of geometric and exponential variables
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• Semigroups, Presburger formulas, and languages
• Fast and Exact Majority in Population Protocols
• The Power of Well-Structured Systems
• Time-Space Trade-offs in Population Protocols
• Leader Election Requires Logarithmic Time in Population Protocols
• Optimal time and space leader election in population protocols
• Stably computable predicates are semilinear
• Brief Announcement
• Clocked Population Protocols
• Stable leader election in population protocols requires linear time

This page was built for publication: Running time analysis of broadcast consensus protocols