Terminating population protocols via some minimal global knowledge assumptions ? ??
We introduce a variant of population protocols capable of termination. The ability to terminate is modeled by an oracle detecting absence of states. We prove that the new model simulates Turing Machines of space logn log n . We demonstrate similarities to linear bounded automata.
population protocol cover-time service rendezvous-based communication interaction counter machine absence detector linear-bounded automaton