The Taub Faculty of Computer Science Events and Talks

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.