Login
English      Slovensko
DIST Oddelek za informacijske znanosti in tehnologijo

V petek, 10. novembra 2017, bo ob 16.00 uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper predavanje v okviru PONEDELJKOVEGA SEMINARJA RAČUNALNIŠTVA IN INFORMATIKE Oddelkov za Informacijske znanosti in tehnologije UP FAMNIT in UP IAM.

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!