• HDR[m] : The header of message m containing its source, destination, sequence number, and delivery number The header contains all information for resending a message and delivering it in the correct order (assume data is reproduced by the application)
• A message m is stable if HDR[m] cannot be lost (e.g., because it has been written to stable storage)
• DEP[m] : The set of processes to which message m has been delivered, as well as any message that causally depends on delivery of m
• COPY[m] : The set of processes that have a copy of HDR[m] in their volatile memory If C is a collection of crashed processes, then Q C is an orphan if there is a message m such that Q ∈ DEP[m] and COPY[m] ⊆ C
• Goal: No orphans means that for each message m, DEP[m] ⊆ COPY[m]
• Pessimistic protocol: for each non stable message m, there is at most one process dependent on m, that is |DEP[m]| ≤ 1
• Consequence: An unstable message in a pessimistic protocol must be made stable before sending a next message
• Optimistic protocol: for each unstable message m, we ensure that if COPY[m] ⊆ C, then eventually also DEP[m] ⊆ C, where C denotes a set of processes that have been marked as faulty
• Consequence: To guarantee that DEP[m] ⊆ C, we generally rollback each orphan process Q until Q DEP[m]