Vi studerar robusta och effektiva distribuerade algoritmer för sökning, lagring och underhåll av data i dynamiska Peer-to-Peer-nätverk (P2P). P2P-nätverk är mycket dynamiska nätverk som upplever tung nod churn (dvs., noder gå med och lämna nätverket kontinuerligt över tid). Vårt mål är att garantera, trots hög nod churn hastighet, att ett stort antal noder i nätverket kan lagra, hämta och underhålla ett stort antal dataobjekt. Våra huvudsakliga bidrag är snabbt randomiserade distribuerade algoritmer som garanterar ovanstående med hög sannolikhet även under hög kontraarial churn. Vi presenterar framför allt följande huvudresultat: 1. En randomiserad distribuerad sökalgoritm som med hög sannolikhet garanterar att sökningar från så många som n=o(n) noder (n är den stabila nätverksstorleken) lyckas i O(log n)- rundor trots O(n/ log 1+δ n) churn, för alla små konstant δ > 0, per runda. Vi antar att churn kontrolleras av en omedveten motståndare (som har fullständig kunskap och kontroll av vad noder går * G. Pandurangan är också ansluten till Institutionen. för datavetenskap, Brown University Providence, RI 02912, USA. Forskning som delvis stöds av följande bidrag: Nanyang Technological University bidrag M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 bidrag MOE2010-T2-2-082, och ett bidrag från USIsrael Binational Science Foundation (BSF). † Forskning som delvis stöds av följande bidrag: Nanyang Technological University stipendiat M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 stipendiat MOE2010-T2-2-082 ∂ Arbete som delvis stöds av NSF Award IIS-1247581. och lämna och vid vilken tid och har obegränsad beräkningskraft, men är omedveten om de slumpmässiga val som görs av algoritmen). 2. Utgångspunkten är följande: En lagrings- och underhållsalgoritm som garanterar, med hög sannolikhet, dataobjekt kan lagras effektivt (med endast  till (log n) kopior av varje dataobjekt) och underhållas i ett dynamiskt P2P- nätverk med churnhastighet upp till O(n/ log 1+δ n) per runda. Vår sökalgoritm tillsammans med vår lagrings- och underhållsalgoritm garanterar att så många som n − o(n) noder effektivt kan lagra, underhålla och söka även under O(n/ log 1+δ n) churn per runda. Våra algoritmer kräver att endast polylogaritmiska i n bitar bearbetas och skickas (per runda) av varje nod. Såvitt vi vet är våra algoritmer de första kända, fullt distribuerade lagrings- och sökalgoritmer som på ett tillfredsställande sätt fungerar under mycket dynamiska inställningar (dvs. höga churnhastigheter per steg). Dessutom är de lokaliserade (dvs. inte kräver någon global topologisk kunskap) och skalbara. Ett tekniskt bidrag av detta dokument, som kan vara av oberoende intresse, visar hur slumpmässiga promenader kan användas för att härleda skalbara distribuerade algoritmer i dynamiska nätverk med adversarial node churn.
Vi visade också i REF att vi kan lagra och hämta ett dataobjekt trots nära linjärt antal noder (dvs upp till O(n/polylog(n) noder) churn i varje omgång.
Storage and search in dynamic peer-to-peer networks
{'venue': "SPAA '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}