Summary
In the course of a concurrent computation, processes P1,..., Pn must reach a common choice of one out of k alternatives A 1,..., A k. They do this by protocols using k shared variables, one for each alternative. If the range of the variables has m values then \(\frac{{\text{1}}}{{\text{2}}}\sqrt[{\text{3}}]{n} \leqq \operatorname{m} \) is necessary, and n + 2≦m is sufficient, for deterministic protocols solving the choice coordination problem (C.C.P.). We introduce very simple randomizing protocols which, independently of n, solve the C.C.P. by use of a fixed alphabet. A single-byte (256-valued) alphabet permits a solution with non-termination probability smaller than 2−127. Many software and hardware tasks involving concurrency can be interpreted as choice coordination problems. Choice coordination problems occur also in nature.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ben-Or, M.: Private communication
Fischer, M., Rabin, M.O.: Concurrent search of a large data-structure. In preparation
Lehmann, D., Rabin, M.O.: On the advantages of free choice: A symmetric and fully distributed solution to the dining philosophers problem. Submitted for publication
Rabin, M.O.: N-process synchronization by 4 · log2 N-valued shared variables. Proceedings of the 21st IEEE Annual Symp. on Foundations of Computer Science (1980). To appear JCSS
Probabilistic algorithms: Algorithms and complexity, New Directions and Recent Trends (J.F. Traub Ed.) Academic Press: New York (1976), pp. 21–39
Treat, A.: Experimental control of ear choice in the moth ear mite. XI. Internationaler Kongress für Entomologie. Wien (1960), pp. 619–621
Author information
Authors and Affiliations
Additional information
This research was supported in part by NSF grants: MCS77-02474 at Washington University, Seattle, MCS80-12716 at University of California at Berkeley. Presented at the Specker Symposium in Zürich, January 1980
Rights and permissions
About this article
Cite this article
Rabin, M.O. The choice coordination problem. Acta Informatica 17, 121–134 (1982). https://doi.org/10.1007/BF00288965
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00288965