Computing with faulty shared objects

This paper investigates the effects of the failure of shared objects on distributed systems. First the notion of a faulty shared object is introduced. Then upper and lower bounds on the space complexity of implementing 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 from a set of shared objects, some of which may suffer any number of faults, 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 processes from n + 10 primitive test & set registers, one of which may be faulty, and 3n + 13 reliable atomic registers, and (3) a reliable consensus object from 2f + 1 read-modify-write registers when f of these may 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.