Space-efficient self-stabilizing counting population protocols on mobile sensor networks. (English) Zbl 1360.68202

Izumi, Tomoko; Kinpara, Keigo; Izumi, Taisuke; Wada, Koichi

Theor. Comput. Sci. 552, 99-108 (2014).

Summary: In this study, we consider a self-stabilizing counting problem for a passively-mobile sensor network with a base station originally proposed by J. Beauquier et al. [Lect. Notes Comput. Sci. 4731, 63–76 (2007; Zbl 1145.68343)], where the base station must count the number of sensors in the network. Self-stabilizing counting means that the base station eventually counts the exact number of sensors in the system from the configuration where each sensor has an arbitrary initial state. In this paper, we focus on the space complexity of the self-stabilizing counting problem in terms of the number of sensor states. We propose two self-stabilizing counting protocols. Given a known upper bound \(P\) on the number of sensors, the first protocol performs counting using \(2P\) sensor states and its convergence time is \(O(\log n)\) in fair executions, where \(n\) is the actual number of sensors. The second protocol uses only \(3 \cdot \lceil P / 2 \rceil\) sensor states but assumes the global fairness, which is an assumption stronger than the standard fairness. The best known protocol requires \(4P\) states while the corresponding lower bound is \(P\), so our result reduces the gap of the feasibility between \(P\) and \(4P\).

MSC:

68M12	Network protocols
68M10	Network design and communication in computer systems

Keywords:

counting problem; symmetric population protocol; self-stabilizing algorithm; mobile sensor networks

Citations:

Zbl 1145.68343

References:

[1]	Angluin, D.; Aspnes, J.; Chan, M.; Fischer, M. J.; Jiang, H.; Peralta, R., Stably computable properties of network graphs, (Proc. of IEEE/ACM International Conference on Distributed Computing in Sensor Systems. Proc. of IEEE/ACM International Conference on Distributed Computing in Sensor Systems, DCOSS (2005)), 63-74
[2]	Angluin, D.; Aspnes, J.; Fischer, M. J.; Jiang, H., Self-stabilizing population protocols, ACM Trans. Auton. Adapt. Syst., 3, 4 (2008)
[3]	Angluin, D.; Aspnes, J.; Diamadi, Z.; Fischer, M. J.; Peralta, R., Computation in networks of passively mobile finite-state sensors, Distrib. Comput., 18, 4, 235-253 (2006) · Zbl 1266.68042
[4]	Angluin, D.; Aspnes, J.; Eisenstat, D.; Ruppert, Eric, The computational power of population protocols, Distrib. Comput., 20, 4, 279-304 (2007) · Zbl 1266.68043
[5]	Angluin, D.; Aspnes, J.; Eisenstat, D.; Ruppert, E., On the power of anonymous one-way communication, (Proc. of the 10th International Conference on Principles of Distributed Systems. Proc. of the 10th International Conference on Principles of Distributed Systems, OPODIS (2005)), 396-411
[6]	Aspnes, J.; Ruppert, E., An introduction to population protocols, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 93, 98-117 (2007) · Zbl 1169.68326
[7]	Beauquier, J.; Blanchard, P.; Burman, J., Self-stabilizing leader election in population protocols over arbitrary communication graphs, (Proc. of the 17th International Conference on Principles of Distributed Systems. Proc. of the 17th International Conference on Principles of Distributed Systems, OPODIS (2013)), 38-52
[8]	Beauquier, J.; Blanchard, P.; Burman, J.; Dëlaet, S., Tight complexity analysis of population protocols with cover times — the ZebraNet example, Theoret. Comput. Sci., 512, 11, 15-27 (2013) · Zbl 1358.68033
[9]	Beauquier, J.; Burman, J., Self-stabilizing mutual exclusion and group mutual exclusion for population protocols with covering, (Proc. of the 15th International Conference on Principles of Distributed Systems. Proc. of the 15th International Conference on Principles of Distributed Systems, OPODIS (2011)), 235-250
[10]	Beauquier, J.; Burman, J.; Clement, J.; Kutten, S., On utilizing speed in networks of mobile agents, (Proc. of the 29th Annual ACM Symposium on Principles of Distributed Computing. Proc. of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC (2010)), 305-314 · Zbl 1315.68010
[11]	Beauquier, J.; Burman, J.; Kutten, S., A self-stabilizing transformer for population protocols with covering, Theoret. Comput. Sci., 412, 33, 4247-4259 (2011) · Zbl 1217.68028
[12]	Beauquier, J.; Burman, J.; Rosaz, L.; Rozoy, B., Non-deterministic population protocols, (Proc. of the 16th International Conference on Principles of Distributed Systems. Proc. of the 16th International Conference on Principles of Distributed Systems, OPODIS (2012)), 61-75
[13]	Beauquier, J.; Clement, J.; Messika, S.; Rosaz, L.; Rozoy, B., Self-stabilizing counting in mobile sensor networks with a Base Station, (Proc. of the 21st International Symposium on Distributed Computing. Proc. of the 21st International Symposium on Distributed Computing, DISC (2007)), 63-76 · Zbl 1145.68343
[14]	Cai, S.; Izumi, T.; Wada, K., How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model, Theory Comput. Syst., 50, 3, 433-445 (2012) · Zbl 1281.68049
[15]	Chatzigiannakis, I.; Michail, O.; Spirakis, P. G., Stably decidable graph languages by mediated population protocols, (Proc. of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems. Proc. of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS (2010)), 252-266
[16]	Devismes, S.; Tixeuil, S.; Yamashita, M., Weak vs. self vs. probabilistic stabilization, (Proc. of the 28th International Conference on Distributed Computing Systems. Proc. of the 28th International Conference on Distributed Computing Systems, ICDCS (2008)), 681-688
[17]	Fischer, M.; Jiang, H., Self-stabilizing leader election in networks of finite-state anonymous agents, (Proc. of the 10th International Conference on Principles of Distributed Systems. Proc. of the 10th International Conference on Principles of Distributed Systems, OPODIS (2006)), 395-409
[18]	Gouda, M. G., The theory of weak stabilization, (Proc. of the 5th International Workshop on Self-stabilization Systems. Proc. of the 5th International Workshop on Self-stabilization Systems, WSS (2001)), 114-123 · Zbl 1030.68524
[19]	Michail, O.; Chatzigiannakis, I.; Spirakis, P. G., Mediated population protocols, Theoret. Comput. Sci., 412, 22, 2434-2450 (2011) · Zbl 1218.68082
[20]	Mizoguchi, R.; Ono, H.; Kijima, S.; Yamashita, M., Upper and lower bounds of space complexity of self-stabilizing leader election in mediated population protocol, (Proc. of the 14th International Conference on Principles of Distributed Systems. Proc. of the 14th International Conference on Principles of Distributed Systems, OPODIS (2010)), 491-503
[21]	Guerraoui, R.; Ruppert, E., Even small birds are unique: population protocols with identifiers, Technical Report, LPD-REPORT-2007-006 (2007)
[22]	Guerraoui, R.; Ruppert, E., Names trump malice: tiny mobile agents can tolerate Byzantine failures, (Proc. 36th International Colloquium on Automata, Languages and Programming. Proc. 36th International Colloquium on Automata, Languages and Programming, ICALP (2009)), 484-495 · Zbl 1248.68091
[23]	Sudo, Y.; Nakamura, J.; Yamauchi, Y.; Ooshita, F.; Kakugawa, H.; Masuzawa, T., Loosely-stabilizing leader election in a population protocol model, Theoret. Comput. Sci., 444, 27, 100-112 (2012) · Zbl 1250.68080