分散アルゴリズム
合意アルゴリズムはいくつかのプロセスが共通の決定に合意する問題を解くものである。
より詳細には、合意プロトコルは以下の4つの特徴を備えなければならない。
終了: 全ての正常なプロセスはある値を決定する。 有効性: もし全てのプロセスが同じ値 v {\displaystyle v} を提案する場合、全ての正常なプロセスは v {\displaystyle v} を決定する。 整合性: 全ての正常なプロセスは最大1つの値を決定し、もし値 v {\displaystyle v} を決定した場合は、 v {\displaystyle v} が他のプロセスによって提案されている。 合意: もし正常なプロセスが v {\displaystyle v} を決定した場合、すべての正常なプロセスは v {\displaystyle v} を決定する。
Paxosアルゴリズムは、合意を実現するための典型的なアルゴリズムである。