コンセンサス数Nとコンセンサス数無限の違い

Question

本の並行プログラミング：Michel Raynalのアルゴリズム、原理、および基礎、セクション16.5.1では、定理75は

比較＆スワップオブジェクトには、無限の合意数があります。

とセクション16.5.2では、補題40は

を言う

MEM-TO-MEM-SWAPオブジェクトタイプは、Nプロセスのシステム内のコンセンサス数Nを持っています。

その後、16.1項で、著者は、コンセンサス番号無限のオブジェクトとして、比較＆スワップとスワップとMEN-TO-MEM-SWAPの両方をテーブルに入れます。

それで、コンセンサス番号Nとコンセンサス番号のオブジェクトを持つオブジェクトの違いは何ですか？

Answer 1

オブジェクトのコンセンサス数は、待ち合わせのある方法でそのようなオブジェクトと同期できる同時プロセスの最大数です（ここではどのような待ち合わせを意味するのはありません）。たとえば、読み書き操作のみを持つレジスタは、待ち時間の同期のみを全く使用できないため、合意番号1があります。テストアンドセット操作のレジスタを使用して、待機中の2つのプロセスを同期させるために使用できます。 3つ以上ではなく、3つ以上の方法では、テストとセットの合意数は2です。

$ n $ -registerの割り当て。プロセスが複数のレジスタにアトミックに書き込むことができる場合、 $ 2n-を許可します。 2 $ $ n $ レジスタがある場合は、待ちを空けないプロセス。より多くのプロセスがより多くのレジスタを必要とします。したがって、 $ n $ からなるオブジェクトのコンセンサス数は、アトミックに割り当てることができるレジスタのレジスタです。 $ 2n-2 $ 。

比較とスワップ操作を備えたシングルレジスタでは、待ち合わないプロセスの数を同期させるのに十分です。したがって、コンペアとスワップの合意数は無限大です。

LEMMA 40は、MEM-AND-SWAPオブジェクトで、 $ n $ 並行プロセスのシステム内のすべてのプロセスの待ち否で、番号 $ n $ 。つまり、任意の数の $ n $ の場合、mem-and-swapのコンセンサス数は少なくとも $ n $ < /スパン>。 （コンセンサス番号が $ n $ の $ n $ 任意の $ n $ の場合、それは無限です。

Raynalの本よりも別のソースを好む場合は、元のモーリスherlihy