a) We know that solving consensus in asynchronous distributed systems is impossible.

b) Let the consensus number of a concurrent object be cn = 2, which means that two processes can solve consensus using the concurrent object.

From (a) and (b), can we conclude that the concurrent object cannot be implemented in asynchronous distributed systems?


1 Answer 1


Yes, if you add a few qualifiers to your statements. Consensus is unsolvable in an asynchronous shared-memory or message-passing system of n>1 processes out of which at least one can fail. If you rule out failures, then consensus is solvable even if the system is asynchronous (e.g. just wait to hear all n proposals and then decide the smallest one).

If O is an object of consensus power 2, then it is impossible to implement O in an asynchronous shared-memory or message-passing system with failures. Otherwise, you could implement consensus for 2 processes, which would contradict the impossibility.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.