BUFFER-OPTIMAL CONSTRUCTIONS OF 1-WRITER MULTIREADER MULTIVALUED ATOMIC SHARED VARIABLES

A 1-writer shared variable construction is buffer-optimal if (i) no co ntrol information is written in the buffers; (ii) buffers contain only one value from the domain of the variable; (iii) optimum number of 1- reader safe buffers are used; (iv) there is only one reading of a buff er in a read execution; and (v) there is only one writing of a 1-reade r buffer, for each reader, in a write execution. In this paper, we con sider design of buffer-optimal constructions of 1-writer multireader m ultivalued atomic shared variables, starting with a (non-buffer-optima l) construction in the literature, An important characteristic of buff er-optimal constructions is conflict-freedom; that is, in each executi on, no reading of a buffer overlaps with any writing of that buffer. T he constructions in this paper illustrate different ways of accomplish ing the conflict-freedom property. (C) 1995 Academic Press, Inc.