Title: A self-stabilising algorithm for 3-edge-connectivity

Authors: Abusayeed M. Saifullah, Yung H. Tsin

Addresses: Computer and Inf. Science and Engineering, University of Florida, E301 CSE Building, P.O. Box 116120, Gainesville, FL 32611, USA; Computer Science and Engineering Department, Washington University, 1 Brookings Drive, Campus Box 1045, St. Louis St Louis, MO 63130, USA. ' School of Computer Science, University of Windsor, 401 Sunset Avenue, Windsor, Ontario N9C 3K7, Canada

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² log Δ) bits per processor, where Δ is an upper bound on the degree of a processor.

Keywords: distributed systems; transient faults; fault tolerance; self-stabilisation; legitimate states; illegitimate states; depth-first search tree; cut-pairs; 3-edge-connected components; time complexity; 3-edge connectivity.

DOI: 10.1504/IJHPCN.2011.038709

International Journal of High Performance Computing and Networking, 2011 Vol.7 No.1, pp.40 - 52

Published online: 21 Mar 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article