On k-Connectivity Problems in Distributed Systems
Vahid Khalilpour Akram, Orhan Dağdevıren · Advances in wireless technologies and telecommunication book series · 2016
k-Connectivity detection and restoration are important problems in graph theory and computer networks. A graph is k-connected if it remains connected after removing k-1 arbitrary nodes. The k-connectivity is an important property of a distributed system because a k-connected network can tolerate k-1 node failures without losing the network connectivity. To achieve the k-connectivity in a network, we need to determine the current connectivity value and try to increase connectivity if the current k is lower than the desired value. This chapter reviews the central and distributed algorithms for detecting and restoring the k-connectivity in graphs and distributed systems. The algorithms will be compared from complexity, accuracy and efficiency perspectives.