Latency analysis of the Totem single-ring protocol

The Totem single-ring protocol provides reliable totally ordered multicasting of messages to processes in process groups over a single local-area network (LAN) using a logical token-passing ring. The protocol provides two levels of message delivery: delivery in agreed order and delivery in safe order. This paper presents the probability density functions (PDFs) for the latency to message delivery for the Totem single-ring protocol for these two levels of service in the presence of both message loss and token loss. These PDFs are calculated by repeated convolutions of the PDFs for the various components of the latency. The analysis shows that the mean latency to safe delivery is greater than the mean latency to agreed delivery and that the tail of the latency distribution for safe delivery is longer. It also shows that a deterministic arrival process for message generation exhibits lower mean latencies and shorter tails of the latency distribution than a Poisson arrival process