TY - GEN
T1 - Cached sensornet transformation of non-silent self-stabilizing algorithms with unreliable links
AU - Kakugawa, Hirotsugu
AU - Yamauchi, Yukiko
AU - Kamei, Sayaka
AU - Masuzawa, Toshimitsu
PY - 2009
Y1 - 2009
N2 - A wireless sensor network is a set of nodes, each is equipped with sensors and a wireless communication device. Cached Sensornet Transform (CST for short) is a methodology for design and implementation of self-stabilizing algorithms for sensor networks. It transforms a self-stabilizing algorithm in the abstract computational model to a program for sensor networks. In the literature, only CST transformation of silent self-stabilizing algorithms have been investigated, while non-silent ones have not been investigated. Our contribution in this paper is threefold. We present a counterexample of a non-silent algorithm transformed by CST that does not behave correctly despite the original algorithm is correct. We show a sufficient condition for original algorithms and networks such that a transformed algorithm by CST behaves correctly. We present a token circulation algorithm that behaves correctly by CST, and derive upper bound of its expected convergence time.
AB - A wireless sensor network is a set of nodes, each is equipped with sensors and a wireless communication device. Cached Sensornet Transform (CST for short) is a methodology for design and implementation of self-stabilizing algorithms for sensor networks. It transforms a self-stabilizing algorithm in the abstract computational model to a program for sensor networks. In the literature, only CST transformation of silent self-stabilizing algorithms have been investigated, while non-silent ones have not been investigated. Our contribution in this paper is threefold. We present a counterexample of a non-silent algorithm transformed by CST that does not behave correctly despite the original algorithm is correct. We show a sufficient condition for original algorithms and networks such that a transformed algorithm by CST behaves correctly. We present a token circulation algorithm that behaves correctly by CST, and derive upper bound of its expected convergence time.
UR - http://www.scopus.com/inward/record.url?scp=70549104894&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70549104894&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-05118-0_30
DO - 10.1007/978-3-642-05118-0_30
M3 - Conference contribution
AN - SCOPUS:70549104894
SN - 3642051170
SN - 9783642051173
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 428
EP - 442
BT - Stabilization, Safety, and Security of Distributed Systems - 11th International Symposium, SSS 2009, Proceedings
T2 - 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2009
Y2 - 3 November 2009 through 6 November 2009
ER -