John Augustine is an assistant professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Madras. He earned his PhD in theoretical computer science from the University of California at Irvine. After his PhD, he has held several positions both in academia and in industry. He is broadly interested in designing and analysing algorithms. More recently, he is interested in developing algorithms suitable for large dynamic environments.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

Peer-to-Peer (P2P) networks are highly dynamic decentralized networks that experience heavy node churn, i.e., nodes join and leave the network continuously over time. We model such P2P systems as synchronous dynamic networks. In each round, an adversary can add and remove a large number of nodes, and also rewire the network subject to some connectivity constraints. Under this adversarial setting, it is often helpful to be able to sample nodes from the network. With this in mind, we will discuss how random walks can be useful in generating these samples. We will then discuss how these random walks can be useful in storing and searching data items despite high churn rate.

This talk is based on our paper “Storage and Search in Dynamic Peer-to-Peer Networks,” joint with Anisur Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson, and Eli Upfal. This paper will be presented shortly in SPAA 2013.

Thomas Sauerwald

--email hidden

passcode not visible

logged in users only