Vi studerar Plurality Consensus i GOSSIP Model över ett nätverk av n anonyma agenter. Varje agent stöder en inledande åsikt eller färg. Vi antar att vid början, antalet agenter som stöder plurality färg överstiger den av de agenter som stöder någon annan färg med en tillräckligt stor fördomar, även om den ursprungliga pluraliteten i sig kan vara mycket långt ifrån absolut majoritet. Målet är att ge ett protokoll som med stor sannolikhet för in systemet i konfigurationen där alla agenter stöder den (ursprungliga) pluralitetsfärgen. Vi anser att Obeslutade-State Dynamics, ett välkänt protokoll som använder bara en mer tillstånd (den obeslutsamma) än de som krävs för att lagra färger. Vi visar att konvergenshastigheten för detta protokoll beror på den ursprungliga färgkonfigurationen som helhet, inte bara på klyftan mellan pluraliteten och den näst största färggemenskapen. Detta beroende fångas bäst av ett nytt begrepp som vi introducerar, nämligen det monokroma avståndet md(c) som mäter avståndet till den ursprungliga färgkonfigurationen c från närmaste monokroma. I den fullständiga grafen visar vi att för ett brett spektrum av indataparametrar konvergerar denna dynamik inom O(md(c) log n) rundor. Vi bevisar att denna övre gräns är nästan tight i den starka bemärkelsen: Med början från alla färger konfigurationc, konvergenstiden är  och (md(c)). Slutligen anpassar vi Obeslutade-State Dynamics för att få ett snabbt, slumpmässigt walk-baserat protokoll för plurality konsensus om regelbundna expanderare. Detta protokoll konvergerar i O(md(c) polylog(n) rundor med endast polylog(n) lokalt minne. En nyckel-ingredient för att uppnå ovanstående gränser är en ny analys av den maximala nod trängsel som är resultatet av att utföra n parallella slumpmässiga promenader på regelbundna expanders. Alla våra gränser håller med stor sannolikhet.
Fortfarande i den enhetliga push-modellen har den obeslutsamma tillståndsdynamiken analyserats i fallet med ett godtyckligt stort antal yttranden, som till och med kan vara en funktion av antalet agenter i systemet REF.
Plurality Consensus in the Gossip Model
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}