E. Douglas Jensen's

Real-Time for the Real World

 
Home  |  Search  |  Contact Me   
 
 

My personal manifesto about the widely misunderstood field of real-time computing...

"I don't understand why people are frightened of new ideas. It's the old ideas that frighten me."
-- John Cage


 

Introduction
About Me
Real-Time
Distributed Real-Time
Distrib. Real-Time Java
Real-Time Java
Real-Time CORBA
Real-Time Resources
Our Documents
 

Distributed Real-Time Computing Systems

Distributed Computing Systems: Asynchronous and Synchronous Formal Models

One of the most fundamental aspects of distributed systems is the distinction between the asynchronous and the synchronous formal models -- not to be confused with the entirely different issues of: messaging that is synchronous (send-wait) vs. asynchronous; or the occurrence of asynchronous events or state transitions. This is a very deep topic (and a somewhat controversial one in the real-time distributed systems research community -- e.g., [Jensen and Ravindran 02]) with a large body of literature (e.g., [Lynch 97]); it is very briefly introduced here only as it pertains to real-time distributed systems.

The asynchronous model of distributed systems has no bounds on
bulletexecution entity (the principles of distributed computing community uses the term "process") execution latencies –-  i.e., arbitrarily long (but finite) times may occur between execution steps
bulletmessage transmission latencies –- i.e., a message may be received an arbitrarily long time after it was sent
bulletclock drift rates -- i.e., process's local clocks may be arbitrarily unsynchronized

In other words, the asynchronous distributed system model makes no assumptions about the time intervals involved in any behaviors.

The synchronous model of distributed systems, conversely, has a' priori known upper and lower bounds on these quantities
bulleteach process has a bounded time between its execution steps
bulleteach message is transmitted over a channel and received in a bounded time
bulletprocess’s local clocks may drift either from each other or from global physical time only by a bounded rate (note that this does not necessarily bound the clocks' accuracy)

It might seem that any implemented distributed system could be considered synchronous by presuming unrealistically tiny lower bounds and huge upper bounds on these three quantities. But the intent of having a system model is to facilitate reasoning about (e.g., proving) properties of the system -- if those presumed bounds are not deterministic (i.e., guaranteed), reasoning based on them can not be deterministic, which may or may not be acceptable in any given circumstances. In particular, meeting hard deadlines requires reasoning based on deterministic worst case latencies, and doing so for multi-node behaviors requires that the system be synchronous.

The asynchronous model is the general case, and any proofs of its properties also apply to the synchronous model, but the converse is not true. However, a number of important properties (such as distributed agreement) have been proven impossible even under very weak conditions in the asynchronous model (e.g., [Fisher et al. 85]), but are readily achievable in the synchronous model.

Neither the asynchronous nor the synchronous models are pragmatic for the vast majority of actual implemented distributed systems. Both are extreme vertices in a space of distributed system models. Distributed system models elsewhere in that space are partially synchronous along some dimension(s). Examples include (but are not limited to): a system may have either bounded process step latencies and unbounded communication latencies, or vice versa; a system may be asynchronous with synchronous subsystems; a system may change from one model to another at different times.

Obviously a real-time distributed system must be at least partially synchronous in some way(s). For example, if time constraints are employed across nodes, appropriately synchronized global physical time is required -- how this impacts the synchronicity/asynchronicity of the system model is a matter of controversy in the distributed real-time computing research community (see the IEEE Transactions on Computers August 2002 special section on asynchronous distributed real-time computer systems). Usually distributed real-time computing systems are also at most partially synchronous, although there are some fully synchronous ones for satisfying hard real-time deadlines in small scale, typically safety-critical, multi-node applications (e.g., []).

to be continued...

 

References

Fisher et al. 85 M. J. Fischer, N. A. Lynch, and M. S. Paterson, Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2):374-382, April 1985.

Jensen and Rivindran 02 Jensen, E. Douglas and Binoy Ravindran, Eds., IEEE Transactions on Computers, Special Section on Asynchronous Distributed Real-Time Systems, August 2002.

Lynch 97 Lynch, Nancy, Distributed Algorithms, Morgan Kaufmann Publishers, ISBN 1558603484, 1st edition August 1997. 35 sample pages at Amazon.com.

Add to Favorites

Print Page

Download a PDF copy of this page

 

 

New DARPA ARMS program on real-time distributed systems

New presentation about the Distributed Real-Time Specification for Java

IEEE Transactions on Computers, special section on Asynchronous Distributed Real-Time Systems, 8/02, Jensen & Ravindran, Eds.

Two new public papers about the Distributed Real-Time Specification for Java are here and here and both are on drtsj.org

The Real-Time CORBA 2/Dynamic Scheduling  Specification has been approved: OMG Document orbos/01-08-34

 
 

View Site Changes  RSS feed | Site Updated 03/30/2008 |  Legal