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
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