TI Protocols for Distributed Real-Time Systems 

LT COINS TR 91-42  

AU Krishnamoorthy Arvind 

YR 1991 

MN May 

OR UMASS 

AB Novel and specialized protocols will be necessary to deal with
the  requirements of time-constrained communication and
synchronized clocks  in an important area of technology, viz.,
the next generation of  distributed real-time systems.  Our
research concentrates on  developing distributed system {\it
protocols} that realize these  requirements.  In this
dissertation, we have proposed, analyzed and  evaluated new
protocols to meet these requirements. A {\it clock
synchronization} protocol is used to provide support for  a
common system-wide time base.  We have proposed and analytically 
evaluated a novel {\it probabilistic algorithm} for clock 
synchronization, that can {\it guarantee a much lower bound} on
the  deviation between clocks than most existing algorithms.  The
guarantee  offered by our algorithm is however probabilistic,
i.e., there is a  non-zero probability that the guarantee offered
by our algorithm will  fail to hold.  The {\it probability of
invalidity} of the guarantee,  i.e., the probabity that the
deviation exceeds the guaranteed  maximum deviation, can however
be made {\it extremely small} by  transmitting a sufficient
number of messages.  We have presented a  detailed analysis of
the protocol.  Among other things, we considered  three different
bounds on the probability of invalidity, and showed  that a bound
on the probability of invalidity decreases exponentially  with
the number of messages. In our work on time-constrained
communication, we have proposed RTLAN,  a new local area network
architecture for distributed real-time  systems.  RTLAN
incorporates new communication abstractions (real-time  virtual
circuit, real-time data-gram) and provides new classes of 
connection-oriented (RTCOS) and connectionless services (RTCLS)
that  explicitly consider the time requirements of messages.  It
employs  specialized {\it real-time communication protocols} at
the medium  access control layer to support these services.  We
have developed,  analyzed and evaluated a homogeneous suite of
five rea-ime medium  access control protocols based on a uniform
window splitting paradigm.  Performance evaluation studies by
simulation show that these  protocols perform well compared to
idealized baseline protocols.