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.23
URN: urn:nbn:de:0030-drops-148256
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14825/
Go to the corresponding LIPIcs Volume Portal

Hitron, Yael ; Parter, Merav

Broadcast CONGEST Algorithms against Adversarial Edges

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

Abstract

We consider the corner-stone broadcast task with an adaptive adversary that controls a fixed number of t edges in the input communication graph. In this model, the adversary sees the entire communication in the network and the random coins of the nodes, while maliciously manipulating the messages sent through a set of t edges (unknown to the nodes). Since the influential work of [Pease, Shostak and Lamport, JACM'80], broadcast algorithms against plentiful adversarial models have been studied in both theory and practice for over more than four decades. Despite this extensive research, there is no round efficient broadcast algorithm for general graphs in the CONGEST model of distributed computing. Even for a single adversarial edge (i.e., t = 1), the state-of-the-art round complexity is polynomial in the number of nodes.
We provide the first round-efficient broadcast algorithms against adaptive edge adversaries. Our two key results for n-node graphs of diameter D are as follows:
- For t = 1, there is a deterministic algorithm that solves the problem within Õ(D²) rounds, provided that the graph is 3 edge-connected. This round complexity beats the natural barrier of O(D³) rounds, the existential lower bound on the maximal length of 3 edge-disjoint paths between a given pair of nodes in G. This algorithm can be extended to a Õ((tD)^{O(t)})-round algorithm against t adversarial edges in (2t+1) edge-connected graphs.
- For expander graphs with edge connectivity of Ω(t²log n), there is a considerably improved broadcast algorithm with O(t log ² n) rounds against t adversarial edges. This algorithm exploits the connectivity and conductance properties of G-subgraphs obtained by employing the Karger’s edge sampling technique.
Our algorithms mark a new connection between the areas of fault-tolerant network design and reliable distributed communication.

BibTeX - Entry

@InProceedings{hitron_et_al:LIPIcs.DISC.2021.23,
  author =	{Hitron, Yael and Parter, Merav},
  title =	{{Broadcast CONGEST Algorithms against Adversarial Edges}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{23:1--23:19},
  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/14825},
  URN =		{urn:nbn:de:0030-drops-148256},
  doi =		{10.4230/LIPIcs.DISC.2021.23},
  annote =	{Keywords: CONGEST, Fault-Tolerant Network Design, Edge Connectivity}
}

Keywords: CONGEST, Fault-Tolerant Network Design, Edge Connectivity
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