The designer of a distributed system has the responsibility of certifying the correctness of the system before the users start using it. This guarantee must hold as long as every hardware and software component works according to its specification. A system may function incorrectly when its components fail, or the process states are corrupted by external perturbations, and there is no provision for fault tolerance. This chapter explains what correctness criteria are considered important for distributed systems and how to prove the correctness properties.
Consider a distributed system consisting of n processes 0, 1, 2, …, n − 1. Let si denote the local state of process i. The global state (also called ...