先入先出隊列的共識編號

Question

多出列隊列的確切共識編號是多少？

我知道這是至少2：
queue.enq(1)
queue.enq(0)
線程A和B每個呼叫queue.deq()。
得到1的線程將返回它自己的值。
得到0的線程將返回另一個值。

但我該如何證明它是恰好2？
我想我應該只使用2-consensus對象來實現一個隊列，但我沒有設法做到這一點。

Answer 1

假設它可以解決3個線程的共識。 考慮樹中所有可能的線性化併發執行的臨界狀態。 左邊，你會決定1.一個正確的，你會決定0.

假設線程從隊列中的deq（）的，然後B隊列中的deq（）的。現在我們走了左邊的分支。 然後假設線程B deq（）來自隊列，然後A deq（）來自隊列。現在我們選擇了正確的分支。

現在，如果線程C deq（）來自隊列，它不應該關心其他哪個deq（）首先。隊列看起來與其相同。

一個矛盾：線程C將決定2個不同的事情，即使執行是相同的，就其而言。