作者：
RAYNAL, MIRISA
Université de Rennes I Campus de Beaulieu 35042 Rennes Cédex France
Many distributed algorithms that control computations are based on logical clocks. Each process has a logical clock that behaves as a counter. The counter is initialized to zero and then increases each time an event...
详细信息
Many distributed algorithms that control computations are based on logical clocks. Each process has a logical clock that behaves as a counter. The counter is initialized to zero and then increases each time an event is produced by the process. This value is then used to stamp the event. Along with the distinct process name, this stamp uniquely identifies the event. Since the logical speeds of the processes are independent, a logical clock may drift with respect to the other clocks. Two control methods exist to correct the values of logical clocks: 1. the a posteriori method, in which the drift is detected and then corrected, and 2. the a priori one, in which the drift is prevented. An a priori technique for correcting logical clocks is examined, and the algorithm used in this technique is studied in several environments.
One of the most common ways of proving a property of invariance for a distributed algorithm is to consider the system as the product of n elementary automata, each of them being the representation of a process. The p...
详细信息
One of the most common ways of proving a property of invariance for a distributed algorithm is to consider the system as the product of n elementary automata, each of them being the representation of a process. The proof then proceeds by induction: it is assumed that the property is true for some state of the product automation, and it is proved that it remains true after each possible transition. The problem with this method is that many situations must be considered. For proving an invariance property by the demonstration by reductio ad absurdum method, the only situation where the contrary property should be true is considered and it is established that this situation cannot exist. From a combinatorial perspective, this static method results in a great simplification. This point is illustrated by applying the method to the proof of a well-known algorithm, given by Dijkstra, Feijen, and Van Gasteren (1983). This algorithm permits the detection of the termination of a distributed computation.
There have been several distributed algorithms for deadlock detection. These algorithms are genera) and detect deadlocks for all topologies. In this paper, we have developed a fast distributed deadlock-detection...
详细信息
There have been several distributed algorithms for deadlock detection. These algorithms are genera) and detect deadlocks for all topologies. In this paper, we have developed a fast distributed deadlock-detection algorithm for hypercube where a node waits for at most one message ai a time. Non-waiting nodes participate in deadlock detection by assisting in signal passing. For analysis purpose, the algorithm is 3 described for synchronous mode of computation. This algorithm terminates inO(n3) time with overwhelming probability for an-dimensional binary cube.
We study the basic problem of constructing a spanning tree distributively in an asynchronous general network, in the presence of faults that occurred prior to the execution of the construction algorithm. This problem ...
详细信息
We study the basic problem of constructing a spanning tree distributively in an asynchronous general network, in the presence of faults that occurred prior to the execution of the construction algorithm. This problem is fundamental in computer communication networks, for example for routing, and as a subroutine for other distributed algorithms. We present for the first time an optimal (in the order of message complexity) fault-resilient spanning forest constructing algorithm for general networks. The algorithm eventually constructs a spanning tree in every component of the network that remained connected in which at least one node initiated the algorithm. For a network with m communication lines and n processors, k of which initiate the algorithm spontaneously, the algorithm we present uses at most O(n log k + m) messages. Another major contribution of this paper is the approach we took in order to modify an existing tree construction algorithm for fault-free networks, to make it fault-resilient.
Consider the following problem: each processor i in a distributed system contains subset S sub(i) of a universal set U; how many messages are necessary and sufficient for each processor to know the intersection of all...
详细信息
Consider the following problem: each processor i in a distributed system contains subset S sub(i) of a universal set U; how many messages are necessary and sufficient for each processor to know the intersection of all the subsets when any two processors can exchange information only through explicit messages? The authors show that the answer to this question is Theta (mn) where m is the cardinality of the smallest sized subset and n is the number of processors.
Load balancing is important for efficient resource use in distributed systems. In the present paper, a distributed ''drafting'' algorithm is developed for load balancing in local-network-based distrib...
详细信息
Load balancing is important for efficient resource use in distributed systems. In the present paper, a distributed ''drafting'' algorithm is developed for load balancing in local-network-based distributed systems. The algorithm serves as the basis for a dynamic process migration protocol that allows load balancing to be accomplished in a manner transparent to users. The algorithm operates independently of network topology information since only some system design parameters are influenced by topology or low-level communication protocol differences. With the algorithm, a compromise can be reached in pursuing the conflicting goals of maximizing processor usage and minimizing communications overhead. The algorithm is illustrated in application to a sample distributed system, showing how it is used for design parameter definition. The algorithm results in significant system improvement without requiring highly accurate estimation of processor loads.
The paper addresses ways in which one can use "broadcast communication" in distributed algorithms and the relevant ❉s of design and complexity. We present an algorithm for merging k sorted lists of n/k eleme...
详细信息
The paper addresses ways in which one can use "broadcast communication" in distributed algorithms and the relevant ❉s of design and complexity. We present an algorithm for merging k sorted lists of n/k elements using k processors and prove its worst case complexity to be 2n, regardless of the number of processors, while neglecting the cost arising from possible conflicts on the broadcast channel. We also show that this algorithm is optimal under single-channel broadcast communication. In a variation of the algorithm, we show that by using an extra local memory of O(k) the number of broadcasts is reduced to n. When the algorithm is used for sorting n elements with k processors, where each processor sorts its own list first and then merging, it has a complexity of O(n/k log(n/k) + n), and is thus asymptotically optimal for large n. We also discuss the cost incurred by the channel access scheme and prove that resolving conflicts whenever k processors are involved introduces a cost factor of at least log k.
A connected undirected graph with n nodes is examined. An asynchronous distributed algorithm that determines a spanning tree of the graph is described. Also, if the edges of the graph are weighted, the same algorith...
详细信息
A connected undirected graph with n nodes is examined. An asynchronous distributed algorithm that determines a spanning tree of the graph is described. Also, if the edges of the graph are weighted, the same algorithm can calculate a minimum-weighted spanning tree. This algorithm can be favorably compared to the one of Gallagher, Humblet, and Spira (1983) in several ways, such as: 1. Identical assumptions are made in regard to cooperation of concurrent processes in a distributed network. 2. The number of message exchanges in the algorithm only depends on the number of nodes of the graph and not on the number of edges. Thus, this algorithm can be well suited in order to implement a broadcasting mechanism in a communication system or to build a communication control tree allowing proper termination of distributed algorithm. Some improvements of the algorithm are indicated that could decrease the number of exchanged messages.
In a given network of N asynchronous processors, each processor has a different integer identifier. The election problem is to identify which processor has the largest identifier. A Hamiltonian cycle that includes a...
详细信息
In a given network of N asynchronous processors, each processor has a different integer identifier. The election problem is to identify which processor has the largest identifier. A Hamiltonian cycle that includes all the processors is fixed. The network has a sense of direction if, at each processor, the label on each tie gives the distance along this Hamiltonian cycle to the processor at the other end of the tie. An algorithm is presented that employs O(N) messages to solve the election problem in a complete network with a sense of direction. In contrast, if at each processor, the links are unlabeled, then the system has no sense of direction.
暂无评论