Modellen av population protokoll hänvisar till en stor samling av enkla oskiljaktiga enheter, ofta kallade agenter. Agenterna kommunicerar och utför beräkningar genom parvisa interaktioner. Vi studerar snabbt och rumseffektivt ledarval i befolkningen av kardinalitet n styrs av en slumpmässig schemaläggare, där under varje steg schemaläggaren enhetligt på måfå väljer för interaktion exakt ett par agenter. Vi presenterar den första o(log 2 )-tid ledare val protokoll. Det fungerar i förväntad parallelltid O(log n log log n) som motsvarar O(n log n log n) parvisa interaktioner. Detta är den snabbast kända ledare valalgoritmen där varje agent använder asymptotiskt optimalt antal O(logglogg n) stater. Det nya protokollet införlivar och sammansmälter framgångsrikt kraften i diverse syntetiska mynt med fas klockor med variabel hastighet. • Teori för beräkning → Utformning och analys av algoritmer; Slumpmässighet, geometri och diskreta strukturer;
Jag är ledsen, men jag är ledsen att jag är sen. REF gav ett toppmodernt protokoll som stabiliserar i O(log n · log n) parallelltid med endast O(log log n)-tillstånd.
Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols
{'venue': "SPAA '19", 'journal': None, 'mag_field_of_study': ['Computer Science']}