Detta dokument handlar om randomiserade ledarval i synkrona distribuerade nätverk. En distribuerad ledare valalgoritm presenteras för kompletta n-node nätverk som körs i O(1) rundor och (med hög sannolikhet) använder endast O( ε n log 3/2 n) meddelanden för att välja en unik ledare (med hög sannolikhet). När vi överväger "explicit" varianten av ledarval där så småningom varje nod känner till ledarens identitet, ger vår algoritm de asymptotiskt optimala gränserna för O(1) rundor och O(n) meddelanden. Denna algoritm utvidgas sedan till att omfatta ett val av ledare på alla anslutna icke-bipartite n-node graf G i O(τ (G) tid och O(τ (G) ε n log 3/2 n) meddelanden, där τ (G) är blandningstiden för en slumpmässig gång på G. Ovanstående resultat innebär mycket effektiv (sublinjär körtid och meddelanden) ledare valalgoritmer för nätverk med små blandningstider, såsom expanderare och hyperkuber. Däremot hade tidigare ledare valalgoritmer åtminstone linjära budskap komplexitet även i kompletta grafer. Dessutom är superlinjära budskap lägre gränser kända för tidseffektiva deterministiska ledare valalgoritmer. Slutligen presenterar vi en nästan matchande lägre gräns för det randomiserade valet av ledare, vilket visar att det behövs meddelanden för alla ledare valalgoritmer som med sannolikhet lyckas minst 1/e + ε, för alla små konstant ε > 0. Vi ser våra resultat som ett steg mot att förstå den randomiserade komplexiteten i ledarval i distribuerade nätverk.
I synnerhet författarna till REF visade att under CONGEST KT 0 modellen, meddelandet komplexiteten i ledarval är O ( ε n log 3 2 n) whp i den fullständiga grafen och mer allmänt, O(τ ε n log 3 2 n) whp i grafer med blandningstid τ (G).
Sublinear Bounds for Randomized Leader Election
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}