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.2022.7
URN: urn:nbn:de:0030-drops-171987
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17198/
Augustine, John ;
Molla, Anisur Rahaman ;
Pandurangan, Gopal ;
Vasudev, Yadu
Byzantine Connectivity Testing in the Congested Clique
Abstract
We initiate the study of distributed graph algorithms under the presence of Byzantine nodes. We consider the fundamental problem of testing the connectivity of a graph in the congested clique model in a Byzantine setting. We are given a n-vertex (arbitrary) graph G embedded in a n-node congested clique where an arbitrary subset of B nodes of the clique of size up to (1/3-ε)n (for any arbitrary small constant ε > 0) can be Byzantine. We consider the full information model where Byzantine nodes can behave arbitrarily, collude with each other, and have unlimited computational power and full knowledge of the states and actions of the honest nodes, including random choices made up to the current round.
Our main result is an efficient randomized distributed algorithm that is able to correctly distinguish between two contrasting cases: (1) the graph G⧵ B (i.e., the graph induced by the removal of the vertices assigned to the Byzantine nodes in the clique) is connected or (2) the graph G is far from connected, i.e., it has at least 2|B|+1 connected components. Our algorithm runs in O(polylog n) rounds in the congested clique model and guarantees that all honest nodes will decide on the correct case with high probability. Since Byzantine nodes can lie about the vertices assigned to them, we show that this is essentially the best possible that can be done by any algorithm. Our result can be viewed also in the spirit of property testing, where our algorithm is able to distinguish between two contrasting cases while giving no guarantees if the graph falls in the grey area (i.e., neither of the cases occur).
Our work is a step towards robust and secure distributed graph computation that can output meaningful results even in the presence of a large number of faulty or malicious nodes.
BibTeX - Entry
@InProceedings{augustine_et_al:LIPIcs.DISC.2022.7,
author = {Augustine, John and Molla, Anisur Rahaman and Pandurangan, Gopal and Vasudev, Yadu},
title = {{Byzantine Connectivity Testing in the Congested Clique}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {7:1--7:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-255-6},
ISSN = {1868-8969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17198},
URN = {urn:nbn:de:0030-drops-171987},
doi = {10.4230/LIPIcs.DISC.2022.7},
annote = {Keywords: Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, fault-tolerant computation, randomized algorithms}
}
|
Keywords: |
|
Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, fault-tolerant computation, randomized algorithms |
|
Collection: |
|
36th International Symposium on Distributed Computing (DISC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
17.10.2022 |
