A self-stabilising algorithm for 3-edge-connectivity. (24th February 2011)

• Record Type: Journal Article
• Authors: Saifullah, Abusayeed M.; Tsin, Yung H.
• Is Part Of: International journal of high performance computing and networking. Volume 7:Number 1(2011)
• Page Start: 40
• Page End: 52
• Publication Date: 2011-02-24
• Subjects: distributed system -- transient fault -- fault-tolerance -- self-stabilisation -- legitimate state -- illegitimate state -- depth-first search tree -- cut-pair -- 3-edge-connected component -- time complexity; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

Abstract

Self-stabilisation is a theoretical framework for fault-tolerance without external assistance. Adoption of self-stabilisation in distributed systems has received considerable research interest over the last decade. In this paper, we propose a self-stabilising algorithm for 3-edge-connectivity of an asynchronous distributed model of computation. A self-stabilising depth-first search algorithm is run concurrently to build a depth-first search spanning tree of the system. Once such a tree is constructed, all the 3-edge-connected components of the system can be detected in O ( h ) rounds, where h is the height of the depth-first search tree. The result of computation is kept in a distributed fashion in the sense that, upon stabilisation of the algorithm, each processor knows all other processors that are 3-edge-connected to it. The space complexity of our algorithm is O ( n 2 log Δ) bits per processor, where Δ is an upper bound on the degree of a processor.