#Number TR-PDS-1996-004 #Title Characterization of Message Ordering Specifications and Protocols #Author V. V. Murty V. K. Garg #Abstract This paper presents a general characterization of message ordering specifications. In general a distributed computation can be considered as a partial order. A specification can be viewed as a set of allowable distributed computations. In this particular characterization message ordering specifications like, FIFO, causal ordering, logically synchronous ordering, are specified as subsets of a ground set $\cal X$, where the ground set $\cal X$ is defined as the set of all distributed computations. The protocols that implement these specifications are classified into three types: (1) those that do nothing, (2) those that can tag information, and (3) those that can have control messages and tag information. In this paper, we present the necessary and sufficient conditions for the existence of a protocol of each type for a given specification. In general, there is no succinct method to describe a specification (that is, a subset of $\cal X$). Later in the paper, we give a succinct representation for a class of specifications using forbidden predicates. Given a forbidden predicates we derive the necessary and sufficient conditions for the existence of a protocol of each type for the corresponding specification. #Bib @TechReport{, author = "V. V. Murty and V. K. Garg", title = "Characterization of Message Ordering Specifications and Protocols", institution = "Parallel and Distributed Systems Laboratory, The University of Texas at Austin", year = 1994, number = "TR-PDS-1996-004", note = "available via ftp or WWW at maple.ece.utexas.edu" }