Ming Li
John Tromp
Skip Abstract Section
Abstract
Sharing data between multiple asynchronous users—each of which can atomically read and write the data—is a feature that may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is presented. The main construction of an n-user atomic variable directly from single-writer, single-reader atomic variables uses O(n) control bits and O(n) accesses per Read/Write running in O(1) parallel time.
- ~ ANDERSON, J. 1993. Composite registers. Dist. Comput. 6, 1993, 141-154. Google Scholar
- AWERBUCH, B., KIROUSIS, L., KRANAKIS, E., AND VITANYI, P. M.B. 1988. A proof technique for ~ register atomicity. In Proceedings of the 8th Conference on Foundations of Software Technology and ~ Theoretical Computer Science. Lecture Notes in Computer Science, Vol. 338. Springer Verlag, ~ Heidelberg, Germany, pp. 286-303. Google Scholar
- BLOOM, B. 1988. Constructing two-writer atomic registers. IEEE Trans. Comput. 37, 1506-1514. Google Scholar
- BURNS, J. m., AND PETERSON, G.L. 1987. Constructing multi-reader atomic values from nonatomic ~ values. In Proceedings of the 6th ACM Symposium on Principles of Distributed Computing (Vancou- ~ ver, B. C., Canada, Aug. 10-12). ACM, New York, pp. 222-231. Google Scholar
- DOLEV, D., AND SHAVIT, N. 1996. Bounded concurrent time-stamp systems are constructible. ~ SIAM J. Comput., to appear. Google Scholar
- DWORK, C., HERLIHY, M., PLOTKIN, S., AND WAARTS, O. 1992. Time-lapse snapshots. In Proceed- ~ ings of the 1st Israel Symposium on Theory of Computing and Systems. pp. 154-170. Google Scholar
- DWORK, C., AND WAARTS, O. 1992. Simple and efficient bounded concurrent timestamping, or, ~ Bounded concurrent timestamp systems are comprehensible! In Proceedings of the 24th Annual ~ ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. ~ 655-666. Google Scholar
- GAWLICK, R., LYNCH, N., AND SHAVIT, W. 1992. Concurrent timestamping made simple. In ~Proceedings of the 1st Israel Symposium on Theory of Computing and Systems. pp. 171-183. Google Scholar
- HALDAR, S., AND VIDYASANKAR, r., 1992. Counterexamples to a one writer multireader atomic ~shared variable construction of Burns and Peterson. ACM Oper. Syst. Rev. 26, l, 87-88. Google Scholar
- HALDAR, S., AND VIDYASANKAR, K. 1995. Constructing 1-writer multireader multivalued atomic ~ variables from regular variables. J. ACM 42, 1 (Jan.), 186-203. Google Scholar
- HERLIHY, M. P. 1988. Impossibility and universality results for wait-free synchronization. In ~ Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (Toronto, ~ Ont., Canada, Aug. 15-17). ACM, New York, pp. 276-290. Google Scholar
- HERLIHY, M. P., AND WING, J. 1990. Linearizability: A correctness condition for concurrent ~ objects. ACM Trans. Prog. Lang. Syst. 12, 3 (July), 463-492. Google Scholar
- ISRAELI, A., AND LI, M. 1987. Bounded time-stamps. In Proceedings of the 28th IEEE Symposium ~ on Foundations of Computer Science. IEEE, New York, pp. 371-382.Google Scholar
- ISRAELI, A., AND PINHASOV, M. 1992. A concurrent time-stamp scheme which is linear in time and ~ space. In Proceedings of the 6th International Workshop on Distributed Algorithms. Lecture Notes in ~ Computer Science, vol. 647. Springer-Verlag, Heidelberg, Germany, pp. 95-109. Google Scholar
- ISRAELI, A., AND SHAHAM, A. 1992. Optimal multi-writer multi-reader atomic register. In Proceed- ~ ings of the llth annual ACM Symposium on Principles of Distributed Computing (Vancouver, B. C., ~ Canada, Aug. 10-12). ACM, New York, pp. 71-82. Google Scholar
- rlROUSiS, L. M., KRANAKIS, m., AND VITANYI, P. M. B. 1987. Atomic multireader register. In ~ Proceedings of the 2nd International Workshop on Distributed Computing. Lecture Notes in Com- ~ puter Science, vol. 312. Springer-Verlag, New York, pp. 278-296. Google Scholar
- LAMPORT, L., 1986. On Interprocess Communication Parts I and II. Dist. Comput. 1, 77-101.Google Scholar
- LI, M., AND VIT~d'4YI, P. M.B. 1988. A very simple construction for atomic multiwriter register. ~ Tech. Rep. TR 01-87. Aiken Comp. Lab., Harvard Univ. Nov.Google Scholar
- LI, M., AND VITANYI, P. M.B. 1989. How to share concurrent asynchronous wait-free variables. In ~ Proceedings of the International Colloquium on Automata, Languages, and Programming. Lecture ~ Notes in Computer Science, vol. 372. Springer-Verlag, New York, pp. 488-505. Google Scholar
- LI, M., AND VITANYI, P. M.B. 1992. Optimality of wait-free atomic multiwriter variables. Inf. Proc. ~ Lett. 43, 107-112. Google Scholar
- LI, M., TROMP, J., AND VIT~'4YI, P. M.B. 1989. How to share concurrent wait-free variables, Tech. ~ Rep. CS-8916. CWI, Amsterdam, The Netherlands, April.Google Scholar
- LYNCH, N. A., AND VAANDRAGER, F.W. 1995. Forward and backward simulations. Part I: Untimed ~ systems, Inf. Comput. 121, 2, 214-233. Google Scholar
- NEWMAN-WOLFE, R. 1989. A protocol for wait-free, atomic, multi-reader shared variables. In ~ Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (Vancouver, ~ B. C., Canada, Aug. 10-12). ACM, New York, pp. 232-248. Google Scholar
- PETERSON, G.L. 1983. Concurrent reading while writing. ACM Trans. Prog. Lang. Syst. 5, 1 (Jan.), ~ 46 -55. Google Scholar
- PETERSON, G. L., AND BURNS, J.E. 1987. Concurrent reading while writing II: The multiwriter ~ case. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science. IEEE, New ~ York, pp. 383-392.Google Scholar
- SCHAFFER, R. 1988. On the correctness of atomic multi-writer registers, Tech. Rep. MIT/LCS/TM- ~ 364. MIT Lab. for Computer Science, MIT, Cambridge, Mass., June.Google Scholar
- SINGH, A. K., ANDERSON, J. H., AND GOUDA, M.G. 1994. The Elusive Atomic Register. J. ACM ~ 41, 2 (Mar.), 311-339. Google Scholar
- TROMP, J. 1989. How to Construct an Atomic Variable. In Proceedings of the 3rd International ~ Worksh~op on Distributed Algorithms. Lecture Notes in Computer Science, vol. 392. Springer-Verlag, ~ Heidelberg, Germany, pp. 292-302. Google Scholar
- VIDYASANKAR, K. 1988. Converting Lamport's Regular Register to an atomic register. Inf. Proc. ~ Lett. 28, 287-290. Google Scholar
- VITANYI, P. M. B., AND AWERBUCH, B. 1986. Atomic shared register access by asynchronous ~ hardware. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science. IEEE, ~ New York, 1986, pp. 233-243. (Errata, Ibid.,1987)Google Scholar
Index Terms
- How to share concurrent wait-free variables
Recommendations
Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...
Randomized two-process wait-free test-and-set
We present the first explicit, and currently simplest, randomized algorithm for two-process wait-free test-and-set. It is implemented with two 4-valued single writer single reader atomic variables. A test-and-set takes at most 11 expected elementary ...
Comments