2019/06/22 by Abusayeed Saifullah, Saifullah, Abusayeed
Computer Science · Engineering · #Asynchronous communication #Computer network #Computer science #Data Structures and Algorithms (cs.DS) #Distributed #Distributed computing #Distributed systems and fault tolerance #Enhanced Data Rates for GSM Evolution #FOS: Computer and information sciences #Graph #Interconnection Networks and Systems #Molecular Communication and Nanonetworks #Parallel #Telecommunications #Theoretical computer science #Vertex (graph theory) #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1906.10275
published in arXiv (Cornell University) (Cornell University)
arxiv created 2019/06/22 · openalex publication_date 2019/06/22 · arxiv updated 2019/06/26 · openalex created_date 2019/07/12 · openalex updated_date 2026/07/28
Self-stabilization for non-masking fault-tolerant distributed system has received considerable research interest over the last decade. In this paper, we propose a self-stabilizing algorithm for 2-edge-connectivity and 2-vertex-connectivity of an asynchronous distributed computer network. It is based on a self-stabilizing depth-first search, and is not a composite algorithm in the sense that it is not composed of a number of self-stabilizing algorithms that run concurrently. The time and space complexities of the algorithm are the same as those of the underlying self-stabilizing depth-first search algorithm which are O(dnΔ) rounds and O(nlog Δ) bits per processor, respectively, where Δ(<= n) is an upper bound on the degree of a node, d (<= n) is the diameter of the graph, and n is the number of nodes in the network.