The authors have developed a novel technique for achieving mutual exclusion in distributed systems. They provide sufficient background to make the paper accessible to readers not familiar with previous work in the area. The novelty of their technique is in using a logical binary-tree structure and basing quorums on a root-to-leaf path in the tree. In this way, they can achieve mutual exclusion by contacting as few as log n nodes in an n-node system. Their quorum-construction technique can also tolerate failed nodes, building more complicated quorum sets using the binary-tree structure.
Their technique achieves significantly lower costs than a majority-consensus algorithm. The costs are, of course, higher than in a centralized scheme. The tolerance of failures is difficult to quantify, and the authors provide graphs indicating that, for most situations of interest, the observed tolerance will be close to that of a majority-consensus algorithm. Their technique thus provides a valuable new tradeoff between costs and tolerance of failures.
In comparing their algorithm with others, the authors make the unfortunate claim that their algorithm does not require nodes to be selected for special purposes based on their superior reliability. In fact, as they admit later in the paper, it is desirable for nodes near the root to be more reliable than nodes near the leaves. The paper does not contain any analysis of the effects of nonuniform node reliability on the algorithm.
One application presented for the new technique is the handling of replicated data. In such cases, providing small quorums for read operations at the expense of large quorums for write operations is often desirable. The technique, as presented, requires that all quorums be constructed identically, which prohibits such a tradeoff.