Detta arbete handlar om den allmänna frågan om kombinerad optimalitet när det gäller tids- och rymdkomplexitet. I detta sammanhang studerar vi problemet med (exakt) beräkning av resursbegränsade och passivt mobila noder i modellen för populationsprotokoll, där rymdens komplexitet är avgörande. De räknade noderna är minnesbegränsade anonyma enheter (kallade agenter) som kommunicerar asynkront i par (enligt rättvisa villkor). Dessutom antar vi att dessa agenter är benägna att misslyckas så att de inte kan initieras korrekt. Denna studie behandlar två klassiska rättvisa förhållanden, och för var och en undersöker vi frågan om tidsoptimalitet för att räkna med det optimala utrymmet per agent. När det gäller slumpmässigt interagerande medel (probabilistisk rättvisa), som vanligt, mäts konvergenstiden i form av parallelltid (eller parallella interaktioner), vilket definieras som antalet parvisa interaktioner fram till konvergens, dividerat med n (antalet agenser). I fall av svag rättvisa, där det bara krävs att varje par av agenter interagerar oändligt ofta, definieras konvergenstiden i termer av icke-null övergångar, d.v.s. de övergångar som påverkar de samverkande agenternas tillstånd. För det första, om vi antar probabilistisk rättvisa, presenterar vi ett "icke-vetande" tidsoptimalt protokoll av O(n log n) förväntad tid med ett optimalt utrymme på bara en bit, och vi bevisar tidsoptimaliteten av detta protokoll. Då, för svag rättvisa, visar vi att en optimal (semi-uniform) lösning inte kan konvergera snabbare än i 2 n ) tid (non-null övergångar). Detta resultat, tillsammans med tidskomplexa analyser av ett redan känt rymdoptimalt protokoll, visar att det också är optimalt i tid (med tanke på de optimala utrymmesbegränsningarna).
I REF föreslogs ett optimalt protokoll för tid och utrymme.
Time and Space Optimal Counting in Population Protocols
{'venue': '20th International Conference on Principles of Distributed Systems, OPODIS 2015, Dec 2016, Madrid, Spain. 2016, 20th International Conference on Principles of Distributed Systems, OPODIS 2015', 'journal': None, 'mag_field_of_study': ['Computer Science']}