DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2021.4

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

Authors: Dan Alistarh, Rati Gelashvili, and Giorgi Nadiradze

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{alistarh_et_al:LIPIcs.DISC.2021.4,
  author =	{Alistarh, Dan and Gelashvili, Rati and Nadiradze, Giorgi},
  title =	{{Lower Bounds for Shared-Memory Leader Election Under Bounded Write Contention}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.4},
  URN =		{urn:nbn:de:0030-drops-148063},
  doi =		{10.4230/LIPIcs.DISC.2021.4},
  annote =	{Keywords: Lower Bounds, Leader Election, Shared-Memory}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.7

Dynamic Averaging Load Balancing on Cycles

Authors: Dan Alistarh, Giorgi Nadiradze, and Amirmojtaba Sabour

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed at a randomly chosen graph node. In the same step, the chosen node picks a random neighbor, and the two nodes balance their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on n and on the graph structure. Variants of the above graphical balanced allocation process have been studied previously by Peres, Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and Sun, 2015]. These authors left as open the question of characterizing the gap in the case of cycle graphs in the dynamic case, where weights are created during the algorithm’s execution. For this case, the only known upper bound is of 𝒪(n log n), following from a majorization argument due to [Peres et al., 2015], which analyzes a related graphical allocation process. In this paper, we provide an upper bound of 𝒪 (√n log n) on the expected gap of the above process for cycles of length n. We introduce a new potential analysis technique, which enables us to bound the difference in load between k-hop neighbors on the cycle, for any k ≤ n/2. We complement this with a "gap covering" argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We provide analytical and experimental evidence that our upper bound on the gap is tight up to a logarithmic factor.

Cite as

Dan Alistarh, Giorgi Nadiradze, and Amirmojtaba Sabour. Dynamic Averaging Load Balancing on Cycles. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alistarh_et_al:LIPIcs.ICALP.2020.7,
  author =	{Alistarh, Dan and Nadiradze, Giorgi and Sabour, Amirmojtaba},
  title =	{{Dynamic Averaging Load Balancing on Cycles}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.7},
  URN =		{urn:nbn:de:0030-drops-124142},
  doi =		{10.4230/LIPIcs.ICALP.2020.7},
  annote =	{Keywords: Algorithms, Load Balancing}
}

Search Results

Documents authored by Nadiradze, Giorgi

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

Abstract

Cite as

Dynamic Averaging Load Balancing on Cycles

Abstract

Cite as

Thanks for your feedback!

Could not send message