The timed asynchronous distributed system model
Published 27 November 2002
Flaviu Cristian, Christof Fetzer
Citations266
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We propose a formal definition for the timed asynchronous distributed system model and we describe extensive measurements of actual message and process scheduling delays and hardware clock drifts that confirm that this model adequately describes current distributed systems built from networked workstations.
Keywords
Computer Science
Journal of the ACMImpossibility of distributed consensus with one faulty process
4,554 Citations1985Michael J. Fischer, Nancy Lynch +1 more
In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process.
Journal of the ACMConsensus in the presence of partial synchrony
1,873 Citations1988Cynthia Dwork, Nancy Lynch +1 more
Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models that allow partially synchronous processors to reach some approximately common notion of time.
IEEE Transactions on CommunicationsInternet time synchronization: the network time protocol
1,833 Citations1991David L. Mills
Communications of the ACMUnderstanding fault-tolerant distributed systems
690 Citations1991F. Cristian
This article attempts to introduce some discipline and order in understanding fault-tolerance issues in distributed system architectures by examining various proposals, discusses their relative merits, and illustrates their use in existing commercial fault-Tolerance systems.
Distributed ComputingProbabilistic clock synchronization
592 Citations1989Flaviu Cristian
A probabilistic method is proposed for reading remote clocks in distributed systems subject to unbounded random communication delays and can achieve clock synchronization precisions superior to those attainable by previously published clock synchronization algorithms.
Leases: an efficient fault-tolerant mechanism for distributed file cache consistency
484 Citations1989Cary Gray, David R. Cheriton
ATOMIC BROADCAST: FROM SIMPLE MESSAGE DIFFUSION TO BYZANTINE AGREEMENT
353 Citations2005Flaviu Cristian, H. Aghili +2 more
A systematic derivation of a family of atomic broadcast protocols that are tolerant of increasingly general failure classes: omission failures, timing failures, and authentication-detectable Byzantine failures and can tolerate any number of link and process failures up to network partitioning is presented.
Failure Mode Assumptions and Assumption Coverage
246 Citations1995David Powell
On the impossibility of group membership
207 Citations1996Tushar Chandra, Vassos Hadzilacos +2 more
It is proved that the primary-partition group membership problem cannot be solved in asynchronous systems with crash failures, even if one allows the removal or killing of non-faulty processes that are erroneously suspected to have crashed.
Distributed Computing: Models and Methods.
86 Citations1990Leslie Lamport, Nancy Lynch
Communications of the ACMSynchronous and asynchronous
81 Citations1996Flaviu Cristian
This article emphasized similarities between synchronous and asynchronous programming by discussing only strict agreement-the kind of asynchronous agreement closest to synchronous agreement that is most likely to be understandable in a uni-tied framework.
ACM SIGCOMM Computer Communication ReviewAMp: a highly parallel atomic multicast protocol
77 Citations1989Paulo Verı́ssimo, Luı́s Rodrigues +1 more
Evaluating quorum systems over the Internet
71 Citations2002Yair Amir, Avishai Wool
The Generic Quorum-system Evaluator (GQE) is developed, which evaluates the behavior of any given quorum system over the unified, real-life history of the events that took place, ordered according to an imaginary global clock.
Elsevier eBooksDistributed Computing: Models and Methods
71 Citations1990Leslie Lamport, Nancy Lynch
An important problem in distributed computing is to provide a user with a non-distributed view of a distributed system to implement a distributed file system that allows the client programmer to ignore the physical location of his data.
AMp: a highly parallel atomic multicast protocol
64 Citations1989Paulo Verı́ssimo, Luı́s Rodrigues +1 more
An atomic multicast protocol for token passing Lans is presented, built on standard Lans, in view of taking advantage of the availability of communications hardware and the possibility of coexistence with standard stations, in the same network.
Real-Time SystemsIntegrating External and Internal Clock Synchronization
62 Citations1997Christof Fetzer, Flaviu Cristian
A new external/internal clock synchronization algorithm which provides both external and internal clock synchronization for as long as a majority of the reference time servers stay correct, as well as derive lower bounds for the best maximum external deviation achievable in standard mode and the best drift rate achievable in degraded mode.
IEEE Transactions on Software EngineeringA highly available local leader election service
55 Citations1999Christof Fetzer, Flaviu Cristian
A protocol is proposed that solves the highly available local leader election problem efficiently and some performance measurements of the implementation are given.
Fail-awareness in timed asynchronous systems
55 Citations1996Christof Fetzer, Flaviu Cristian
It is shown how fail-awareness can be applied in partitionable systems, i.e. systems in which communication is not certain due to network failures or excessive performance failures, and several fail-aware partitionable services are described to show the applicability of this approach.
On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times
55 Citations2005Christof Fetzer, Ulrich Schmid +1 more
It is shown that consensus can nevertheless be solved deterministically in this asynchronous system model because there exists no upper or lower bound on the transmission delay of messages or the relative speed of processes.
Journal of the ACMSimulating synchronized clocks and common knowledge in distributed systems
44 Citations1993Gil Neiger, Sam Toueg
Fail-awareness: an approach to construct fail-safe applications
43 Citations2002C. H. Fetter, F. Cristian
This work presents a framework for building fail-safe hard real-time applications on top of an asynchronous distributed system subject to communication partitions, i.e. using processors and communication facilities whose real- time delays cannot be guaranteed.
eCommons (Cornell University)Election Vs. Consensus in Asynchronous Systems
40 Citations1995Laura Sabel, Keith Marzullo
It is shown that there are other problems that cannot be solved in an asynchronous system, and for the same intuitive reason: it is impossible to distinguish a very slow processor from a crashed processor.
IEE Proceedings - SoftwareFail-aware datagram service
39 Citations1999Christof Fetzer, F. Cristian
In timed asynchronous distributed systems, it is often useful for a process p to know that another process q will not use a certain piece of information p has sent to q beyond a certain deadline, so this kind of interprocess communication is called communication by time.
Modelling and Analysis of Computer Network Clocks
34 Citations1998David L. Mills
Analytical models are used to express the accuracy and stability of a computer clock and to establish its design parameters with respect to time and frequency error tolerances based on the theory of adaptive-parameter, phase-lock loops.
Information and ComputationSimulating synchronous processors
25 Citations1987Jennifer L. Welch
It is shown how a distributed system with synchronous processors andynchronous message delays can be simulated by a system with both asynchronous processors and asynchronous message delays in the presence of various types of processor faults.
Group, majority, and strict agreement in timed asynchronous distributed systems
25 Citations2002Flaviu Cristian
This work investigates possible meanings for replicated data 'consistency' in timed asynchronous systems, subject to crash/performance process failures and omission/performance communication failures which may partition correct team members into isolated parallel groups.
A fail-aware membership service
23 Citations2002Christof Fetzer, Flaviu Cristian
A new protocol that can be used to implement a partitionable membership service for timed asynchronous systems that minimizes wrong suspicions of processes by giving processes a second chance to stay in the membership before they are removed.
PADRE: a Protocol for Asymmetric Duplex REdundancy
22 Citations2003D. Essame, Jean Arlat +1 more
A protocol for duplex redundancy management in critical systems that aims to increase the system availability without jeopardizing its safety and an application to a fully automated train control system is described.
A Fail-Aware Datagram Service
14 Citations1998Christof Fetzer, Flaviu Cristian
FORTRESS: A System to Support Fail-Aware Real-Time Applications
10 Citations1997Christof Fetzer, Flaviu Cristian
Fortress allows clients to detect when a service cannot provide its standard semantics anymore due to un-masked failures, and provides fail-aware clock synchronization, membership and atomic broadcast services.
Building fault-tolerant hardware clocks from COTS components
9 Citations2003Christof Fetzer, F. Cristian
This work shows how one can build clocks with a bounded drift rate from components off-the-shelf (COTS) to achieve a tight synchronization with UTC in systems with access to at least one GPS receiver.
Implementation and performance of a stable-storage service in Unix
5 Citations2002Flaviu Cristian, S. Mishra +1 more
This paper describes the design, implementation, and performance of a stable-storage service that has been implemented on top of the Unix operating system that allows servers to create, access, and delete persistent memory that survives server crashes.