*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
