Managing Priorities in Atomic Multicast Protocols

Group communication and atomic multicast (i.e., total-order multicast) topics have been studied for more than two decades from both a theoretical and a practical point of view. Most of this work is concerned about the classical definition of total order (informally, all the messages are received in the same order). However, in some cases additional guarantees are needed, like priority-based delivery, which allows a user application to prioritize the sending and delivery of certain messages. In this paper, we present several techniques to modify an existing total order protocol to take into account message priorities and show how existing total order algorithms can be modified according to these techniques.