Scalable message stability detection protocols

Abstract

In group communication, in order to deliver multicast messages reliably in a group, it is common practice for each member to maintain copies of all messages it sends and receives in a buffer for potential local retransmission. The storage of these messages is costly and buffers may grow out of bound. A form of garbage collection is needed to address this issue. Garbage collection occurs once a process learns that a message in its buffer has been received by every process in the group. The message is declared {\it stable} and is released from the buffer. An important part of garbage collection is message stability detection. This dissertation presents the result of an investigation into message stability detection protocols. A number of message stability detection protocols used in popular reliable multicast protocols are studied with a focus on their performance in large scale settings. This dissertation proposes a new gossip-style protocol with improved scalability and fault tolerance. This dissertation also shows that by adding a hierarchical structure to the set of basic protocols, their performance can be significantly improved when the number of participants is large.