An Informal Visit to the Wonderful Land of Consensus Numbers and Beyond

Abstract

Since its introduction by M. Herlihy in 1991, consensus number has be- come a central notion to capture and understand the agreement and synchro- nization power of objects in the presence of asynchrony and any number of process crashes. This notion has now become fundamental in shared mem- ory systems, when one is interested in the design of universal constructions for high level objects defined by a sequential specification.

The aim of this survey is to be a guided tour in the wonderful land of consensus numbers. In addition to more ancient results, it also presents recent results related to the existence of an infinity of objects –of increasing synchronization/agreement power– at each level of the consensus hierarchy.