Networks Cannot Compute Their Diameter in Sublinear Time

Silvio Frischknecht, Stephan Holzer and Roger Wattenhofer

Abstract:
We study the problem of computing the diameter of a network in a distributed way. The model of distributed computation we consider is: in each synchronous round, each node can transmit a different (but) short message to each of its neighbors. We provide an lower bound for the number of communication rounds needed, where n denotes the number of nodes in the network. This lower bound is valid even if the diameter of the network is a small constant. We also show that a -approximation of the diameter requires rounds. Furthermore we use our new technique to prove an lower bound on approximating the girth of a graph by a factor
.

Guest: Stephan Holzer
Host: Chen Avin

Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks

John Augustine, Gopal Pandurangan, Peter Robinson and Eli Upfal

Abstract:
Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node {\em churn} (i.e., nodes join and leave the network continuously over time). Our main contributions are randomized distributed algorithms that guarantee {\em stable almost-everywhere agreement} with high probability even under high adversarial churn in polylogarithmic number of rounds. In particular, we present the following results:
1. An -round (n is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to {\em linear} churn {\em per round} (i.e., , for some small constant ), assuming that the churn is controlled by an oblivious adversary (has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm).
2. An -round randomized algorithm that achieves almost-everywhere agreement with high probability under up to churn per round (for some small ), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm).
Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.

Guests: Gopal Pandurangan with John Augustine and Peter Robinson
Host: Chen Avin

Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

Leonid Barenboim and Michael Elkin

Abstract:
We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2∆− 1)-edge-coloring requires O(∆) + log∗ n time [23], where ∆ is the maximum degree of the input graph. Also, recent results of [5] for vertex-coloring imply that one can get an O(∆)-edge-coloring in O(∆^ϵ ·log n) time, and an O(∆^{1+ϵ})-edge-coloring in O(log ∆ log n) time, for an arbitrarily small constant ϵ > 0. In this paper we devise a significantly faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(∆)-edge-coloring in O(∆^ϵ ) + log∗ n time, and an O(∆^{1+ϵ} )-edge-coloring in O(log ∆) + log∗ n time. This result improves the state-of-the-art running time for deterministic edge-coloring with this number of colors in almost the entire range of maximum degree ∆. Moreover, it improves it exponentially in a wide range of ∆, specifically, for 2^Ω(log* n) ≤ ∆ ≤ polylog(n). In addition, for small values of ∆ (up to log^{1−δ} n, for some fixed δ > 0) our deterministic algorithm outperforms all the existing randomized algorithms for this problem.

Guest: Leonid Barenboim
Host: Chen Avin