Observations on non-silent self-stabilizing algorithms in sensor networks with probabilistically intermittent link failures

Hirotsugu Kakugawa, Yukiko Yamauchi, Sayaka Kamei, Toshimitsu Masuzawa

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


A wireless sensor network is a set of nodes, each is equipped with a sensing device and a wireless communication device. Because centralized control is hard to achieve in a large scale sensor network, self-* is a key concept in the design of a wireless sensor network. Self-stabilization is one of the self-* properties, and it is one of the most promising theoretical backgrounds for self-organizing wireless sensor network protocols. Herman [T. Herman, Models of self-stabilization and sensor networks, in: Proceedings of the 5th International Workshop of Distributed Computing, IWDC, 2003, pp. 205214] proposed Cached Sensornet Transform (CST for short) for design and implementation of self-stabilizing algorithms for sensor networks. It transforms a self-stabilizing algorithm in a high-level computational model to a program for sensor networks. Our contribution in this paper is threefold. We show that there exists a non-silent algorithm that behaves correctly in a high-level computational model but its transformed version by CST does not behave correctly if packets are lost. We show a sufficient condition for original algorithms and networks such that the algorithm transformed by CST behaves correctly. As a case study, we present a token circulation algorithm that behaves correctly by CST and derive the upper bound of its expected convergence time.

Original languageEnglish
Pages (from-to)4336-4349
Number of pages14
JournalTheoretical Computer Science
Issue number33
Publication statusPublished - Jul 29 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Observations on non-silent self-stabilizing algorithms in sensor networks with probabilistically intermittent link failures'. Together they form a unique fingerprint.

Cite this