100222

無待機同期続き。ここでconsensus numberを同意数と訳した。この数はこの論 文で定義された数で、あるオブジェクトが同意数Nであるということは、少くと もN処理での無待機実装をすることができるという定義。
ここでの処理は、物理的な並列処理数。1CPUであればいくらスレッドがあった としても、処理数は1。この場合、それらスレッドの処理はスレッドの切り替え が割り込みを起因とするので(任意に切り替えもできるけれど、それは明らかに 考慮する必要がない)それを制限するだけでいい。これが二つになると両方の CPUの割り込みを禁止したとしても、禁止した時点で走行しているスレッドが、 きわどい領域にやってくる可能性があるので、共有メモリの読み書きの方法で は無理。ここでTest-And-Set命令が出てくるのだけど、実はこの命令でも同意 数2である。

The Many Faces of Consensus in Distributed Systems
John Turek, Dennis Shasha
IEEE Computer 1992

この論文では

非同期共有メモリで失敗に対して停止する傾向のシステムがあったとしよう。
Herlihyは同期基本要素の同意数を定義した。同意数nの基本要素は任意のn-1の
プロセッサが停止したとしても、同意を達成することができる。定義により、
nではない、同意数n-1の基本要素はは同意数nの基本要素を構成することができ
ない(そうでなければその基本要素は同意数nだろう)。逆に、同意数nの基本要
素はn-1の基本要素を構成できる。

と紹介している。ここで「同意」というのはオブジェクトを共有する処理に おいて、その処理それぞれがオブジェクトの状態を同一に認識できることだ。 この論文の導入は面白い

ボブとアリスは多くのことで共通することを気づいた。例えば、彼らは電
話よりE-mailを好んだ。寒い冬の日、アリスは10:00にボブにメールした。
「正午にLa Trysteの前で会おうよ」

この二人の間のE-mailの接続は、その通信を落としてしまうことで知られ
ていた。しかし今日は幸運にもアリスのメールはボブのワークステーションに
10:20に到着した。ボブは予定表を見ると、昼食は自由だ。そして彼は
承諾のメールを送った。

アリスはその承諾を10:45分に受けとった。そして出かける準備をし、ふ
と彼女は思った: 「もしボブが、私が彼の承諾のメールを受けとったこと
を知らなかったら、彼は私が待っていないと思うかもしれない。彼の承諾
の承諾をした方がいい」

 And so it goes. We can show that, ultimately. ボブとアリスのど
ちらも、少なくともどちらかの一人が、他方を待つために寒い中待ち続け
ることがないことを、完全に示せる。

これを例にして話が進む。

 + 信頼できる通信手段の教え。電話はこの問題を解決する。
アリス: 昼に会おうよ
ボブ: OK。じゃ、後で

E-mailが即時性も到達保証もないというのは一般にはもう伝わらないかも..。 今でもないのだけれど。

Wait-Free Synchronization

MAURICE HERLIHY

Digital Equipment Corporation

ACM Transactions on Programming Langages and Systems, vol.11, no.1,
January 1991,p124-149.

二つの並行物体XとYがあった時、YによるXの無待機実装は存在するか?

無待機処理が存在することを示すのは明解だ: それを表わせばいい。最近の文
献の多くはこの手法である。例は、不可分でない「安全」なレジスタから「不
可分」なレジスタ[18]、単純な不可分なレジスタから複雑な不可分なレジスタ
[4,5,16,23,25,26,29,31]、ネットワークの結合から、リードモディファイライ
トの操作[11,15]、単純な物体から、待ち行列や集合のような型付けされた物体
[14,19,20]。

そのような実装が「ない」ことを示すのは少々明解ではない。この論文の最初
では、「YによるXの無待機な実装はない」という形式を得る、単純で新しい技
法を提案する。我々はある層の物体はそれより上の階層のどの物体も実装でき
ないというような物体の階層を得た(図1を見よ)。基本的な考えは以下のようで
ある: それぞれの物体はそれに関連づけられる「合意数」を持ち、これはその
物体が単純な合意問題を解決できる最大の処理数である。nあるいはそれ以上の
並行処理があるシステムにおいて、nよりも小さい合意数の物体から、合意数n
の無待機な物体を実装することは不可能であることを紹介する。

FF13続き。ダークマター運動。あともうちょっと。シャオロングイはやっぱり 足を上げたらすぐD/D/Dにして受けた方が効率がいい。弱体も常にフルに入れて おくこと。ダルしか入れるのがない状態で。