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.
We propose efficient, programming language-independent, location-transparent references as a substitute for pointers in distributed applications. These references provide the semantics of normal pointers for both loca...
详细信息
ISBN:
(纸本)0897914953
We propose efficient, programming language-independent, location-transparent references as a substitute for pointers in distributed applications. These references provide the semantics of normal pointers for both local and distributed, transient and persistent objects. They may be passed in messages between and within nodes using a low-overhead presentation-layer protocol. The programmer remains free to create, delete or migrate objects at will. Sending references (or migrating objects) may cause references to be chained together across any number of spaces;we provide a short-circuit protocol to optimize access through such chains. Integrated with these references, we provide efficient, distributed, garbage collection of acyclic data structures. Even in the presence of network failures such as lost messages, duplicated messages, out of order messages and site failures, the correctness of GC is guaranteed. The protocol assumes the existence of local garbage collectors of the tracing family. The protocol combines: (i) local tracing (from a conservative root);(ii) conservative distributed reference counting;(iii) periodic tightening of the counts;and (iv) allowance for messages in transit during GC. The protocol uses only information local to each site, or exchanged between pairs of sites;no global mechanism is necessary. It is parallel and should scale to very large systems, e.g. tens of thousands of nodes connected using both local and wide-area networks.
The design and efficient operation of a distributed information system to support scientific modeling is subject to a variety of balancing concerns, such as computation, data, and communication load and constraints on...
详细信息
ISBN:
(纸本)089791502X
The design and efficient operation of a distributed information system to support scientific modeling is subject to a variety of balancing concerns, such as computation, data, and communication load and constraints on the use of restricted-license third-party software components, special purpose I/O devices, and large data resources. The Regional Ecosystem Information System (REIS described here uses object-oriented principles to separate abstract system objects from site-specific, representation dependent data files and executables. REIS is implemented using an object manager that provides the translation between abstract accesses and accesses to physically distributed system elements, and a distribution manager based on a version of the Linda distribution paradigm that supports actual accesss to physically distributed objects. An overview of REIS design is presented, along with preliminary results on some basic performance attributes of this approach to distribution and balancing.
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:
(纸本)9780897914956
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].
The problem of fault-tolerant coordination is fundamental in distributedcomputing. In the past, researchers have considered two types of coordination: general coordination, in which the actions of faulty processors a...
ISBN:
(纸本)9780897914956
The problem of fault-tolerant coordination is fundamental in distributedcomputing. In the past, researchers have considered two types of coordination: general coordination, in which the actions of faulty processors are irrelevant, and consistent coordination, in which the faulty processors are forbidden from acting inconsistently. This paper studies the possibility and complexity of achieving coordination in synchronous and asynchronous systems with crash, send-omission, and general omission failures. We indicate the systems in which coordination cannot be achieved and, when it can, analyze the computational complexity of optimally achieving it. In some cases, optimum solutions can be implemented in polynomial time, while in others they require NP-hard local computation. These results provide a thorough characterization of coordination and will thus aid researchers in determining the approach to take when attempting to achieve fault-tolerant coordination.
The proceedings contain 28 papers. The topics discussed include: practical uses of synchronized clocks undistributed systems;randomized wait-free concurrent objects;efficient parallel algorithms on restartable fail-st...
ISBN:
(纸本)0897914392
The proceedings contain 28 papers. The topics discussed include: practical uses of synchronized clocks undistributed systems;randomized wait-free concurrent objects;efficient parallel algorithms on restartable fail-stop processors;resiliency of interactive distributed tasks;how to withstand mobile virus attacks;on the value of information in distributed decision-making;optimal space distributed move-to-front lists;compact deterministic distributed dictionaries;a theory of relaxed atomicity;real-time sequence transmission problem;and consensus in the presence of timing uncertainty: omission and byzantine failures.
A distributed move-to-front list is a data object that abstracts a temporal ordering on a set of processes in a distributed system. We present a lower bound and a matching upper bound of ®(log2n) bits on the spac...
Synchronized clocks are interesting because they can be used to improve performance of a distributed system by reducing communication. Since they have only recently become a reality in distributed systems, their use i...
详细信息
暂无评论