JPS60500232A - 障害がない場合に最適化される、複数プロセッサの合意を得る方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 障害力ぐない場合に最適化される、複数プロセッサの合意を得る方法 ［技術分野］ 本発明は複数のプロセッサが同期されたフェーズで情報を交換するようなネット ワークに係り、更に詳細に説明すれば、障害プロセッサが存在する場合でさえも 、前記複数のプロセッサ間で分散されたタスクを実行するか、または全く実行し ないかについて、これらのプロセッサ間の合意（ａｇｒｅｅｍｅｎｔ）を得る方 法に係る。

［背景技術］ Ｃ，ＰＵネットワークに分散されたタスクの並行処理によって計算を行なうこと は、よく知られている。事実、米国特許第４２７４１３９号に記述されたシステ ムでは、１つのタスクを実行中の局所ＣＰＵが別の機能を他の遠隔ＣＰＵに送り 、そしてこの遠隔Ｃ，ＰＵで処理された出力結果を、局所ＣＰＵが受取るように している。同様に、同時係属出願の米国特許出願第４．５９７４６号（１９８３ 年１月２１日出願）では、所与の計算を構成する複数の並行処理可能なタスクと 対話するために、単一の物理ポートを使用する方法が開示されている。この方法 に利用される機能の中には、パス・スルー（ｐａｓｓ−ｔｈｒｏｕｇｈ）、即ち １つのサイトの使用者が別のサイトのＣＰＵにログオンし、そのファイルを転送 することを可能にする機能がある。

一般に、計算とは複数の並行処理可能なタスクから成り、これらのタスクにはネ ットワーク中の局所または遠隔ＣＰＵにおける情報のアクセス、変更、及び復元 が含まれる。このことは、調整、活動の同時性、または最終結果の相似性を必要 とする。例としては、分散された複数の勘定口座の借方／貸方に同額を記入する こと、同じ開始クロック値を使用すること、等の多種多様のものがある。それら に共通する重要な特性は、複数の非同期プロセッサが、それらの１つによって生 ぜられた情報値を使用するとともに、それら依存することである。この場合、受 取った値が送られた最初の値であったかどうかを決定することが必要である。こ の問題を処理するために２クラスのプロトコル、即ち多重フェーズ確約（ｃｏｍ ｍｉｔ）／放棄プロトコル及びビザンチン合意（Ｂｙｚａｎｔｊ　ｎｅＡｇｒｅ ｅｍｅｎｔ）プロトコルが考案されている。

確約／放棄プロトコルとビザンチン合意プロ１−コルは共に、ネットワーク構成 のＣＰＵ　（ノート）間で同期されたフェーズのメツセージを交換すること、及 びそれぞれのノードでこれらのメツセージを評価することを含む。その目的は、 すべてのノートにおけるトランザクションの一様な確約を最終的に保証すること であるが、プロトコルの種類によって強調点が異なる。例えば、ビザンチン合意 プロトコルは、アクティブノードの各々が、ネットワーク中の他のすへてのアク ティブノードのアイデンティティを知っていること、そしてそれらの間に直接結 合があることを仮定する。更に、ビザンチン合意プロトコルは、高いメツセージ ・オーバヘッドで、一定期間内に集中的に合意しようとする。これに対し、多重 フェーズ確約プ」トコルは、Ｇｒａｙ、”Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍｓ 、　ＡｎＡｄｖｃｉｎｃｅｄ　Ｃｔ＋ｕｒｓｅ”、Ｓｐｅｒｉｎｇｅｒ　Ｖｅｒ ｌａｇ、１９７８て説明しているように、タスクの階層に焦点を当てており、ノ ードに関する個々のノードの知識を従属ノードに限定している。

多重フェーズ確約プロトコルは、多くのメツセージが失なわれても許容すること ができるが、これらのプロトコルは調整用プロセッサノードについては、−瞬の 障害でさえも許容することができない。このノードは、ネットワーク構成された 幾つかのプロセッサに、トランザクションの確約信号を選択的に送り、その他の プロセッサには、トランザクションの放棄信号を送る。それとは対照的に、ビザ ンチン合意プロトコルは、平均してより多くのメツセージを必要とし、限られた 数のノード／リンク障害を許容するが、これらの障害には、各種のものがある。

従って、このプロトコルの目的が、保証された同報通信を確保することである場 合、メツセージ・オーバヘットと保証の信頼性の間で、トレードオフが計られる 。

また、５ｋｅｅｎ、”Ｎｏｎ−ＢｌｏｃｋｉｎｇＣｏｍｍｉｔ　Ｐｒｏｔｏｃｏ ｌｓ”、１９８Ｌｐｐ１３３−１４２には、障害時の閉塞（ブロッキング）の可 能性を減少させる多重フェーズ確約プロトコルが記述されている。計算の目的が 、複写されたデータベースの同時更新である場合、プロトコルのクラス間のメツ セージ伝送量が同じ大きさとなることがある。

Ｐｅａｓｅ　ｅｔ　ａｌ、”Ｒｅａｃｈｉｎｇ　Ａｇｒｅｅｍｅｎｔ　ｉｎ　ｔ ｈｅ　Ｐｒｅｓｅｎｃｅ　ｏｆＦａｕｌ、ｔｓ”、２７　Ｊｏｕｒｎａｌ　ｏｆ 　ｔｈｅ　ＡＣＭ、ｐｐ２２８−２３４．　Ａｐｒｉｌ　１９８０では、ビザン チン合意プロトコルを、同期されたフェーズで情報交換する手段を有するネット ワークにおいて非同期プロセッサの間の、−貫性及び合意を実現する方法として 定義している。これは、いくつかのプロセッサに障害がある場合でさえも適用さ れる。それと関連して、Ｌａｍｐｏｒｔ、”Ｔｈｅ　ＢｙｚａｎｔｉｎｅＧｅｎ ｅｒａｌｓ　’　Ｐｒｏｂｌｅｍ”、８４　ＡＣＭ　Ｔｒａｍｓａｃｔｉｏｎ　 ｏｎ　Ｐｒｏｇｒａｍｍｊ、ｎｇＬａｎｇｕａｇｅｓ　ａｎｄ　Ｓｙｓｔｅｍｓ 、ｐｐ３８２−４０１．Ｊｕｌ−ｙ　１．９８２では、軍事用語の瞳側が図式的 に説明されている。しかしながら、両方向性のリンクによって情報を交換できる ｎプロセッサのネットワークに適用された場合の問題点は、潜在的に障害のある プロセッサ、またはリンクを含む環境において、プロセッサの１つによって伝送 中の、メツセージの内容（値）についてすべてのプロセッサが合意することであ る。このような環境の下では、障害のある構成要素の動作についていがなる仮定 も行なわれない。従って、どの方法も、メツセージを中継することができなかっ たり、またはその内容を破壊することさえあるプロセッサまたはリンクに、対処 しなければならない。

ビザンチン合意（ＢＡ）は、１−組のプロセッサに対する回報通信を結果的に保 証するものである。つまり、システム中の障害の数が、この保証の信頼性を特徴 づけるパラメータｔを越えないことを条件として、正しく動作するすべてのプロ セッサが同じメツセージを受取るが、またはどのプロセッサもメジセージを受取 らない、ということである。特徴としては、潜在的に信頼性が低いプロセッサの ネットワークは、いくつかの同期されたフェーズの情報交換を行なう手段を含む 。

この情報交換後、前記プロセッサはすべて、それらのプロセッサの１つが最初に 保持していた値について合意しなければ（１）すべての正しいプロセッサが同じ 値について合意し、かつ、 （２）もし最初の値が正しければ、すべてのプロセッサがその値について合意す る ときに得られる。

項目（１）及び（２）が暗に含んでいるのは、プロセッサの各々がそのプロトコ ルの実行を完了して合意に達するのに成る時間を要すること、そしてすべてのプ ロセッサがこの時間について承知していなければならない、ということである。

もし、すべてのプロセッサが同じフェーズで合意に達する。ならば、それは“即 時”の合意と呼ばれ、そうでない場合は、′最後Ｉ′合意と呼ばれる。

プロトコルは必要に応じて確認（ａｕｔｈｅｎｔｉｃａｔｉｏｎ）を使用し、こ れにより任意のプロセッサが新しい値またはメツセージを情報交換に導入するこ とを阻止する。確認プロトコルは、送信プロセッサがメツセージに署名を添付す ることを要求する。この署名には符号化されたメツセージのサンプル部分が含ま れているので、任意の受信プロセッサはこのメツセージ力（真正であり且つ生成 プロセッサによって作成されたことを検査できる。また、どのプロセッサも、他 のプロセッサの署名を偽造不可能な、即ち、見破られずにメツセージ内容を変更 できないものと仮定される。

若しも、信頼性度ｔを有するＢＡがｔよりも少ない障害によって影響されるとす れば、実際にはｆ個の障害しか生じえないという合意に、複数のプロセッサがど れ位の時間で到達できるであろうか。この問題の解決には、停止の概念を′明白 にすることが含まれる。プロセッサは、それが合意の値を決めたとき停止してい るとみなされ、この合意に関するそれ以上の処理またはメツセージの中継を行な わない。成るプロセッサが、特定の合意に関して停止したとき、他のプロセッサ またはそれ自身の合意の結果に影響することなく、その通信リンクの全部を切断 することができる。

従来技術では、確認を用いてパ即時ＢＡ”を達成するための方法は、ｔ＋１のフ ェーズ及び０（ｎｔ）メツセージを必要とする。ここで、確認を必要とする幾つ かのプロトコルでは、ｎプロセッサのネットワークにおいて合意を得るためのメ ツセージ数が、係数ｎ及びｔを含む小さな多項式関数で表わされるものと仮定す る。また、確認なしに、これらの結果が更に変更されるものと仮定する。

［発明の説明］ 本発明の目的は、ネットワーク化されたアクティブなプロセッサ間でビザンチン 合意を得るための、計算機で実現可能な方法を提供することである。但し、この ネットワークでは、合意を得るのに必要なフェーズ及びメツセージの数が制限さ れており、またこれらのプロセッサが確認された回報通信メツセージを同期化さ れたフェーズで交換するものとする。それに関連して、本発明の他の目的は、高 々ｔ（ｎ／２）個のプロセッサ／リンクに障害があったとしても、信頼性のある （１＋１．）接続のネットワークに結合されたｎプロセッサ間で、該方法が動作 可能であり、更に、（ｔ＋２）のフェーズで合意を得ることができるようにする ことである。本発明の他の目的は、障害のあるプロセッサがない場合に、該方法 により最小数のフェーズで合意を得ることである。

これらの目的は、下記ステップ（ａ）〜（ｃ）を含む方法によって達成される： （ａ）　偽造不可能な署名を有する値メツセージを、開始プメセツサから、それ 自身を含むすべてのアクティブなプロセッサに同報通信する。

（ｂ）　各受信プロセッサは前記のメツセージを受取り、それ自身の偽造不可能 な署名を付加して、それ自身を含む他のすべてのアクティブなプロセッサに渡す 。

（ｃ）　若しアクティブなプロセッサがどれもみな署名し、全員一致のサポート を得るならば、アクティブな各プロセッサはこのメツセージ値に合意し且つ最初 の２メツセージの通過の終りで停止する。若し、署名数が少なくともｔ＋１であ るが、全員一致でないならば、署名を行ない且つｔ＋１の署名を有するメツセー ジを送付し、全員一致のサポー１−による停止がなされない各プロッセサは、受 取ったメツセージを、繰返し送付し、ｔ＋２メツセージが通過するまで、その署 名をメツセージに付加するステップを続行する。ｔ＋２メツセージが通過した時 点で、若し、少なくともｔ＋１の署名がメツセージに付加されていれば、その値 に対する合意が得られ、そうでない場合には、省略時の値（ｄｅｆａｕｌｔ　ｖ ａ］、ｕｅ）がとられる。

この方法の核心は、それ自身を含むすべてのアクティブなプロセッサに対し、受 取ったメツセージの″署名及び送信″を行なうことである。若し、最初の２つの メツセージの連続通過後、すべてのプロセッサが署名した（全員一致でサポート した）ならば、早期の停止が得られる。そうでない場合は、これらの全員一致の サポートが得られないプロセッサは、ｔ＋２の通過が生じるまで、受取ったメツ セージの署名、送信を繰返し行なうステップを続行する。この方法の利点は、障 害が無いときに早期の停止を生じるだけではなく、メツセージ数を０（ｎｔ）ま で直線的に制限するという点にある。従来技術の他の方に関しては、関与プロセ ッサ数が２ｔ＋１はどに小さいときは、前記のような障害がない場合の早期停止 は許されない。

［図面の簡単な説明］ 第１図はＢＡ呼出しの流れ図、 第２図は回報通信モニタの流れ図、 第３図は同報通信モニタとビザンチン・モニタの間の起時間（すａｋｅｕｐ　ｔ ｉｍｅ）の伝達に関する流れ図、第４図はビザンチン・モニタの流れ図、第５図 は、７プロセツサのネットワークで、その中の３プロセツサに障害があるかもし れない場合の、メツセージ署名、送付のシナリオを示す図である。

最良の実施態様 本発明の方法は、完全かつ確実に接続された同期ネットワークにおいて、すべて のプロセッサが、大部分の時間、正常であると仮定する。この方法は特に、（ａ ）障害のあるプロセッサがない場合、または（ｂ）最大ｔプロセッサまで障害の ある場合、ビザンチン合意を得るのに必要なフェーズ及び確認されたメツセージ の数を最小限にするように定められている。

ビザンチン合意及び同期されたフェーズの情報交換以下の説明は、関係するネッ トワークがアクティブなプロセッサだけから成り、そしてメツセージ・トラフィ ックが複数のプロセッサをアクティブと非アクティブ（ｐａｓｓｉｖｅ）に区分 することによって部分的に管理できるという仮定の下に行なう。ここで、フェー ズ１ではすべての“アクティブ″なプロセッサに対し、ソースＳが偽造不可能な 署名を有する値■を送付する（生じる）ものと仮定しよう。これに関連して、“ フェーズ″を有向グラフで表わす場合、そのノードはプロセッサを表わし、枝は ノードの対の間で伝送されるメッセーすべてのプロセッサがこのメツセージの値 ■を受取り、前記メツセージを処理し、次の停止を決定までの時間差と定義され る。

若し、２番目のプロセッサによって、（Ｖ）ｓが正確に受取られるならば、この プロセッサは、その署名（（ｖ）ｓ）ｐを添付し、フェーズ２の間に、それ自身 を含むすべてのプロセッサに対し、署名されたメツセージを送付する。また、こ のフェーズの間に、（（ｖ）ｓ）ｐが、それ自身を含む各プロセッサｐがら、ｑ 番目のプロセッサによって正確に受取られ、かつフェーズ２の間に、他のメツセ ージが受取られないならば、ｑ番目のプロセッサは、この方法に対する、これ以 上の関与を停止し、その確約された値のリストに値■を加える。フェーズ２で、 署名された値■が、それ自身を含むすべてのプロセッサから正確に受取られると 、″早期停止″が行なわれる。この制約がないと、ｑ番目のプロセッサは、フェ ーズ（ｔ＋２）まで待たなければならない。その後に、値Ｖを確約された値のリ ストに加えることができる。

若し、■以外の値を、ｑ番目のプロセッサが受取ったならば、送信者の障害が推 定され、ｑ番目のプロセッサはその省略時の値をとる。

特殊メツセージ構文 ここで、特殊メツセージ構文を次のように定義する：（１）値Ｖのセットは原文 メツセージのセットに含まれる。

（２）　ラベルは、原子メツセージ、確認またはラベル・シーケンスのどれかで ある。

（３）確認は形式ラベル（ａ）ｐである。ただしｐはプロセッサの名前であり、 ラベルａは１つのラベルである。

（４）　ラベル・シーケンスは、形式ラベルａ、ｂのラベルである。ただし、ラ ベルａ、ｂはラベルである。（ａ、ｂ。

ｃ）ｐは（ａ　）ｐ　（ｂ　）ｐ　（ｃ　）と同じてはないことに注意されたい 。

（５）若し、ａ＝ｂであるが、またはａがＣの一部であり且つｂ＝ｃ　（ｐ）と なるようなラベルＣ及びプロセッサｐがあるか、またはｂ＝ｃ、ｄであり且っａ がＣ若しくはｄの一部であるようなラベルＣ及びｄがあれば、ラベルａはラベル ｂの一部である。

（６）　メツセージ番スコンマのないラベルである。

［低いサポート及び密なメツセージ］ 成るプロセッサが値■について“低いサポート″を有するといわれるのは１次の ようなｔ＋１のプロセッサＰの各々ごとに、当該プロセッサがその唯一の原子メ ツセージ部分として、■を有するｐによって署名された確認を受取る場合である 。任意のフェーズで成るプロセッサに受取られたメツセージが″密″であるとい われるのは、その唯一の原子メツセージ部分が値であり、その他のすべての部分 が確認であり、そして複数のプロセッサの明白な■署名がそのメツセージに現ね れる場合である。ここで説明の便宜上、ｐ＋ｇ＊ｒ及びＳをプロセッサとし、■ を値とし、ｔ＝２とする。そうすると、（（（ｖ　）　ｓ　）ｐ）ｑがフェーズ ４ではなく、フェーズ３で受取られるならば、これは“密”なメツセージである 。これに関連して、シーケンス（（ｖ）ｓ）ｐ　、　（（ｖ’）　ｓ）ｑは■に 対して１′低いサポート”である。なぜなら、これは原子部分Ｖを有するメツセ ージに（ｔ＋１）＝３の明白な署名を含むからである。一般に、フェーズにで受 取った密なメツセージは次の形式％式％） を有する。低いサポートはフェース２でｔメツセージを必要とする。後に、メツ セージ数は、フェーズを後の１つの密なメツセージと同じ位、大きくまたは小さ くなることがある。

密なメツセージと低いサポートの概念は次のように表現することができる： フェーズｑで受取った密なメツセージ＝（値Ｖだけの）原子メツセージ部分十明 白なｑプロセッサからの確認低いサポート＝原子部分の値■だけを有する密なメ ツセージで受取ったｑ＞＝（ｔ＋１）の明白な署名若し、成るプロセッサがフェ ーズ２で停止せず、かっこのプロセッサが値Ｖについて低いサポートを有するな らば、このプロセッサは、（１）その確約された値のリストにＶを加え、そして （２）若し、■が最初の２つの値の１つであるならば、密なメツセージを含む十 分なメツセージを送り、■に対する低いサポートを伝達しなければならない。最 後に、プロセッサは、若し前記以外の場合で停止しないならば、フェーズｔ＋２ の後に停止しなければならない。

本発明の方法は、障害のない場合には、全員一致のサポーシを受取るプロセッサ がフェーズ２で停止することを可能にするという点で最適化されるが、障害があ る場合には、全員一致のサポートを受けないプロセッサは、低いサポートを有す る密なメツセージを、フェーズ２とフェーズｔ＋２の間の期間中待ち、伝達され た値をそれらの確約された値のリストに加え、そして、最初に受取った前記２つ の値に対応するすべてのプロセッサに、密なメツセージを伝送しなければならな い。

相互依存効果と局所クロッキング 複数ノードを有するネットワークは、メツセージ・インターフェースに対の伝送 が存在するような、単一送信者／単一受信者型のネットワークである。既に説明 したように、用語″フェーズは、ノード対間のメツセージ伝送を特徴づけ、かつ 大まかに″時間間隔″′に対応する。相互依存の問題は、時間がノード間におい て正確に同じではないという事実から生じる。詳細については、Ｌａｍｐｏｒｔ 、”Ｔｉｍｅ、Ｃ１ｏｃｋｓ、ａｎｄ　ｔｈｅＯｒｄｅｒｉｎｇ　ｏｆ　Ｅｖｅ ｎｔｓ　ｉｎ　ａ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍ”、２１Ｃｏｓｎｍ ｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ、ｐｐ５５８−５６５．　Ｊｕｌ ｙ　１９７８に記述されている。実際的には、これは、若しシステムが大域（グ ローバル）クロックによって同期化できるなら、用語“フェーズ″は時間間隔と 同義語である。

局　ノードの　打検２ 初めに、本発明の方法は、主記憶、入出力チャネル、制御装置、直接アクセス記 憶装置及びその他のＩ１０装置が、それぞれ接続されている少なくとも１つのＣ ＰＵを含むような計算システムで実行可能である。このようなシステムは米国特 許第３４００３７１号に説明されている。このシステムには、プロセスの実行に 必要な、計算システムまたはオペレーティング・システムの機能のすべてが、資 源として含まれる。

代表的な資源には、主記憶、■／○装置、ＣＰＵ、データ・セット、及び制御プ ログラムまたは処理プログラムが含まれる。更に、このようなシステムは多重プ ログラミング能力を有する。これは、計算システムによる２つ以上のプロセスの 並行処理に適し、ＩＢＭ社から発行された刊行物ＧＣ２８−６６４６（１９７３ 年７月）に説明されているＩＢＭシステム／３６０オポレーテイング・システム によって動作するコンピュータで管理することができる。非同期動作する複数の ＣＰＵから成るネットワークは、米国特許第３９４０７４３号、同第４２２３３ ８０号に記述されている。

本発明の方法を実行する流れ図 ネットワークの各プロセッサ・ノードには、第２図の同報通信モニタ及び第４図 のビザンチン合意モニタが含まれる。

回報通信モニタは、ノードに対する一般的なメツセージ通信プロセッサである。

また、これには、障害がない場合に早期停止、即ちフェーズ２によって停止する ビザンチン合意を決定する機能も含まれる。対照的に、ビザンチン合意モニタは 早期停止以外の合意を決定する。

第１図には、メツセージ構文が示されている。これは、合意プロセスの開始時に ビザンチン合意が呼出される場合は、合意識別子（ＡＩ）、生成時刻（ＴＧ）、 及び値（ｖ）を含むメツセージが生成されることを意味する。（ビザンチン合意 の目的は、プロセッサが初めに伝えたことに関しての合意を確認することである 。そして、メツセージは署名され、他のすべてのアクティブなプロセッサに送信 される。これは、ネットワーク中の他のすべてのアクティブな関与プロセッサが 分っているからである。更に、完壁なものにするために、″署名″として、暗号 化されたメツセージを用いたり、または少なくとも１つの追加ＦＣＣバイトを用 いることができる。

モニタの属性 モニタは、計算資源に結合された手順の集りである。これは、資源を割当てたり 、資源に対する参照を制御する責任を有する。一般しこ、システム中の各資源は 特定のモニタを有する。例えば、記憶モニタ、通信（回報通信）モニタ、または ＣＰＵモニタがある。モニタの各々は、責任を有する資源についての情報を含む テーブルまたは他の構造に対し、排他的なアクセスを有する。モニタに関連する ものに１メール・ボックスｌ′がある。メール・ボックスは、２つ以上の送信プ ロセスからのメツセージを記録できるような受信者に関連したキュー（ｑｕｅｕ ｅ）である。

回報通信モニタ 第２図には、本発明による回報通信モニタの流れ図が示されている。このモニタ は、指定された論理レジスタにイニシアル・タイムを記録する。モニタ手順は、 最初に回報通信メイル・ボックスをアクセスしてこれをロックは、そして繰返し 手順（ループ）を用いて、メール・ボックスを定義する外部ソースからのメツセ ージのキューが使い果たされるまで、各メツセージを順次に処理するように構築 される。この時点で、メール・ボックスは、アンロック（ｕｎＬｏｃｋ）されて おり、新しいメツセージの到着を待つ。各メツセージは、その中に組込まれた回 報通信情報ブロックによって形式化される。このブロックトこは、アイデンティ ティ、生成時刻及び確約値にす対するステータス情報が含まれる。そして、一般 的に認められる幾つかのループがある。最初のループは、誤っているか、または 確認されていないか、または現在時刻（ＣＴ）がメツセージ生成時刻（ＴＧ）を 所定量越えているようなメツセージをすべて廃棄することに関連する。これらの 量は署名数（Ｓ）に等しい時間単位である。メツセージが廃棄されると、回報通 信モニタは゛″休休止状状態戻る。メツセージが確認されたものであって、誤り のないものであり、しかも現在時刻が、生成時刻に所定の増加量を加えたものを 越えていないと仮定すれば、″ベース″′と呼ばれる一定配列の目的リストから 成るデータ構造がアクセスされる。６ベース”は、任意の合意について最初に受 取られるメツセージである。また、メツセージ内の検出されたベースの数をカウ ントするために、走行変数に７！ｌ′ＫＯにセットされる。これらのベースは、 その生成時刻（Ｔ　Ｇ）によって配列されるので、“次のベース”を取出す次の ステップは、リストから次の最大の大きさを有するＴＧを得ることを意味する。

若し、次のベース″がなければ、この最初のプロセスのメツセージは、この一定 配列のリストのデータ構造にベースとして記憶される。

次のベース”を取出すステップで、次のベース″が見つかったものと仮定すると 、処理中のメツセージのアイデンティティをベースのアイデンティティと比較す る必要がある。

若し、両者が等しくないならば、次のベースが取出され、比較される。ベースが なくなるまで、または処理中のメツセージのＡＩ（合意識別子）と同じＡＩを有 するベースが見つかるまで、一定配列のリストは走査される。カウントは一単位 ずつ増加される、即ちに＝に＋１となる。

次に、若し、ベースが見つかったならば、このベースの値がメツセージの値Ｖに 等しいかどうかについて検査が行なわされる。若し、処理中のメツセージの値と 、ベースの値が等しくないならば、Ｋが２よりも小さい場合に、ベースは再走査 される。このリストでは２つのベースだけを維持すればよいことに注意されたい 。これは、現在のメツセージと１つのベースの間の値Ｖの不一致が、送信者の障 害を表わすのに十分であるという判断を前提としている。即ち１、若し、送信者 が同じＡＩの下に異なった値を有する２つのメツセージを送るならば、障害が表 示される。若し、ベースが２回以上ルー一致であるならば、メツセージは廃棄さ れる。

ここで、現在処理されたメツセージ値Ｖがベース値に等しいものと仮定しよう。

若し、該ベースが“Ｃ”または“ｄ”によってマークされれば、それは廃棄され る。これは、これ以上のメツセージ処理またはビザンチン合意を行なわなくても よいことを意味し、合意は既に決定されていることを表わす。

若し、ベースがマークされていなければ、メツセージの署名は、ベースの署名を 更新するのに用いられる。即ち、最初のｔ＋２の署名は完全に記憶され、それら のすべてに適切なビットがマークされる。

若し、現在時刻ＣＴが生成時刻ＴＧラプラス単位を越えていないならば、それは 早期停止時刻以前、即ちフェーズ２の範囲内にある。若し、すべての署名が受取 られているならば、全員一致のサポートが存在する。一方、すべての署名が受取 られていなかったならば、メツセージは廃棄され、回報通信モニタは“休止”状 態に戻る。

ここで早期停止中の処理について考えてみると、ベースを検査して、処理中のメ ツセージ及びベースと同じＡＩを有するもう１つのベースが存在するかどうかを 調べる。若し、存在するなら、ベースは、ｌｌｄ”をマークしてリストに戻され 、プロセッサは省略時の値をとる。さもなければ、ベースは、ＬＬ　Ｃ＋１をマ ークしてリストに戻され、そしてベース値■が合意値左して採用される。この実 現形態では、省略時の値は、送信者が障害を有するという情報を含む。ｔｒ　ｃ Ｉ＋またはｄ′″のどちらかにベースがマークされた後、回報通信モニタは″休 止″状態になる。こうして、早期停止のプロセスが完了する。

次に、データ構造を循環した後、ベースが存在しないものと仮定すると、処理中 のメツセージがベースとして記憶される。若し、そのメツセージの署名数が２つ であれば、回報通信モニタは直ちに″休止″状態に戻る。他方、若し、署名数が ２以外であれば、プロセッサは、そのメツセージに署名し、これを自らを含む、 すべての他のプロセッサに同報通信する。

その後、同報通信モニタは″休止″状態に戻る。

回報通信モニタは、各メツセージを順次に処理し、時間確認または誤り基準に適 合しないメツセージを廃棄してベースを確立する。同報通信モニタが合意を決定 する唯一の時機は早期停止の場合である。同報通信モニタの活動と同期していな いのは、ビザンチン・モニタの活動であり、該モニタは早期停止の合意以外の合 意を決定することを目的とする。回報通信モニタとビザンチン・モニタの間の通 信は、ベースを変更し、それを記憶することによって行なわれる。

第３図を参照するに、そこではメツセージがベースとして記憶され、生成時刻＋ ２単位がビザンチン・モニタのベースをポイントする起動時間のリストに入れら れる。起動時間の最も早い時機にビザンチン・モニタを起動するため、ビザンチ ン・モニタのタイマが必要に応じてリセットされる。

ビザンチン・モニタ 第４図には、ビザンチン・モニタの流れ図が示されている。

このモニタは、２つの配列されたリストに応答する。このモニタは、呼出される と、同報通信メール・ボックスをアクセスし、ロックして、現在時刻を得るとと もに、配列されたリストをロックする。これに関しては、最初のリストは、いく つかのベースのＴＧ＋２またはＴＧ＋ｔ＋２に対応する起動時間の一定配列のリ ストであるが、他のリス１−は、依然としてアクティブなベースの配列されたリ ストである。これらのリストの内容はループによって処理される。］一つのメツ セージがベースとして記憶されるごとに、時刻ＴＯ＋２単位は、ビザンチン・モ ニタの起動時間として記憶される。そのリスト上の該目的に関連するのは、他の リストに記憶されたベースに対するポインタである。オペレーティング・システ ムが起動時間に応答してビザンチン・モニタを呼出す場合、この起動時間はリス トから除去され、そして関連するベースのアクセスが行なわれる。このベースは 、”ｃ”またはＬＬ　ｄ”とマークされているか、または全くマークされていな い。若し、このベースがマークされているならば、ビザンチン・モニタは“休止 ”状態に戻る。若し、ベースが“マークされていない′″ならば、起動時間ＷＴ はベースの生成時刻ＴＧと比較される。若し、ＷＴ＝ＴＯ＋２であり、そして、 ベースに低いサポート（ｔ＋１の署名）があれば、ベースは署名されたとえ、前 に送信されていても、全部のプロセッサに送信される。

いずれにしても、ＴＧ十ｔ＋２の新しい起動時間がリストに載せられる。また、 若し、最も早い″起動時間″に起動する必要があれば、ビザンチン・モニタはそ のタイマをリセットした後に“休止”に戻る。若し、ＷＴ＝ＴＧ＋ｔ＋２ならば 、ベースのメツセージに付随する署名数が検査され、それが十分にサポートされ ているかどうかが確かめられる。即ち、若し、署名数Ｓが（ｔ＋１）よりも小さ ければ、サポートは不十分であるとみなされ、ベースは“ｄ”とマークされる。

プロセッサは合意とは反対の決定をし、省略時の値をとる。そして、ビザンチン ・モニタは“休止”状態に戻る。他方、若し、５＝）（ｔ＋１）ならば、リスト において同じ識別子を有するもう１つのベースの探索が行なわれる。若し、この ベースが見つかれば、それを“ｄ”とマークし、プロセッサは合意に反対の決定 をして、省略時の値をとり、ビザンチン・モニタは″休止″状態に戻る。若し、 同じ識別子を有するもう１つのベースがなければ、ベースはｒｒ　Ｃｕとマーク され、プロセッサはそのベースの合意値Ｖをとる。その後、ビザンチン・モニタ は″休止″状態に戻る。

ビザンチン・モニタの機能は、時刻ＴＧ＋　（ｔ＋２）時間単位で合意を決定す ることである。従って、同報通信モニタは、最初の２フエーズ内で、合意の可否 を決定するが、ビザンチン・モニタは、フェーズｔ＋２で、合意の可否を非同期 的に決定する。この方法によって、障害のない場合には２フエーズ内に、または 、障害数ｔが（ｎ／２）よりも小さい場合にはｔ＋２フェーズ内に、アクティブ なプロセッサはことごとく、合意値または省略時の値に達することが保証される 。

本発明のビザンチン合意方法 本発明の方法は、複数のプロセッサがトランザクションの確約または放棄につい ての合意を、所定の時間内で保証することが望ましい場合、本発明の方法は２フ エーズ確約プロトコルに適用することができる。従って、本方法によるメツセー ジに成るプロセッサが応答し、その応答が、同期された（ｔ＋１）接続のプロセ ッサ・ネットワーク中の更にもう１つのプロセッサに受取られるのに要する時間 の上限τが存在する。（ｔ＋１）接続ネットワークは、ネットワーク中の任意の ２点がｔ＋１の「互いに素Ｊ　（ｄｉｓｊｏｉｎｔ）なる経路を有することを意 味すると定義される。

若し、プロセッサが成る値を予期し、その後、時間τ内にそれを受取らなければ 、このプロセッサは、送信または受信プロセッサのどちらかに障害があると結論 する。本発明の方法を２フエーズ確約に適用するプロトコルは、下記のステップ を必要とする： （ａ）　ノードの１つをトランザクション・コーディネータとして指定し、（そ のクロックの）時刻ｔで、″確約準備（ｐｒｅｐａｒｅ−ｔｏ−ｃｏｍｍｉｔ） ”メツセージを、すべての関与プロセッサに同報通信し、 （ｂ）　各プロセッサは、″準備された（ｐｒｅｐａｒｅｄ）　”レコードを記 録して″イエス″と投票するか、または放棄して″ノー″と投票することにより 、″確約準備″に応答し、（ｃ）　若し１時刻ｔ＋２でまでに、トランザクショ ン・コーディネータが、すべてのネットワーク関与者から″イエス″を受取って いるならば、ビザンチン合意プロトコルを用いて事象１′確約″を同報通信する か、または前記ビザンチン・プロトコルを用いて″放棄″″を同報通信し、（ｄ ）　若し、そのクロックの時刻ｔ＋６τまでに、プロセッサは、′確約”するこ とを決定していなければ、″放棄″すること髪決定する、即ち省略時の値を採用 する。

敢瀝ＬＪｂＢ（社）乙ナリオ 第５図には、ＣＰＵネットワークのグラフのノード間の有向性の枝に沿ったメツ セージ伝達パターンが示されている。

この場合、ｎ＝７のＣＰＵがあり、そのうち、ｔ＝３のｃｐＵに障害がある。黒 丸のノードは障害のあるプロセッサを表わし、白丸のノートは正しいプロセッサ を表わす。第１のフェーズで、Ａは値Ｖを含み、Ａが署名したメツセージを、時 物ＴＧにおいてＢにだけ（不正な様式で）送る。第２のフェーズで、Ｂは、送ら れたメツセージに正しく署名し、それをすべてのノードに送る。第３のフェーズ で、Ｇは（不正な様式で）そのメツセージに署名し、それをＦにだけ送る。第４ のフェーズで、Ｆは同じように（不正な様式で）そのメツセージに署名し、それ をＥにだけ送る。最後の第５のフェーズで、Ｅは正しく、そのメツセージに署名 し、それをすべてのノードに送る。面白いことに、メツセージは、それが少なく ともｔ＋１の署名を必要とするという理由がら、第４７エーズまでは十分にサポ ートされず、第５フエーズになって始めて十分にサポートされる。メツセージが 署名され、ノードＧ及びＦから送られるためには、両ノードは、たぶん共謀して 動作するものとみられる。Ｅにだけ送られたメツセージに（ｔ＋１）＝４の署名 をノードが添付するのは、第４フエーズにおいてだけである。若し、下が実際に 、たった１つのノードの代りにすべてのノードにメツセージを送っていたならば 、フェーズＴＧ＋４で合意が決定されたであろう。

複数のフェーズは、不連続に生じているように説明されてはいるが、入子関係で もよいことはいうまでもない。更に。

若し、ネットワークが完全に接続され、各ノードが他のあらゆるノードに連結さ れ、かつ少なくとも巨＋１）接続であるならば、本発明は、変更なしに、ｔ（ｎ ／２）の範囲まで、検出されないノード／リンク障害に耐えるであろう。

有利な点として、本発明は、ベースがすべてのアクディプなプロセッサの署名を 含んでいる場合、その時点（第２）ニーズ）で即時停止を要求する。早期停止し ない場合、プロセッサは少なくともｔ＋１の署名が得られる。ｔ＋２のフェーズ まで待って始めて、確約された値のリストに値Ｖを加えることができる。若し、 ■以外の値を受取ったならば、このプロセッサは、送信者に障害があったものと 結論づけ、省略時の値を採用する。障害の証拠は即時停止を満足させないことで あると考えられる。即ち、若し、２フエーズの処理の後、プロセッサが停止して いなければ、ノードの１つのどこかに障害がある。

ＦＩＧ、　Ｉ ＦＩＧ、　３ ＦＩＧ、　２ Ｇ・　ｏＢ ＦＩｏ、　５ 国際調査報告

Claims (3)

【特許請求の範囲】
1. （１）　信頼性のある（ｔ＋１）接続のネットワークにおいてｎプロセッサ間の 合意を得る方法であって、誤゛りがない場合は早期停止を保証し、ｔ（ｎ／２） の誤りがある場合は最後的には停止し、 開始プロセッサの偽造不可能な署名を有する値メツセージを、該開始プロセッサ からそれ自身を含むアクティブなすへてのプロセッサに同報通信するステップと 、アクティブな各受信プロセッサが、このようなメツセージにそれ自身の偽造不 可能な署名を添付して、それ自身を含む他のすべてのアクティブなプロセッサに 送るステップと、 アクティブな各プロセッサは、あらゆるアクティブなプロセッサが署名している 場合は、最初の２つのメツセージ通過の終りに、メツセージ値に合意して停止し 、署名数が少なくともｔ＋１であるが、全員一致ではない場合は、そのメツセー ジに署名して、ｔ＋１の署名とともに送り、そして全員一致のサポートによる停 止をされなかった各プロセッサは、（ｔ＋２）のメツセージ通過が済むまで、繰 返し、受取ったメツセージを送り且つそれにその署名を添付するステップを続け 、（ｔ＋２）のメツセージ通過の時点で、少なくとも”（−”ｔ　＋　１　）の 署名がメツセージに添付されている場合は、その値に合意し、そうでなければ、 省略時の値をとるステップと を含むことを特徴とするプロセッサ間の合意を得る方法。
2. （２）請求の範囲第（１）項において、生成された各メツセージが、合意識別子 （ＡＩ）、生成時刻（ＴＧ）　、メツセージ値（Ｖ）、及び少なくとも１つの添 付された署名を含むことを特徴とするプロセッサ間の合意を得る方法。
3. （３）請求の範囲第（１）項において、各プロセッサが少なくとも回報通信モニ タ及びビザンチン合意モニタを含むことを出願人　インターナショナル・ビジネ ス・マシーンズ・コーポレーション 代理人　弁理士　頓　宮　孝　− （外１名）