FIFO队列的共识编号

Question

多出队列的确切共识编号是多少？

我知道它至少为2：
queue.enq(1)
queue.enq(0)
线程A和B都调用queue.deq()。
得到1的线程将返回自己的值。
获取0的线程将返回另一个线程的值。

但是我如何证明它的确切共识编号为2？
我认为我应该使用仅使用2个共识对象来实现队列，但我没有成功。

- DazedAndConfused

---

Maurice Herlihy的论文“无等待同步”已经有证明。 - Alexey Kukanov

Answer 1

我认为Adar Hefer的答案是正确的。但我还是觉得，个人意见，这些正式的答案很麻烦。

作为一种非正式的回答。如果你需要在多个线程上达成一致意见，使用FIFO队列，你会怎么做？所以你可以存储三个或更多的提议，这里没有问题。然后你可以抽签，要么赢，要么输，或者第二次输。仍然没有问题。但如何获得正确的“投票”值呢？对于赢家来说，你只需要获取你的线程ID，但是如何确保另外两个线程也采用了赢家的值呢？如果你是一个失败的线程，从你的角度来看，你无法知道其他两个线程中的哪一个获胜了。你只知道你已经输了，应该采取另一个提议值。赌博一样地去尝试，你可能会选对——也可能不会。

- Khamaseen

---

为什么胜利的线程不能将其ID或获胜值写入共享变量，然后每个人都从那里读取呢？ - ilstam

我唯一看到的实际问题是，如果获胜线程在选择WIN抽签后但在更新共享变量之前终止，则会出现问题。 - ilstam

但这让我想到一个问题。如果有两个线程，一个选了LOSE，而第二个线程在甚至写入自己的值之前就死亡了，那会发生什么？ - ilstam

原子寄存器是在《多处理器编程的艺术》一书中定义的：https://dev59.com/5Wox5IYBdhLWcg3w8IxJ 。无论如何，一个线程在绘制/出队之前写入它的值。但我的问题是，如果另一个线程死了怎么办？即线程A写入其值，然后绘制LOSE。线程B立即死亡，甚至没有机会提议/写入其值。因此，线程A知道它应该使用B的值，但B从未提出过值。在这种情况下，我们是否达成共识？ - ilstam

如果获胜者没有写下其价值，那么仅凭两个线程是不可能画出平局的。因此A先画并获胜。 - Khamaseen

Answer 2

假设它可以解决3个线程的共识问题。 考虑所有可能的线性并发执行树中的关键状态。 向左走，你会决定1。向右走，你会决定0。

假设线程A从队列中deq（）然后B从队列中deq（）。现在我们走了左边的分支。 然后假设线程B从队列中deq（），然后A从队列中deq（）。现在我们走了右边的分支。

现在，如果线程C从队列中deq（），它不应关心其他线程先deq（）哪一个。无论哪种情况，队列对它来说都是相同的。

矛盾：线程C将决定两个不同的事情，即使就它而言，执行是相同的。

- Adar Hefer