#Number
TR-PDS-1997-005

#Title
Message Ordering based on Colorful Forbidden Predicates

#Author
Venkataesh V. Murty
Vijay K. Garg

#Abstract
In this paper we study a class of message ordering guarantees that can be
implemented by tagging information to the user messages and without any
control messages. To specify the message ordering, we use the method called
{\em forbidden predicates} introduced in~\cite{ord:tech:murty2}. In this
paper we extend the concept of forbidden predicates by defining three
attributes for each message, that is, color, sending and receiving process.
All existing message ordering specifications such as FIFO, flush channels,
causal ordering, and logically synchronous ordering as well as many new
message orderings can be concisely specified using forbidden predicates.

We present a general algorithm to implement the message ordering that can
be specified using forbidden predicates and are implementable without
control messages.
This shows the similarities in all the specification that are implementable
without control messages. We further present techniques to generate efficient
protocol for a given specification.


#Bib
@TechReport{,
  author =   "Venkataesh V. Murty and Vijay K. Garg",
  title =    "Message Ordering based on Colorful Forbidden Predicates",
  institution =  "Parallel and Distributed Systems Laboratory, ECE
                  Dept. University of Texas at Austin",
  year =         "1997",
  number =    "ECE-PDS-1997-005",
  note =     "available via ftp or WWW at maple.ece.utexas.edu
          as technical report TR-PDS-1997-005"
}