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...
详细信息
This paper handles the problem of designing a deterministic dictionary structure in a distributed system. The structure is required to be compact (namely, store only a single copy of each data item) and memory balance...
Complex programs are often required to display graceful degradation, reacting adaptively to changes in the environment. Under ideal circumstances, the program's behavior satisfies a set of application-dependent co...
详细信息
Complex programs are often required to display graceful degradation, reacting adaptively to changes in the environment. Under ideal circumstances, the program's behavior satisfies a set of application-dependent constraints. In the presence of events such as failures, timing anomalies, synchronization conflicts, or security breaches, certain constraints may become difficult or impossible to satisfy, and the application designer may choose to relax them as long as the resulting behavior is sufficiently "close" to the preferred behavior. This paper describes the relaxation lattice method, a new approach to specifying graceful degradation for a large class of programs. A relaxation lattice is a lattice of specifications parameterized by a set of constraints, where the stronger the set of constraints, the more restrictive the specification. While a program is able to satisfy its strongest set of constraints, it satisfies its preferred specification, but if changes to the environment force it to satisfy a weaker set, then it will permit additional "weakly consistent" computations which are undesired but tolerated. The use of relaxation lattices is illustrated by specifications for programs that tolerate 1) faults, such as site crashes and network partitions, 2) timing anomalies, such as attempting to read a value "too soon" after it was written, 3) synchronization conflicts, such as choosing the oldest "unlocked" item from a queue, and 4) security breaches, such as acquiring unauthorized capabilities. A preliminary version of this paper appeared in the proceedings of the Sixth acm SIGACT-SIGOPS symposium on principles of distributedcomputing [17].
Interaction is a fundamental notion in computation. In many cases, important properties are revealed by considering the interactive aspects of problems. In this work, we examine the power and limitations of interactio...
详细信息
Idle workstations in a network represent a significant computing potential. In particular, their processing power can be used by parallel-distributed programs that treat the network as a loosely-coupled multiprocessor...
详细信息
This conference proceedings contains 27 papers. The main subjects are shared memory multiprocessors, achievement of causal consistency, semantics of distributed services, storage management, message-passing systems, c...
详细信息
This conference proceedings contains 27 papers. The main subjects are shared memory multiprocessors, achievement of causal consistency, semantics of distributed services, storage management, message-passing systems, clock synchronization algorithms, high speed network control, analysis of communication protocols, reasoning about probabilistic algorithms, and totally asynchronous systems.
We describe the control protocols of the PARIS experimental network. This high bandwidth network for integrated communication (data, voice, video) is currently operational as a laboratory prototype. It will also be de...
详细信息
ISBN:
(纸本)9780897914048
We describe the control protocols of the PARIS experimental network. This high bandwidth network for integrated communication (data, voice, video) is currently operational as a laboratory prototype. It will also be deployed within the AURORA Testbed that is part of the NSF/DARPA Gigabit Networking program. The high bandwidth dicates the need of specialized hardware to support faster packet handling and control protocols. A new network control architecture is presented which exploits the specialized hardware in order to support the expected real time needs of future traffic. In particular, since control information can be distributed quickly, decisions can be made based upon more complete and accurate information. In some respects, this has the effect of having the benefits of centralized control (e.g. easier bandwidth resource allocation to connections), while retaining the fault-tolerance and scalability of a distributed architecture.
暂无评论