Buffer-Optimal Constructions of 1-Writer Multireader Multivalued Atomic Shared Variables

✍ Scribed by S. Haldar; K. Vidyasankar

• Book ID: 102974740
• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 623 KB
• Volume: 31
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1995.1156

✦ Synopsis

A 1-writer shared variable construction is buffer-optimal if (i) no control 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 buffer in a read execution; and (v) there is only one writing of a 1 -reader buffer, for each reader, in a write execution. In this paper, we consider design of bufferoptimal constructions of 1 -writer multireader multivalued atomic shared variables, starting with a (non-buffer-optimal) construction in the literature. An important characteristic of buffer-optimal constructions is confict-freedom; that is, in each execution, no reading of a buffer overlaps with any writing of that buffer. The constructions in this paper illustrate different ways of accomplishing the conflict-freedom property. 1995 Academic Press, Inc.