Synchronization Operations

Why is mutual exclusion so wrong?

  • Asynchronous interrupts
  • Heterogeneours processors(异质处理器,性能水平不同的意思)
  • Fault-tolerance
  • Machine level instruction granularity

Consensus

Each thread has a private input, they communicate and agree on one thread's input.

Formally, consensus is

  • Consistent: all threads decide the same value
  • Valid: the common decision is some thread's input

Theorem: there is no wait-free implementation of \( n \)-thread consensus (\( n > 1 \)) from read-write registers.

Concurrent consensus object:

  • Each thread execute a method only once
  • Linearizable to sequential consensus object in which the input of threades is decided on who completed its method first

Generic consensus protocol:

abstract class ConsensusProtocol implements Consensus {
    protected Object[] proposed = new Object[N];

    private void propose(Object value) {
        proposed[ThreadID.get()] = value;
    }

    abstract public Object decide(Object value);
}

Consensus Using FIFO Queue

Question: Can a FIFO queue implement \( n \)-thread (\( n > 1 \)) consensus?

We first find the consensus number of a FIFO queue.

From the theorem, the consensus number of registers is 1. If the consensus number of a queue is > 1, then we cannot implement a queue using registers.

public class QueueConsensus extends ConsensusProtocol {
    private Queue queue;

    public QueueConsensus {
        queue = new Queue();
        queue.enq(Ball.Red);   // a red ball
        queue.enq(Ball.Black); // a black ball
    }

    public decide(Object value) {
        propose(value);
        Ball ball = this.queue.deq();
        if (ball == Ball.Red) {
            return proposed[i]; // get red ball, I decide
        } else {
            return proposed[1 - i]; // I was second, let other decide
        }
    }
}
  • Winner get red ball and decides her own value
  • Loser get black ball and can find winner's value in array
    • Because threads write array before dequeue

Theorem: we can solve 2-thread consensus using only a two-dequeuer queue and some atomic registers.

Implications: it is impossible to implement a two-dequeuer wait-free FIFO queue from read/write memory. (可以通过反证法证明,如果存在,则寄存器可以解决2线程的共识问题)

Consensus Numbers

An object X has consensus number \( x \),

  • if it can be used to solve \( n \)-thread consensus
  • but not \( (n + 1) \)-thread consensus

Theorem:

  • atomic read/write registers have consensus number 1
  • multi-dequeuer FIFO queues have consensus number at least 2
  • if you can implement X from Y, and X has consensus number \( c \), then Y has consensus number at least \( c \)
  • conversely, if Y has a consensus number \( d < c \), then there is no way to construct a wait-free implementation of X by Y

Multiple Assignment

Theorem: atomic registers cannot implement multiple assignment (i.e. atomic write to multiple locations).

Proof: if we can write to 2 elements of a 3-array, we can solve 2-consensus. Who first writes to two elements wins. We can check the left one element we did not write to see if we win or lose.

public class MultiConsensus extends ConsensusProtocol {
    Assign2 a = new Assign2(3, EMPTY);

    public Object decide(Object value) {
        a.assign(i, i, i + 1, i);
        int other = a.read((i + 2) % 3);
        if (other == EMPTY || other == a.read(1)) { // 1 is mid
            return proposed[i]; // I win
            // the other thread did not write or wrote after me
        } else {
            return proposed[1 - i];
        }
    }
} 

Read-Modify-Write

RMW: a method call returns object's prior value \( x \), and replaces \( x \) with mumble(x) atomically.

A RMW method mumble(x) is non-trivial if there exists a value v such that v != mumble(v).

  • identity(x) := x is trivial
  • getAndInc(x) := x + 1 is non-trivial

Theorem: any non-trivial RMW object has consensus number at least 2.

Corollary: no wait-free implementation of non-trivial RMW objects from registers.

public class RMWConsensus extends ConsensusProtocol {
    private RMWRegister r = v;

    public Object decide(Object value) {
        propose(value);
        if (r.getAndMumble() == v) {
            return proposed[i]; // original value, I win
        } else {
            return proposed[1 - i]; // mumbled, I lose
        }
    }
}
  • Commute: \( f_i(f_j(v)) = f_j(f_i(v)) \)
  • Overwrite: \( f_i(f_j(v)) = f_i(v) \)

Claim: any set of RMW objects that commutes or overwrites has consensus number exactly 2.

Compare-And-Set

CAS registers has infinite consensus number.

public class CASConsensus extends ConsensusProtocol {
    private AtomicInteger r = new ...(-1);

    public Object decide(Object value) {
        propose(value);
        r.compareAndSet(-1, ThreadID.get());
        return proposed[r.get()]; // who swapped wins
    }
}

Lock-Freedom Revised

  • Any wait-free implementation is lock-free.
  • Lock-free is the same as wait-free if the execution is finite.
  • Lock-free is to wait-free as deadlock-free is to lockout-free.

Lock-free consensus is as impossible as wait-free consensus.