Consensus Numbers

1
2
3
public interface Consensus<T> {
    T decide(T value);
}
  • consistent: all threads decide the same value,
  • valid: the common decision value is some thread’s input.

Def 5.1.1 A class C solves $n$-thread consensus if there exist a consensus protocol using any number of objects of class C and any number of atomic registers.

Def 5.1.2 The consensus number of a class C is the largest $n$ for which that class solves $n$-thread consensus. If no largest $n$ exists, we say the consensus number of the class if infinite.

Corollary 5.1.1 Suppose one can implement an object of class C from one or more objects of class D, together with some number of atomic registers. If class C solves $n$-consensus, then so does class D.

A protocol state is critical if:

  • It is bivalent, and
  • if any thread moves, the protocol state becomes univalent.

Lemma 5.1.3. Every wait-free consensus protocol has a critical state.

5.2 Atomic Registers

Whether we can solve consensus using atomic registers?

– no

There is no binary consensus protocol for two threads.

1
2
3
4
5
6
7
8
9
public abstract class ConsensusProtocol<T> implements Consensus<T> {
    protected T[] proposed = (T[]) new Object[N];
    // announce my input value to the other threads
    void propose(T value) {
        proposed[ThreadID.get()] = value;
    }
    // figure out which thread was first
    abstract public T decide(T value);
}

不是，你都有互斥的 Queue 了，那不是等同于作弊么

5.4 FIFO Queues

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class QueueConsensus<T> extends ConsensusProtocol<T> {
    private static final int WIN = 0;	// first thread
    private static final int LOSE = 1;	// second thread
    Queue queue;
    // initialize queue with two items
    public QueueConsensus() {
        queue = new Queue();
        queue.enq(WIN);
        queue.enq(LOSE);
    }
    // figure out which thread was first
    public T decide(T value) {
        propose(value);
        int status = queue.deq();
        int i = ThreadID.get();
        if (status == WIN) return proposed[i];
        else return proposed[1 - i];
    }
}

Corollary 5.4.1 It is impossible to construct a wait-free implementation of a queue, stack, priority queue, set, or list from a set of atomic registers.

5.5 Multiple Assignment Objects

5.6 Read-Modify-Write Operations

Many, if not all, of the classical synchronization operations provided by multiprocessors in hardware can be expressed as read-modify-write (RMW) operations, or, as they are called in their object form, read-modify-write registers.

1
2
3
getAndSet(v);
getAndIncrement();
...
1
2
3
4
5
6
7
8
9
10
11
12
13
class RMWConsensus extends ConsensusProtocol {
    // initialize to v such that f(v) != v
    private RMWRegister r = new RMWRegister(v);
    public Object decide(Object value) {
    propose(value);
        int i = ThreadID.get();
        int j = 1 - i;
        if (r.rmw() == v)
            return proposed[i];
        else
            
    }
}