I have been reading The Art of Multiprocessor Programming, and have been pondering on the foundation of lock-free and wait-free algorithms for the last few weeks.

The book introduces the concept of registers and consensus. The ideas are fairly abstract, but the proofs and results are very rewarding.

It gives me a good insight on how lock/wait free algorithm are constructed.

Consensus Definitions

Consensus is a distributed computing problem on how multiple thread or task can agree upon some value based on an input. To write out as an object, a consensus object has a single method called decide().

public interface Consensus<T> {
	T decide(T value);
}

The decide() method have to meet the following two conditions:

1. consistent: all threads decide the same value
2. valid: the common decision value is some thread’s input

A consensus protocol is a class that implements consensus in a wait-free manner.

A consensus number is the largest number of thread a class can solves the consensus problem. If a class has consensus number >= n in a n-thread system, the class is considered universal. If n is infinite, the consensus number for the class is infinite.

Atomic Registers

In hardware level, thread communicates with each other through shared memory. But in a theoretical standpoint, we can simplify this by saying that threads communicates through shared concurrent objects.

Consider an object called AtomicRegister that holds some value and has a read() and write() function. It is an abstraction from hardware primitives such as load/store instruction, and it is used to inter-thread communications.

public interface AtomicRegister<T> {
	T read();
	void write(T v);
}

AtomicRegister is wait-free and linearizable. This implies that if a method call completes before another, the earlier call must have taken effects before the later call.

Here comes two striking conclusions.

1. AtomicRegister has a consensus number  1.
2. It is impossible to construct a wait-free or lock-free implementation of an object with consensus number n from an object with a lower consensus number.

Therefore, in order to implement any lock-free or wait-free data structure, modern processor must provide more than just loads and stores.

The Power of Compare-And-Swap

Modern processor provides some powerful synchronization mechanism such as Compare-And-Swap. In x86, the instruction is called CMPXCHG.

The instruction takes in two arguments: an expected value and an updated value. If the current register value is equal to the expect value, then it is replaced by the updated value. Otherwise, the value is left untouched.

In Java concurrent package, this functionality is provided by the method compareAndSet() in a class called AtomicInteger.

It is not difficult to see that compareAndSet() has an infinite consensus number.

With compareAndSet(), we can implement a consensus protocol with an infinite consensus number.

class CASConsensus<T> {
	private final int FIRST = -1;

	private AtomicInteger r = new AtomicInteger(FIRST);

	// N-thread system where each have its own propose value
	// The array index correspond to its thread id.
	protected T[] proposed = (T[]) new Object[N];

	// Propose a value for this thread. However, it might not be chosen.
	void propose(T value) {
		proposed[ThreadId.get()].value;
	}

	// Take in a value, and obtain consensus among all thread
	// to see which value is decided.
	public Object decide(Object value) {
		propose(value);
		int i = ThreadID.get();
		if(r.compareAndSet(FIRST,i))
			return proposed[i];
		else
			return proposed[r.get()]
		}
	}
}

In the CAS consensus protocol, compareAndSet() ensures that the first thread’s proposed value will be accepted, and all other threads will yield. This is simple, yet very powerful.

Conclusion

Without modern hardware support, it is impossible to implement any lock-free or wait-free object.

Compare-And-Swap has an infinite consensus number, and it is a key operation for a wait-free consensus protocol.

Side Note

Apparently, with a wait-free consensus protocol, there exists algorithms to convert any object into a lock-free or wait-free concurrent object. We will save that for next time. 🙂