SELF-STABILIZING MASTER–SLAVE TOKEN CIRCULATION AND EFFICIENT SIZE-COMPUTATION IN A UNIDIRECTIONAL RING OF ARBITRARY SIZE

DOI Web Site 被引用文献1件
  • WAYNE GODDARD
    School of Computing and Department of Mathematical Sciences, Clemson University, Clemson SC 29634, USA
  • PRADIP K. SRIMANI
    School of Computing, Clemson University, Clemson SC 29634, USA

抄録

<jats:p> Self-stabilizing algorithms represent an extension of distributed algorithms in which nodes of the network have neither coordination, synchronization, nor initialization. We consider the model where there is one designated master node and all other nodes are anonymous and have constant space. Recently, Lee et al. obtained such an algorithm for determining the size of a unidirectional ring. We provide a new algorithm that converges much quicker. This algorithm exploits a token-circulation idea due to Afek and Brown. Disregarding the time for stabilization, our algorithm computes the size of the ring at the master node in O(n log n) time compared to O(n<jats:sup>3</jats:sup>) steps used in the algorithm by Lee et al. We have also shown that the master node, after determining the size of the ring, can compute the average of observations made at each node in O(n) rounds or O(n<jats:sup>2</jats:sup>) steps. It seems likely that one should be able to obtain master–slave algorithms for other problems in networks. </jats:p>

収録刊行物

被引用文献 (1)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ