LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Why Extension-Based Proofs Fail
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Why Extension-Based Proofs Fail

96 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Faith Ellen, from the University of Toronto, examines a core proof technique in distributed computing: the valency argument, a type of extension-based proof modeled as an interaction between a prover and a protocol. She shows that although no wait-free algorithm exists to solve 2-set agreement among three processes communicating by read and write, this impossibility result cannot actually be established through an extension-based proof. Ellen works through the structure of such proofs, where they succeed, and why this particular case resists them, then surveys several other known impossibility results in distributed computing that likewise have no extension-based proof. Delivered as part of the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar II, the talk is aimed at an audience already familiar with distributed algorithms and impossibility arguments, and it treats the limits of a standard proof technique as a subject in its own right.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 36 m
Compared with MathematicsLonger than 93%
Source channelInstitute for Advanced Study (YouTube)