Vi studerar randomiserade algoritmer för att placera en sekvens av n noder på en cirkel med enhet omkrets. Noder delar cirkeln i delade bågar. Vi önskar att en nyligen anländ nod (som är omedveten om sitt index i sekvensen) väljer sin position i cirkeln genom att lära sig positionerna för så få befintliga noder som möjligt. Samtidigt önskar vi att variationen i båge-längder är liten. I detta syfte föreslår vi en ny algoritm som fungerar enligt följande: Den k th noden väljer r slumpmässiga punkter på cirkeln, inspekterar storleken på v bågar i närheten av varje slumpmässig punkt, och placerar sig i mitten av den största båge stött. Vi visar att för varje kombination av r och v uppfyller rv ≥ c log k, där c är en liten konstant, förhållandet mellan den största till den minsta båge-längd är som mest åtta w.h.p., för en godtyckligt lång sekvens av n noder. Denna strategi för nodplacering ligger till grund för en ny decentraliserad lastbalanseringsalgoritm som vi föreslår för Distribuerade Hash Tables (DHTs) i peer-to-peer-miljöer. Underliggande analysen av vår algoritm är Structurald Coupon Collection över n/b discounting cliques med b noder per clique, för alla n, b ≥ 1. Noder avslöjas till en början. Vid varje steg väljer vi d noder oberoende och enhetligt på måfå. Om alla noder i motsvarande kliquer är täckta, gör vi ingenting. Annars väljer vi, bland de valda kliquer med minst en avtäckt nod, en slumpmässigt och täcker en avtäckt nod inom den klicken. Vi visar att så länge bd ≥ c log n, O(n) steg är tillräckliga för att täcka alla noder w.h.p. och vart och ett av de första stegen lyckas täcka en nod w.h.p. Dessa resultat används sedan för att analysera en stokastisk process för att odla binära träd som är mycket balanserade - bladen av trädet hör till högst fyra olika nivåer med hög sannolikhet.
En bättre fördelning föreslås i REF, genom den typ av varje anslutning nod kan välja sin position i hash utrymme genom att lära sig positionerna för några befintliga noder.
Decentralized algorithms using both local and random probes for P2P load balancing
{'venue': "SPAA '05", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}