Name
Abstract | ||
|---|---|---|
In the course of a concurrent computation, processes P1,..., Pn must reach a common choice of one out of k alternatives A1,..., Ak. 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. |
Year | DOI | Venue |
|---|---|---|
1982 | 10.1007/BF00288965 | Acta Inf. |
Keywords | Field | DocType |
Information System,Operating System,Data Structure,Communication Network,Information Theory | Information theory,Concurrent computation,Data structure,Coordination game,Discrete mathematics,Combinatorics,Shared variables,Concurrency,Mathematics,Alphabet | Journal |
Volume | Issue | ISSN |
17 | 2 | 0001-5903 |
Citations | PageRank | References |
61 | 25.92 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael O. Rabin | 1 | 3471 | 3060.62 |