Vi anser att följande distribuerade konsensus problem: Varje nod i ett komplett kommunikationsnätverk av storlek n ursprungligen har ett yttrande, som väljs godtyckligt från en ändlig uppsättning  på. Systemet måste konvergera mot ett samförståndstillstånd där alla, eller nästan alla noder, har samma uppfattning. Dessutom bör detta yttrande vara giltigt, dvs. det bör vara ett av de som ursprungligen ingick i systemet. Detta villkor bör uppfyllas även i närvaro av en adaptiv, illvillig motståndare som kan ändra åsikterna hos ett begränsat antal noder i varje omgång. Vi betraktar tremajoritetsdynamiken: Vid varje omgång drar varje nod åsikten från tre slumpmässiga grannar och sätter sin nya åsikt till majoriteten (tiotalet bryts godtyckligt). Låt k vara antalet giltiga yttranden. Vi visar att om k n α, där α är en lämplig positiv konstant, tremajoritetsdynamiken konvergerar i tiden polynom i k och log n med hög sannolikhet även i närvaro av en motståndare som kan påverka upp till o ( ε n) noder vid varje omgång. Tidigare var konvergensen av 3-majoritetsprotokollet känd endast för 2, med ett argument som är robust till kontradiktoriska fel. Å andra sidan var inget anonymt, uniform-gossip protokoll som är robust till kontradiktoriska fel kända för  på > 2.
I REF studeras 3-majoritetsregeln under en adaptiv motståndare som visar att den konvergerar med tiden polynom i k och n w.h.p.
Stabilizing Consensus with Many Opinions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}