Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings

DOI10.1006/JAGM.1996.0828MaRDI QIDQ4339006zbMATH OpenOpenAlexFDO

Authors

Publication date 9 October 1997

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1996.0828

zbMATH Keywords

contendersprobabilistic algorithms

Mathematics Subject Classification ID

Computer system organization (68M99) Parallel algorithms in computer science (68W10)

Recommendations

• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Tight lower bounds for probabilistic solitude verification on anonymous rings
• Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots
• An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks
• An efficient silent self-stabilizing 1-maximal matching algorithm in anonymous networks
• A self-stabilizing algorithm for maximal matching in anonymous networks
• A practical approximation algorithm for optimal \(k\)-anonymity
• On the time and the bit complexity of distributed randomised anonymous ring colouring
• Message terminating algorithms for anonymous rings of unknown size
• Efficient dispersion on an anonymous ring in the presence of weak Byzantine robots

Cited in

(5)

• On the number of active nodes in a multicomputer system
• Tight lower bounds for probabilistic solitude verification on anonymous rings
• Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size
• Message terminating algorithms for anonymous rings of unknown size
• Randomized function evaluation on a ring

This page was built for publication: Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings

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