Motiverad av behovet av robust och snabb distribuerad beräkning i mycket dynamiska Peer-to-Peer-nätverk (P2P) studerar vi algoritmer för det grundläggande distribuerade avtalsproblemet. 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 designa snabba algoritmer (löper i ett litet antal rundor) som garanterar, trots hög nodfrekvens, att nästan alla noder når en stabil överenskommelse. Våra huvudsakliga bidrag är randomiserade distribuerade algoritmer som garanterar stabil nästan överallt överenskommelse med hög sannolikhet även under höga kontradiktoriska churn i ett polylogaritmiskt antal rundor. Vi presenterar framför allt följande resultat: 1. En O(log 2 n)-round (n är den stabila nätverksstorleken) randomiserad algoritm som uppnår nästan var som helst överenskommelse med hög sannolikhet under upp till linjär churn per runda (dvs., εn, för några små konstant ε > 0), förutsatt att churn kontrolleras av en glömsk motståndare (som har fullständig kunskap och kontroll av vad noder ansluter sig och lämnar och vid vilken tid och har obegränsad beräkningskraft, men är omedveten om de slumpmässiga val som görs av algoritmen).
REF:s arbete tar upp avtalsproblemet i ett dynamiskt P2P-nätverk enligt en kontradiktorisk churnmodell där churnhastigheterna kan vara mycket stora, upp till linjära i antalet noder i nätverket.
Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}