Document Open Access Logo

Proving the Herman-Protocol Conjecture

Authors Maria Bruna, Radu Grigore, Stefan Kiefer, Joël Ouaknine, James Worrell

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.104.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Maria Bruna
Radu Grigore
Stefan Kiefer
Joël Ouaknine
James Worrell

Cite AsGet BibTex

Maria Bruna, Radu Grigore, Stefan Kiefer, Joël Ouaknine, and James Worrell. Proving the Herman-Protocol Conjecture. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 104:1-104:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.104

Abstract

Herman's self-stabilization algorithm, introduced 25 years ago, is a well-studied synchronous randomized protocol for enabling a ring of N processes collectively holding any odd number of tokens to reach a stable state in which a single token remains. Determining the worst-case expected time to stabilization is the central outstanding open problem about this protocol. It is known that there is a constant h such that any initial configuration has expected stabilization time at most hN2. Ten years ago, McIver and Morgan established a lower bound of 4/27 ~ 0.148 for h, achieved with three equally-spaced tokens, and conjectured this to be the optimal value of h. A series of papers over the last decade gradually reduced the upper bound on h, with the present record (achieved in 2014) standing at approximately 0.156. In this paper, we prove McIver and Morgan's conjecture and establish that h = 4/27 is indeed optimal.
Keywords
  • randomized protocols
  • self-stabilization
  • Lyapunov function
  • expected time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Aldous and J. A. Fill. Reversible Markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at URL: http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  2. R. Arratia. Limiting point processes for rescalings of coalescing and annihilating random walks on Z^d. The Annals of Probability, 9(6):909-936, 1981. Google Scholar
  3. D. Balding. Diffusion-reaction in one dimension. J. Appl. Prob., 25:733-743, 1988. Google Scholar
  4. M. Bruna, R. Grigore, S. Kiefer, J. Ouaknine, and J. Worrell. Proving the Herman-Protocol Conjecture. Technical report, arxiv.org, 2015. Available at ěrb|http://arxiv.org/abs/1504.01130|. Google Scholar
  5. PRISM case studies. Randomised self-stabilising algorithms. ěrb|http://www.prismmodelchecker.org/casestudies/self-stabilisation.php|. Google Scholar
  6. C. Cooper, R. Elsässer, H. Ono, and T. Radzik. Coalescing random walks and voting on graphs. In Proc. PODC, pages 47-56. ACM, 2012. Google Scholar
  7. D. Coppersmith, P. Tetali, and P. Winkler. Collisions among random walks on a graph. SIAM Journal on Discrete Mathematics, 6(3):363-374, 1993. Google Scholar
  8. J.T. Cox. Coalescing random walks and voter model consensus times on the torus in Z^d. The Annals of Probability, 17(4):1333-1366, 1989. Google Scholar
  9. E. Csóka and S. Mészáros. Generalized solution for the Herman protocol conjecture. Technical report, arxiv.org, 2015. Available at ěrb|http://arxiv.org/abs/1504.06963|. Google Scholar
  10. P.-G. de Gennes. Soluble model for fibrous structures with steric constraints. J. Chem. Phys., 48(5):2257-2259, 1968. Google Scholar
  11. E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Comm. ACM, 17(11):643-644, 1974. Google Scholar
  12. S. Dolev. Self-Stabilization. MIT Press, 2000. Google Scholar
  13. Y. Feng and L. Zhang. A Tighter Bound for the Self-Stabilization Time in Herman’s Algorithm. Inf. Process. Lett., 113(13):486-488, 2013. Google Scholar
  14. Y. Feng and L. Zhang. A nearly optimal upper bound for the self-stabilization time in Herman’s algorithm. Dist. Comp., pages 1-12, 2015. Google Scholar
  15. M. E. Fisher. Walks, walls, wetting, and melting. J. Stat. Phys., 34(5-6):667-729, 1984. Google Scholar
  16. L. Fribourg, S. Messika, and C. Picaronny. Coupling and self-stabilization. Dist. Comp., 18:221-232, 2005. Google Scholar
  17. S. Y. Grigoriev and V. B. Priezzhev. Random walk of annhilating particles on the ring. Theor. Math. Phys., 146(3):411-420, 2006. Google Scholar
  18. J. Haslegrave. Bounds on Herman’s algorithm. Theoretical Computer Science, 550:100-06, 2014. Google Scholar
  19. T. Herman. Probabilistic self-stabilization. Inf. Process. Lett., 35(2):63-67, 1990. Google Scholar
  20. A. Israeli and M. Jalfon. Token management schemes and random walks yield self-stabilizing mutual exclusion. In Proc. PODC, pages 119-131. ACM, 1990. Google Scholar
  21. S. Kiefer, A. Murawski, J. Ouaknine, J. Worrell, and L. Zhang. On stabilization in Herman’s algorithm. In Proc. ICALP, volume 6756 of LNCS. Springer, 2011. Google Scholar
  22. L. Lamport. Solved problems, unsolved problems and non-problems in concurrency. In Proc. PODC, pages 1-11. ACM, 1984. Google Scholar
  23. A. McIver and C. Morgan. An elementary proof that Herman’s ring is Θ(N²). Inf. Process. Lett., 94(2):79-84, 2005. Google Scholar
  24. T. Nakata. On the expected time for Herman’s probabilistic self-stabilizing algorithm. Theor. Comput. Sci., 349(3):475-483, 2005. Google Scholar
  25. R.I. Oliveira. On the coalescence time of reversible random walks. Trans. Amer. Math. Soc., 364(4):2109-2128, 2012. Google Scholar
  26. J. Rambeau and G. Schehr. Distribution of the time at which N vicious walkers reach their maximal height. Phys. Rev. E, 83, 2011. Google Scholar
  27. G. Schehr, S. N. Majumdar, A. Comtet, and P. J. Forrester. Reunion probability of N vicious walkers: Typical and large fluctuations for large N. J. Stat. Phys., 150:491-530, 2013. Google Scholar
  28. M. Warner. Aggregation in dense solutions of rods. J. Chem. Soc. Faraday. Trans., 87(6):861-867, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact