Self-stabilizing Silent Disjunction in an Anonymous Network

Document Type

Article

Publication Date

1-1-2017

Publication Title

Theoretical Computer Science

Volume

665

First page number:

51

Last page number:

72

Abstract

In this paper, we give a distributed silent self-stabilizing algorithm, DISJ, for the disjunction problem in a connected network. In this problem, each process x has an input bit x.in, assigned by the application layer, and each process must compute the disjunction of the input bits of all processes. DISJ is uniform, and works in an anonymous network under the distributed unfair daemon. The stabilization time of DISJ is O(n) rounds, where n is the size of the network, and the memory requirement per process is O(log⁡D+Δ) where D and Δ are, respectively, the diameter, and the maximum degree of the network. © 2016 Elsevier B.V.

Keywords

Anonymous network; Disjunction; Self-stabilization; Silence; Unfair daemon

Language

english

Find It

UNLV article access

Find in your library

Share

COinS