Asynchronous leasing

Abstract

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