Document Open Access Logo

Lower Bounds for Shared-Memory Leader Election Under Bounded Write Contention

Authors Dan Alistarh, Rati Gelashvili, Giorgi Nadiradze

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.4.pdf
  • Filesize: 0.67 MB
  • 17 pages

Document Identifiers

Author Details

Dan Alistarh
  • IST Austria, Klosterneuburg, Austria
Rati Gelashvili
  • Novi Research, Menlo Park, CA, USA
Giorgi Nadiradze
  • IST Austria, Klosterneuburg, Austria

Funding

  • Alistarh, Dan: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).
  • Nadiradze, Giorgi: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).

Acknowledgements

The authors would like to thank the DISC anonymous reviewers for their useful feedback and comments.

Cite AsGet BibTex

Dan Alistarh, Rati Gelashvili, and Giorgi Nadiradze. Lower Bounds for Shared-Memory Leader Election Under Bounded Write Contention. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.4

Abstract

This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrency
Keywords
  • Lower Bounds
  • Leader Election
  • Shared-Memory

Metrics

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

References

  1. Yehuda Afek, Eli Gafni, John Tromp, and Paul M. B. Vitányi. Wait-free test-and-set (extended abstract). In WDAG '92: Proceedings of the 6th International Workshop on Distributed Algorithms, pages 85-94, 1992. Google Scholar
  2. Dan Alistarh and James Aspnes. Sub-logarithmic test-and-set against a weak adversary. In International Symposium on Distributed Computing, pages 97-109. Springer, 2011. Google Scholar
  3. Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. Tight bounds for asynchronous renaming. Journal of the ACM (JACM), 61(3):1-51, 2014. Google Scholar
  4. Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui. Fast randomized test-and-set and renaming. In Proceedings of the 24th international conference on Distributed computing, DISC'10, pages 94-108, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://portal.acm.org/citation.cfm?id=1888781.1888794.
  5. Dan Alistarh, Rati Gelashvili, and Adrian Vladu. How to elect a leader faster than a tournament. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 365-374, 2015. Google Scholar
  6. James Aspnes. Notes on theory of distributed systems. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.04235.
  7. James Aspnes, Keren Censor-Hillel, Hagit Attiya, and Danny Hendler. Lower bounds for restricted-use objects. SIAM Journal on Computing, 45(3):734-762, 2016. Google Scholar
  8. Hagit Attiya and Keren Censor. Tight bounds for asynchronous randomized consensus. J. ACM, 55(5):1-26, 2008. URL: https://doi.org/10.1145/1411509.1411510.
  9. Hagit Attiya and Faith Ellen. Impossibility results for distributed computing. Synthesis Lectures on Distributed Computing Theory, 5(1):1-162, 2014. Google Scholar
  10. James E Burns and Nancy A Lynch. Bounds on shared memory for mutual exclusion. Information and Computation, 107(2):171-184, 1993. Google Scholar
  11. Cynthia Dwork, Maurice Herlihy, and Orli Waarts. Contention in shared memory algorithms. Journal of the ACM (JACM), 44(6):779-805, 1997. Google Scholar
  12. Aryaz Eghbali and Philipp Woelfel. An almost tight rmr lower bound for abortable test-and-set. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.04840.
  13. Faith Ellen, Danny Hendler, and Nir Shavit. On the inherent sequentiality of concurrent objects. SIAM Journal on Computing, 41(3):519-536, 2012. Google Scholar
  14. George Giakkoupis, Maryam Helmi, Lisa Higham, and Philipp Woelfel. An O(√n) space bound for obstruction-free leader election. In International Symposium on Distributed Computing, pages 46-60. Springer, 2013. Google Scholar
  15. George Giakkoupis, Maryam Helmi, Lisa Higham, and Philipp Woelfel. Test-and-set in optimal space. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 615-623, 2015. Google Scholar
  16. George Giakkoupis and Philipp Woelfel. Efficient randomized test-and-set implementations. Distributed Computing, 32(6):565-586, 2019. Google Scholar
  17. Wojciech Golab, Danny Hendler, and Philipp Woelfel. An o(1) rmrs leader election algorithm. SIAM Journal on Computing, 39(7):2726-2760, 2010. Google Scholar
  18. Danny Hendler and Nir Shavit. Operation-valency and the cost of coordination. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 84-91, 2003. Google Scholar
  19. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):123-149, 1991. Google Scholar
  20. Maurice Herlihy, Victor Luchangco, and Mark Moir. Obstruction-free synchronization: Double-ended queues as an example. In 23rd International Conference on Distributed Computing Systems, 2003. Proceedings., pages 522-529. IEEE, 2003. Google Scholar
  21. Maurice P Herlihy and Jeannette M Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463-492, 1990. Google Scholar
  22. Prasad Jayanti. A time complexity lower bound for randomized implementations of some shared objects. In Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pages 201-210, 1998. Google Scholar
  23. Prasad Jayanti, King Tan, and Sam Toueg. Time and space lower bounds for nonblocking implementations. SIAM Journal on Computing, 30(2):438-456, 2000. Google Scholar
  24. Yong-Jik Kim and James H Anderson. A time complexity lower bound for adaptive mutual exclusion. Distributed Computing, 24(6):271-297, 2012. Google Scholar
  25. Leslie Lamport. A fast mutual exclusion algorithm. ACM Transactions on Computer Systems (TOCS), 5(1):1-11, 1987. Google Scholar
  26. Mark Moir and James H. Anderson. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming, 25:1-39, 1995. Google Scholar
  27. Gary L. Peterson and Michael J. Fischer. Economical solutions for the critical section problem in a distributed system (extended abstract). In Proceedings of the ninth annual ACM symposium on Theory of computing, STOC '77, pages 91-97, New York, NY, USA, 1977. ACM. URL: https://doi.org/10.1145/800105.803398.
  28. Eugene Styer and Gary L Peterson. Tight bounds for shared memory symmetric mutual exclusion problems. In Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, pages 177-191, 1989. Google Scholar
  29. John Tromp and Paul Vitányi. Randomized two-process wait-free test-and-set. Distrib. Comput., 15(3):127-135, 2002. URL: https://doi.org/10.1007/s004460200071.
  30. Jae-Heon Yang and James H Anderson. Time bounds for mutual exclusion and related problems. In Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing, pages 224-233, 1994. 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