Paxos
複数のProposer(1,2,...k)が思い思いの値(v1,v2,...vk)と提案番号(n1,n2,...nk)を持ち寄り、Acceptorのクラスタの中でv1,v2,...vkのどれかの値を選択することに合意する
Paxosに於いて選択されるとは「Acceptorの過半数が同じ$ v_xを選んだ」という状態になること。
いきなり原典であるThe Part-Time Parliamentを読みに行く人は大抵挫折する。現状これだけ日本語で解説されているものがあるので理解が目的であれば原典の方は暇なときに読む読み物として考えるぐらいで充分である。
Paxosアルゴリズムとは「ただ一つの覆らない値を選択する」アルゴリズムであり、誤解を恐れずに言うとこれ単品ではロクな使い道がない。
分散キーバリューストアであれば、複数のキーバリューペアが次々と追加・更新・参照・削除できる事を当然期待し...しかしPaxosアルゴリズム単品ではどうやってもその期待に応えることはできない。
分散KVSをつくるには
Chubbyのように更にPaxosを拡張したMulti-Paxosなどに頼ることになる。
Paxosで一度合意(選択)した値はアルゴリズム上二度と覆らない。