TY - GEN
T1 - Upper and lower bounds of space complexity of self-stabilizing leader election in mediated population protocol
AU - Mizoguchi, Ryu
AU - Ono, Hirotaka
AU - Kijima, Shuji
AU - Yamashita, Masafumi
PY - 2010
Y1 - 2010
N2 - This paper investigates the space complexity of a self stabilizing leader election in a mediated population protocol (SS-LE MPP). Cai, Izumi and Wada (2009) showed that SS-LE in a population protocol (SS-LE PP) for n agents requires at least n agent-states, and gave a SS-LE PP with n agent-states for n agents. MPP is a model of distributed computation, introduced by Chatzigiannakis, Michail and Spirakis (2009) as an extension of PP allowing an extra memory on every agents pair. While they showed that MPP is stronger than PP in general, it was not known if a MPP can really reduce the space complexity of SS-LE with respect to agent-states. We in this paper give a SS-LE MPP with (2/3)n agent-states and a single bit memory on every agents pair for n agents. We also show that there is no SS-LE MPP with any constant agent-states and any constant size memory on each agents-pair for general n agents.
AB - This paper investigates the space complexity of a self stabilizing leader election in a mediated population protocol (SS-LE MPP). Cai, Izumi and Wada (2009) showed that SS-LE in a population protocol (SS-LE PP) for n agents requires at least n agent-states, and gave a SS-LE PP with n agent-states for n agents. MPP is a model of distributed computation, introduced by Chatzigiannakis, Michail and Spirakis (2009) as an extension of PP allowing an extra memory on every agents pair. While they showed that MPP is stronger than PP in general, it was not known if a MPP can really reduce the space complexity of SS-LE with respect to agent-states. We in this paper give a SS-LE MPP with (2/3)n agent-states and a single bit memory on every agents pair for n agents. We also show that there is no SS-LE MPP with any constant agent-states and any constant size memory on each agents-pair for general n agents.
UR - http://www.scopus.com/inward/record.url?scp=78650909527&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78650909527&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-17653-1_35
DO - 10.1007/978-3-642-17653-1_35
M3 - Conference contribution
AN - SCOPUS:78650909527
SN - 3642176526
SN - 9783642176524
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 491
EP - 503
BT - Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Proceedings
T2 - 14th International Conference on Principles of Distributed Systems, OPODIS 2010
Y2 - 14 December 2010 through 17 December 2010
ER -