|M.Sc Student||Toukan Tariq|
|Subject||Fault-Tolerant Information Spreading Algorithms|
|Department||Department of Computer Science||Supervisor||Professor Keren Censor-Hillel|
|Full Thesis text|
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 Gn,k, consisting of n ∕ k cliques of size k that are connected by a path of matchings, requiring Ω(n ∕ √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 Gn,k, our algorithm completes in O(n log3(n) ∕ k) rounds with high probability, and is resilient to independent failures that occur with large probabilities.