Analysis of fully distributed splitting and naming probabilistic procedures and applications

DOI10.1016/J.TCS.2015.02.016MaRDI QIDQ2345463zbMATH OpenOpenAlexFDO

Authors A. Zemmari, Yves Métivier, John Michael Robson

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

countingprobabilistic analysisMonte Carlo algorithmelection algorithmspanning tree computationsplitting and naming

Mathematics Subject Classification ID

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

Recommendations

• Analysis of fully distributed splitting and naming probabilistic procedures and applications (extended abstract)
• Graph Transformations
• Anonymous processors with synchronous shared memory: Monte Carlo algorithms
• On lower bounds for the time and the bit complexity of some probabilistic distributed graph algorithms. Extended abstract
• Distributed enumeration

Cites work

• scientific article; zbMATH DE number 1979528 (Why is no real title available?)
• scientific article; zbMATH DE number 790246 (Why is no real title available?)
• Asymptotic properties of a leader election algorithm
• Calling names on nameless networks
• Computing on an anonymous ring
• Distributed Computing
• Elections in anonymous networks
• How to select a loser
• Introduction to Distributed Algorithms
• On the distribution for the duration of a randomized leader election algorithm
• Randomized leader election
• Symmetry breaking in distributed networks
• The computational power of population protocols
• \textsc{Maximal Independent Sets} in radio networks

Cited in

(10)

• Beeping a deterministic time-optimal leader election
• Global synchronization and consensus using beeps in a fault-prone multiple access channel
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• Distributed enumeration
• Counting in one-hop beeping networks
• A lower bound for probabilistic distributed algorithms
• Analysis of fully distributed splitting and naming probabilistic procedures and applications (extended abstract)
• Assigning labels in an unknown anonymous network with a leader
• Computing large independent sets in a single round
• Anonymous processors with synchronous shared memory: Monte Carlo algorithms

This page was built for publication: Analysis of fully distributed splitting and naming probabilistic procedures and applications

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