Analysis of fully distributed splitting and naming probabilistic procedures and applications

DOI10.1016/j.tcs.2015.02.016zbMath1315.68273OpenAlexW2171508772MaRDI QIDQ2345463

Akka Zemmari, John Michael Robson, Yves Métivier

Publication date: 22 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.016

zbMATH Keywords

Monte Carlo algorithmprobabilistic analysiscountingelection algorithmspanning tree computationsplitting and naming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Monte Carlo methods (65C05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items

Counting in one-hop beeping networks ⋮ Computing large independent sets in a single round ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ Unnamed Item ⋮ Global synchronization and consensus using beeps in a fault-prone multiple access channel

Cites Work

• Unnamed Item
• Unnamed Item
• How to select a loser
• Symmetry breaking in distributed networks
• Elections in anonymous networks
• Calling names on nameless networks
• On the distribution for the duration of a randomized leader election algorithm
• Randomized leader election
• The computational power of population protocols
• Asymptotic Properties of a Leader Election Algorithm
• Computing on an anonymous ring
• Introduction to Distributed Algorithms
• Maximal independent sets in radio networks
• Distributed Computing