03/13/2012

Speaker(s) : Damien Imbs

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 for t+1 processes. Expressed differently, 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.)

An object has consensus number (CN) x if it can solve consensus between x processes but not for x+1 processes. If such an x does not exist, it has CN infinity. This means that an object with CN x can always be used to build x-consensus objects (objects which can solve consensus between only x processes). As examples, registers have CN 1, Test&Set have CN 2 and Compare&Swap have CN infinity.

We consider 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) x-consensus objects. 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+1,t,1) are equivalent, we focus on the pair (t,x) of parameters of a system model. Our main result is the following: the system models ASM(n1,t1,x1) and ASM(n2,t2,x2) have the same computational power for colorless decision tasks if and only if ⌊t1/x1⌋ = ⌊t2/x2⌋. As can be seen, this 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 ≤ t'< t*(x-1).

This talk will present the base principles of the BG simulation, our new simulation, and what it implies with respect to the computational power of system models, when considering colorless tasks.

Franck.Petit (at) nulllip6.fr