Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Fault-Tolerant Information Spreading Algorithms
event speaker icon
Tariq Toukan (M.Sc. Thesis Seminar)
event date icon
Wednesday, 11.02.2015, 11:30
event location icon
Taub 401
event speaker icon
Advisor: Prof. Keren Censor-Hillel
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)$ to all neighbors. We investigate the problem of information spreading, where each node has an initial token, and the goal is to collect tokens 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. On the other hand, we show that the naturally-robust fully randomized algorithm is slow on the intuitive $k$-vertex-connected family of graphs consisting of $n/k$ cliques of size $k$ connected by a path of matchings, denoted by $G_{n,k}$, 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.