READING MANY VARIABLES IN ONE ATOMIC OPERATION - SOLUTIONS WITH LINEAR OR SUBLINEAR COMPLEXITY

We address the problem of reading several variables (components) X1,.. ., X(c), all in one atomic operation, by only one process, called the reader, while each of these variables are being written by a set of wr iters. 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 derive d from the existing literature. (The time complexity of a construction is the number of suboperations of a high-level operation and its spac e complexity is the number of atomic shared variables it needs.) In th is paper, we provide a deterministic protocol that has linear (in the number of processes) space complexity, linear time complexity for a re ad operation, and constant time complexity for a write. Our solution d oes not make use of time-stamps. Rather, it is the memory location whe re 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 algo rithm. This algorithm has an overwhelmingly small, controllable probab ility of error. Its space complexity, and also the time complexity of a read operation, are sublinear. The time complexity of a write is con stant. On the other hand, under the Archimedean time assumption, we ge t a protocol whose time and space complexity do not depend on the numb er of writers, but are linear in the number of components only. (The t ime complexity of a write operation is still constant.)