MULTIWRITER CONSISTENCY CONDITIONS FOR SHARED MEMORY REGISTERS Academic Article uri icon

abstract

  • Regularity is a shared memory consistency condition that has received considerable attention. Lamport-s original definition of regularity assumed a single-writer model, however, and is not well defined when the shared register may have multiple writers. In this paper, we consider four possible definitions of multiwriter regularity. The definitions are motivated by variations on a quorum-based algorithm schema for implementing them. We study the relationships between these definitions and a number of other well-known consistency conditions, and we give a partial order describing the relative strengths of these consistency conditions. Finally, we provide a practical context for our results by studying the correctness of two well-known algorithms for mutual exclusion under each of our proposed consistency conditions. 2011 Society for Industrial and Applied Mathematics.

published proceedings

  • SIAM JOURNAL ON COMPUTING

author list (cited authors)

  • Shao, C., Welch, J. L., Pierce, E., & Lee, H.

citation count

  • 15

complete list of authors

  • Shao, Cheng||Welch, Jennifer L||Pierce, Evelyn||Lee, Hyunyoung

publication date

  • January 2011