Abstract
herobustnessofPeer-to-Peersystemsischallengedbyitshighlydynamicnature.Highfre-quentpeerfailureanddepartureeventscauseuncertaintyforwhichisconsideredexceptionalintraditionaldistributedsystems.Speci cally,insucientlylargeheterogeneousoverlaysmessagelossanddelaysarelikelytooccur.Thishasaseriouslyimpactonoverlayrouting,especiallyonlongerpaths.Mostoftheexistingsolutionstothisproblemrelyonmessageredundancytodecreasethelossanddelays.Thisincursalargebandwidthcost.WeproposeamodeltoestimateandimprovetheForwardFeedbackProtocol(FFP).FFPusessinglepathtoroutemessageanddetectsthemessagelossandexcessivedelayswhilerouting.Afterpeersendsaservice,theoutcomeissignalledalongtheroutingpath.Basedonlyonthebinary(positiveandnegative)signals,eachoverlaypeerlocallyandindependentlylearnstoroutetoavoidfailures.Whentheoutcomeoflookupisfailure,theacknowledgementoffeedbackhelpspeertocheckthepositionofthefailedpeerthenbroadcastsawarninginformationtopeerswhicharoundthefailedpeerandavoidstomeetitinfuture.Thelocalpeerinteractionsleadtotheemergenceoffastreliableoverlayroutes.Thisisacontinuousprocess,thesystemconstantlyself-organizesinresponsetochangingdelayandlossconditions.WeevaluatetheprotocolandsimulateinChordPeer-to-Peersystem.Thebandwidthisused2-4timeslessinoursystemthantheexistingoverlayroutingapproachesthatdependentonhighmessageredundancyforfault-tolerance.Despitethelessbandwidthmighttocause owreliability,FFPachievesuptoa25%higherdeliverysuccessrateincomparisontotheexistingsolutions.TheprotocolisscalablewithlocalstatesizeofO(log2N)intermsoftheoverlaynetworksizeandisuniversallyapplicabletoallrecursivelyroutingoverlays.