000052620 001__ 52620
000052620 005__ 20190316233459.0
000052620 037__ $$aREP_WORK
000052620 245__ $$aThe Gap in Circumventing the Consensus Impossibility
000052620 269__ $$a2004
000052620 260__ $$c2004
000052620 336__ $$aReports
000052620 520__ $$aThe seminal impossibility of reaching consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value out of two possible values 0 or 1. On the other hand, abstractions that were shown to be, in some precise sense, minimal to circumvent the impossibility were determined for a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). These abstractions include synchronization primitives, namely shared object types, as well as failure detector oracles. This paper addresses the question of whether these abstractions were actually also minimal to circumvent the impossibility of weak consensus. We first show that any deterministic object type that implements weak consensus also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but not consensus, even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power ∞. Finally, we exhibit a failure detector that implements weak consensus but not consensus.
000052620 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000052620 700__ $$0241770$$g128437$$aKouznetsov, Petr
000052620 8564_ $$uhttps://infoscience.epfl.ch/record/52620/files/IC_TECH_REPORT_200428.pdf$$zn/a$$s176972
000052620 909C0 $$xU10407$$0252114$$pDCL
000052620 909CO $$ooai:infoscience.tind.io:52620$$qGLOBAL_SET$$pIC$$preport
000052620 937__ $$aLPD-REPORT-2004-004
000052620 970__ $$a200428/IC
000052620 973__ $$sPUBLISHED$$aEPFL
000052620 980__ $$aREPORT