p-grid a self-organizing access structure for p2p information system

《p-grid a self-organizing access structure for p2p information system》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、-Grid:Aself-organizingaccessstructurefor2informationsystemsarlAbererDepartmentofCommunicationSystemsSwissFederal
nstituteofTechnology(EF)1015ausanne,Switzerlandkarl.aberer@ep .chAbstracteer-To-eersystemsaredrivingamajorparadigmshiftintheeraofgenuinelydistributedcomput-ing.Gnut

2、ellaisagoodexampleofaeer-To-eersuccessstory:arathersimplesoftwareenables
nternetuserstofreelyexchangeles,suchas3musicles.Butitshowsupalsosomeofthelimitationsofcurrent2informationsystemswithrespecttotheirabilitytomanagedataeÆciently.
nthispaperweintroduce-Grid,ascalableaccessst

3、ructurethatisspecicallydesignedforeer-To-eerinformationsystems.-Gridsareconstructedandmaintainedbyusingrandomizedalgorithmsstrictlybasedonlocalinteractions,providereliabledataaccessevenwithunreliablepeers,andscalegracefullybothinstorageandcommunicationcost.eywords.eer-To-eercomp

4、uting,Distributed
ndexing,DistributedDatabases,RandomizedAlgo-rithms.1
ntroductioneer-To-eer(2)systemsaredrivingamajorparadigmshiftintheeraofgenuinelydistributedcomputing.ajorindustrialplayersbelieve2re ectssocietybetterthanothertypesofcomputerarchitectures.
tissimilartowhenint

5、he1980'stheCgaveusabetterre ectionoftheuser"(www.infoworld.com).
na2infrastructure,thetraditionaldistinctionbetweenclientsandback-end(ormiddletierapplica-tion)serversissimplydisappearing.Everynodeofthesystemplaystheroleofaclientandaserver.Thenodepaysitsparticipationintheglobalexchan

6、gecommunitybyprovidingaccesstoitscomputingresources.Gnutellaisagoodexampleofa2successstory:arathersimplesoftwareenables
nternetuserstofreelyexchangeles,suchas3musicles.
nthecurrent2le-sharingsystems,likeGnutella[1],noindexingmechanismsaresupported.Searchrequestsarebroadcastedo

7、verthenetworkandeachnodereceivingasearchrequestscansitslocaldatabase(i.e.itslesystem)forpossibleanswers.Thisapproachisextremelycostlyintermsofcommunicationandleadstohighsearchcostsandresponsetimes.ForsupportingeÆcientsearch,however,appropriateaccessstructuresareprerequisite.Accessst