TY - GEN
T1 - Tight Bounds on the Message Complexity of Distributed Tree Verification
AU - Kutten, Shay
AU - Robinson, Peter
AU - Tan, Ming Ming
N1 - Publisher Copyright:
© Shay Kutten, Peter Robinson, and Ming Ming Tan;
PY - 2024/1
Y1 - 2024/1
N2 - We consider the message complexity of verifying whether a given subgraph of the communication network forms a tree with specific properties both in the KTρ (nodes know their ρ-hop neighborhood, including node ids) and the KT0 (nodes do not have this knowledge) models. We develop a rather general framework that helps in establishing tight lower bounds for various tree verification problems. We also consider two different verification requirements: namely that every node detects in the case the input is incorrect, as well as the requirement that at least one node detects. The results are stronger than previous ones in the sense that we assume that each node knows the number n of nodes in the graph (in some cases) or an α approximation of n (in other cases). For spanning tree verification, we show that the message complexity inherently depends on the quality of the given approximation of n: We show a tight lower bound of Ω(n2) for the case α ≥ √2 and a much better upper bound (i.e., O(n log n)) when nodes are given a tighter approximation. On the other hand, our framework also yields an Ω(n2) lower bound on the message complexity of verifying a minimum spanning tree (MST), which reveals a polynomial separation between ST verification and MST verification. This result holds for randomized algorithms with perfect knowledge of the network size, and even when just one node detects illegal inputs, thus improving over the work of Kor, Korman, and Peleg (2013). For verifying a d-approximate BFS tree, we show that the same lower bound holds even if nodes know n exactly, however, the lower bounds is sensitive to d, which is the stretch parameter. First, under the KT0 assumption, we show a tight message complexity lower bound of Ω(n2) in the LOCAL model, when d ≤ 2+Ω(1)n . For the KTρ assumption, we obtain an upper bound on the message complexity of O(n log n) in the CONGEST model, when d ≥ maxn{2−,ρ1+1}, and use a novel charging argument to show that Ω ( ρ1 ( nρ )1+ ρc ) messages are required even in the LOCAL model for comparison-based algorithms. For the well-studied special case of KT1, we obtain a tight lower bound of Ω(n2).
AB - We consider the message complexity of verifying whether a given subgraph of the communication network forms a tree with specific properties both in the KTρ (nodes know their ρ-hop neighborhood, including node ids) and the KT0 (nodes do not have this knowledge) models. We develop a rather general framework that helps in establishing tight lower bounds for various tree verification problems. We also consider two different verification requirements: namely that every node detects in the case the input is incorrect, as well as the requirement that at least one node detects. The results are stronger than previous ones in the sense that we assume that each node knows the number n of nodes in the graph (in some cases) or an α approximation of n (in other cases). For spanning tree verification, we show that the message complexity inherently depends on the quality of the given approximation of n: We show a tight lower bound of Ω(n2) for the case α ≥ √2 and a much better upper bound (i.e., O(n log n)) when nodes are given a tighter approximation. On the other hand, our framework also yields an Ω(n2) lower bound on the message complexity of verifying a minimum spanning tree (MST), which reveals a polynomial separation between ST verification and MST verification. This result holds for randomized algorithms with perfect knowledge of the network size, and even when just one node detects illegal inputs, thus improving over the work of Kor, Korman, and Peleg (2013). For verifying a d-approximate BFS tree, we show that the same lower bound holds even if nodes know n exactly, however, the lower bounds is sensitive to d, which is the stretch parameter. First, under the KT0 assumption, we show a tight message complexity lower bound of Ω(n2) in the LOCAL model, when d ≤ 2+Ω(1)n . For the KTρ assumption, we obtain an upper bound on the message complexity of O(n log n) in the CONGEST model, when d ≥ maxn{2−,ρ1+1}, and use a novel charging argument to show that Ω ( ρ1 ( nρ )1+ ρc ) messages are required even in the LOCAL model for comparison-based algorithms. For the well-studied special case of KT1, we obtain a tight lower bound of Ω(n2).
KW - Distributed Graph Algorithm
KW - Lower Bound
UR - http://www.scopus.com/inward/record.url?scp=85184135505&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85184135505&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.OPODIS.2023.26
DO - 10.4230/LIPIcs.OPODIS.2023.26
M3 - Conference contribution
AN - SCOPUS:85184135505
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th International Conference on Principles of Distributed Systems, OPODIS 2023
A2 - Bessani, Alysson
A2 - Defago, Xavier
A2 - Nakamura, Junya
A2 - Wada, Koichi
A2 - Yamauchi, Yukiko
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 27th International Conference on Principles of Distributed Systems, OPODIS 2023
Y2 - 6 December 2023 through 8 December 2023
ER -