Technical Report MSC-2015-08

Title: Fault-Tolerant Information Spreading Algorithms
Authors: Tariq Toukan
Supervisors: Keren Censor-Hillel
Abstract: We consider a distributed system of $n$ nodes communicating in the synchronous Vertex-Congest model. In this model, in each round, each node sends the same message of size $O(\log n)$ bits to all neighbors. We investigate the problem of information spreading, where each node has an initial message, and the goal is to collect messages of all other nodes.

Focusing on communication graphs that are $k$-vertex-connected, we argue that since the existing near-optimal algorithm that requires $O(n\log(n)/k)$ rounds after some preprocessing uses static paths for routing, it becomes highly sensitive to failures. While combining paths together and using redundant routing makes the algorithm more resistant, the construction of the paths in the presence of failures is still an open problem. On the other hand, we show that the naturally-robust fully randomized algorithm is slow on a simple family of $k$-vertex-connected graphs, denoted by $G_{n,k}$, consisting of $n/k$ cliques of size $k$ that are connected by a path of matchings, requiring $\Omega(n/\sqrt{k})$ rounds.

We propose an algorithm that uses non-uniform randomization, with probabilities that change over time according to the execution. We prove that for $G_{n,k}$, our algorithm completes in $O(n\log^3(n)/k)$ rounds with high probability, and is resilient to independent failures that occur with large probabilities.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion