Search

The rupture degree of an incomplete connected graph G is defined by where w(G − S) denotes the number of components in the graph G − S and m(G − S) is the order of the largest component of G − S. This parameter can be used to measure the vulnerability of a graph. In this paper, some bounds consisted of the relationships between the rupture degree and some vulnerability parameters on the rupture degree of a graph are given. [ABSTRACT FROM AUTHOR]

In this paper, we propose an approximation algorithm for the Fault-Tolerant Metric Facility Location problem which can be implemented in a distributed and asynchronous manner within O(n) rounds of communication, where n is the number of vertices in the network. Given a constant size set $\mathcal{R}$ which represents distinct levels of fault-tolerant requirements of all cities, as well as the two-part (facility and connection) cost of the optimal solution, i.e. F* + C*, the cost of our solution is no more than $|\mathcal{R}|\, \cdot \,F^* \, + \,2C^* $ for the general case, and less than F* + 2C* for the special case where all cities have a uniform connectivity requirement. Extensive numerical experiments showed that the quality of our solutions is comparable (within 4% error) to the optimal solution in practice. [ABSTRACT FROM AUTHOR]

A self-stabilizing algorithm is a distributed algorithm that can start from any initial (legitimate or illegitimate) state and eventually converge to a legitimate state in finite time without being assisted by any external agent. In this paper, we propose a self-stabilizing algorithm for finding the 3-edge-connected components of an asynchronous distributed computer network. The algorithm stabilizes in O(dnΔ) rounds and every processor requires O(nlogΔ) bits, where Δ(≤ n) is an upper bound on the degree of a node, d(≤ n) is the diameter of the network, and n is the total number of nodes in the network. These time and space complexity are at least a factor of n better than those of the previously best-known self-stabilizing algorithm for 3-edge-connectivity. The result of the computation is kept in a distributed fashion by assigning, upon stabilization of the algorithm, a component identifier to each processor which uniquely identifies the 3-edge-connected component to which the processor belongs. Furthermore, the algorithm is designed in such a way that its time complexity is dominated by that of the self-stabilizing depth-first search spanning tree construction in the sense that any improvement made in the latter automatically implies improvement in the time complexity of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of k-out-of-ℓ exclusion, a generalization of the mutual exclusion problem, in which there are ℓ units of a shared resource, and any process can request up to k units (1 ≤ k ≤ ℓ). A protocol is self-stabilizing if, starting from an arbitrary configuration, be it initial state or after a corrupted state, the protocol can start behaving normally within a finite time. We propose the first deterministic self-stabilizing distributed k-out-of-ℓ exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process. [ABSTRACT FROM AUTHOR]

The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) of memory per processor used by a leader election algorithm. We first observe that Ω(M + log d) bits are necessary and then show that O(n log d) bits are sufficient to construct a leader election algorithm that works on any network, where n, d and M are the number of processors, the maximum number of adjacent processors, and the maximum size (in bits) of a message, respectively. We next show that, for any arbitrarily fixed constant n, O(1) bits are sufficient to construct a leader election algorithm that works in any network of size n. [ABSTRACT FROM AUTHOR]

Sense of direction is a property of the edge-labeling of a network whose availability facilitates computations and often decreases their complexity. In this paper we consider the problem of providing a sense of direction to an anonymous, unoriented torus. The edges of the torus are initially labeled arbitrarily, and they have to be relabeled with a classical compass sense of direction. We first describe an algorithm where the relabeling of the edges is performed by a mobile agent that carries a token. The algorithm is optimal both in terms of number of tokens (with no tokens the task cannot be performed), and in terms of number of moves. We then show that the same technique can be used to orient the torus in the classical message-passing environment, thus obtaining an orientation algorithm that improves all the existing ones in this setting. [ABSTRACT FROM AUTHOR]

It is well known that a solution for the Firing Squad Synchronization Problem (FSSP) takes time 2n - 1, n being the number of soldiers. It is also known that a solution on a square of n × n soldiers takes the same time. The main result of this paper is a new solution for the FSSP on networks shaped as squares. Our solution is optimal in two aspects: it is communication optimal (the so-called 1-bit solution) and is also time optimal, as it takes 2n - 1 time. It is also used as a building block to construct a very efficient solution on the square torus. Our approach applies also to linearly shaped networks and yields on the ring almost optimal time & communication solutions. In particular, for the square torus with n rows and rings of n processors, if n is even our solution is time & communication optimal. Otherwise, it is communication-optimal but does not match the lower bound on the time of a synchronization just by 1 time unit. [ABSTRACT FROM AUTHOR]