[Colloq] Thesis Proposal - Scott Roche - Robust Local Algorithms for Communication and Stability in Distributed Networks - April 9, 11am - 308 Hurtig Hall

[Fong, Andy]

Thursday, April 9th, 11:00 a.m. - 12:00 p.m

308 Hurtig Hall



Title:

Robust Local Algorithms for Communication and Stability in Distributed Networks



Abstract:

In a world in which our technological infrastructure is increasingly reliant on platforms that are distributed in nature, there is a substantial need for distributed algorithms and network designs that are able to perform a wide range of tasks as or more efficiently than their non-distributed counterparts. Furthermore, these algorithms and networks must be resilient to changes and disruptions in the network. Arguably the best way to do this is to design algorithms that are decentralized.

By exchanging messages and data with immediate neighbors and running other subprocesses locally (often involving some sort of random choice), a coordinated solution to problem still emerges from the system.



The work for my doctoral thesis focuses on two aspects of distributed algorithm design. Both involve a fully decentralized system running algorithms or processes locally, with limited system-wide knowledge. The first research area involves a protocol for information spreading with potential application to the study of epidemics on networks. We introduce a process which we call coalescing- branching random walks, that combine aspects of branching systems and coalescing particle systems and study the process on various types of finite graphs.

Specifically, we study the length of time it takes for every node in a network to be visited by the walk at least once and provide results for various types of graphs, including expanders, trees, grids, and cliques.



The second branch of work for my thesis involves designing a distributed algorithm which maintains the expander topology of a network in the presence of a high degree of adversarial deletion and insertion of nodes. This algorithm makes heavy use of random walks as a source of randomness when choosing new connections to make between nodes of the network. We show that this algorithm can withstand up to O(n/polylog(n)) adversarial node deletions/additions per round while maintaining a network that is an almost-everywhere bounded-degree expander graph in each round. Furthermore, each node need only send a polylogarithmic (in

n) number of bits in each round.



Rajmohan Rajaraman, Professor, CCIS

Ravi Sundaram, Professor, CCIS

Daniel Wichs, Assistant Professor, CCIS

Gopal Pandurangan, Associate Professor, University of Houston George Giakkoupis, Researcher, IRISA/INRIA, Rennes, France.

Andrew W. Fong
Assistant Director for Graduate Admissions and Enrollment

Northeastern University
College of Computer and Information Science
360 Huntington Avenue
451 West Village H
Boston, MA 02115
617-373-8493
a.fong at neu.edu