文章基本信息

标题：(Q, S)-distance model and counting algorithms in dynamic distributed systems
本地全文：下载
作者：Zhiwei Yang ; Weigang Wu ; Yishun Chen 等
期刊名称：International Journal of Distributed Sensor Networks
印刷版ISSN：1550-1329
电子版ISSN：1550-1477
出版年度：2018
卷号：14
期号：1
页码：1
DOI：10.1177/1550147718756872
出版社：Hindawi Publishing Corporation
摘要：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.
关键词：Node counting; dynamic systems; dynamic networks; distributed algorithms; system model