PROSTOR: FAMNIT-Muzejski3 ob 16:00

PREDAVATELJ: Prof. Dr. Robert Elsässer

NASLOV: Plurality Consensus – Dva izbirna protokola in nekatere njegove različice

POVZETEK:

Denimo problem distribuiranega pluralnega soglasja. V najosnovnejšem dvotirnem procesu imamo podatek, v katerem najprej vsako vozlišče vsebuje eno od $k$ različnih mnenj. V vsakem (sinhronem) koraku vsako vozlišče izbere dve sosedi enakomerno naključno. če se strinjata mnenji obeh sosedov, se to mnenje sprejme.

Pokašemo, da če je $k =O (n ^\epsilon) $ za nekaj majhnih $\epsilon$, se ta protokol konvergira z začetno večino v koraku $ O (k \ cdot \ log {n}) $, dokler je začetna razlika med največjim in drugim največjim mnenjem $ \ Omega (\ sqrt {n \ log n}) $. Ta zgornja meja ima tudi v prisotnosti nasprotnika, ki lahko spremeni do $ O (\ sqrt {n \ log n} / k) $ vozlišč za vsak krog. Zahtevana začetna razlika je v naslednjem smislu omejena na faktor $ \ sqrt {\ log {n}} $ tudi v odsotnosti nasprotnika: če je razlika samo $ O (\ sqrt {n}) $, potem lahko največje mnenje izgubi glas s konstantno verjetnostjo.

Poleg tega, razmišljamo o preprostih spremembah protokola z dvema mošnostima, da bi pospešili proces v sinhronem modelu in razširili enega od rezultatov na asinhrono nastavitev, opisano s sekvenčnim komunikacijskim modelom, v katerem se izvaja samo en naključno izbrano vozlišče opravi največ 2 poizvedbi na korak.

Vabljeni!