#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" }