オブジェクトXのconsensus number: 以下の条件で[[Wait-Free]]な[[Consensus algorithm|Consensus]]を解けるプロセス数の最大値 - X のインスタンスを任意個使ってよい - Read-writeレジスタも任意個使ってよい オブジェクトXが[[Linearizability|線形化可能]]かつ[[Wait-Free]]と仮定したときに、それを使っていくつのプロセスが競合する環境下での[[Consensus algorithm|Consensus]]を実現できるか？ | Consensus number | オブジェクトの例 | | ---------------- | --------------------------------------------------------------------- | | 1 | Read-writeレジスタ、[[atomic snapshot]] | | 2 | [[test-and-set]]、[[fetch-and-increment]]、[[swap]]、[[queue]]、[[stack]] | | 2m−2 | m 個のレジスタへの同時代入（m-assignment） | | ∞ | [[compare-and-swap]]、[[LL SC]]、[[sticky register]] | たとえばTest-and-setがあれば2プロセス間のコンセンサスは実現できる Consensus numberが無限のオブジェクトは[[FLP Impossibility]]より実現不可能