#Number
TR-PDS-1994-001

#Title
Synchronous Message Passing

#Author
Venkatesh V. Murty
Vijay K. Garg

#Abstract
This paper studies the characteristics of synchronous ordering
of messages.  Synchronous ordering of messages defines
synchronous communication based on the causality relation
rather than time. We present the necessary characteristics of
any algorithm providing deadlock-free synchronous ordering of
the messages.  We also present the sufficient conditions,
based on the causality relations, for any algorithm to provide
synchronous ordering. The paper proposes an algorithm using
acknowledgment messages to implement the sufficient
conditions. The acknowledgment messages are used to satisfy
the causality relation between the events.  The algorithm is
deadlock-free, and provides a higher degree of concurrency
then the algorithms which define synchronous communication
based on time.

#Bib
@TechReport{,
  author = 	 "V.V. Murty and V.K. Garg", 
  title = 	 "Synchronous Message Ordering", 
  institution =  "Parallel and Distributed Systems Laboratory, The
		  University of Texas at Austin", 
  year =	 1994,
  number =	 "TR-PDS-1994-001",
  note =	 "available via ftp or WWW at maple.ece.utexas.edu"
}