Universality of Consensus

How to prove statements of the form “there is no wait-free implementation of $X$ by $Y$”?

6.2 Universality

A class $C$ is universal if one can construct a wait-free implementation of any object from some number of objects of $C$ and some number of read-write registers.

6.3 A Lock-Free Universal Construction

1
2
3
public interface SeqObject {
    public abstract Response apply(Invocation invoc);
}

(the apply() method applies the invocation and returns a response).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Node {
    public Invoc invoc;
    public Consensus<Node> decideNext;	// decide next Node in list
    public Node next;					// the next node
    public int seq;						// sequence number
    public Node(Invoc invoc) {
        invoc = invoc;
        decideNext = new Consensus<Node>();
        seq = 0;
    }
    public static Node max(Node[] array) {
        Node max = array[0];
        for (int i = 1; i < array.length; i++)
            if (max.seq < array[i].seq)
                max = array[i];
        return max;
    }
}

This shows a universal construction that transforms any sequential object into a lock-free linearizable concurrent object. This construction assumes that sequential objects are deterministic: if we apply a method to an object in a particular state, then there is only one possible response, and one possible new object state. We can represent any object as a combination of a sequential object in its initial state and a log: a linked list of nodes representing the sequence of method calls applied to the object (and hence the object’s sequence of state transitions).

我们只要存下调用序列就可以知道状态了。

那么怎么让它并发呢？也就是 apply() 能够并发地被调用。

只要在调用 apply() 的时候，都创建一个 node，通过一个 $n$-线程的共识协议来竞争哪一个节点被添加到调用序列当中。

赢者得到执行（什么达尔文），它把对象复制到本地，然后顺序执行（真的不计内存消耗了？）最后返回自己的结果。

败者就必须继续竞争（所以不是 wait-free）

详细的暂时不看了。

6.4 A Wait-Free Universal Construction

Core: help less fortunate threads to complete their calls. helping

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Universal {
    private Node[] announce;	// array added to coordinate helping
    private Node[] head;
    private Node tail = new node(); tail.seq = 1;
    for (int j = 0; j < n; j++) { head[j] = tail; announce[j] = tail; }
    public Response apply(Invoc invoc) {
        int i = ThreadID.get();
        announce[i] = new Node(invoc);
        head[i] = Node.max(head);
        while (announce[i].seq == 0) {
            Node before = head[i];
            Node help = announce[(before.seq + 1 % n)];
            if (help.seq == 0)
                prefer = help;
            else
                prefer = announce[i];
            after = before.decideNext.decide(prefer);
            before.next = after;
            after.seq = before.seq + 1;
            head[i] = after;
        }
        SeqObject MyObject = new SeqObject();
        current = tail.next;
        while (current != announce[i]) {
            MyObject.apply(current.invoc);
            current = current.next;
        }
        head[i] = announce[i];
        return MyObject.apply(current.invoc);
    }
}

我的智商不够看懂这个（懒）

7 就是 spinlock 了，终于有锁了，流下了激动的眼泪。