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 nvertex (arbitrary) graph G embedded in a nnode 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 2B+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:17:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772556},
ISSN = {18688969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17198},
URN = {urn:nbn:de:0030drops171987},
doi = {10.4230/LIPIcs.DISC.2022.7},
annote = {Keywords: Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, faulttolerant computation, randomized algorithms}
}
Keywords: 

Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, faulttolerant computation, randomized algorithms 
Collection: 

36th International Symposium on Distributed Computing (DISC 2022) 
Issue Date: 

2022 
Date of publication: 

17.10.2022 