Title: Distributed Algorithmic Foundations of Dynamic Networks
Abstract:
Many of today's real-world communication networks are highly dynamic, i.e., their network topology changes continuously over time. Examples include Peer-to-Peer (P2P) networks and ad hoc wireless and sensor networks. Such networks are now widely used in various applications, including sharing data and resources, search and storage, Internet telephony, environment monitoring and management. In P2P networks (e.g., Skype, BitTorrent), the topology changes at a rapid rate due to continuous joining and leaving of nodes; in ad hoc sensor and vehicular networks, the topology changes dynamically due to failure or mobility of the nodes. Performing robust and efficient non-trivial distributed computation in such highly dynamic networks is challenging. In this talk, I will give an overview of our recent results that make progress towards developing an algorithmic theory of dynamic networks. First, I will present a rigorous theoretical framework for studying dynamic networks. Then I will present efficient techniques and algorithms for solving the fundamental agreement problem in dynamic networks. I will also present efficient algorithms for key problems such as information spreading, search, and storage. To complement our algorithms, I will also present almost tight lower bounds for agreement and information spreading.
