Vi anser att det råder enighet om mångfalden i ett nätverk av n noder. Till en början har varje nod en av k åsikter. Noderna kör ett (randomized) distribuerat protokoll för att komma överens om plurality opinion (det yttrande som ursprungligen stöds av de flesta noder). Noder i sådana nätverk är ofta ganska billiga och enkla, och därför söker man protokoll som inte bara är snabba utan också enkla och utrymmeseffektiva. Vanligtvis protokoll beror starkt på den använda kommunikationsmekanismen, som sträcker sig från sekventiell (endast ett par noder kommunicerar när som helst) till helt parallell (alla noder kommunicerar med alla sina grannar på en gång) kommunikation och allt mellan. Vi föreslår en ram för att utforma protokoll för en mängd kommunikationsmekanismer. Vi introducerar protokoll som löser plurality consensus problem och är med sannolikhet 1-o(1) både tid och utrymme effektiv. Våra protokoll bygger på ett intressant förhållande mellan plurality consensus och distribuerad lastbalansering. Detta förhållande gör att vi kan utforma protokoll som generaliserar den senaste tekniken för ett stort utbud av problemparametrar. I synnerhet får vi samma gränser som det senaste resultatet av [3] (som bara tar hänsyn till två åsikter om en klick) med hjälp av ett mycket enklare protokoll som generaliserar naturligt till allmänna grafer och flera åsikter.
Berenbrink m.fl. REF löser pluralitetssamsyn i allmänna grafer och för allmän skevhet med hjälp av belastningsbalansering.
Plurality Consensus via Shuffling: Lessons Learned from Load Balancing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}