The Multiplicative Power of Consensus Numbers

摘要

The Borowsky-Gafni (BG) simulation algorithm is a powerful reduction algorithm that shows that t-resilience of decision tasks can be fully characterized in terms of wait-freedom. Said in another way, the BG simulation shows that the crucial parameter is not the number n of processes but the upper bound t on the number of processes that are allowed to crash. The BG algorithm considers colorless decision tasks in the base read/write shared memory model. (Colorless means that if, a process decides a value, any other process is allowed to decide the very same value.) This paper considers system models made up of n processes prone to up to t crashes, and where the processes communicate by accessing read/write atomic registers (as assumed by the BG) and (differently from the BG) objects with consensus number x, accessible by at most x processes (with x ≤ t < n). Let ASM(n,t,x) denote such a system model. While the BG simulation has shown that the models ASM(n, t, 1) and ASM(t + l,t, 1) are equivalent, this paper focuses the pair (t,x) of parameters of a system model. Its main result is the following: the system models ASM(n_1,t_1,x_1) and ASM(n_2,t_2,x_2) have the same computational power for colorless decision tasks if and only if [t_1/x_1 = t_2/x_2]- As can be seen this contribution complements and extends the BG simulation. It shows that consensus numbers have a multiplicative power with respect to failures, namely the system models ASM(n, t',x) and ASM(n, t, 1) are equivalent for colorless decision tasks iff (t×x)