Message ordering is a fundamental abstraction in distributed systems. However, usual ordering guarantees are purely syntactic'', that is, message
semantics'' is not taken into consideration, despite the fact that in several cases semantic information about messages leads to more efficient message ordering protocols. In this paper we define the Generic Broadcast problem, which orders the delivery of messages only if needed, based on the semantics of the messages. Semantic information about the messages is introduced in the system by a conflict relation defined over messages. We show that Reliable and Atomic Broadcast are special cases of Generic Broadcast, and propose an algorithm that solves Generic Broadcast efficiently. In order to assess efficiency, we introduce the concept of deliver latency.
IC_TECH_REPORT_199912.pdf
openaccess
239.15 KB
Adobe PDF
3194dc149ce69aa6cea6aff7284daf7a
PS99.ps
openaccess
439.56 KB
Postscript
2eb9f8e1cf0c96abb17c8238c30ede66