In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 200-214. Springer, September 1997.
Abstract: We analyze the achievable fault tolerances of shared memory consistency conditions in the form of t-resilience, the ability to withstand up to t node failures. We derive tight bounds for linearizability, sequential consistency, processor consistency, and some weaker memories in totally asynchronous systems, in which failed and slow nodes cannot be distinguished. For linearizability, we show that neither the read nor the write operation can tolerate more failures than a minority of the nodes. For sequential consistency, processor consistency, and related conditions, we show that one operation can be wait-free and the other cannot tolerate more failures than a minority of the nodes. Several weaker conditions can have both operations wait-free.