This paper investigates a new shared-memory model called immediate atomic snapshot memory. It is an extension of atomic snapshot memory in which a write operation in addition to writing, also returns an atomic snapsho...
详细信息
ISBN:
(纸本)0897916131
This paper investigates a new shared-memory model called immediate atomic snapshot memory. It is an extension of atomic snapshot memory in which a write operation in addition to writing, also returns an atomic snapshot of the memory. Unlike regular atomic snapshot, immediate snapshot is guaranteed to closely follow the write operation. This model was previously used to obtain an impossibility result. Here we investigate its utility for the design of algorithms. We first implement the one-shot version in the read-write model. We then use the model to design a new renaming algorithm. The renaming algorithm we obtain is simple and requires at worst n cycles of one-shot immediate snapshots. Since our implementation of the one-shot immediate snapshot requires O(n2) primitive read-write operations, we obtain an O(n3) renaming algorithm. Currently the best renaming algorithm is exponential. Our implementation of the immediate snapshot relies on a priori knowledge of the bound on the number of snapshots to be taken. We were not able to dispense with this condition and thus were unable to obtain an implementation of the long-lived object.
The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. A novel modular presentation of the problem is described whi...
详细信息
ISBN:
(纸本)0897916131
The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. A novel modular presentation of the problem is described which allows to deal with different assumptions for the delay of messages. We present a definition of clock synchronization under arbitrary delay assumptions, and present an optimal clock synchronization algorithm for general systems. We then show that in local systems (where delays on each link are independent of the other links) the inputs for the clock synchronization algorithm can be computed from the maximum local shifts for each pair of processors sharing a link. The maximum local shift for two processors depends only on their views. This allows our theory to deal with systems where different links adhere to different assumptions, or the same link satisfies several sets of assumptions;such mixtures are quite likely in practice. In particular, we show how to compute the maximum local shifts from the views, and hence provide optimal algorithms for systems where some links may have upper and/or lower bounds on the delay, some may have a bound on the difference between the delay in both directions, some may have both kinds of bounds and some may have no bounds. Previous results dealt only with the case where upper and lower bounds were known for all links. We introduce a new notion of optimality, that requires an algorithm to achieve the best possible precision on each instance;this notion is stronger than the previously used notion of worst case optimality. In contrast to the worst case approach, the new notion handles models where the worst-case behavior of any clock synchronization algorithm is inherently unbounded.
The symposium materials contain 25 papers. The topics covered include distributed priority algorithms, connection-based communication in dynamic networks, adaptive packet routing, computing with faulty shared memory, ...
详细信息
ISBN:
(纸本)0897914953
The symposium materials contain 25 papers. The topics covered include distributed priority algorithms, connection-based communication in dynamic networks, adaptive packet routing, computing with faulty shared memory, fault-tolerant coordination, self-stabilization, shared-memory multiprocessors, fast mutual exclusion, fast network decomposition, the weakest failure detector for solving consensus, leader election in complete networks, randomized coordinated attack protocols, distributed edge coloring, and proving probabilistic correctness statements.
This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simula...
详细信息
ISBN:
(纸本)0897914953
This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simulate reliable shared-memory objects, despite the fact that the available memory objects (e.g. read/write registers, test-and-set registers, read-modify-write registers) may be faulty.
Analysis and design of distributed algorithms and protocols are difficult issues. An important cause for those difficulties is the fact that the logical structure of the solution is often invisible in the actual imple...
详细信息
ISBN:
(纸本)0897914953
Analysis and design of distributed algorithms and protocols are difficult issues. An important cause for those difficulties is the fact that the logical structure of the solution is often invisible in the actual implementation. We introduce a framework that allows for a formal treatment of the design process, from an abstract initial design to an implementation tailored to specific architectures. A combination of algebraic and axiomatic techniques is used to verify correctness of the derivation steps. This is shown by deriving an implementation of a distributed minimum weight spanning tree algorithm in the style of [GHS].
We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In [CT91], we proved that ♦W, a failure detector that provides...
详细信息
ISBN:
(纸本)0897914953
We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In [CT91], we proved that ♦W, a failure detector that provides surprisingly little information about which processes have crashed, is sufficient to solve Consensus in asynchronous systems with a majority of correct processes. In this paper, we prove that to solve Consensus, any failure detector has to provide at least as much information as ♦W. Thus, ♦W is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.
Certain types of routing, scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. We present fast and simple randomized algorithms for edge coloring a graph, in t...
详细信息
ISBN:
(纸本)0897914953
Certain types of routing, scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. We present fast and simple randomized algorithms for edge coloring a graph, in the synchronous distributed point-to-point model of computation. Our algorithms compute an edge-coloring of a graph G with n nodes and maximum degree Δ with at most (1.6+Ε)Δ+log2+δn colors with high probability (arbitrarily close to 1), for any fixed Ε, δ>0. To analyze the performance of our algorithms, we introduce new techniques for proving upper bounds on the tail probabilities of certain random variables. Chernoff-Hoeffding bounds are fundamental tools that are used very frequently in estimating tail probabilities. However, they assume stochastic independence among certain random variables, which may not always hold. Our results extend the Chernoff-Hoeffding bounds to certain types of random variables which are not stochastically independent. We believe that these results are of independent interest, and merit further study.
The session problem is an abstraction of synchronization problems in distributed systems. It has been used as a test-case to demonstrate the differences in the time needed to solve problems in various timing models, f...
详细信息
ISBN:
(纸本)0897914953
The session problem is an abstraction of synchronization problems in distributed systems. It has been used as a test-case to demonstrate the differences in the time needed to solve problems in various timing models, for both shared memory (SM) systems and message-passing (MP) systems. In this paper, the session problem continues to be used to compare timing models quantitatively. The session problem is studied in two new timing models, the periodic and the sporadic. Both SM and MP systems are considered. In the periodic model, each process takes steps at a constant unknown rate;different processes can have different rates. In the sporadic model, there exists a lower bound but no upper bound on step time, and message delay is bounded. We show upper and lower bounds on the time complexity of the session problem for these models. In addition, upper and lower bounds on running time are presented for the semi-synchronous SM model, closing an open problem from [4]. Our results suggest a hierarchy of various timing models in terms of time complexity for the session problem.
The paper deals with the issue of station delay in token-ring networks. It explains why one-bit-delay is the minimum possible delay at every station and shows that the station delay depends on the distributed computat...
详细信息
ISBN:
(纸本)0897914953
The paper deals with the issue of station delay in token-ring networks. It explains why one-bit-delay is the minimum possible delay at every station and shows that the station delay depends on the distributed computations performed in the ring. Then, the paper introduces the distributed priority mechanism for token-rings, as approved by the IEEE-802.5 standard. This mechanism attaches to the token, that circulates around the ring and controls the access to the shared medium, a priority field P and a reservation field R. These two fields work together in an attempt to match the service priority of the ring to the highest priority message that is waiting to be sent. It is shown that due to the computation restrictions imposed by the one-bit-delay requirements, this priority mechanism has a grave deficiency as follows. When the token priority is higher than the maximum reservation (P>R), the token should make up to P round-trips, where P is the number of priority levels, before P is reduced to R. During this time period, no station may seize the token and send a message. This leads to loss of bandwidth. The paper presents a new priority mechanism that retains the desired properties of the standard. However, in the new protocol when P>R holds, P is reduced to R in at most 1 round-trip rather than in up to P round-trips.
暂无评论