Populationsprotokoll är en populär modell av distribuerad dator, där slumpmässigt verkande agenter med liten beräkningskraft samarbetar för att gemensamt utföra beräkningsuppgifter. Inspirerad av utvecklingen inom molekylär beräkning, och i synnerhet DNA-data, har det senaste algoritmiska arbetet fokuserat på komplexiteten i att lösa enkla men grundläggande uppgifter i befolkningsmodellen, såsom ledarval (som kräver stabilisering till en enda agent i en särskild "ledare" stat), och majoritet (där agenter måste stabilisera till ett beslut om vilka av två möjliga initiala stater hade högre initiala räkning). Kända resultat pekar mot en inneboende avvägning mellan tids komplexiteten hos sådana algoritmer och rymdens komplexitet, dvs. Storleken på det minne som finns tillgängligt för varje agent. I detta dokument utforskar vi denna kompromiss och ger nya övre och nedre gränser för majoritets- och ledarval. För det första visar vi en enhetlig lägre gräns, som relaterar det tillgängliga utrymmet per nod med den tids komplexitet som kan uppnås genom ett protokoll: till exempel, vårt resultat innebär att alla protokoll lösa någon av dessa uppgifter för n agenter som använder O(log log n) stater måste ta  på (n/polylogn) förväntad tid. Detta är det första resultatet att karakterisera tid komplexitet för protokoll som använder super-konstant antal stater per nod, och visar att snabba, poly-logaritmiska körtider kräver protokoll för att ha relativt stora rymdkostnader. På den positiva sidan ger vi algoritmer som visar att snabb, polylogaritmisk stabiliseringstid kan uppnås med hjälp av O(log 2 n) utrymme per nod, när det gäller båda uppgifterna. Sammantaget lyfter våra resultat fram en tids komplexitet separation mellan O(log log n) och  på (log 2 n) stat utrymme storlek för både majoritet och ledare val i population protokoll, och införa nya tekniker, som bör tillämpas mer allmänt.
I REF presenteras ytterligare övre och nedre gränser för dessa uppgifter som belyser en tids komplexitetsseparation mellan O(log log n) och  på (log 2 n) statsutrymme för både majoritets- och ledarval.
Time-space trade-offs in population protocols
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}