COMPUTING WITH FAULTY SHARED OBJECTS

This paper investigates the effects of the failure of shared objects o n distributed systems. First the notion of a faulty shared object is i ntroduced. Then upper and lower bounds on the space complexity of impl ementing reliable shared objects are provided. Shared object failures are modeled as instantaneous and arbitrary changes to the state of the object. Several constructions of nonfaulty wait-free shared objects f rom a set of shared objects, some of which may suffer any number of fa ults, are presented. Three of these constructions are: (1) A reliable atomic read/write register from 20f + 8 atomic read/write registers f of which may be faulty, (2) a reliable test & set register for n proce sses from n + 10 primitive test & set registers, one of which may be f aulty, and 3n + 13 reliable atomic registers, and (3) a reliable conse nsus object from 2f + 1 read-modify-write registers when f of these ma y be faulty. Using these constructions a universal construction of any linearizable shared object from a set of either n-processor consensus objects or n-processor read-modify-write registers, some of which may be faulty, is presented.