On Space-optimality Of Buffer-based Conflict-free Constructions Of 1-writer 1-reader Multivalued Atomic Variables From Safe Bits

摘要

A shared variable construction is called buffer-based if the values of the variable are stored in buffers that are different from control storage. Each buffer stores only a single value from the domain of the variable. A buffer-based construction is conflict-free if, in each execution of the shared variable, no reading of any buffer overlaps with any writing of that buffer. This paper studies shared space requirements for wait-free, conflict-free, deterministic constructions of 1-writer 1-reader multivalued atomic variables from safe variables. That four buffers are necessary and sufficient for such constructions has been established in the literature. This paper establishes the requirement for control storage. The least shared space for such a construction in the literature is (four safe buffers and) four safe control bits. We show that four safe control bits are necessary for such constructions when the reader is restricted to read at most one buffer in each read operation.