Fooling views: a new lower bound technique for distributed computations under congestion
- PDF / 503,612 Bytes
- 15 Pages / 595.276 x 790.866 pts Page_size
- 108 Downloads / 187 Views
Fooling views: a new lower bound technique for distributed computations under congestion Amir Abboud1 · Keren Censor-Hillel2 · Seri Khoury3 · Christoph Lenzen4 Received: 8 August 2018 / Accepted: 6 March 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of fooling views and exemplify its strength by proving two new lower bounds for triangle membership in the Congest(B) model: 1. Any 1-round algorithm requires B ≥ cΔ log n for a constant c > 0. 2. If B = 1, even in constant-degree graphs any algorithm must take Ω(log∗ n) rounds. The implication of the former is the first proven separation between the Local and the Congest models for deterministic triangle membership. The latter result is the first non-trivial lower bound on the number of rounds required, even for triangle detection, under limited bandwidth. All previous known techniques are provably incapable of giving these bounds. We hope that our approach may pave the way for proving lower bounds for additional problems in various settings of distributed computing for which previous techniques do not suffice.
1 Introduction In a group of n players with names of O(log n) bits, how many time steps does it take for someone to find out if there are three players that are all friends with each other? All computation is free, and in the beginning, all players know This research has received funding from the European Union’s Horizon 2020 research and innovation programme under Grant Agreement No. 755839. This research is also supported in part by the Israel Science Foundation (Grant 1696/14).
B
Seri Khoury [email protected] Amir Abboud [email protected] Keren Censor-Hillel [email protected] Christoph Lenzen [email protected]
1
IBM Almaden Research Center, San Jose, USA
2
Department of Computer Science, Technion, Haifa, Israel
3
UC Berkeley, Berkeley, USA
4
MPI for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
their friends. Then, at each step, each player can send B = O(log n) bits privately to each of its friends. This multi-party communication puzzle is known as the triangle detection problem in the popular Congest model of distributed computing. Its complexity is poorly understood. In the naive protocol, each player (node) tells all its friends about all its other friends (sends its neighborhood to every neighbor). This takes a single round in the Local model and O(n) rounds in Congest. A clever randomized protocol of Izumi and Le Gall [34] provides a solution with O(n 2/3 (log n)2/3 ) rounds in Congest. This algorithm was recently improved by Chang et al. [21,22]. First, in [21], the upper bound was improved to O(n 1/2+o(1) ), and more recently in [22], it was improved to O(n 1/3+o(1) ). This is essentially what we know about the problem. Before our work, it could not be ruled out that the problem can be solved in O(1) rounds, or even a single round, even with a bandw
Data Loading...
