טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentToukan Tariq
SubjectFault-Tolerant Information Spreading Algorithms
DepartmentDepartment of Computer Science
Supervisor Professor Keren Censor-Hillel
Full Thesis textFull thesis text - English Version


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 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.