The Power of Global Knowledge on Self-stabilizing Population Protocols

03/17/2020
by   Yuichi Sudo, et al.
0

In the population protocol model, many problems cannot be solved in a self-stabilizing way. However, global knowledge, such as the number of nodes in a network, sometimes allows us to design a self-stabilizing protocol for such problems. In this paper, we investigate the effect of global knowledge on the possibility of self-stabilizing population protocols in arbitrary graphs. Specifically, we clarify the solvability of the leader election problem, the ranking problem, the degree recognition problem, and the neighbor recognition problem by self-stabilizing population protocols with knowledge of the number of nodes and/or the number of edges in a network.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset