Backoff protocols for distributed mutual exclusion and ordering

Abstract

Presents a simple and efficient protocol for mutual exclusion in synchronous message-passing distributed systems subject to failures. Our protocol borrows design principles from prior work in backoff protocols for multiple access channels such as the Ethernet. Our protocol is adaptive in that the expected amortized system response time - informally, the average time a process waits before entering the critical section - is a function only of the number of clients currently contending and is independent of the maximum number of processes that might contend. In particular, in the contention-free case, a process can enter the critical section after only one round-trip message delay. We use this protocol to derive a protocol for ordering operations on a replicated object in an asynchronous distributed system subject to failures. This protocol is always safe, is probabilistically live during periods of stability and is suitable for deployment in practical systems.