# 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) {
}

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];
}
}
}


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);