Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity

We address the problem of reading several variables (components) X1…., Xc, all in one atomic operation, by only one process, called the reader, while each of these variables are being written by a set of writers. All operations (i.e., both reads and writes) are assumed to be totally asynchronous and wait-free. For this problem, only algorithms that require at best quadratic time and space complexity can be derived from the existing literature. (The time complexity of a construction is the number of suboperations of a high-level operation and its space complexity is the number of atomic shared variables it needs.) In this paper, we provide a deterministic protocol that has linear (in the number of processes) space complexity, linear time complexity for a read operation, and constant time complexity for a write. Our solution does not make use of time-stamps. Rather, it is the memory location where a write writes that differentiates it from the other writes. Also, introducing randomness in the location where the reader gets the value that it returns, we get a conceptually very simple probabilistic algorithm. This algorithm has an overwhelmingly small, controllable probability of error. Its space complexity, and also the time complexity of a read operation, are sublinear. The time complexity of a write is constant. On the other hand, under the Archimedean time assumption, we get a protocol whose time and space complexity do not depend on the number of writers, but are linear in the number of components only. (The time complexity of a write operation is still constant).