Logical classification of distributed algorithms (Bakery algorithms as an example)

We argue that logical descriptions of distributed algorithms can reveal key features of their high-level properties, and can serve to classify and explicate fundamental similarities even among superficially very dissimilar algorithms. As an illustration, we discuss two distinct mutual-exclusion algorithms: the Bakery algorithm of Lamport is for shared memory, and the Ricart and Agrawala version is for message passing. It is universally agreed that they are both instances of “the Bakery algorithm” family, but is there a formal expression of this affinity? Here we present logical properties expressed naturally in Tarskian event structures that allow us to capture the similarities precisely. We use the notions of low-level and high-level events to organize the comparison. We find a set of properties expressed in quantification language which are satisfied by every Tarskian system execution that models a run by either one of the protocols, and we suggest these properties as a formal explication for the similarity of the two algorithms. An abstract proof shows that these common properties imply the mutual exclusion, and the informal arguments explain the sense in which they capture the essence of the two Bakery algorithms.