Trade-offs in implementing causal message logging protocols

Casual message logging protocols [3] have several attractive properties: they introduce no blocking, send no additional messages over those sent by the application, and can never cause orphans to be created by crashes. Causal message logging, however, does require additional data to be piggybacked on application messages. The amount of such piggybacked data can become large. In this paper, we present five different implementations of casual message logging. All of the corresponding protocols are parameterized by ~, the maximum number of processes that can fail concurrently. We also explore how the application's communication structure can be exploited to limit the amount of piggybacked data. 1 Introduction Message logging is a common technique used to build systems that can tolerate process crash failures. These protocols require that each process periodically record its local state and log the messages it received after having recorded that state. When a process crashes, a new process is created in its place: the new process is given