The choice coordination problem

摘要: In the course of a concurrent computation, processes P1,..., Pn must reach common choice one out k alternatives A 1,..., k. They do this by protocols using shared variables, for each alternative. If range variables has m values then $$\frac{{\text{1}}}{{\text{2}}}\sqrt[{\text{3}}]{n} \leqq \operatorname{m} $$ is necessary, and n + 2?m sufficient, deterministic solving coordination problem (C.C.P.). We introduce very simple randomizing which, independently n, solve C.C.P. use fixed alphabet. single-byte (256-valued) alphabet permits solution with non-termination probability smaller than 2?127. Many software hardware tasks involving concurrency can be interpreted as problems. Choice problems occur also in nature.