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.

1. See Sect. 2 for the definition.

2. Angluin et al. [2] adopted the following notion of weak global fairness that is slightly weaker than the strong global fairness we defined here; a trace is fair if for every possible transition \(C \rightarrow C^{\prime }\), if \(C\) occurs infinitely often in the trace, then \(C^{\prime }\) occurs infinitely often. This fairness is weaker since that \(C\) occurs infinitely often does not always imply an occurrence of the immediate transition from \(C\) to \(C^{\prime }\). However, these two notions of global fairness are equivalent, in the sense that an MPP under a scheduler observing the weak global fairness is SS-LE if and only if it is SS-LE under a scheduler observing the strong global fairness. The strong global fairness however helps to make proofs considerably more compact, so we in this paper adopt this definition. See [12] for more information. In this paper, the fairness always means the strong global fairness.

3. A system is said to be weak stabilizing, if it satisfies this weaker convergence condition. Gouda [13] showed that any weak stabilizing system under the (strongly) globally fair scheduler is self-stabilizing, if the number of configurations is finite, as in this paper. Since this weaker convergence condition helps to make proofs considerably more compact, we use this condition in the rest of the paper.

The authors thank the associate editor and the anonymous reviewers for their serious and valuable comments. The authors are supported by Grants-in-Aid for Scientific Research.

Authors and Affiliations

1. Department of Informatics, Kyushu University, 744, Moto-oka, Nishi-ku, Fukuoka, 819-0395, Japan

   Ryu Mizoguchi, Shuji Kijima & Masafumi Yamashita

2. Department of Economic Engineering, Kyushu University, 6-19-1, Hakozaki, Higashi-ku, Fukuoka, 812-8581, Japan

   Hirotaka Ono

Corresponding author

Correspondence to Shuji Kijima.

A preliminary version [16] appeared in OPODIS 2010.

Reprints and permissions