On space complexity of self-stabilizing leader election in mediated population protocol

摘要

Chatzigiannakis et al. (Lect Notes Comput Sci 5734:56-76, 2009) extended the Population Protocol (PP) of Angluin et al. (2004) and introduced the Mediated Population Protocol (MPP) by introducing an extra memory on every agent-to-agent communication link (i.e., edge), in order to model more powerful networks of mobile agents with limited resources. For a general distributed system of autonomous agents, Leader Election (LE) plays a key role in their efficient coordination. A Self-Stabilizing (SS) protocol has ideal properties required for distributed systems of huge numbers of not highly reliable agents typically modeled by PP or MPP; it does not require any initialization and tolerates a finite number of transient failures. Cai et al. (2009) showed that for a system of n agents, any PP for SS-LE requires at least n agent-states, and gave a PP with n agent-states for SS-LE. In this paper, we show, for a system of n agents, any MPP for SS-LE with 2 edge-states (i.e., 1 bit memory) on every edge requires at least (1/2) lg n agent-states, and give an MPP for SS-LE with (2/3)n agent-states and 2 edge-states on every edge. Furthermore, we show that a constant number of edge-states on every edge do not help in designing an MPP for SS-LE with a constant number of agent-states, and that there is no MPP for SS-LE with 2 agent-states, regardless of the number of edge-states; the edge-state is not a complete alternative of the agent-state, although it can help in reducing the number of agent-states, when solving SS-LE.