multithreading - FIFO队列的共识数

Question

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

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

但是我如何证明它恰好是 2？
我想我应该只使用 2-consensus 对象来实现一个队列，但我没能做到。

Answer 1

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

假设线程 A deq() 来自队列，然后 B deq() 来自队列。现在我们选择了左边的分支。然后假设线程 B deq() 来自队列，然后 A deq() 来自队列。现在我们选择了正确的分支。

现在，如果线程 C deq() 来自队列，它不应该关心其他 deq() 中的哪一个先。无论哪种方式，队列看起来都相同。

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

Answer 2

我认为Adar Hefer 的回答是正确的。我仍然认为，个人观点，这些正式的答案很痛苦。

作为非正式的回答。如果您必须使用 FIFO 队列就多个线程达成共识，您会怎么做？所以你可以在这里存储三个或更多的提议，没问题。比你可以画的稻草，无论是赢，输，还是第二个输。仍然没有问题。但是你如何获得正确的“投票”价值？对于 WIN，您可以只获取您的 threadID，但您如何确保其他两个线程也获取获胜者的值？如果您是失败的线程，从您的角度来看，您无法看到其他两个线程中的哪一个获胜。你所知道的是你已经输了，应该采取其他建议的价值。把它赌掉，你可能会画出正确的——你可能不会。