1 Search Results for "Antaki, Shiri"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.7
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems

Authors: Shiri Antaki, Quanquan C. Liu, and Shay Solomon

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the classic sequential, centralized setting where the main quality measure of an algorithm is its update time, i.e. the time needed to restore the solution after each update. While real-life networks are very often distributed across multiple machines, the fundamental question of finding efficient dynamic, distributed graph algorithms received little attention to date. The goal in this setting is to optimize both the round and message complexities incurred per update step, ideally achieving a message complexity that matches the centralized update time in O(1) (perhaps amortized) rounds. Toward initiating a systematic study of dynamic, distributed algorithms, we study some of the most central symmetry-breaking problems: maximal independent set (MIS), maximal matching/(approx-) maximum cardinality matching (MM/MCM), and (Δ + 1)-vertex coloring. This paper focuses on dynamic, distributed algorithms that are deterministic, and in particular - robust against an adaptive adversary. Most of our focus is on our MIS algorithm, which achieves O (m^{2/3}log² n) amortized messages in O(log² n) amortized rounds in the Congest model. Notably, the amortized message complexity of our algorithm matches the amortized update time of the best-known deterministic centralized MIS algorithm by Gupta and Khan [SOSA'21] up to a polylog n factor. The previous best deterministic distributed MIS algorithm, by Assadi et al. [STOC'18], uses O(m^{3/4}) amortized messages in O(1) amortized rounds, i.e., we achieve a polynomial improvement in the message complexity by a polylog n increase to the round complexity; moreover, the algorithm of Assadi et al. makes an implicit assumption that the network is connected at all times, which seems excessively strong when it comes to dynamic networks. Using techniques similar to the ones we developed for our MIS algorithm, we also provide deterministic algorithms for MM, approximate MCM and (Δ + 1)-vertex coloring whose message complexities match or nearly match the update times of the best centralized algorithms, while having either constant or polylog(n) round complexities.
Cite as

Shiri Antaki, Quanquan C. Liu, and Shay Solomon. Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{antaki_et_al:LIPIcs.ITCS.2022.7,
  author =	{Antaki, Shiri and Liu, Quanquan C. and Solomon, Shay},
  title =	{{Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{7:1--7:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.7},
  URN =		{urn:nbn:de:0030-drops-156039},
  doi =		{10.4230/LIPIcs.ITCS.2022.7},
  annote =	{Keywords: dynamic graph algorithms, distributed algorithms, symmetry breaking problems, maximal independent set, matching, coloring}
}
  • Refine by Author
  • 1 Antaki, Shiri
  • 1 Liu, Quanquan C.
  • 1 Solomon, Shay

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Dynamic graph algorithms

  • Refine by Keyword
  • 1 coloring
  • 1 distributed algorithms
  • 1 dynamic graph algorithms
  • 1 matching
  • 1 maximal independent set
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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