000161205 001__ 161205
000161205 005__ 20190812205458.0
000161205 0247_ $$2doi$$a10.1007/s00446-007-0043-z
000161205 022__ $$a0178-2770
000161205 02470 $$2ISI$$a000252888300003
000161205 037__ $$aCONF
000161205 245__ $$aFailure detectors as type boosters
000161205 269__ $$a2008
000161205 260__ $$bSpringer-Verlag$$c2008
000161205 336__ $$aConference Papers
000161205 500__ $$aNational Licences
000161205 520__ $$aThe power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the weakest failure detector to solve consensus among a number k > n of processes that communicate using shared objects of a type T with consensus power n. In other words, we seek for a failure detector that is sufficient and necessary to "boost" the consensus power of a type T from n to k. It was shown in Neiger (Proceedings of the 14th annual ACM symposium on principles of distributed computing (PODC), pp. 100-109, 1995) that a certain failure detector, denoted Omega (n) , is sufficient to boost the power of a type T from n to k, and it was conjectured that Omega (n) was also necessary. In this paper, we prove this conjecture for one-shot deterministic types. We first show that, for any one-shot deterministic type T with cons(T) <= n, Omega (n) is necessary to boost the power of T from n to n + 1. Then we go a step further and show that Omega(n) is also the weakest to boost the power of (n + 1)-ported one-shot deterministic types from n to any k > n. Our result generalizes, in a precise sense, the result of the weakest failure detector to solve consensus in asynchronous message-passing systems (Chandra et al. in J ACM 43(4):685-722, 1996). As a corollary, we show that Omega (t) is the weakest failure detector to boost the resilience level of a distributed shared memory system, i.e., to solve consensus among n > t processes using (t - 1)-resilient objects of consensus power t.
000161205 6531_ $$aWait-Free Hierarchies
000161205 6531_ $$aDistributed Consensus
000161205 6531_ $$aRobust
000161205 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000161205 700__ $$aKouznetsov, Petr$$g128437$$0241770
000161205 7112_ $$dOct 01-03, 2003$$cSORRENTO, ITALY$$a17th International Conference on Distributed Computing
000161205 773__ $$j20$$tDistributed Computing$$q343-358
000161205 8564_ $$zPUBLISHER'S VERSION$$uhttps://infoscience.epfl.ch/record/161205/files/446_2007_Article_43.pdf$$s733468
000161205 909C0 $$xU10407$$pDCL$$0252114
000161205 909CO $$pconf$$pIC$$ooai:infoscience.tind.io:161205
000161205 917Z8 $$xWOS-2010-11-30
000161205 937__ $$aEPFL-CONF-161205
000161205 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000161205 980__ $$aCONF