Linear Time Distributed Swap Edge Algorithms

Document Type

Article

Publication Date

6-2-2020

Publication Title

Information Processing Letters

Volume

161

First page number:

1

Last page number:

9

Abstract

In this paper, we consider the all best swap edges problem in a distributed environment. We are given a 2-edge connected positively weighted network X, where all communication is routed through a rooted spanning tree T of X. If a tree edge fails, the communication network will be disconnected. However, since X is 2-edge connected, communication can be restored by replacing e by non-tree edge , called a swap edge of e, whose ends lie in different components of . Of all possible swap edges of e, we would like to choose the best, according to four different objective functions. Overall, the problem is to identify the best swap edge for every tree edge, so that in case of any edge failure, the best swap edge can be activated quickly. There are solutions to this problem for a number of cases in the literature. A major concern for all these solutions is to minimize the number of messages. However, especially in fault-transient environments, time is a crucial factor. In this paper we present a novel technique that addresses this problem from a time perspective; in fact, we present a distributed solution that works in linear time with respect to the height h of T for a number of different criteria, while retaining the optimal number of messages and space per each processor x of degree. To the best of our knowledge, there is no prior algorithm for the all best swap edges problem whose asymptotic complexity matches ours in all three measures: time, space, and number of messages.

Keywords

Swap edges; Edge failure; Distributed computing; Distributed algorithms; Fault tolerance

Disciplines

Computer Sciences | Physical Sciences and Mathematics | Theory and Algorithms

Language

English

UNLV article access

Find in your library

Share

COinS