On September 22, 2016, Dr. John Ebenezer Augustine will give a talk about "Robust and Efficient Computation in Dynamic Networks with Heavy Churn" in the context of the SFB 901.
Abstract:
Peer-to-Peer (P2P) networks — typically overlays on top of the Internet — pose some unique challenges to algorithm designers. Primarily, the difficulty comes from heavy churn owing to the short life span of most nodes in the network. Reminiscent of Theseus’ paradox, most nodes in a typical P2P network churn out within an hour only to be replenished with incoming new nodes. In order to maintain a well-connected network despite churn at this level, the overlay has to be constantly reworked. This results in the overlay network graphs being a dynamic graphs that exhibits both edge dynamism and heavy node churn. In this talk, we will discuss how to design fast algorithms that are robust against such dynamic networks.
We will begin with a discussion on how to create and maintain an overlay network that has good expansion despite adversarial churn. Subsequently, assuming such an overlay network with good expansion, we will present a few basic techniques like fast information dissemination, random walks, and support estimation. Finally, we show how to use these techniques to design algorithms to solve fundamental problems like agreement, leader election, storing and retrieving data items.