Abstract

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. We will discuss some impossibility results in distributed computing that cannot be proved using extension-based proofs. This work was inspired by Toni's early work on weak proof systems that cannot be used to prove the pigeonhole principle.

Attachment

Video Recording