{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:36:57Z","timestamp":1782970617610,"version":"3.54.5"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,6,20]],"date-time":"2007-06-20T00:00:00Z","timestamp":1182297600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2007,7,13]]},"DOI":"10.1007\/s00446-007-0034-0","type":"journal-article","created":{"date-parts":[[2007,6,19]],"date-time":"2007-06-19T13:23:53Z","timestamp":1182259433000},"page":"75-93","source":"Crossref","is-referenced-by-count":23,"title":["Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings"],"prefix":"10.1007","volume":"20","author":[{"given":"Joffroy","family":"Beauquier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maria","family":"Gradinariu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Colette","family":"Johnen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,6,20]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Anagnostou, E., El-Yaniv, R.: More on the power of random walks\u2014uniform self-stabilizing randomized algorithms. In: WDAG91, Distributed Algorithms 5th International Workshop Proceedings. LNCS, vol. 579, pp. 31\u201351. Springer, Heidelberg (1991)","DOI":"10.1007\/BFb0022436"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: STOC80, the 12th Annual ACM Symposium on Theory of Computing, pp. 82\u201393. ACM (1980)","DOI":"10.1145\/800141.804655"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Ostrovsky, R.: Memory-efficient and self-stabilizing network reset. In: PODC94, the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 254\u2013263 (1994)","DOI":"10.1145\/197917.198104"},{"key":"34_CR4","unstructured":"Beauquier, J., Cordier, S., Dela\u00ebt, S.: Optimum probabilistic self-stabilization on uniform rings. In: WSS95, the 2nd Workshop on Self-Stabilizing Systems, pp. 15.1\u201315.15 (1995)"},{"issue":"5","key":"34_CR5","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1006\/jpdc.2001.1832","volume":"62","author":"J. Beauquier","year":"2002","unstructured":"Beauquier J., Durand-Lose J., Gradinariu M. and Johnen C. (2002). Token based self-stabilizing uniform algorithms. J Parallel Distrib. Comput. 62(5): 899\u2013921","journal-title":"J Parallel Distrib. Comput."},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Gradinariu, M., Johnen, C.: Memory space requirements for self-stabilizing leader election protocols. In: PODC99, the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 199\u2013208 (1999)","DOI":"10.1145\/301308.301358"},{"key":"34_CR7","unstructured":"Beauquier, J., Gradinariu, M., Johnen, C.: Randomized self- stabilizing and space optimal leader election under arbitrary scheduler on rings. Technical Report 1225, L.R.I, December (1999)"},{"key":"34_CR8","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Gradinariu, M., Johnen, C.: Cross-over composition - enforcement of fairness under unfair adversary. In: WSS01, the 5th International Workshop on Self-Stabilizing Systems. LNCS, vol. 2194, pp. 19\u201334. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-45438-1_2"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Johnen, C., Messika, S.: All k-bounded policies are equivalent for self-stabilization. In: SSS\u201906, the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems. LNCS. Springer, Heidelberg (2006)","DOI":"10.1007\/978-3-540-49823-0_6"},{"key":"34_CR10","unstructured":"Billingsley P. (1986). Probability and Measure. Wiley"},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"Boulinier, C., Petit, F., Villain, V.: When graph theory helps self-stabilization. In: PODC04, the 23th Annual ACM Symposium on Principles of Distributed Computing, pp. 150\u2013160 (2004)","DOI":"10.1145\/1011767.1011790"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Christoff, I.: Testing equivalences and fully abstract models for probabilistic processes. In: CONCUR90, the 1st International Conference on Concurrency Theory. LNCS, vol. 458, pp. 126\u2013140, Springer, Heidelberg (1990)","DOI":"10.1007\/BFb0039056"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Datta, A.K., Tixeuil, S., Gradinariu, M.: Self-stabilizing mutual exclusion under arbitrary scheduler. Comput. J. 47(1) (2004)","DOI":"10.1093\/comjnl\/47.3.289"},{"key":"34_CR14","unstructured":"de Alfaro, L.: Formal Verification of Probabilistic systems. PhD Thesis, Stanford University, (1997)"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"D\u00e9fago, X., Gradinariu, M., Messika, S., Raipin Parv\u00e9dy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In: DISC06, the 20th International Conference on Distributed Computing. LNCS, vol. 3274, pp. 46\u201360. Springer, Heidelberg (2006)","DOI":"10.1007\/11864219_4"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Dolev, S., Gouda, M.G., Schneider, M.: Memory requirements for silent stabilization. In: PODC96, the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 27\u201334 (1996)","DOI":"10.1145\/248052.248055"},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Dolev, S., Herman, T.: Parallel composition of stabilizing algorithms. In: WSS99, the 4th Workshop on Self-Stabilizing Systems (published in association with ICDCS99 The 19th IEEE International Conference on Distributed Computing Systems), pp. 25\u201332 (1999)","DOI":"10.1109\/SLFSTB.1999.777483"},{"key":"34_CR18","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02278851","volume":"7","author":"S. Dolev","year":"1993","unstructured":"Dolev S., Israeli A. and Moran S. (1993). Self-stabilization of dynamic systems assuming only Read\/Write atomicity. Distrib. Comput. 7: 3\u201316","journal-title":"Distrib. Comput."},{"key":"34_CR19","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1109\/32.387472","volume":"21","author":"S. Dolev","year":"1995","unstructured":"Dolev S., Israeli A. and Moran S. (1995). Analyzing expected time by scheduler-luck games. IEEE Trans. Softw. Eng. 21: 429\u2013439","journal-title":"IEEE Trans. Softw. Eng."},{"key":"34_CR20","doi-asserted-by":"crossref","unstructured":"Duchon, P., Hanusse, N., Tixeuil, S.: Optimal randomized self- stabilizing mutual exclusion on synchronous rings. In: DISC04, the 18th International Conference on Distributed Computing. LNCS, vol. 3274, pp. 216\u2013229 Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-30186-8_16"},{"issue":"1","key":"34_CR21","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s00446-003-0102-z","volume":"17","author":"M. Duflot","year":"2004","unstructured":"Duflot M., Fribourg L. and Picaronny C. (2004). Randomized dining philosophers without fairness assumption. Distrib. Comput. 17(1): 65\u201376","journal-title":"Distrib. Comput."},{"issue":"3","key":"34_CR22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s00446-005-0142-7","volume":"18","author":"L. Fribourg","year":"2006","unstructured":"Fribourg L., Messika S. and Picaronny C. (2006). Coupling and self- stabilization. Distrib. Comput. 18(3): 221\u2013232","journal-title":"Distrib. Comput."},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"Gouda, M.G., Haddix, F.: The alternator. In: WSS99, the 4th Workshop on Self-Stabilizing Systems (published in association with ICDCS99 The 19th IEEE International Conference on Distributed Computing Systems), pp. 48\u201353 (1999)","DOI":"10.1109\/SLFSTB.1999.777486"},{"key":"34_CR24","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1109\/32.92911","volume":"17","author":"M.G. Gouda","year":"1991","unstructured":"Gouda M.G. and Herman T. (1991). Adaptive programming. IEEE Trans. Softw. Eng. 17: 911\u2013921","journal-title":"IEEE Trans. Softw. Eng."},{"key":"34_CR25","doi-asserted-by":"crossref","unstructured":"Gradinariu, M., Johnen, C.: Self-stabilizing neighborhood unique naming under unfair scheduler. In: Euro-Par\u201901 Parallel Processing. LNCS, vol. 2150, pp. 458\u2013465, Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44681-8_67"},{"key":"34_CR26","unstructured":"Gradinariu, M., Tixeuil, S.: Self-stabilizing vertex coloration and arbitrary graphs. In: OPODIS\u201900, 4th International Conference On Principles Of DIstributed Systems, pp. 55\u201370 (2000)"},{"key":"34_CR27","doi-asserted-by":"crossref","unstructured":"Israeli, A., Jalfon, M.: Token management schemes and random walks yield self-stabilizing mutual exclusion. In: PODC90, the 9th Annual ACM Symposium on Principles of Distributed Computing, pp. 119\u2013131 (1990)","DOI":"10.1145\/93385.93409"},{"key":"34_CR28","doi-asserted-by":"crossref","unstructured":"Itkis, G., Levin, L.: Fast and lean self-stabilizing asynchronous protocols. In: FOCS94, the 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 226\u2013239 (1994)","DOI":"10.1109\/SFCS.1994.365691"},{"key":"34_CR29","unstructured":"Johnen, C.: Service time optimal self-stabilizing token circulation protocol on anonymous unidrectional. In: SRDS02, the 21th IEEE Symposium on Reliable Distributed Systems, pp. 80\u201389. IEEE Computer Society Press, (2002)"},{"key":"34_CR30","doi-asserted-by":"crossref","unstructured":"Johnen, C.: Bounded service time and memory space optimal self-stabilizing token circulation protocol on unidirectional rings. In: IPDPS\u201904, the 18th IEEE International Parallel & Distributed Processing Symposium (2004)","DOI":"10.1109\/IPDPS.2004.1302973"},{"issue":"4","key":"34_CR31","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/71.920585","volume":"12","author":"M.H. Karaata","year":"2001","unstructured":"Karaata M.H. (2001). Self-stabilizing strong fairness under weak fairness. IEEE Trans. Parallel Distrib. Syst. 12(4): 337\u2013345","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"34_CR32","doi-asserted-by":"crossref","unstructured":"Lehmann, D., Rabin, M.O.: On the advantages of free choice: a symmetric and fully-distributed solution to the dining philosophers problem. In: POPL81, the 8th Annual ACM Symposium on Principles of Programming Languages, pp. 133\u2013138 (1981)","DOI":"10.1145\/567532.567547"},{"key":"34_CR33","doi-asserted-by":"crossref","unstructured":"Mayer, A., Ofek, Y., Ostrovsky, R., Yung, M.: Self-stabilizing symmetry breaking in constant-space. In: STOC92, the 24th Annual ACM Symposium on Theory of Computing, pp. 667\u2013678 (1992)","DOI":"10.1145\/129712.129777"},{"issue":"5","key":"34_CR34","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1006\/jpdc.2001.1828","volume":"62","author":"M. Nesterenko","year":"2002","unstructured":"Nesterenko M. and Arora A. (2002). Stabilization-preserving atomicity refinement. J. Parallel Distrib. Comput. 62(5): 766\u2013791","journal-title":"J. Parallel Distrib. Comput."},{"issue":"1","key":"34_CR35","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01843570","volume":"1","author":"A. Pnueli","year":"1986","unstructured":"Pnueli A. and Zuck L. (1986). Verification of multiprocess probabilistic protocols. Distrib. Comput. 1(1): 53\u201372","journal-title":"Distrib. Comput."},{"key":"34_CR36","doi-asserted-by":"crossref","unstructured":"Pogosyants, A., Segala, R.: Formal verification of timed properties of randomized distributed algorithms. In: PODC95, the 14th Annual ACM Symposium on Principles of Distributed Computing, pp. 174\u2013183 (1995)","DOI":"10.1145\/224964.224984"},{"key":"34_CR37","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Randomized byzantine generals. In: FOCS84, the 24st Annual IEEE Symposium on Foundations of Computer Science, pp. 403\u2013409 (1984)","DOI":"10.1109\/SFCS.1983.48"},{"key":"34_CR38","doi-asserted-by":"crossref","unstructured":"Rosaz, L.: Self-stabilizing token circulation on asynchronous uniform unidirectional rings. In: PODC00, the 19th Annual ACM Symposium on Principles of Distributed Computing, pp. 249\u2013258 (2000)","DOI":"10.1145\/343477.343626"},{"key":"34_CR39","unstructured":"Segala, R.: Modeling and Verification of Randomized Distributed Real-Time Systems. PhD thesis, MIT, Departament of Electrical Engineering and Computer Science (1995)"},{"key":"34_CR40","doi-asserted-by":"crossref","unstructured":"Segala, R., Lynch, N.: Probabilistic simulations for probabilistic processes. In: CONCUR94, the 5th International Conference on Concurrency Theory. LNCS, vol. 836, pp. 481\u2013496. Springer, Heidelberg (1994)","DOI":"10.1007\/978-3-540-48654-1_35"},{"key":"34_CR41","doi-asserted-by":"crossref","unstructured":"van Glabbeek, R.J., Smolka, S.A., Steffen, B., Toft, C.M.N.: Reactive, generative and stratified models of probabilistic processes. In: LICS90, the 5th Annual IEEE Symposium on Logic in Computer Science (1990)","DOI":"10.1109\/LICS.1990.113740"},{"key":"34_CR42","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: Automatic verification of probabilistic concurrent finite-state programs. In: FOCS85, the 25st Annual IEEE Symposium on Foundations of Computer Science, pp. 327\u2013338, (1985)","DOI":"10.1109\/SFCS.1985.12"},{"key":"34_CR43","doi-asserted-by":"crossref","unstructured":"Varghese, G.: Compositional proofs of self-stabilizing protocols. In WSS97, the 3rd Workshop on Self-Stabilizing Systems, pp. 80\u201394. Carleton University Press (1997)","DOI":"10.1515\/9780773591141-007"},{"key":"34_CR44","doi-asserted-by":"crossref","unstructured":"Wu, S.H., Smolka, S.A., Stark, E.W.: Composition and behaviors of probabilistic I\/O automata. In: CONCUR94, the 5th International Conference on Concurrency Theory. LNCS, vol. 836, pp. 513\u2013528 Springer, Heidelberg (1994)","DOI":"10.1007\/978-3-540-48654-1_37"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0034-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-007-0034-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0034-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T04:10:29Z","timestamp":1707970229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-007-0034-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,20]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,7,13]]}},"alternative-id":["34"],"URL":"https:\/\/doi.org\/10.1007\/s00446-007-0034-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,20]]}}}