Computer Science/Discrete Mathematics Seminar II

A valency argument is an elegant and well-known technique for proving impossibility results in distributed computing. It is an example of an extension-based proof, which is modelled as an interaction between a prover and a protocol. Even though there is no wait-free algorithm to solve 2-set agreement among 3 processes that communicate using read and write, I will explain why there is no extension-based proof of this result. I will also mention some other impossibility results that do not have extension-based proofs.