Vi studerar en plurality-consensus process där var och en av n anonyma agenter i ett kommunikationsnät initialt stöder en färg som valts från uppsättningen [k]. Sedan, i varje omgång, kan varje agent revidera sin färg enligt de färger som för närvarande hålls av ett slumpmässigt urval av sina grannar. Det antas att den ursprungliga färgkonfigurationen uppvisar en tillräckligt stor fördomar s mot en fast plurality färg, det vill säga antalet noder som stöder plurality färg överstiger antalet noder som stöder någon annan färg av s ytterligare noder. Målet är att delvis stödjas av italienska MIER-processen för att konvergera till den stabila konfigurationen där alla noder stöder den ursprungliga pluraliteten. Vi anser att en grundläggande modell där nätverket är en klick och uppdateringsregeln (kallas här 3-majoritet dynamik) av processen är följande: varje agent tittar på färgerna på tre slumpmässiga grannar och sedan tillämpar majoritetsregeln (bryta band enhetligt). Vi bevisar att processen konvergerar i tiden O(min {k, (n/ log n) 1/3 } log n) med hög sannolikhet, förutsatt att s c min{2k, (n/ log n) 1/3 } n log n. Vi bevisar sedan att vår övre gräns ovan är tight så länge k (n/ log n) 1/4. Detta faktum innebär en exponentiell tidsklyfta mellan plurality-consensus-processen och medianprocessen (se Doerr et al. i det 23:e årliga ACM-symposiet om parallellism i algoritmer och arkitekturer (SPAA'11), s 149-158. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. En naturlig fråga är om tittar på mer (än tre) slumpmässiga grannar kan avsevärt påskynda processen. Vi ger ett negativt svar på denna fråga: i synnerhet visar vi att prover av polylogaritmisk storlek kan påskynda processen endast med en polylogaritmisk faktor.
Författarna till REF utgår från att fördomarna är  och (min{ ε 2k, (n/ log n) 1/6 } · ε n log n).
Simple dynamics for plurality consensus
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}