AGREEMENT-RELATED PROBLEMS: FROM SEMI-PASSIVE REPLICATION TO TOTALLY ORDERED BROADCAST
Xavier Défago · 2000
Abstract Agreement problems constitute a fundamental class of problems in the context of distributed sys-tems. All agreement problems follow a common pattern: all processes must agree on some com-mon decision, the nature of which depends on the specific problem. This dissertation mainlyfocuses on three important agreements problems: Replication , Total Order Broadcast , and Con-sensus .Replication is a common means to introduce redundancy in a system, in order to improve itsavailability. A replicated server is a server that is composed of multiple copies so that, if one copyfails, the other copies can still provide the service. Each copy of the server is called a replica. Thereplicas must all evolve in manner that is consistent with the other replicas. Hence, updating thereplicated server requires that every replica agrees on the set of modifications to carry over. Thereare two principal replication schemes to ensure this consistency: active replication and passive replication.In Total Order Broadcast, processes broadcast messages to all processes. However, all mes-sages must be delivered in the same order. Also, if one process delivers a message