Random Walks Despite Heavy Churn With Application To Storing and Retrieving Data Items
John Augustine
IIT Madras

Time: 11am, May 24, 2013
Venue: Room 3501

Abstract:

 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.