TY - GEN
T1 - Space complexity of self-stabilizing leader election in population protocol based on k-interaction
AU - Xu, Xiaoguang
AU - Yamauchi, Yukiko
AU - Kijima, Shuji
AU - Yamashita, Masafumi
PY - 2013
Y1 - 2013
N2 - Population protocol (PP) is a distributed computing model for passively mobile systems, in which a computation is executed by interactions between two agents. This paper is concerned with an extended model, population protocol based on interactions of at most k agents (PPk). Beauquier et al. (2012) recently introduced the model, and showed a hierarchy of computational powers of PPk with respect to k; a PPk+1 is strictly more powerful than a PPk. Motivated by a further understanding of the model, this paper investigates the space complexity of PPk for self-stabilizing leader election (SS-LE), which is a fundamental problem for a distributed system. Cai et al. (2012) showed that the space complexity of SS-LE for n agents by a PP (i.e., PP2) is exactly n. This paper shows that the space complexity of SS-LE for n agents by a PPk is exactly ⌈(n - 1)/(k - 1)⌉ + 1.
AB - Population protocol (PP) is a distributed computing model for passively mobile systems, in which a computation is executed by interactions between two agents. This paper is concerned with an extended model, population protocol based on interactions of at most k agents (PPk). Beauquier et al. (2012) recently introduced the model, and showed a hierarchy of computational powers of PPk with respect to k; a PPk+1 is strictly more powerful than a PPk. Motivated by a further understanding of the model, this paper investigates the space complexity of PPk for self-stabilizing leader election (SS-LE), which is a fundamental problem for a distributed system. Cai et al. (2012) showed that the space complexity of SS-LE for n agents by a PP (i.e., PP2) is exactly n. This paper shows that the space complexity of SS-LE for n agents by a PPk is exactly ⌈(n - 1)/(k - 1)⌉ + 1.
UR - http://www.scopus.com/inward/record.url?scp=84893904462&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893904462&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-03089-0_7
DO - 10.1007/978-3-319-03089-0_7
M3 - Conference contribution
AN - SCOPUS:84893904462
SN - 9783319030883
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 86
EP - 97
BT - Stabilization, Safety, and Security of Distributed Systems - 15th International Symposium, SSS 2013, Proceedings
T2 - 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2013
Y2 - 13 November 2013 through 16 November 2013
ER -