An Anonymous Wait-Free Weak-Set Object Implementation

We consider a system of n anonymous processes communicating through multi-writer/multi-reader (MWMR) registers. A weak-set object is a particularly interesting communication abstraction for anonymous processes; it may be seen as the equivalent of an atomic snapshot object in an anonymous system. It can be accessed through two operations: \(\textsc {add}()\) and \(\textsc {get}()\). Intuitively, an \(\textsc {add}(v)\) operation puts value v in the set represented by the object, while a \(\textsc {get}()\) operation returns the contents of the set. The paper describes a wait-free atomic implementation of a weak-set object shared by n anonymous processes using 3n MWMR registers. The description of the algorithm is incremental. The paper first presents an implementation that is wait-free only for the \(\textsc {Get}()\) operations, using 2n MWMR registers. Then it describes an implementation that is wait-free for the \(\textsc {Get}()\) and the \(\textsc {Add}()\) operations, using \(3n+1\) MWMR registers, and finally it is improved to an implementation using 3n MWMR registers. In addition, a lower-bound of n registers for the implementation of a wait-free atomic weak-set is proved.