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 G* _{n,k}*, consisting of

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(