Population protokoll är en populär modell för distribuerad dator, där n agenter med begränsad lokal stat interagerar slumpmässigt, och samarbeta för att kollektivt beräkna globala predikat. Inspirerad av den senaste utvecklingen inom DNA-programmering har en omfattande serie tidningar, i olika samhällen, undersökt modellens beräkningsbarhet och komplexitet. Majoritet, eller konsensus, är en central uppgift i denna modell, där agenter måste gemensamt fatta beslut om vilka av två stater A eller B som hade en högre initialräkning. Två komplexa mått är viktiga: den tid som ett protokoll kräver för att stabilisera till ett utdatabeslut, och den tillståndsstorlek som varje agent behöver för att göra det. Det är för närvarande känt att majoriteten kräver  påslagning (log log n) tillstånd per agent för att möjliggöra snabb (polylogaritmisk tid) stabilisering, och att O(log 2 n) tillstånd är tillräckliga. Det finns således ett exponentiellt gap mellan de övre och nedre gränserna för detta problem. Vi tar upp denna fråga. På den negativa sidan ger vi en ny nedre gräns av  och (log n) tillstånd för alla protokoll som stabiliserar i O(n 1‐c ) förväntad tid, för alla konstant c > 0. Detta resultat är villkorat av grundläggande monotonitet och utgående antaganden, som tillgodoses av alla kända protokoll. Tekniskt sett utgör det en betydande avvikelse från tidigare lägre gränser, eftersom det inte är beroende av förekomsten av täta konfigurationer. Istället inför vi en ny generaliserad kirurgi teknik för att bevisa förekomsten av felaktiga utföranden för någon algoritm som skulle motsäga den lägre gränsen. Därefter gäller vår nedre gräns för mer allmänna initiala konfigurationer. På den positiva sidan ger vi en ny algoritm för majoritet som använder O(log n) tillstånd, och stabiliserar i O(log 2 n) förväntad tid. Centralt i algoritmen är en ny fasklocka utan ledare, som gör det möjligt för agenter att synkronisera i faser av  på varandra följande interaktioner med hjälp av O(log n) tillstånd per agent, utnyttja en ny koppling mellan populationsprotokoll och power-of-two-choices lastbalanseringsmekanismer. Vi använder också vår fasklocka för att bygga en ledare valalgoritm med ett tillstånd utrymme av storlek O(log n), som stabiliserar i O(log 2 n) förväntad tid.
Det för närvarande mest kända protokollet från REF kräver O(log n)-tillstånd och O log 2 n parallelltid, vilket är tight w.r.t.