マルチデキューアキューの正確なコンセンサス数は?
私はそれが少なくとも 2 であることを知っています:
queue.enq(1)
queue.enq(0)
スレッド A と B はそれぞれ呼び出しますqueue.deq()。
1 を取得したスレッドは、独自の値を返します。
0 を取得したスレッドは、もう一方の値を返します。
しかし、それが正確に 2であることを証明するにはどうすればよいですか?
2 コンセンサス オブジェクトのみを使用してキューを実装する必要があると思いますが、うまくいきませんでした。
3 つのスレッドのコンセンサスを解決できると仮定します。可能なすべての線形化された同時実行のツリーで、重大な状態を考えてみましょう。左に曲がれば1、右に曲がると0。
キューからのスレッド A の deq() と、キューからのスレッド B の deq() を想定します。今、私たちは左の枝を取りました。次に、スレッド B の deq() がキューから、次にスレッド A の deq() がキューからだとします。今、私たちは右の枝を取りました。
ここで、スレッド C の deq() がキューからのものである場合、他のスレッドのどれが最初に deq() されたかを気にする必要はありません。キューはどちらの方法でも同じに見えます。
矛盾: スレッド C は、実行に関する限り同一であっても、2 つの異なることを決定します。