03/08/2020

Brief announcement: Why extension-based proofs fail

Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu

Keywords: impossibility proofs, set agreement, valency arguments

Abstract Paper Similar Papers

Abstract: We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We explain why this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at PODC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 25:11 
 0
 0
 0
 0
 3:08 
 0
 0
 0
 0
 11:18 
 0
 0
 0
 0
 14:29 
 0
 0
 0
 0
 12:11 
 0
 0
 0
 0
 16:58 
 0
 0
 0
 0
 4:52 
 0
 0
 0
 0
 23:56 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 14:50 
 0
 0
 0
 0
 22:51 
 0
 0
 0
 0
 5:02 
 0
 0
 0
 0
 26:06 
 0
 0
 0
 0
 11:17 
 0
 0
 0
 0
 20:02 
 0
 0
 0
 0
 15:33 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 23:36 
 0
 0
 0
 0
 5:40 
 0
 0
 0
 0
 14:54 
 0
 0
 0
 0
 14:38 
 0
 0
 0
 0
 5:22 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 15:41 
 0
 0
 0
 0
 17:30 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 15:28 
 0
 0
 0
 0
 11:59 
 0
 0
 0
 0
 14:30 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 9:58 
 0
 0
 0
 0
 3:00 
 0
 0
 0
 0
 13:54 
 0
 0
 0
 0
 25:04 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 25:07 
 0
 0
 0
 0
 10:27 
 0
 0
 0
 0
 28:00 
 0
 0
 0
 0
 14:13