The Gap in Circumventing the Consensus Impossibility

The seminal impossibility of reaching consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value out of two possible values 0 or 1. On the other hand, abstractions that were shown to be, in some precise sense, minimal to circumvent the impossibility were determined for a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). These abstractions include synchronization primitives, namely shared object types, as well as failure detector oracles. This paper addresses the question of whether these abstractions were actually also minimal to circumvent the impossibility of weak consensus. We first show that any deterministic object type that implements weak consensus also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but not consensus, even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power ∞. Finally, we exhibit a failure detector that implements weak consensus but not consensus.