Query Protocols for Highly Resilient Peer-to-Peer Networks
Suresh Jagannathan, Gopal Pandurangan, Siriam Srinivasan · Purdue e-Pubs (Purdue University System) · 2003
A1Jslract-The dccenlrnUud and ad "oe nalure DC peer-Iopeer (P2P) m:lworks means thot bulb lhe structure DC Ihe nebrork, :llld the cODlent slored within it lire highly variable.Real-world :.1udlcs IndiCllte (hul only a SDl:J.11nllmbtr or peers remain persislent ORr slg.nifi~unl time periods.ODd lhal lhe perceLved imparlance of object!; :.1ored in the network, meBSlJl"Cd in lums DC areess or update rrequency, may Dol Collow B uniform dlslribul1on.In this poper, we present WARP, a P2P sys(em !hilt e:cplolls these dis1lm:tions8S an mlegnll part uCUs design.WARP empIDjS B. DOVe! Cault•tolenmt rnecllanism.to lJUluage Ihe dynamic nnhIre DC node Drrimls and deparlW"C.';'by allowing mul6pre physical nodes 10 semee dalll mopped to a single node in the o\'e£1oy.Moreover, the overbay supports diITen::J:lt query lypl$, di.!.'tingulsh.Ing quutrs lopopulnror valuable dnta from quuIl!:S 10 UDjHJpular or I~vulwJble dsl::l.We prol'e via a rigorous stochaSlie anlllysts that any queJJ', regardless o( type, "'ill be,sUI:tessruIly' scni«d wlih high probability.Furtbu, we show thDt for a Dc'twork "'ilb N nodlCS", Ihc hop complexity o( the prolocolls O(/oSN) with high probahility.We wso ddine bAndwidth complellity, 11 measure or congesUon at :lily node, and prol'C that 11 is O(log'3.N) lrilb higb probabIlity.We provide Ddelnlled simubtion of the system lind show that It conforms clllSely 10 our IhtDn:lit"aJ guarantees.I. INTRODUCTION A P2P networked system is a collabora1.inggroupofInlemct nodes which overlay their own special-purpose network on top of the Internet.Such il syslem performs appliCl1lion~ leYel rouLing on top of IP roUting.These systems.like the Internet itself, can be large.require distributed ClJntrol and configuration.and have a routing mecbanism that allows eaeh node ro communicale wilh Lhe rest of the system.P2P networks ~emerging