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