(Q, S)-distance model and counting algorithms in dynamic distributed systems

Zhiwei Yang, Weigang Wu, Yishun Chen, Xiaola Lin, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

With the advance in mobile network-based systems, dynamic system has become one of the hotspots in fundamental study of distributed systems. In this article, we consider the dynamic system with frequent topology changes arising from node mobility or other reasons, which is also referred to as “dynamic network.” With the model of dynamic network, fundamental distributed computing problems, such as information dissemination and election, can be formally studied with rigorous correctness. Our work focuses on the node counting problem in dynamic environments. We first define two new dynamicity models, named (Q, S)-distance and (Q, S)*-distance, which describe dynamic changes of information propagation time against topology changes. Based on these two models, we design three different counting algorithms which basically adopt the approach of diffusing computation. These algorithms mainly differ in communication cost due to different information collection procedures. The correctness of all the algorithms is formally proved and their performance is evaluated via both theoretical analysis and experimental simulations.

Original languageEnglish
JournalInternational Journal of Distributed Sensor Networks
Volume14
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • distributed algorithms
  • dynamic networks
  • dynamic systems
  • Node counting
  • system model

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Networks and Communications

Cite this