Analysis of fully distributed splitting and naming probabilistic procedures and applications
DOI10.1016/J.TCS.2015.02.016zbMATH Open1315.68273OpenAlexW2171508772MaRDI QIDQ2345463FDOQ2345463
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
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
countingprobabilistic analysisMonte Carlo algorithmelection algorithmspanning tree computationsplitting and naming
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)
Cites Work
- Introduction to Distributed Algorithms
- Computing on an anonymous ring
- The computational power of population protocols
- \textsc{Maximal Independent Sets} in radio networks
- On the distribution for the duration of a randomized leader election algorithm
- Asymptotic properties of a leader election algorithm
- How to select a loser
- Symmetry breaking in distributed networks
- Randomized leader election
- Title not available (Why is that?)
- Calling names on nameless networks
- Elections in anonymous networks
- Title not available (Why is that?)
- Distributed Computing
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)
