Asynchronous Leasing

Leasing is a very effective way to improve the performance of distributed algorithms without hampering their fault-tolerance. The notion of lease has traditionally been defined using a global notion of time and was hence strongly tied to synchronous system models. This paper introduces a new notion of lease devised for an asynchronous system model. We give the precise properties of our lease abstraction, we show how it can be implemented in an asynchronous system model, and we then illustrate its use by significantly improving the performance of a consensus-based atomic broadcast algorithm.

Related material