Another way of achieving consensus in asynchronous systems is to relax the definition of ``asynchronous'' and allow some level of synchrony. The question then becomes, ``How much and what kind of synchrony do we need before consensus is possible?''
We can identify three kinds of asynchrony in the system described by Fisher et al.: (1) process asynchrony, where each process may go to sleep for an arbitrary amount of time; (2) communication asynchrony, where there is no upper bound on the possible delay of a message; and (3) message order asynchrony, where messages may be delivered in a different order than they were sent. Dolev et al. in [6] investigate the possibility of a consensus algorithm with only some of these asynchronies in the system.
They prove that only making the processes synchronous is not enough, but making either the communication or message order synchronous is alone enough, so long as the idea of an ``atomic step'' of a processor is retained. (In Fisher et al., each processor could perform an ``atomic step'', which consisted of receiving a message, performing some computation, and sending messages to other processes.) For example, if the atomicity of this operation is lost (i.e., if an arbitrary delay is allowed in the middle of the operation), then no consensus algorithm is possible with only communcation synchrony.
There are two components of an ``atomic step'' which are important: atomicity of a receive and send operation, and broadcast capability. Four minimal cases were described:
Any of these four scenarios is enough to allow the possibility of a consensus protocol, and any weakening of them makes such a protocol impossible.