License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.24
URN: urn:nbn:de:0030-drops-148266
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14826/
Go to the corresponding LIPIcs Volume Portal

Hitron, Yael ; Parter, Merav

General CONGEST Compilers against Adversarial Edges

pdf-format:
LIPIcs-DISC-2021-24.pdf (0.7 MB)

Abstract

We consider the adversarial CONGEST model of distributed computing in which a fixed number of edges (or nodes) in the graph are controlled by a computationally unbounded adversary that corrupts the computation by sending malicious messages over these (a-priori unknown) controlled edges. As in the standard CONGEST model, communication is synchronous, where per round each processor can send O(log n) bits to each of its neighbors.
This paper is concerned with distributed algorithms that are both time efficient (in terms of the number of rounds), as well as, robust against a fixed number of adversarial edges. Unfortunately, the existing algorithms in this setting usually assume that the communication graph is complete (n-clique), and very little is known for graphs with arbitrary topologies. We fill in this gap by extending the methodology of [Parter and Yogev, SODA 2019] and provide a compiler that simulates any CONGEST algorithm ? (in the reliable setting) into an equivalent algorithm ?' in the adversarial CONGEST model. Specifically, we show the following for every (2f+1) edge-connected graph of diameter D:
- For f = 1, there is a general compiler against a single adversarial edge with a compilation overhead of Ô(D³) rounds. This improves upon the Ô(D⁵) round overhead of [Parter and Yogev, SODA 2019] and omits their assumption regarding a fault-free preprocessing phase.
- For any constant f, there is a general compiler against f adversarial edges with a compilation overhead of Ô(D^{O(f)}) rounds. The prior compilers of [Parter and Yogev, SODA 2019] were limited to a single adversarial edge.
Our compilers are based on a new notion of fault-tolerant cycle covers. The computation of these cycles in the adversarial CONGEST model constitutes the key technical contribution of the paper.

BibTeX - Entry

@InProceedings{hitron_et_al:LIPIcs.DISC.2021.24,
  author =	{Hitron, Yael and Parter, Merav},
  title =	{{General CONGEST Compilers against Adversarial Edges}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{24:1--24:18},
  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/opus/volltexte/2021/14826},
  URN =		{urn:nbn:de:0030-drops-148266},
  doi =		{10.4230/LIPIcs.DISC.2021.24},
  annote =	{Keywords: CONGEST, Cycle Covers, Byzantine Adversaries}
}

Keywords: CONGEST, Cycle Covers, Byzantine Adversaries
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI