[Colloq] Thesis Defense: Sott Roche, Mon, Nov 14, 10 AM, 366 WVH

[Rajmohan Rajaraman]

TITLE: Robust local algorithms for communication and stability in distributed networks
SPEAKER: Scott Roche
DATE: Monday, November 14
TIME: 10:00am-12:00noon

LOCATION: 366 WVH

ABSTRACT:

Distributed systems running on large-scale networks such as the Internet
need to cope with constant change and interruption. There is a strong
benefit to algorithms, protocols, and overlay networks that can adapt to
these changes. Furthermore, it is even better if these systems operate
in a decentralized fashion, in which individual agents know little about
the rest of the network, yet are still able to carry out useful
computations.  

My thesis work focuses on two “lower-layer” primitives essential for
robust distributed, networked systems: communication through information
spreading protocols and distributed maintenance of overlay network
topology. The first topic involves a protocol for information spreading,
with potential applications to the study of the spread of epidemics on
networks. We introduce a process we call coalescing-branching (cobra)
random walks and place them in the context of other random-walk based
information spreading protocols. We study the cover time of these walks
— the number of time steps until all nodes have been visited by the walk
at least once. We provide high-probability upper bounds to the cover
time for various graph families: trees, grids, cliques, and arbitrary
graphs. We also provide a bound for cover time in terms of the
conductance of a graph.

The second branch of work focuses on a distributed protocol which
maintains the expander topology of the overlay network in the presence
of large-scale churn of nodes. The algorithm makes use of random walks
as a source of randomness to create new edges. We show that this
algorithm can withstand up to n / polylog(n) adversarial node deletions
and additions per round while maintaining a network that is an
almost-everywhere expander graph, while only sending a polylogarithmic
number of bits per node per round.  

COMMITTEE:

George Giakkoupis (INRIA Rennes, France)
Gopal Pandurangan (U. Houston)
Rajmohan Rajaraman (Advisor)
Ravi Sundaram 
Daniel Wichs