Atomicity in a distributed system

Abstract

The aim of this first lecture has been to define precisely what a correct distributed algorithm is. The safety property considered is what we call " atomicity ", or " linearizability ", defined by reference to the sequential specification of a computer object. The liveliness property under consideration is the so-called " wait-freedom " (" absence of wait "). The two properties were illustrated using the register equivalence theorem and an algorithm for implementing a weak counter.

Here are the main topics covered during the first lecture :

• " Atomicity " ;
• " Wait-freedom " ;
• " Equivalence theorem between registers " ;
• " Register algorithms " ;
• " Some initial impossibility results ".