(57)【特許請求の範囲】
【請求項１】
ある数（Ｎ）のノードによって維持されるブロックチェーン上で実装されるコンピュータ実装合意方法であって、前記ノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個の前記ノードがバックアップ・ノードとして機能し、前記方法が前記一次ノードによって実行され、前記方法が、
事前準備メッセージを前記バックアップ・ノードの少なくとも一部にマルチキャストすることと、
（Ｑ−１）個以上の準備メッセージを前記バックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することであって、前記準備メッセージが、対応する前記バックアップ・ノードによる前記事前準備メッセージの受容をそれぞれ示し、Ｑ（定数）が、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆが、（Ｎ−１）／３を最も近い整数に切り下げた値である、取得することと、
前記事前準備メッセージおよび前記（Ｑ−１）個以上の準備メッセージを格納することと、
コミット・メッセージを前記バックアップ・ノードの少なくとも一部にマルチキャストすることであって、前記コミット・メッセージが、前記一次ノードが前記（Ｑ−１）個以上の準備メッセージに同意していることを示す、マルチキャストすることと、
前記一次ノードおよび前記バックアップ・ノードのうちのＱ個以上のノードから、対応する前記ノードが前記対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得することとを含んでいる、コンピュータ実装合意方法。
【請求項２】
前記事前準備メッセージを前記バックアップ・ノードの少なくとも一部にマルチキャストする前に、前記方法が、１つまたは複数のトランザクション要求を、１つまたは複数のクライアントまたは前記バックアップ・ノードのうちの１つまたは複数のうちの少なくとも１つから取得することをさらに含んでいる、請求項１に記載の方法。
【請求項３】
前記事前準備メッセージが、前記１つまたは複数のトランザクション要求に対応する１つまたは複数のトランザクションの順序を含んでおり、
前記コミット・メッセージが、前記コミット・メッセージを送信した前記対応するノードが前記順序に同意していることを示す、請求項２に記載の方法。
【請求項４】
前記順序に従って、前記１つまたは複数のトランザクションを、前記一次ノードによって維持される前記ブロックチェーンのローカル・コピーに詰め込むことをさらに含んでいる、請求項３に記載の方法。
【請求項５】
前記Ｑ個以上のコミット・メッセージが、前記マルチキャストされたコミット・メッセージを含んでいる、請求項１から４のいずれか一項に記載の方法。
【請求項６】
前記事前準備メッセージおよび前記（Ｑ−１）個以上の準備メッセージを格納することが、
前記事前準備メッセージおよび前記（Ｑ−１）個以上の準備メッセージのみを格納することを含んでいる、請求項１から５のいずれか一項に記載の方法。
【請求項７】
前記コミット・メッセージをマルチキャストした後に、
システムの再起動を実行することと、
格納された前記事前準備メッセージおよび格納された前記（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含んでいる、請求項１から６のいずれか一項に記載の方法。
【請求項８】
前記事前準備メッセージおよび前記（Ｑ−１）個以上の準備メッセージを格納した後で、前記コミット・メッセージをマルチキャストする前に、
システムの再起動を実行することと、
格納された前記事前準備メッセージおよび格納された前記（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含んでいる、請求項１から６のいずれか一項に記載の方法。
【請求項９】
前記システムの再起動を実行することが、
ビュー変更をトリガーせずに前記システムの再起動を実行することを含んでいる、請求項８に記載の方法。
【請求項１０】
ブロックチェーンを維持するための一次ノードとして機能している合意システムであって、
１つまたは複数のプロセッサと、
前記１つまたは複数のプロセッサに結合されており、請求項１から９のいずれか一項に記載の方法を実行するために前記１つまたは複数のプロセッサによって実行可能な命令が格納されている、１つまたは複数のコンピュータ可読メモリとを備えている、合意システム。
【請求項１１】
ブロックチェーンを維持するための一次ノードとして機能している合意装置であって、請求項１から９のいずれか一項に記載の方法を実行するために複数のモジュールを備えている、合意装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、一般に、合意システムおよび合意方法のための方法およびデバイスに関連しており、特に、プラクティカル・ビザンチン・フォールト・トレランス（ＰＢＦＴ：Ｐｒａｃｔｉｃａｌ  Ｂｙｚａｎｔｉｎｅ  Ｆａｕｌｔ  Ｔｏｌｅｒａｎｃｅ）合意システムおよび合意方法に関連している。
【背景技術】
【０００２】
プラクティカル・ビザンチン・フォールト・トレランス（ＰＢＦＴ）は、ブロックチェーン・システムなどの分散システムにおいて実装できる合意メカニズムの一種である。ＰＢＦＴ合意メカニズムは、システムの特定のノードが（例えば、不十分なネットワーク接続またはその他の原因によって）故障しているか、または（例えば、悪意を持って活動しながら）誤った情報を他のピアに伝搬しているにもかかわらず、分散システムが安全性および活性を含む十分な合意に達することができるようにする。そのようなメカニズムの目的は、システムの正しい機能に対する、およびシステム内の機能しているノード（例えば、故障していない善意のノード）によって達せられた合意に対する、機能していないノードの影響を軽減することによって、破滅的なシステム故障を防ぐことである。
【０００３】
ＰＢＦＴ合意メカニズムは、独立したノード故障および特定の独立したノードによって伝搬されて操作されるメッセージが存在することを仮定することによって、ビザンチン故障（例えば、機能していないノード）を許容するプラクティカル・ビザンチン状態マシンの複製を提供することに重点を置く。このＰＢＦＴ合意メカニズムでは、例えば、ブロックチェーン・システム内のすべてのノードが、ある順序で順序付けられ、１つのノードが一次ノード（リーダー・ノードまたはマスターノードとしても知られている）になり、他のノードがバックアップ・ノードと呼ばれる（フォロワー・ノードとしても知られている）。システム内のすべてのノードは互いに通信し、目標は、すべての善意のノードが、システムの状態に関して同意／合意に達することである。
【０００４】
例えば、ＰＢＦＴ合意メカニズムが機能するために、特定の脆弱性の期間内で、ブロックチェーン・システム内の機能していないノードの数が、同時に、システム内のノードの総数の３分の１以上になることができない、ということが仮定される。この方法は、多くてもＦ個のノードが同時に機能していないノードである限り、活性および安全性の両方を効果的に提供する。言い換えると、一部の実装では、ＰＢＦＴ合意メカニズムによって許容できる機能していないノードの数Ｆは、（Ｎ−１）／３を最も近い整数に切り下げた数に等しく、Ｎはシステム内のノードの総数を指定する。一部の実装では、ＰＢＦＴ合意メカニズムを実装するブロックチェーン・システムは、合計で少なくとも３Ｆ＋１個のノードが存在する場合、最大でＦ個のビザンチン故障を処理することができる。
【０００５】
ＰＢＦＴ合意メカニズムは、通常、正常動作プロトコル（３段階プロトコルとしても知られている）およびビュー変更プロトコルを含み、正常動作プロトコルは、メカニズムの安全性を保証するために提供され、一方、ビュー変更プロトコルは、メカニズムの活性を保証するために提供される。正常段階プロトコルは、主に３つのフェーズ（すなわち、事前準備フェーズ、準備フェーズ、およびコミット・フェーズ）を順番に含んでいる。すべてのフェーズはメッセージ駆動型であり、すなわち、現在のフェーズにおいて十分な数のメッセージを取得することによって、プロトコル内の次のフェーズがトリガーされる。正常動作プロトコルでは、プロセス全体が、各フェーズで連続的に受信された十分な数のメッセージに応じて、大きく前進する。ビュー変更プロトコルにおいてさえ、プロセスは、正常動作プロトコルでの準備メッセージに基づいて前進する。したがって、ＰＢＦＴ合意メカニズムが、機能するために、合意メッセージに大きく依存しているということを理解することができる。１つまたは複数のノードが機能しなくなった場合（例えば、ダウンタイムおよび再起動が発生した場合）、メモリに格納されたメッセージが失われ、合意プロセス全体に影響を与え、不整合さえ招くであろう。
【発明の概要】
【０００６】
本明細書のさまざまな実施形態は、合意システムのダウンタイムの回復のためのシステム、方法、および非一時的コンピュータ可読媒体を含むが、これらに限定されない。
【０００７】
一実施形態によれば、コンピュータ実装合意方法が、ある数（Ｎ）のノードによって維持されるブロックチェーン上で実装され、ノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、この方法が一次ノードによって実行される。この方法は、事前準備メッセージをバックアップ・ノードの少なくとも一部にマルチキャストすることと、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することであって、これらの準備メッセージが、対応するバックアップ・ノードによる事前準備メッセージの受容をそれぞれ示し、Ｑ（定数）が、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆが（Ｎ−１）／３を最も近い整数に切り下げた値である、取得することと、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することと、コミット・メッセージを、バックアップ・ノードの少なくとも一部にマルチキャストすることであって、このコミット・メッセージが、一次ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す、マルチキャストすることと、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得することとを含む。一実施形態では、Ｑ個以上のコミット・メッセージが、マルチキャストされたコミット・メッセージを含む。
【０００８】
一部の実施形態では、事前準備メッセージをバックアップ・ノードの少なくとも一部にマルチキャストする前に、この方法は、１つまたは複数のトランザクション要求を、１つまたは複数のクライアントまたはバックアップ・ノードのうちの１つまたは複数のうちの少なくとも１つから取得することをさらに含む。
【０００９】
他の実施形態では、事前準備メッセージが、１つまたは複数のトランザクション要求に対応する１つまたは複数のトランザクションの順序を含み、コミット・メッセージが、コミット・メッセージを送信した対応するノードがこの順序に同意していることを示す。
【００１０】
さらに他の実施形態では、この方法は、この順序に従って、１つまたは複数のトランザクションを、一次ノードによって維持されるブロックチェーンのローカル・コピーに詰め込むことをさらに含む。
【００１１】
さらに他の実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することが、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージのみを格納することを含む。
【００１２】
一部の実施形態では、コミット・メッセージをマルチキャストした後に、この方法は、システムの再起動を実行することと、格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含む。
【００１３】
他の実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納した後で、コミット・メッセージをマルチキャストする前に、この方法は、システムの再起動を実行することと、格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含む。
【００１４】
さらに他の実施形態では、コミット・メッセージをそれぞれマルチキャストした後に、バックアップ・ノードのうちの（Ｑ−１）個以上のうちの最大でＦ個が機能しておらず、システムの再起動を実行しない。
【００１５】
さらに他の実施形態では、最大でＮ個のノードすべてにクラッシュが発生し、Ｎ個のノードのうちの少なくともＱ個が、システムの再起動を実行し、対応する格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージをそれぞれ読み込む。
【００１６】
一部の実施形態では、システムの再起動を実行することが、ビュー変更をトリガーせずにシステムの再起動を実行することを含む。
【００１７】
他の実施形態では、ブロックチェーンを維持するための一次ノードとして機能している合意システムが、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合されており、前述の実施形態のいずれかの方法を実行するために１つまたは複数のプロセッサによって実行可能な命令が格納されている、１つまたは複数のコンピュータ可読メモリとを備える。
【００１８】
さらに他の実施形態では、ブロックチェーンを維持するための一次ノードとして機能している合意装置が、前述の実施形態のいずれかの方法を実行するために複数のモジュールを備える。
【００１９】
さらに別の実施形態によれば、合意システムは、ブロックチェーンを維持するためである。ある数（Ｎ）のノードがブロックチェーンを維持し、Ｎ個のノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、この合意システムが、一次ノードとして機能し、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、１つまたは複数のプロセッサによって実行可能な命令を使用して構成された１つまたは複数の非一時的コンピュータ可読メモリとを備え、それらの命令が、システムに、事前準備メッセージをバックアップ・ノードのうちの少なくとも一部にマルチキャストすることと、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することとであって、それらの準備メッセージが、対応するバックアップ・ノードによる事前準備メッセージの受容をそれぞれ示し、Ｑ（定数）が、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆが（Ｎ−１）／３を最も近い整数に切り下げた値である、取得することと、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することと、コミット・メッセージを、バックアップ・ノードの少なくとも一部にマルチキャストすることであって、このコミット・メッセージが、一次ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す、マルチキャストすることと、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得することとを含んでいる動作を実行させる。
【００２０】
さらに別の実施形態によれば、非一時的コンピュータ可読記憶媒体はブロックチェーンを維持するためである。ある数（Ｎ）のノードがブロックチェーンを維持し、Ｎ個のノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、この記憶媒体が、一次ノードに関連付けられ、１つまたは複数のプロセッサによって実行可能な命令を使用して構成され、それらの命令が、１つまたは複数のプロセッサに、事前準備メッセージをバックアップ・ノードのうちの少なくとも一部にマルチキャストすることと、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することとであって、それらの準備メッセージが、対応するバックアップ・ノードによる事前準備メッセージの受容をそれぞれ示し、Ｑ（定数）が、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆが（Ｎ−１）／３を最も近い整数に切り下げた値である、取得することと、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することと、コミット・メッセージを、バックアップ・ノードの少なくとも一部にマルチキャストすることであって、このコミット・メッセージが、一次ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す、マルチキャストすることと、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得することとを含んでいる動作を実行させる。
【００２１】
さらに別の実施形態によれば、合意装置は、ブロックチェーンを維持するためである。ある数（Ｎ）のノードがブロックチェーンを維持し、Ｎ個のノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、この合意装置が、一次ノードとして機能し、事前準備メッセージをバックアップ・ノードの少なくとも一部にマルチキャストするための第１のマルチキャスト・モジュールと、事前準備メッセージをバックアップ・ノードのうちの少なくとも一部にマルチキャストすることと、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得するための第１の取得モジュールであって、それらの準備メッセージが、対応するバックアップ・ノードによる事前準備メッセージの受容をそれぞれ示し、Ｑ（定数）が、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆが（Ｎ−１）／３を最も近い整数に切り下げた値である、第１の取得モジュールと、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納するための格納モジュールと、コミット・メッセージを、バックアップ・ノードの少なくとも一部にマルチキャストするための第２のマルチキャスト・モジュールであって、このコミット・メッセージが、一次ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す、第２のマルチキャスト・モジュールと、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得するための第２の取得モジュールとを備える。
【００２２】
本明細書において開示される実施形態は、１つまたは複数の技術的効果を有する。一部の実施形態では、方法およびシステムは、ノードのうちの１つまたは複数にシステム・クラッシュが発生した後に、ＰＢＦＴ合意システムのさまざまなノードが正常動作を再開できることを保証できる。他の実施形態では、合意検証の各回で、合意システムのノード（一次またはバックアップ）が、中断（例えば、システム全体のクラッシュ）が発生したときに、一貫性のない合意結果およびブロックチェーンの分岐を引き起こさずに合意検証を再開できるように、事前準備メッセージおよび十分な数の準備メッセージを格納してよい。さらに他の実施形態では、クラッシュ後に、ノードが、システムの再起動を実行し、格納されたメッセージを読み込んで、正常機能を復元してよい。格納されたメッセージを読み込むことによって、システムのダウンタイムの回復を促進できる。さらに他の実施形態では、（正常動作プロトコルの準備フェーズで）準備メッセージを取得した後で、（正常動作プロトコルのコミット・フェーズで）コミット・メッセージをマルチキャストする前に、事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージが格納されてよい。したがって、ダウンタイムの回復を実現するために、事前準備メッセージおよび（Ｑ−１）個の準備メッセージより多くのメッセージを格納する必要がないため、格納のためにコミットする必要のあるシステム・リソースが少なくなる。一部の実施形態では、一貫性のない合意結果およびブロックチェーンの分岐を伴わずに、最大でＦ個の悪意のあるノードまたは故障しているノードを許容できる。すなわち、最大でＦ個のノードが信頼できない場合でも、ＰＢＦＴ合意システムの定数によって決定された合意検証は信頼できる。
【００２３】
本明細書で開示されたシステム、方法、および非一時的コンピュータ可読媒体のこれらおよびその他の特徴だけでなく、構造の関連する要素および部分の組合せの動作および機能の方法ならびに製造の経済性が、添付の図面を参照して以下の説明および添付の特許請求の範囲を検討したときに、さらに明らかになってよく、それらすべてが、類似する参照番号がさまざまな図内の対応する部分を指定している本明細書の一部を形成する。しかし、それらの図面が単に例示および説明を目的としており、制限として意図されていないということが、明確に理解されるべきである。
【図面の簡単な説明】
【００２４】
【図１】さまざまな実施形態に従ってネットワークを示す図である。
【図２Ａ】ＰＢＦＴの正常動作プロトコルを示す図である。
【図２Ｂ】１つの故障しているレプリカを含むＰＢＦＴの正常動作プロトコルを示す図である。
【図２Ｃ】ＰＢＦＴの正常動作プロトコルおよびビュー変更プロトコルを示す図である。
【図３Ａ】ＰＢＦＴの正常動作プロトコルのステップのフローチャートを示す図である。
【図３Ｂ】ＰＢＦＴのビュー変更プロトコルのステップのフローチャートを示す図である。
【図３Ｃ】さまざまな実施形態に従って、合意システムの正常動作プロトコルのステップのフローチャートを示す図である。
【図４Ａ】さまざまな実施形態に従って、合意ステップのフローチャートを示す図である。
【図４Ｂ】さまざまな実施形態に従って、合意ステップのフローチャートを示す図である。
【図４Ｃ】さまざまな実施形態に従って、合意ステップのフローチャートを示す図である。
【図４Ｄ】さまざまな実施形態に従って、合意ステップのフローチャートを示す図である。
【図５Ａ】さまざまな実施形態に従って、合意方法のフローチャートを示す図である。
【図５Ｂ】さまざまな実施形態に従って、合意方法のフローチャートを示す図である。
【図６Ａ】さまざまな実施形態に従って、合意システムのブロック図を示す図である。
【図６Ｂ】さまざまな実施形態に従って、合意システムのブロック図を示す図である。
【図７】本明細書に記載された実施形態のいずれかが実装されてよいコンピュータ・システムのブロック図を示している。
【発明を実施するための形態】
【００２５】
本明細書において開示される実施形態は、ＰＢＦＴのダウンタイム回復のシステム、方法、および非一時的コンピュータ可読媒体を含むが、これらに限定されない。さまざまな実施形態では、ブロックチェーン・システムなどの分散ネットワーク・システムが複数のノードを含んでよい。ブロックチェーン・システムは、ＰＢＦＴ合意メカニズムを実装してよく、複数のノードのうちの１つが一次ノードとして指定され、他のノードがバックアップ・ノードとして指定される。一部の実施形態によれば、ブロックチェーン・システムにおいて実行される合意検証の各回で、合意メッセージのすべてではなく、一部のみが格納される。例えば、正常動作プロトコルの間の事前準備メッセージおよび十分な数の準備メッセージが格納される。一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個の準備メッセージのみが格納される。Ｑは、定数を表し、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値になり、Ｆは、（Ｎ−１）／３を最も近い整数に切り下げた値になる。このようにして、合意検証プロセスを中断（例えば、システム全体のクラッシュ）から再開して、効果的かつ効率的に進めることができ、システムのストレージ消費を少なくし、一貫性のない合意結果およびブロックチェーンの分岐を引き起こさない。ＰＢＦＴと同様に、開示されるシステム、方法、および非一時的コンピュータ可読媒体は、ＳｅｃｕｒｅＲｉｎｇ、Ｂｙｚａｎｔｉｎｅ  Ｐａｘｏｓ、Ｑ／Ｕ、ＨＱ、Ｚｙｚｚｖｙｖａ、ＡＢｓＴＲＡＣＴｓ、ＲＢＦＴ、Ａｄａｐｔ、Ｔａｎｇａｒｏａ、ＣｈｅａｐＢＦＴ、ＭｉｎＢＦＴ、ＦａｓｔＢＦＴなどの、その他の合意プロトコルに適用できる。ＰＢＦＴのさまざまな態様を、Ｍ．  Ｃａｓｔｒｏ、Ｂ．  Ｌｉｓｋｏｖ、「Ｐｒａｃｔｉｃａｌ  Ｂｙｚａｎｔｉｎｅ  Ｆａｕｌｔ  Ｔｏｌｅｒａｎｃｅ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｔｈｉｒｄ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ（１９９９年２月）で参照することができ、この文献は参照によって全体として本明細書に組み込まれている。
【００２６】
図１は、さまざまな実施形態に従ってネットワーク１２０を示している。以下で提示されるコンポーネントは、例示的であるよう意図されている。図に示されているように、ネットワーク１２０は、ブロックチェーン・システムなどの分散ネットワーク・システム１１２を含んでよい。ネットワーク・システム１１２は、サーバ、コンピュータ、携帯電話などの１つまたは複数のコンピューティング・デバイスに実装された１つまたは複数のノード（例えば、ノード０、ノード１、ノード２、ノード３、ノード４…ノードｉ、…など）を備えてよい。ネットワーク・システム１１２は、ネットワーク１２０または追加システムの他のデバイスにアクセスするために、適切なソフトウェア（例えば、合意プログラム）および／またはハードウェア（例えば、有線、無線接続）と共にインストールされてよい。各ノードは、１つまたは複数のプロセッサおよび１つまたは複数のプロセッサに結合された１つまたは複数のメモリを含んでよい。例えば、１つまたは複数のメモリは、非一時的かつコンピュータ可読であり、１つまたは複数のプロセッサに、本明細書に記載された動作を実行させるように、１つまたは複数のプロセッサによって実行可能な命令を使用して構成される。この図ではノードが単一のコンポーネントとして示されているが、それらのノードを単一のデバイスまたは一緒に結合された複数のデバイスとして実装できるということが、理解されるであろう。一般に、ノードは、互いに通信することができてよく、ネットワーク・システム１１２の外部の他のデバイスと通信することができてよい。例えば、１つまたは複数の有線ネットワークまたは無線ネットワーク（例えば、インターネット）を介して、データを伝達することができる。
【００２７】
さまざまな実施形態では、ネットワーク・システム１１２が、複数のノードを備えているブロックチェーン・システムとして実装されてよい。例えば図１に示されているように、ブロックチェーン・システムは、複数のブロックチェーン・ノード（例えば、ノード０、ノード１、ノード２、ノード３、ノード４、…ノードｉなど）を備えている。複数のノードは、あるブロックチェーン・ノードが別のブロックチェーン・ノードと通信するネットワーク（例えば、ピアツーピア・ネットワーク）を形成してよい。図に示されているブロックチェーン・ノードの順序および数は、説明を簡単にするための単なる例である。ブロックチェーン・ノードは、サーバ、コンピュータなどにおいて実装されてよい。各ブロックチェーン・ノードは、ＴＣＰ／ＩＰなどのさまざまなタイプの通信方法を介して一緒に結合された１つまたは複数の物理ハードウェア・デバイスまたは仮想デバイスに対応してよい。分類に応じて、ブロックチェーン・ノードは、満杯になったノード、Ｇｅｔｈノード、合意ノードなどを含んでよい。
【００２８】
さまざまな実施形態では、ブロックチェーン・システムが、ノードＡおよびノードＢ（例えば、軽量ノード）などの他のシステムおよびデバイスと情報をやりとりしてよい。この情報のやりとりは、例えば、要求を受信し、その要求の実行結果を返す目的で、データの送信および受信を含んでよい。１つの例では、ユーザＡが、ブロックチェーンを経由してユーザＢとトランザクションを行いたいことがある。このトランザクションは、ユーザＡの口座にある資産をユーザＢの口座に移すことを含んでいることがある。ユーザＡおよびユーザＢは、トランザクション用の適切なブロックチェーン・ソフトウェア（例えば、仮想通貨ウォレット）がインストールされたデバイスのノードＡおよびＢをそれぞれ使用することができる。ノードＡは、ノード０との通信を介してブロックチェーンにアクセスすることができ、ノードＢは、ノード１との通信を介してブロックチェーンにアクセスすることができる。例えば、ノードＡは、ノード０を介してトランザクション要求をブロックチェーンにサブミットすることができ、ノードＢは、ノード１を介してスマート・コントラクト実行要求をブロックチェーンにサブミットすることができる。ブロックチェーンの外で、ノードＡおよびノードＢが通信の他のチャネル（例えば、ノード０および１を通過しない標準的なインターネット通信）を有してよい。
【００２９】
ブロックチェーン・ノードはそれぞれ、メモリを備えるか、またはメモリに結合されてよい。一部の実施形態では、このメモリは、プール・データベースを格納してよい。プール・データベースは、分散方式で、複数のブロックチェーン・ノードによってアクセス可能であってよい。例えば、プール・データベースは、ブロックチェーン・ノードのメモリにそれぞれ格納されてよい。プール・データベースは、ユーザによって操作されるノードＡおよびＢなどの、１つまたは複数のユーザ・デバイスによってサブミットされた複数のトランザクションを格納してよい。
【００３０】
ブロックチェーン・ノードは、合意を通じて、トランザクションをブロックチェーンと呼ばれる分散型台帳に記録する、ネットワーク（例えば、Ｐ２Ｐネットワーク）を形成する。Ｐ２Ｐネットワークの参加者は、ブロックチェーンを維持するノードと呼ばれることがある。ブロックチェーンのＰＳＰネットワークでは、各ノードが合意検証に参加し、ブロックチェーンの完全な台帳のコピーを格納する。すべてのノードは、ブロックチェーン合意アルゴリズムによってトランザクションのバッチを確認し、すべてのノードが一貫性のある確認結果、したがって、ブロックチェーンの一貫性のあるコピーを持つことを保証する。
【００３１】
ブロックチェーン合意アルゴリズムの１つは、プラクティカル・ビザンチン・フォールト・トレランス（ＰＢＦＴ）である。ビザンチン・フォールト・トレランスは、一般的なビザンチン問題に由来する。Ｐ２Ｐネットワーク・システムの場合、機能していないノードの数が特定の制限内である限り、システムは適切に機能し続けることができる。そのようなシステムは、ビザンチン・フォールト・トレラント・システムと呼ばれる。ＰＢＦＴは、ビザンチン・フォールト・トレランスのネットワーク能力の最適化の一例である。ＰＢＦＴは、サーバをコピーし、サーバのコピーとのクライアントの情報のやりとりを同期させることによって、ビザンチン状態マシンをネットワークに提供する。
【００３２】
ＰＢＦＴの動作の中心は、ブロックチェーンに記録された情報の一貫性のある全体的視点の維持であり、それによって、ユーザが分散方式で互いに情報をやりとりできるようにするための骨格を形成する。ＰＢＦＴ合意メカニズムの安全性は、ブロックチェーン・システムにとって極めて重要である。合意モデルの２つの重要な特性は、（１）安全性または一貫性：すべての善意のノードが同じ有効な出力を生成すること、および（２）活性：すべての善意のノードが、中間段階で止まることなく、合意において最終的にある値を生成することである。セキュリティで保護された堅牢なＰＢＦＴ合意メカニズムは、ノードの故障、ネットワークの分割、メッセージの遅延、不規則な順序でのメッセージ配信、メッセージの破損などの、多種多様なビザンチン動作を許容し、システム内の機能していないノードの数が限定されている限り、複数のノードで合意に達する必要がある。その目的で、ＰＢＦＴモデルは、以下で詳細に説明される、正常動作／一貫性プロトコルおよびビュー変更プロトコルという、２つの相互排他的なプロトコルのうちのいずれか１つの下で機能する。本明細書では、機能していないとは、故障していることおよび／または悪意があることを意味し、機能しているとは、故障しておらず、善意であることを意味する。可能性のある故障している動作および／または悪意のある動作としては、メッセージを配信できないこと、メッセージ配信の遅延、不規則な順序でのメッセージ配信、ビザンチン故障（プロトコルに違反して、任意のメッセージを、さまざまなノードに配信する）などが挙げられる。
【００３３】
一部の実施形態では、プラクティカル・ビザンチン・フォールト・トレランス（ＰＢＦＴ）メカニズムを実装するブロックチェーン・システムが、合計でＮ個のノードを含んでよく、Ｎ個のノードのうちの１つが一次ノードとして機能し、Ｎ個のノードのうちの他のノードがバックアップ・ノードとして機能する。ビュー変更プロトコルを通じて、別のノードが新しい一次ノードになるように選ばれてよいため、一次ノードの指定は特定のノードに固定されなくてよい。例えば、一次ノードは、モジュロ演算によって選ばれてよく、モジュロ演算では、最低のシリアル番号（ビュー番号の剰余）を有する機能しているノードが、新しい一次ノードになる。現在のビューおよびノードの総数Ｎが、一次ノードのｉｄ＝（ビュー＋１）ｍｏｄ  Ｎを決定してよい。ＰＢＦＴでは、新しい一次ノードが選ばれるたびに、ビューが変更される。例えば、各ビュー変更と共に、ビューが０から単調に増加する。すなわち、一次ノードにおける変更と共に、ビューが変化してよい。
【００３４】
一部の実施形態では、一次ノードがビューｖで機能しており、正常動作プロトコルが実行される。正常動作の場合、一次ノードおよび／またはバックアップ・ノードが、未検証のトランザクションに関連付けられた要求を１つまたは複数のクライアントから受信してよい。例えば、ノードＡがクライアントとして要求を一次ノードおよび／またはバックアップ・ノードにサブミットしてよい。この要求は、未検証のトランザクション（例えば、合意検証によってブロックチェーン内の新しいブロックに追加されるトランザクション）を含んでよい。未検証のトランザクションの例としては、ブロックチェーンベースの金融トランザクション、スマート・コントラクトのデプロイメント、または実行トランザクションなどが挙げられる。一次ノードおよびバックアップ・ノードは、トランザクションの何らかの予備的検証を実行してもしなくてもよい。要求を受信するバックアップ・ノードは、受信された要求を一次ノードに転送してよい。一次ノードで、未検証のトランザクションを含む要求が特定のレベルに達したか、またはその他の方法でトリガー条件を満たした後に、一次ノードは、１回の合意検証を開始し、未検証のトランザクションに対して検証結果を提案してよい。バックアップ・ノードは、この合意に応答し、提案を確認し、合意に達してよい。ノードの要件は、それらのノードが決定論的であり、同じ状態で開始することである。最終結果は、すべての善意のノードが、レコードの順序に関して合意に達し、それを受け入れるか、または拒否する。合意検証が実行された後に、トランザクションが、ブロックチェーンの新しいブロックに詰め込まれ、ノードによって維持されるローカル・ブロックチェーンのコピーに追加されてよい。また、最初に要求を送信したクライアント（例えば、ノードＡ）に通知される。
【００３５】
前述したように、安全性を維持するために、ＰＢＦＴ合意メカニズムは、正常動作プロトコルの３つのフェーズ（事前準備フェーズ、準備フェーズ、およびコミット・フェーズ）を主に含んでいる。図２Ａ〜図２Ｃを参照すると、ＰＢＦＴ合意メカニズムを実装するブロックチェーン・システムの例が、４つのレプリカ（レプリカ０、レプリカ１、レプリカ２、およびレプリカ３）を含んでいる（レプリカは、ノードの別の用語である）。番号０〜３は、新しい一次ノードを決定するために使用できる、レプリカのシリアル番号である。レプリカ０は、一次ノード０に対応してよく、レプリカ１、２、および３は、バックアップ・ノード１、２、および３に対応してよい。これらのレプリカは、例えば、前述したネットワーク・システム１１２の対応するノードにおいて実装されてよい。正常動作プロトコルが、機能していないノードが存在しない図２Ａに示されており、別の正常動作プロトコルが、レプリカ３が機能していないノードである図２Ｂに示されている。両方の状況では、正常動作プロトコルが、事前準備フェーズ、準備フェーズ、およびコミット・フェーズに加えて、要求フェーズおよび応答フェーズという２つのフェーズをさらに含んでよい。図２Ａに対応するステップのフローチャートが、図３Ａに示されている。
【００３６】
図２Ａ、２Ｂ、および３Ａを参照すると、クライアントが要求（メッセージ）を、要求を提唱する責任を負う一次ノード（レプリカ０）にサブミットするときに、正常動作プロトコルが要求フェーズで開始している。要求は、クライアント、要求動作（例えば、合意検証のための１つまたは複数のトランザクション）、および要求のタイムスタンプの情報を含んでよい。クライアント（クライアント・ノードとも呼ばれる）は、例えば、前述したノードＡに実装されてよい。ノードＡは、軽量ノード（例えば、携帯電話に実装されたノード）であってよい。追加的または代替的に、クライアントは要求をバックアップ・ノードにサブミットしてよく、バックアップ・ノードは、事前準備フェーズの前に、この要求を一次ノードに転送する。要求を一次ノードが受信するのか、バックアップ・ノードが受信するのかにかかわらず、対応するノードが、受信された要求をネットワーク内の他のノードにマルチキャストしてよい。したがって、いずれにせよ一次ノードは、クライアントによって合意ネットワークにサブミットされた保留中の要求を最終的に取得することができる（ステップ３１１）。
【００３７】
それに応じて、一次ノードは、リーダーのように機能し、要求に関連付けられた１つまたは複数のトランザクションを検証するようにバックアップ・ノードを誘導する。一次ノードは、ビュー内の要求の実行を順序付ける責任を負う。事前準備フェーズでは、一次ノードが複数の要求を取得し、取得された要求の妥当性を確認し、要求ごとにシーケンス番号を提案してよい。したがって、各要求は、増加するシーケンス番号を割り当てられ、このようにして順番に並べられてよい。さらに、事前準備メッセージは、ブロック高さを含んでよい。ブロック高さは、ブロックチェーンの現在の高さに基づいてよい。例えば、ブロックチェーンが１０００個のブロックを現在含んでいる場合、ブロック高さは、１０００個のブロックがブロックチェーン内にすでに存在していることを示す１０００であってよく、または要求に関連付けられた１つまたは複数のトランザクションがブロックチェーンの１００１番目のブロック（他のノードによってまだ検証されていない）に詰め込まれるように提案されていることを示す１００１であってよい。一次ノードは、クライアントの要求を、対応するシーケンス番号および／またはブロック高さと共に転送してよい。例えば、一次ノードは、要求を取得した後に、シーケンス番号を割り当てることによって対応するトランザクションを実行するために、要求をある順序で配置し、リストに格納してよい。一次ノードは、事前準備メッセージを、ブロックチェーン・システム内のすべてのバックアップ・ノード（レプリカ１〜レプリカ３）に送信してよい（ステップ３１２）。図２Ａに示されているように、一次ノードが、事前準備メッセージ内で、または事前準備メッセージと共に、このリストをバックアップ・ノードにマルチキャストしてよい。図２Ｂに示されているように、バックアップ・ノード（レプリカ３）が機能しておらず、一次ノードがそれを認識していない場合でも、一次ノードは、依然として事前準備メッセージを送信することができる（ステップ３１３）。各バックアップ・ノードは、事前準備メッセージが有効である限り、それを受け入れる。事前準備メッセージは、ビュー番号、シーケンス番号、一次ノードによる署名、ダイジェスト（ｄ）、その他のメタデータなどを含んでよく、これらを使用して、事前準備メッセージの妥当性を決定することができる。
【００３８】
準備フェーズでは、バックアップ・ノードが事前準備メッセージを受け入れる場合、バックアップ・ノードは、次に、一次ノードを含むブロックチェーン・システム内の他のノードに、準備メッセージをマルチキャストする（ステップ３１４）。準備メッセージをマルチキャストするということは、送信側ノードが事前準備メッセージに同意するということを示している。各準備メッセージは、有効である限り、受信側ノードによって受け入れられる。準備メッセージの妥当性は、同様に、ビュー番号、シーケンス番号、対応するバックアップ・ノードの署名、ダイジェスト（ｄ）、その他のメタデータなどに基づいて決定することができる。バックアップ・ノードが有効な事前準備メッセージを一次ノードから受信し、（Ｑ−１）個以上の個別の有効な一貫性のある準備メッセージを他のノードから取得した場合（ステップ３１５）、バックアップ・ノードが準備され、定数（Ｑ）は、すべてのレプリカ／ノードのデータの一貫性およびフォールト・トレランス要件を保証するために必要なレプリカ／ノードの数を指定する。一部の実施形態では、ＰＢＦＴシステムを実装するブロックチェーン・システムは、少なくとも３Ｆ＋１個のレプリカ／ノードを含み、Ｆは、ＰＢＦＴが安全性および活性を伴って機能するために許容できるビザンチン故障／機能していないノードの数を指定し、定数（Ｑ）は２Ｆ＋１に等しい。この場合、事前準備メッセージおよび少なくとも２Ｆ個のメッセージを格納することができる。２Ｆ個の準備メッセージは、マルチキャストされた準備メッセージを含んでよい。ここで、事前準備メッセージを一次ノードの準備メッセージと同等のものとして扱うことができるため（ただし、一次ノード自体は、準備メッセージを送信しなくてよい）、ＱではなくＱ−１（この場合は２Ｆ）個の準備メッセージが必要である。事前準備メッセージをもう１つの準備メッセージとして数える場合、すべてのノードのうちの少なくともＱ（例えば、２Ｆ＋１）個が事前準備メッセージを受け入れたことを示す、少なくともＱ（例えば、２Ｆ＋１）個の個別の有効な準備メッセージが存在し、そのうちの最大でＦ個の機能していないノードを許容できる。したがって、事前準備から準備までのフェーズは、要求がビューｖで実行される場合に、その要求のシーケンス番号で実行されるということに、少なくともＦ＋１個の機能しているノード（最大でＦ個の機能していないノードを考慮した２Ｆ＋１個の準備されたノード）が同意しているということを保証する。準備フェーズは、ビュー内の各要求のフォールト・トレラントな一貫性のある順序付けを保証する。
【００３９】
一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個の準備メッセージの受信後に、バックアップ・ノードは順序を検証し、その検証結果を、一次ノードによって事前準備メッセージに書き込まれている提案された検証結果と比較してよい。順序を検証するための複数の手法が存在してよい。例えば、提案された検証結果は、ダイジェスト（ｄ）に書き込まれている提案されたマークル・パトリシア・トライのルートを含んでよい。バックアップ・ノードは、順序に従って、要求に関連付けられたトランザクションを配置し、マークル・パトリシア・トライのルートを計算し、提案されたマークル・パトリシア・トライのルートと比較してよい。この計算は、ブロックチェーン内の既存のブロックのノードのハッシュなどの、特定の既存の情報を必要としてもよい。この比較は、バックアップ・ノードによって計算されたダイジェスト（Ｄ（ｍ））を生成する。ダイジェスト（Ｄ（ｍ））がダイジェスト（ｄ）と一致する場合、検証が成功する。検証が行われた後に、バックアップ・ノードは、要求の順序付け（例えば、要求に関連付けられたトランザクションをブロックチェーンの新しいブロックに詰め込むための順序）に同意してよい。同様に、バックアップ・ノードは、受信したコミット・メッセージ（コミット・フェーズに関して下で説明される）が同じダイジェストＤ（ｍ）を含んでいるかどうかを検証し、他のノードも要求の順序付けに同意しているかどうかを決定してよい。準備されたノードがＱ（例えば、２Ｆ＋１）個のコミット・メッセージを取得し、より低いシーケンス番号を有するすべての要求の実行が完了している場合、このノードは要求を実行してよい。
【００４０】
一部の実施形態では、事前準備メッセージは、要求の実行に関連する新しいブロックまたはその他の情報（例えば、要求に関連付けられたトランザクション）のダイジェスト（ｄ）を含んでよい。ダイジェスト（ｄ）（例えば、ハッシュ値）は、ハッシュ・アルゴリズムをトランザクションなどのデータに適用することの数値結果であってよい。バックアップ・ノードは、ダイジェスト（ｄ）を確認するためのトランザクションを実行してよい。複数の要求の場合、バックアップ・ノードは、順序（すなわち、要求のシーケンス番号）に従って要求を実行し、ダイジェストＤ（ｍ）を取得してよい。Ｄ（ｍ）およびｄが一致する場合、バックアップ・ノードは、バックアップ・ノードが一次ノードの妥当性確認結果に同意することを示すコミット・メッセージ（コミット・フェーズに関して下で説明される）をマルチキャストする。特定のシーケンス番号の保留中の要求に関して、準備されたノードがＱ（例えば、２Ｆ＋１）個のコミット・メッセージを取得し、より低いシーケンス番号を有するすべての要求の実行が完了している場合、このノードは要求を実行してよい。
【００４１】
コミット・フェーズにおいて、ノードが準備された場合、このノードは、コミット・メッセージを他のノードにマルチキャストしてよい（ステップ３１６）。このノードは、コミット・メッセージを他のノードから受信してよい。各ノードは、コミット・メッセージが有効である限り、それを受け入れる。コミット・メッセージは、ビュー番号、シーケンス番号、署名、ダイジェスト、その他のメタデータなどを含んでよく、これらを使用して、メッセージの妥当性を決定することができる。一部の実施形態では、ノードが少なくともＱ個の個別の有効な一貫性のあるコミット・メッセージを取得した場合、それは、定数のノードがコミットし（すなわち、少なくとも（Ｑ−Ｆ）個の善意のノードが準備され）、合意が達せられたということを示す（ステップ３１７）。少なくともＱ個の有効なコミット・メッセージは、マルチキャストされたコミット・メッセージを含んでよい。したがって、準備からコミットまでのフェーズは、要求がそのシーケンス番号で、ビューｖ内で最終的に実行されるということに、少なくとも（Ｑ−Ｆ）個の機能しているノード（最大でＦ個の機能していないノードを考慮したＱ個のコミット・メッセージ）が同意しているということを保証する。各ノードは異なるビューでコミットすることがあるため（例えば、一部のノードが新しいビューにすでに移行しており、他の一部のノードが前のビューに留まっている場合）、受信されたコミット・メッセージは、異なるビュー内で実行されたコミットに対応することがある。機能しているノードが各要求のシーケンス番号に同意するため、コミット・フェーズは、複数のビューにわたる各要求のフォールト・トレラントな一貫性のある順序付けを保証する。
【００４２】
一部の実施形態では、ノードが少なくともＱ個の個別の有効な一貫性のあるコミット・メッセージを取得した場合、ノードは、対応する要求を実行してよい。例えば、Ｑ個のコミット・メッセージが取得されたということは、新しいブロックの合意検証が実行されたということを意味する。したがって、ノードは、新しいブロックを、ブロックチェーンのローカルに維持されるコピーに詰め込んでよい。そうでない場合、バックアップ・ノードは、ビュー変更プロトコルを直接トリガーしてよい。
【００４３】
応答フェーズにおいて、要求の実行後に、ノードが応答メッセージをクライアントに直接送信する。ブロックチェーンに詰め込まれたトランザクションの場合、応答メッセージがブロックチェーン内のトランザクションのアドレスを含んでよい。最大でＦ個の故障が許容されるため、クライアントは、結果を受け入れる前に、異なるノードからの有効な署名、ならびに同じ要求のタイムスタンプおよび同じ実行結果を含んでいる（Ｑ−Ｆ）個の応答を待つ。図２Ａおよび図２Ｂに示されているＰＢＦＴネットワーク・システムの場合、合計で４つのノードが存在するため、最大で１つ（Ｆ＝１）の機能していないノードを許容することができる。したがって図２Ｂでは、レプリカ３が機能していなくても、依然として合意に達することができる。
【００４４】
一次ノードが要求をマルチキャストせずに一定の時間が経過した場合、活性を維持するために、ビュー変更プロトコルにおいて一次ノードを交換することができる。例えば、バックアップ・ノードはタイマーを維持してよい。バックアップ・ノードは、要求を受信し、タイマーがまだ実行されていない場合、タイマーを開始する。バックアップ・ノードは、要求を実行するのを待たなくなった（すなわち、要求が実行される）ときにタイマーを停止するが、その時点で１つまたは複数の他の要求の実行を待っている場合、タイマーを再開する。タイマーが終了した場合、バックアップ・ノードは、一次ノードが機能していないということを決定してよい。したがってバックアップ・ノードは、ビュー変更メッセージを他のノードにマルチキャストしてよい。別の例の場合、バックアップ・ノードは、一次ノードが悪意を持っているということを決定してよい。したがってバックアップ・ノードは、ビュー変更メッセージをマルチキャストしてよい。別の例の場合、クライアントは、クライアントが要求を一次ノードに送信した後に、応答を受信せずに多すぎる時間が経過したかどうかを、タイマーを使用して決定できる。このタイマーが終了した場合、クライアントはその要求をすべてのノードに送信する。ノードがこの要求についてすでに知っている場合、再ブロードキャストは無視される。ノードがこの要求について知らない場合、ノードはタイマーを開始する。ノードのタイマーのタイムアウトの時点で、ノードは、一次ノードが故障しているという疑いに基づいて、ビュー変更メッセージを他のバックアップ・ノードにマルチキャストすることによって、ビュー変更プロセスを開始する（ステップ３２１）。送信側ノードが故障していないことを他のノードが知るように、ビュー変更メッセージは、システム状態を（以前の正常動作中のそのノード自身の準備メッセージを含んでいるアーカイブされたメッセージの形態で）含む。
【００４５】
圧倒的多数の機能しているノードが、一次ノードが機能していないかどうかを決定して、その一次ノードを除去し、直列の次の一次ノードを置き換えに使用することができる。一次ノードが故障しているということを十分な数のノードが断定したときに、ビュー変更が発生する。図２Ｃの一部はビュー変更プロトコルを示しており、ビュー変更プロトコルに対応するステップのフローチャートが、図３Ｂに示されている。図２Ｃおよび図３Ｂを参照すると、ビュー変更フェーズにおいて、現在のビューがｖである場合、ノードｐ＝（ｖ＋１）ｍｏｄ  Ｎが、新しい一次ノードになるために、Ｑ個の有効なビュー変更メッセージを取得するのを待ち、ｐはレプリカ／ノードのシリアル番号であり、ｖはビュー番号であり、Ｎはレプリカ／ノードの総数である（ステップ３２２）。Ｑ個のビュー変更メッセージは、マルチキャストされたビュー変更メッセージを含んでよい。前のビューがｖであるため、ビュー変更メッセージはそれぞれ、新しいビューｖ＋１を含んでよい。新しい一次ノードｐがＱ個のビュー変更メッセージを取得した後に、一次ノードｐは新しいビュー・メッセージをマルチキャストする（ステップ３２３）。このメッセージは、受信されたすべての有効なビュー変更メッセージ、および一次ノードの故障に起因してまだ完了していないことがあるすべての要求のセットを含む。新しい一次ノードは、最後のチェックポイントを決定し、特に、故障していないノードの最後の状態に追い付くことを保証してよく、これは、新しいビュー内で以前の要求（例えば、準備されてコミットされたが、実行されていない要求）を再コミットすることを含んでよい。ビュー変更が発生している間、新しい要求は受け入れられない。ノードが、Ｑ個のビュー変更メッセージを含んでいる有効な新しいビュー・メッセージを受信した後に、このノードは、ビューｖ＋１に移行し、未完了の要求のセットを処理する。その後、正常動作プロトコルが続行し、各ノードが、最後の安定したチェックポイントのシーケンス番号と準備メッセージ内の最高の番号の間の要求をやり直すが、要求を再実行することは避ける。バックアップ・ノードは、新しい一次ノードのタイマーを設定してよい（ステップ３２４）。
【００４６】
図３Ｃは、図３Ｂに類似しているが、格納フェーズが追加されている点が異なる。すなわち、ステップ３３１〜３３７はそれぞれステップ３１１〜３１７に類似しているが、ステップ３９９がステップ３３５と３３６の間で追加として実行される点が異なる。一部の実施形態では、図３Ｃに示されているように、準備フェーズ（バックアップ・ノードまたは一次ノードが（Ｑ−１）個の準備メッセージを取得する）とコミット・フェーズ（バックアップ・ノードまたは一次ノードがコミット・メッセージをマルチキャストする）の間で、格納フェーズにおいて事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージが格納されてよい。以下では、図４Ａ〜図６Ｂを参照して、さらに詳細が説明される。
【００４７】
図４Ａは、本明細書のさまざまな実施形態に従って一次ノードによって実行される合意ステップ４１０ａのフローチャートを示している。図４Ｂは、本明細書のさまざまな実施形態に従ってバックアップ・ノードによって実行される合意ステップ４１０ｂのフローチャートを示している。これら２つの図は、少なくとも３Ｆ＋１個のノードが含まれているＰＢＦＴ合意メカニズムを実装するブロックチェーン・システムを示している。ただし、本明細書はこれに限定されない。ブロックチェーン・システムは、有効な合意プロセスを維持し、安全性および活性の要件を満たすために、定数のノードがシステム内に存在する限り、「少なくとも３Ｆ＋１」以外の数のノードを含んでよい。一部の実施形態では、合意ステップ４１０ａは、図４Ａに示されているようにビューｖ内の一次ノードによって実行され、合意ステップ４１０ｂは、図４Ｂに示されているようにビューｖ内のバックアップ・ノードによって実行され、ビュー変更のトリガーは発生しない。このビューは、Ｎ個のノードのうちのどれが一次ノードと見なされるかを示しており、Ｎはネットワーク・システム内のノードの数を指定する。ステップ４１０ａおよび４１０ｂは、図１のシステム１００の１つまたは複数のコンポーネント（例えば、前述したノード０、ノード１、ノード２、…、またはノードｉ、または類似するデバイス、あるいはノードのいずれかおよび追加のデバイス（例えば、ノードＡ）の組合せ）によってそれぞれ実装されてよい。この図では、ノードＡ（例えば、前述した軽量ノード）はクライアントであり、ノード０〜ノード３はネットワーク・システム１１２内のノードである。現在のビューｖ内で、ノード０が一次ノードとして機能し、ノード１〜３がバックアップ・ノードとして機能する。ステップ４１０ａおよび４１０ｂは、さまざまなハードウェアマシンおよび／またはソフトウェアを備えている合意システムまたはデバイス（例えば、コンピュータ、サーバ）によってそれぞれ実装されてよい。例えば、合意システムまたはデバイスは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、システムまたはデバイス（例えば、プロセッサ）にステップ４１０ａまたは４１０ｂを実行させるように１つまたは複数のプロセッサによって実行可能な命令を使用して構成された、１つまたは複数の非一時的コンピュータ可読記憶媒体（例えば、１つまたは複数のメモリ）とを備えてよい。以下で提示される動作は、例示的であるよう意図されている。実装に応じて、この動作は、さまざまな順序で、または並列に実行される、追加のステップ、より少ないステップ、または代替のステップを含んでよい。
【００４８】
図４Ａおよび４Ｂの縦方向に、さまざまなステップが「要求」フェーズ、「事前準備」フェーズ、「準備」フェーズ、「格納」フェーズ、「コミット」フェーズ、および「応答」フェーズに対応しており、これらのフェーズは、図１〜図３Ｃを参照する前述の説明で参照されてよい。さまざまなフェーズの配置は、明確にするために示されており、厳密な順序の要件を有していなくてよい。例えば格納フェーズは、準備フェーズが終了する前に開始してよく、かつ／またはコミット・フェーズが開始した後に終了してよい。図４Ａに示されているように、例えば、下で説明されているような中断（例えば、ダウンタイムの状況）が発生した場合に、任意選択的なステップ４９８が、ステップ４１５とステップ４１７の間で追加として実行されてよい。一次ノードおよびバックアップ・ノードは、ＰＢＦＴ合意メカニズムにおいて定義されるノードであってよい。
【００４９】
図４Ａのステップ４１０ａおよび図４Ｂのステップ４１０ｂは、１つまたは複数の要求の１回の合意検証に適用されてよい。例えば、１回の合意検証は、１つまたは複数のトランザクション要求を処理してよい。合意検証に成功した場合、対応するトランザクションがブロックチェーンの新しいブロックに詰め込まれる。以下の説明では、特に示されない限り、特定のステップが組み合わせられるとき、図４Ａまたは図４Ｂのいずれかを参照する。ステップ４１１ａおよび４１２ａは図４Ａのみに現れ、ステップ４１１ｂおよび４１２ｂは図４Ｂのみに現れる。ステップ４１３、４１４、４１５、４１６、および４１７は、図４Ａおよび図４Ｂの両方に示されている。
【００５０】
図４Ａに示されているように、ステップ４１１ａで、要求フェーズにおいて一次ノードが要求をクライアントから取得してよい。例えば、要求は、一次ノード（ノード０）によってクライアント（ノードＡ）から直接取得されるか、または破線で示されているように、要求を一次ノードに転送したバックアップ・ノード（例えば、バックアップ・ノード１、２、または３）から取得されてよい。一部の実施形態では、要求は、合意検証に関する（スマート・コントラクトを含むか、または含まない）１つまたは複数のトランザクションを伴ってよい。合意検証は、正常動作プロトコルの実行中に実行されてよい。代替として、要求は他の動作に対応してよい。
【００５１】
ステップ４１２ａで、事前準備フェーズにおいて、一次ノード（ノード０）が、バックアップ・ノード（ノード１、２、および３）への要求と一緒に事前準備メッセージをマルチキャストする。一部の実施形態では、複数の要求を取得した後に、一次ノードは、事前準備メッセージおよび複数の要求をバックアップ・ノードの各々にマルチキャストしてよい。事前準備メッセージは、要求の順序（例えば、要求に関連付けられたトランザクションの順序）を含んでよい。
【００５２】
正常動作プロトコルにおいてバックアップ・ノード（例えば、ノード１、２、または３）によって実行されるステップを示している図４Ｂに示されているように、バックアップ・ノードが、ステップ４１１ｂで、事前準備フェーズにおいて要求と一緒に事前準備メッセージを取得する。この要求は、合意検証に関連するトランザクションを含んでよい。一部の実施形態では、事前準備メッセージおよび要求が一次ノードから取得されてよい。一部の実施形態では、事前準備メッセージが一次ノードから取得されてよく、要求がクライアント、一次ノード、および／または任意のその他のバックアップ・ノードから取得されてよい。一次ノードが機能していない場合、ビュー変更プロトコルがトリガーされてよい。
【００５３】
ステップ４１２ｂで、準備フェーズにおいて、事前準備メッセージが有効である場合、バックアップ・ノードが準備メッセージをシステム内の他のノードにマルチキャストする。
【００５４】
ステップ４１３で、準備フェーズにおいて、一次ノードまたはバックアップ・ノードが他のノードから送信された準備メッセージを受信する。（Ｑ−１）個の有効な準備メッセージを取得することは、合意プロセスが次のコミット・フェーズに移行する前に満たされるべき条件であってよい。図４Ａおよび４Ｂに示された実施形態では、例えば、（Ｑ−１）は２Ｆであり、２Ｆ個以上の準備メッセージが必要である。２Ｆ個以上の準備メッセージは、バックアップ・ノードまたは一次ノード自体の準備メッセージを含んでよい。バックアップ・ノードの場合、２Ｆ個以上の準備メッセージは、ステップ４１２ｂでの準備メッセージ（すなわち、ステップ４１２ｂでのバックアップ・ノード自体による準備メッセージのマルチキャスト）を含んでよい。
【００５５】
ステップ４１４で、一次ノードまたはバックアップ・ノードが、事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージを格納してよい。例えば、３Ｆ個の準備メッセージがノードによって取得された場合、事前準備メッセージおよび２Ｆ〜３Ｆ（２Ｆおよび３Ｆを含む）個の準備メッセージがノードによって格納されてよい。一部の実施形態では、事前準備メッセージおよびＱ−１個の準備メッセージのみが格納される。一部の実施形態では、事前準備メッセージおよび２Ｆ個の準備メッセージのみが格納される。例えば、３Ｆ個の準備メッセージが取得された場合、システム全体が中断（例えば、システム・クラッシュ）から回復した後に、多すぎるシステムの記憶リソースを消費することなく有効な合意プロセスが効果的かつ効率的に再開されて前進するために格納される必要がある合意メッセージの最小量は、事前準備メッセージおよび２Ｆ個の準備メッセージであってよい。一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することが、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージのみを格納することを含んでおり、つまり、事前準備メッセージおよび少なくとも２Ｆ個の準備メッセージ以外のメッセージが格納されないことを意味する。例えば、合意検証の各回で、コミット・メッセージは格納されない。同じことが、複数回の合意検証が実行される場合に適用されてよい。
【００５６】
ステップ４１３およびステップ４１４は、順序通りに、同時に、または別の方式で実行されてよい。一部の実施形態では、（Ｑ−１）個以上の準備メッセージが取得された場合にのみ、事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージの格納が実行されてよい。他の実施形態では、各メッセージが取得された後にいつでも、事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージの格納が実行されてよい。
【００５７】
一部の実施形態では、中断からのシステムの回復後に、格納されたメッセージが取り出し可能である限り、事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージが、さまざまな方式で格納されてよい。例えば、事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージは、格納がシステム・クラッシュおよび再起動による影響を受けないことを保証する永続的記憶装置に格納されてよい。
【００５８】
一部の実施形態では、システムの動作に中断（例えば、システム・クラッシュに起因するダウンタイム）が生じていない場合、ステップ４１５が実行されてよい。一実施形態では、少なくとも事前準備メッセージおよび（Ｑ−１）個の準備メッセージが格納された後に、ステップ４１５でコミット・フェーズが実行される。ステップ４１５では、コミット・フェーズにおいて、一次ノードおよびバックアップ・ノードがそれぞれ、コミット・メッセージを他のノードにマルチキャストする。各ノードは、他のノードによってマルチキャストされたコミット・メッセージを受信してもよい。ステップ４１６で、一次ノードまたはバックアップ・ノードが、少なくとも定数（Ｑ）（この場合は２Ｆ＋１）のコミット・メッセージを取得してよい。バックアップ・ノードまたは一次ノードの場合、図４Ａおよび４Ｂに示されているように、Ｑ個のコミット・メッセージが、ステップ４１５でのコミット・メッセージ（すなわち、ステップ４１５でバックアップ・ノードまたは一次ノード自体によってマルチキャストされたコミット・メッセージ）を含んでよい。ステップ４１７で、あるノードが、十分な数のノード（例えば、Ｑ個のノード）がコミットしたことを確認した場合、このノードは、順序に従って要求を実行し、応答メッセージを介してクライアント（ノードＡ）に通知してよい。
【００５９】
一部の実施形態では、コミット・メッセージがマルチキャストされた後に、システムの動作に中断（例えば、システム・クラッシュに起因するダウンタイム）が生じている場合、ステップ４１５の後のステップ４１７の前に、任意選択的なステップ４９８が実行されてよい。ステップ４９８で、一次ノードまたはバックアップ・ノードがシステムの再起動を実行し、ノードがステップ４１４で一度格納した事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージを読み込んでよい。一部の実施形態では、システムは、中断の後に、自主的に、または選択の余地なく、再起動してよい。その後、残りのステップ４１６〜４１７またはステップ４１７が続いてよい。
【００６０】
一部の実施形態では、コミット・メッセージがマルチキャストされる前に、システムの動作に中断（例えば、システム・クラッシュに起因するダウンタイム）が生じている場合、ステップ４１４の後のステップ４１５の前に、任意選択的なステップ４９９が実行されてよい。ステップ４９９で、一次ノードまたはバックアップ・ノードが、ノードが格納フェーズ（ステップ４１４）で一度格納した事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージを読み込んでよい。一部の実施形態では、システムは、中断の後に、自主的に、または選択の余地なく、再起動してよい。ステップ４９９が実行された場合、特定の状況下で（例えば、機能していないノードが一次ノードであり、一次ノードが、タイムアウト期間内にその機能する状態を再開していない場合）、ビュー変更プロトコルがトリガーされてよい。しかし、タイムアウト条件が満たされない場合（例えば、タイムアウト条件をトリガーする前にステップ４９９が完了した場合）、図４Ａおよび４Ｂに示されているように、ビュー変更プロトコルがトリガーされなくてよい。したがって、機能していない一次ノードが、タイムアウト条件を回避できるほど十分に素早くその機能する状態を再開した場合、ビュー変更プロトコルがトリガーされなくてよく、プロトコルにおいてステップ４１５〜４１７が続いてよい。タイムアウト条件が満たされた場合（例えば、タイムアウト条件がトリガーされる前にステップ４９９が完了しない場合）、図４Ｃおよび図４Ｄを参照して下で説明されているように、ビュー変更プロトコルがトリガーされてよい。
【００６１】
図４Ｃは、本明細書のさまざまな実施形態に従って、ビューｖ＋１内の新しい一次ノードになるビューｖ内のバックアップ・ノードによる合意ステップ４２０ａのフローチャートを示している。図４Ｄは、本明細書のさまざまな実施形態に従って、ビューｖ＋１内でバックアップ・ノードのままであるビューｖ内のバックアップ・ノードによる合意ステップ４２０ｂのフローチャートを示している。ステップ４２０ａおよび４２０ｂは、図１のシステム１００の１つまたは複数のコンポーネント（例えば、前述したノード０、ノード１、ノード２、…、またはノードｉ、または類似するデバイス、あるいはノードのいずれかおよび追加のデバイス（例えば、ノードＡ）の組合せ）によって実装されてよい。この図では、ノードＡ（例えば、前述した軽量ノード）はクライアントであり、ノード０〜ノード３はブロックチェーン・ノードである。図４Ａおよび図４Ｂにおいて説明されているように、ビューｖ内ではノード０が一次ノードとして機能していたが、図４Ｃおよび図４Ｄのビューｖ＋１の場合、ノード１が新しい一次ノードになり、ノード２〜３はバックアップ・ノードのままである。ステップ４２０ａおよび４２０ｂは、分散ネットワーク・システム（例えば、ブロックチェーン・システム）の１つまたは複数のノードによってそれぞれ実装されてよい。ステップ４２０ａおよび４２０ｂは、さまざまなハードウェアマシンおよび／またはソフトウェアを備えている合意システムまたはデバイス（例えば、コンピュータ、サーバ）によってそれぞれ実装されてよい。例えば、合意システムまたはデバイスは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、システムまたはデバイス（例えば、プロセッサ）にステップ４２０ａおよび４２０ｂを実行させるように１つまたは複数のプロセッサによって実行可能な命令を使用して構成された、１つまたは複数の非一時的コンピュータ可読記憶媒体（例えば、１つまたは複数のメモリ）とを備えてよい。以下で提示される動作は、例示的であるよう意図されている。実装に応じて、この動作は、さまざまな順序で、または並列に実行される、追加のステップ、より少ないステップ、または代替のステップを含んでよい。
【００６２】
前述したように、図４Ｂのステップ４１４の後のステップ４１５の前にビュー変更がトリガーされた場合、図４Ｃおよび図４Ｄに示されているステップが実行される。簡潔にするために、ステップ４９９の前のステップ（図４Ｂに示されているステップ４１４までのステップ）は、図４Ｃおよび図４Ｄにおいて再現されない。
【００６３】
一部の実施形態では、図４Ｃおよび図４Ｄに示されている合意ステップ４２０ａおよび４２０ｂは、ビュー変更をトリガーする状況に対応してよい。ビューｖ内の一次ノード（例えば、ノード０）は、故障するか、またはその他の方法で機能しなくなることがある。図４Ｃの場合、ビューｖ＋１内の新しい一次ノードになるビューｖ内のようなバックアップ・ノード（例えば、ノード１）は、ステップ４９９、４２３、４２４ａ、４２５ａ、４２６ａ、４２５、４２６、および４２７を実行してよい。ビューｖ＋１内でバックアップ・ノードのままであるビューｖ内のバックアップ・ノード（例えば、ノード２または３）は、ステップ４９９、４２３、４２４ｂ、４２５ｂ、４２６ｂ、４２５、４２６、および４２７を実行してよい。２つの図の縦方向に、さまざまなステップが「ビュー変更」フェーズ、「新しいビュー」フェーズ、「準備」フェーズ、「コミット」フェーズ、および「応答」フェーズに対応しており、これらのフェーズは、図１〜図３Ｃを参照する前述の説明で参照されてよい。さまざまなフェーズの配置は、明確にするために示されており、厳密な順序の要件を有していなくてよい。一次ノードおよびバックアップ・ノードは、ＰＢＦＴ合意メカニズムにおいて定義されるノードであってよい。以下の説明では、特定のステップが組み合わせられるとき、図４Ｃまたは図４Ｄのいずれかを参照する。
【００６４】
一部の実施形態では、ステップ４９９に示されているように、まだビューｖ内にある一次ノード（ノード０）およびバックアップ・ノード（ノード１、２、および／または３）の一部が、ステップ４１４でそれぞれ格納された事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージをそれぞれ読み込んでよい。メッセージが永続的記憶装置から格納された場合、ここでそれらのメッセージが永続的記憶装置から読み込まれてよい。正常動作の中断（例えば、システム・クラッシュに起因するダウンタイム）に応答して、システムの再起動が実行されてよい。
【００６５】
一実施形態では、一次ノードが機能していないという疑いがあるとき、ステップ４２３に示されているように、バックアップ・ノード（例えば、ノード１、２、また３）がビュー変更メッセージをマルチキャストしてよく、このビュー変更メッセージは、読み込まれた事前準備メッセージおよび読み込まれた少なくとも（Ｑ−１）個の準備メッセージを含んでよい。ビュー変更プロトコルにおいて、バックアップ・ノードのうちの１つが新しい一次ノードになってよく、残りのノードがバックアップ・ノードのままであってよい。新しい一次ノードの選択は、上で説明されている。例えば、図に示されているように、ノード１が、新しい一次ノードになるように選ばれてよく、ノード２および３がバックアップ・ノードのままであってよい。
【００６６】
ステップ４２４ａで、バックアップ・ノードが、対応するノードがビュー変更メッセージに同意していることをそれぞれ示す少なくともＱ個のビュー変更メッセージを他のノードから取得した場合、新しい一次ノード（例えば、ノード１）が選択されてよい。少なくともＱ個のビュー変更メッセージが、バックアップ・ノード自体によってマルチキャストされたビュー変更メッセージを含んでよい。ステップ４２５ａで、新しい一次ノード（例えば、ノード１）が、少なくともＱ個のビュー変更メッセージを含んでいる新しいビュー・メッセージを、バックアップ・ノードのうちの少なくとも一部にマルチキャストする。
【００６７】
図４Ｄに示されているように、ステップ４２４ｂで、ビュー変更プロトコルの過程で、バックアップ・ノードが、対応するノードがビュー変更メッセージに同意していることをそれぞれ示すＱ個以上のビュー変更メッセージを新しい一次ノードが受信したことを示す新しいビュー・メッセージを、新しい一次ノードから取得してよい。ステップ４２５ｂで、バックアップ・ノードが、新しいビュー・メッセージの受容を示す別の準備メッセージをマルチキャストする。別の準備メッセージは、少なくともビュー番号に関して、図４Ａおよび図４Ｂの準備メッセージと異なってよい。
【００６８】
図４Ｃを参照すると、ステップ４２６ａで、新しい一次ノード（ノード１）が別の（Ｑ−１）個以上の準備メッセージを取得してよい。ステップ４２６ｂで、残りのバックアップ・ノードが、別の（Ｑ−１）個以上の準備メッセージをそれぞれ取得してよい。図４Ｃおよび図４Ｄの準備フェーズは、図４Ａおよび図４Ｂの準備フェーズに類似しているが、ビュー変更後の準備メッセージの内容が異なってよく、一部のノードが要求の一部をコミットしていてよいという点が異なる。区別するために、図４Ｃおよび図４Ｄの準備フェーズの準備メッセージは、別の準備メッセージまたは別の量の準備メッセージと呼ばれる。
【００６９】
ビュー変更プロトコルにおけるステップ４２５〜４２７は、正常動作プロトコルにおけるステップ４１５〜４１７に類似しているが、次の態様において異なっていてよい。（１）ビュー番号、（２）コミットされる要求が、対応するノードで再コミットされる必要がない、（３）機能していないノード０がステップ４２５〜４２７を実行しなくてよいか、またはステップ４２５〜４２７を正しく実行しなくよい。
【００７０】
開示された方法は、記憶装置の消費に対する要求を少なくして、ブロックチェーン・システムの適切な機能を保証することができる。１つの例では、ノードの総数が少なくとも３Ｆ＋１個であるブロックチェーン・システムにおいて、少なくともＦ＋１個のノードがコミット・メッセージをマルチキャストした場合、それは、少なくとも２Ｆ＋１個のノードが準備を完了しており、事前準備メッセージおよび少なくとも２Ｆ個の準備メッセージが持続しているということを意味する。一部の実施形態では、事前準備メッセージおよび少なくとも２Ｆ個の準備メッセージが、格納フェーズにおいて各ノードによって格納される。例えば、一次ノードおよび／または一部のバックアップ・ノードが、事前準備メッセージおよび準備メッセージを格納している。そのため、格納フェーズのないプロセスとは異なり、１つまたは複数のノードまたは最悪の場合にすべてのノードにシステム・クラッシュが発生して再起動した場合でも、格納フェーズで一度格納された事前準備メッセージおよび少なくとも２Ｆ個のメッセージが読み込まれる。その結果、再起動して機能を再開しない（コミット・メッセージをマルチキャストしていても、していなくてもよい）Ｆ個のノードが存在する場合でも、事前準備メッセージおよび少なくとも２Ｆ個のメッセージが格納されて読み込まれるため、合意検証プロセス全体が、記憶装置の消費に対する要求を少なくし、その他の方法では不整合および／または分岐を引き起こすことがあるか、あるいはシステムの安全性および／または活性に影響を与えることがあるシステム・クラッシュによる影響を受けずに、効果的に再開され、前進することができる。
【００７１】
一部の実施形態では、一次ノードが、再起動したノードのうちのノードでないとすると、タイムアウト期間が終了した場合に、ビュー変更がトリガーされてよい。少なくともＱ個のノードが準備を完了しているため、そのうちのＦ個がコミットしており、再起動を実行しない場合でも、（Ｑ−Ｆ）個のノードがシステムの再起動を実行し、格納された事前準備メッセージおよび準備メッセージを読み込んでよい。再起動された（Ｑ−Ｆ）個のノードによってマルチキャストされたビュー変更メッセージは、クラッシュ前からの事前準備メッセージおよび準備メッセージを運び、新しい一次ノードによってマルチキャストされた新しいビュー・メッセージが同じメッセージを運ぶことを保証する。このようにして、一貫性のない合意結果およびブロックチェーンの分岐が防がれる。
【００７２】
他の実施形態では、一次ノードが、再起動したＱ個のノードのうちのノードである場合、一次ノードは、正常動作プロトコルの再開を試みるか、または他の動作を提案してよい。再起動が十分に高速でない場合、少なくとも（Ｑ−Ｆ）個のノードが、読み込まれた事前準備メッセージおよび準備メッセージによってロックされるため、それらのノードは一次ノードに応答しない。したがって、合意に達することができず、新しい一次ノードを選ぶためにビュー変更がトリガーされてよい。残りのノードは、前述したビュー変更の実施形態に従ってよい。
【００７３】
図５Ａは、本明細書のさまざまな実施形態に従って、合意方法５１０のフローチャートを示している。方法５１０は、図１のシステム１００の１つまたは複数のコンポーネント（例えば、前述したノード０、ノード１、ノード２、…、またはノードｉ、または類似するデバイス、あるいはノードのいずれかおよび１つまたは複数の追加のデバイス（例えば、ノードＡ）の組合せ）によって実装されてよい。方法５１０は、１つまたは複数のブロックチェーン・ノード（例えば、バックアップ・ノード）によって実装されてよい。方法５１０は、さまざまなハードウェアマシンおよび／またはソフトウェアを備えている合意システムまたはデバイス（例えば、コンピュータ、サーバ）によって実装されてよい。例えば、合意システムまたはデバイスは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、システムまたはデバイス（例えば、プロセッサ）に方法５１０を実行させるように１つまたは複数のプロセッサによって実行可能な命令を使用して構成された、１つまたは複数の非一時的コンピュータ可読記憶媒体（例えば、１つまたは複数のメモリ）とを備えてよい。以下で提示される方法５１０の動作は、例示的であるよう意図されている。実装に応じて、方法５１０は、さまざまな順序で、または並列に実行される、追加のステップ、より少ないステップ、または代替のステップを含んでよい。下で説明されているさまざまなブロックは、特に指定されない限り、図に示された順序で実行される必要はない。例えば、ブロック５１２は、ブロック５１３が開始された後に開始し、ブロック５１３が終了される前に終了してよい。同様に、ブロック５１５は、ブロック５１６が開始された後に開始し、ブロック５１６が終了される前に終了してよい。別の例を挙げると、ブロック５１３および５１４は、順序通りに、または並列に実行されてよい。
【００７４】
一部の実施形態では、方法５１０が、ある数（Ｎ）のノードによって維持されるブロックチェーン上で実装されてよく、ノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、方法５１０がバックアップ・ノードのうちの１つによって実行される。Ｎは、４以上の任意の整数であることができる。一部の実施形態では、Ｎは３Ｆ＋１に等しく、Ｆは、ＰＢＦＴ合意メカニズムにおいてシステムが許容できる機能していないノードの数を指定する。一次ノードおよびバックアップ・ノードは、ＰＢＦＴ合意メカニズムにおいて定義されるノードであってよい。方法５１０は、１つまたは複数の要求（例えば、ブロックチェーン・トランザクション要求）の１回の合意検証に適用されてよい。方法５１０のステップは、現在のビュー内のバックアップ・ノードによって実行されてよく、このバックアップ・ノードはバックアップ・ノードのままであってよく、またはビュー変更が行われる場合に、新しい一次ノードになってよい。ＰＢＦＴ合意メカニズムに従うビューは、方法５１０の実施中に変化することもあれば、変化しないこともある。方法５１０のさらなる詳細については、図１〜図４Ｂおよび関連する前述の説明を参照することができる。
【００７５】
ブロック５１１は、事前準備メッセージを一次ノードから取得することを含んでいる。一部の実施形態では、事前準備メッセージを一次ノードから取得する前に、方法５１０は、１つまたは複数のトランザクション要求を、１つまたは複数のクライアント、一次ノード、または他のバックアップ・ノードのうちの１つまたは複数のうちの少なくとも１つから取得することをさらに含む。用語「トランザクション要求」におけるトランザクションは、ブロックチェーン・システムを介して実施され、ブロックチェーンに記録されてよい。トランザクションは、例えば、金融トランザクション、ブロックチェーン契約をデプロイするか、または呼び出すブロックチェーン契約トランザクション、ブロックチェーンの状態（例えば、世界状態）を更新するトランザクションなどを含んでよい。トランザクションは、金銭のやりとりを伴う必要はない。トランザクション要求は、合意検証を介してブロックチェーンに追加されるブロックチェーン・トランザクションを含んでよい。一実施形態では、事前準備メッセージは、１つまたは複数のトランザクション要求に対応する１つまたは複数のトランザクションの順序を含む。この順序は、トランザクション要求を実行するために事前準備メッセージをマルチキャストする一次ノードによって提案されてよい。この順序は、トランザクションを含んでいる提案された新しいブロックの一意のハッシュ値の識別に対応してよい。一次ノードおよびバックアップ・ノードは、提案された順序を検証し、合意に達しようと試みる。代替として、この要求は、１つまたは複数のコンピューティング・デバイスに対する、情報を提供すること、または別の機能を実行することの別の命令を含んでよい。
【００７６】
ブロック５１２は、準備メッセージを一次ノードおよび他の（Ｎ−２）個のバックアップ・ノードのうちの少なくとも一部にマルチキャストすることを含んでおり、この準備メッセージは、事前準備メッセージの受容を示す。マルチキャストとは、ＰＢＦＴシステム内の他のノードのうちの１つまたは複数あるいはすべてへのブロードキャストを意味する。機能している各バックアップ・ノードは、準備メッセージをマルチキャストしてよい。
【００７７】
ブロック５１３は、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することを含んでおり、Ｑ（定数）は、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値になり、Ｆは、（Ｎ−１）／３を最も近い整数に切り下げた値になる。例えば、方法５１０を実行しているノードは、Ｎ個のノードのうちの１つである。（Ｑ−１）個の準備メッセージは、個別のノードからであってよく、有効かつ一貫性があり、少なくとも（Ｑ−１）個のバックアップ・ノードおよび一次ノードが事前準備メッセージに同意していることを示す。
【００７８】
ブロック５１４は、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することを含んでいる。例えば、（Ｑ−１）が２Ｆであり、３Ｆ個の準備メッセージが前のステップで取得された場合、ここで、事前準備メッセージおよび２Ｆ〜３Ｆ（２Ｆおよび３Ｆを含む）個の準備メッセージが格納されてよい。一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個の準備メッセージのみが格納される。例えば、（Ｑ−１）が２Ｆであり、３Ｆ個の準備メッセージが前のステップで取得された場合、ここで、事前準備メッセージおよび２Ｆ個の準備メッセージのみが格納されてよい。一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することが、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージのみを格納することを含む。例えば、事前準備メッセージおよび（Ｑ−１）個の準備メッセージのみが格納される。事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージ以外のメッセージは、格納されない。例えば、合意検証の各回で、コミット・メッセージは格納されない。同じことが、複数回の合意検証が実行される場合に適用されてよい。
【００７９】
一部の実施形態では、システムの再起動などのシステムのダウンタイムの回復後に、格納されたデータが取り出し可能である限り、事前準備メッセージおよび少なくとも（Ｑ−１）個の準備メッセージが、さまざまな方式で格納されてよい。例えば、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージが、リレーショナル・データベース、非リレーショナル・データベース、文書システムなどに格納されてよい。例えば、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージが、永続的記憶装置に格納されてよい。本明細書に記載された格納ステップおよびその他のステップは、プログラミング言語によって制限されなくてよい。
【００８０】
一部の実施形態では、ブロック５１４は、ブロック５１３が満たされた場合にのみ、すなわち、（Ｑ−１）個以上の準備メッセージが取得された場合にのみ、実行されてよい。他の実施形態では、各事前準備メッセージまたは準備メッセージは、受信されたときにすぐに格納されてよい。
【００８１】
一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納した後で（ブロック５１４）、コミット・メッセージをマルチキャストする前に（ブロック５１５）、この方法は、システムの再起動を実行することと、格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含む。正常動作の中断（例えば、システム・クラッシュ、停電など）に応答して、システムの再起動が実行されてよい。中断は、ＰＢＦＴシステム内のノードのうちの１つまたは複数あるいはすべてに発生することがある。一部の実施形態では、最大でＮ個のノードすべてにクラッシュが発生し、Ｎ個のノードのうちの少なくともＱ個が、システムの再起動を実行し、対応する格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージをそれぞれ読み込む。次に、ビュー変更プロトコルがトリガーされてもされなくてもよい。
【００８２】
一実施形態では、再起動がタイムアウトのトリガーを回避するほど十分に素早く、したがってシステムの再起動がビュー変更のトリガーを回避する場合、ビュー変更プロトコルがトリガーされなくてよい。すなわち、システムの再起動を実行することは、ビュー変更をトリガーせずにシステムの再起動を実行することを含む。それに応じて、ブロック５１５からの方法５１０の残りのステップが続いてよい。
【００８３】
そうでない場合、ビュー変更プロトコルがトリガーされてよい。一実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納した後で、コミット・メッセージをマルチキャストする前に、この方法は、読み込まれた事前準備メッセージおよび読み込まれた（Ｑ−１）個以上の準備メッセージを含んでいるビュー変更メッセージをマルチキャストすることをさらに含む。他のバックアップ・ノードが、ビュー変更メッセージをマルチキャストしてもよい。バックアップ・ノードのうちの１つが新しい一次ノードになるように選ばれてよく、この新しい一次ノードは、先行するステップを実行した１つのバックアップ・ノードであってもなくてもよい。
【００８４】
一部の実施形態では、上記のステップを実行したバックアップ・ノードが、新しい一次ノードになるように選ばれない場合、このバックアップ・ノードはバックアップ・ノードのままであってよく、ビュー変更中に次のステップを実行してよい。事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納した後で、コミット・メッセージをマルチキャストする前に、この方法は、対応するノードがビュー変更メッセージに同意していることをそれぞれ示すＱ個以上のビュー変更メッセージを新しい一次ノードが受信したことを示している、新しいビュー・メッセージを、新しい一次ノードから取得することと、別の準備メッセージを、新しい一次ノードを含んでいるバックアップ・ノードのうちの少なくとも一部にマルチキャストすることであって、この別の準備メッセージが新しいビュー・メッセージの受容を示す、マルチキャストすることと、別の（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することであって、これらの別の（Ｑ−１）個以上の準備メッセージが、マルチキャストされた別の準備メッセージを含んでいる、取得することとをさらに含む。
【００８５】
他の実施形態では、上記のステップを実行したノードが、新しい一次ノードになるように選ばれた場合、このノードは新しい一次ノードになってよく、ビュー変更中に次のステップを実行してよい。事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納した後で、コミット・メッセージをマルチキャストする前に、この方法は、対応するノードがビュー変更メッセージに同意していることをそれぞれ示すＱ個以上のビュー変更メッセージを、バックアップ・ノードのうちのＱ個以上からそれぞれ取得することであって、これらのＱ個以上のビュー変更メッセージがマルチキャストされたビュー変更メッセージを含んでいる、取得することと、新しい一次ノードとして機能している１つのバックアップ・ノードがＱ個以上のビュー変更メッセージを受信したことを示す新しいビュー・メッセージを、バックアップ・ノードのうちの少なくとも一部にマルチキャストすることと、別の（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することであって、これらの別の（Ｑ−１）個以上の準備メッセージが、別のマルチキャストされた準備メッセージを含んでいる、マルチキャストすることとをさらに含む。
【００８６】
ビュー変更が行われない場合は、ブロック５１１〜５１４と同じビュー内にいる間に、またはブロック５１５の前にビュー変更が行われた場合は、新しいビュー内で、ブロック５１５および５１６ならびに次のステップが実行されてよい。
【００８７】
ブロック５１５は、コミット・メッセージを一次ノードおよび他のバックアップ・ノードのうちの少なくとも一部にマルチキャストすることを含んでおり、このコミット・メッセージは、１つのバックアップ・ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す。一部の実施形態では、このコミット・メッセージは、１つのバックアップ・ノードが事前準備メッセージに同意し、（Ｑ−１）個以上の準備メッセージを取得したことを示す。一部の実施形態では、コミット・メッセージをマルチキャストすることに同意することに関して、検証ステップが実行されてよい。例えば、前述したように、ダイジェストｄに対して検証するために、順序に従ってダイジェストＤ（ｍ）が決定されてよい。一致する場合、コミット・メッセージがマルチキャストされてよい。
【００８８】
一部の実施形態では、コミット・メッセージをそれぞれマルチキャストした後に、ブロック５１３で、バックアップ・ノードのうちの（Ｑ−１）個以上のうちの最大でＦ個が故障しているか、またはその他の方法で機能しておらず、システムの再起動を実行しない。例えば、コミットしたＦ個のノードでシステム・クラッシュが発生し、これらのノードが再起動せず、機能を再開しないことがある。それにもかかわらず、一貫性のない結果およびブロックチェーンの分岐を引き起こさずに、合意検証を適切に実行することができる。
【００８９】
ブロック５１６は、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得することを含んでいる。一部の実施形態では、このコミット・メッセージは、コミット・メッセージをマルチキャストした対応するノードが事前準備メッセージに同意し、（Ｑ−１）個以上の準備メッセージを取得したことを示す。Ｑ個のコミット・メッセージは、個別のノードからであってよく、有効かつ一貫性があり、Ｑ個のノードが順番に要求を実行する準備ができているということを示す。したがって、大部分のノードによって合意が達せられ、次の実行ステップを実行することができる。
【００９０】
一部の実施形態では、コミット・メッセージをマルチキャストした後に（ブロック５１５）、要求を実行する前に、この方法は、システムの再起動を実行することと、格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含む。システムの再起動は、自主的に、または選択の余地なく、実行されてよい。システムの再起動は、システム・クラッシュなどの、システムまたはデバイスの機能の中断によって引き起こされてよい。
【００９１】
一部の実施形態では、方法５１０は、この順序に従って、１つまたは複数のトランザクションを、１つのバックアップ・ノードによって維持されるブロックチェーンのローカル・コピーに詰め込むことをさらに含んでよい。例えば、少なくとも（Ｑ−Ｆ）個の善意のノード（Ｑ個のコミット・メッセージだが、最大でＦ個の機能していないノードを考慮している）がコミット・メッセージ内のダイジェストｄを検証したときに、要求の合意が検証されてよい（または一次ノードの場合、一次ノードがダイジェストｄを提案したため、検証を実行する必要がなくてよい）。その結果、十分な数のノードが対応するトランザクションを検証した場合、それらのトランザクションをブロックチェーンに詰め込むことができる。最初に要求を送信したクライアント（例えば、ノードＡ）に通知されてよい。
【００９２】
図５Ｂは、本明細書のさまざまな実施形態に従って、合意方法５２０のフローチャートを示している。方法５２０は、図１のシステム１００の１つまたは複数のコンポーネント（例えば、前述したノード０、ノード１、ノード２、…、またはノードｉ、または類似するデバイス、あるいはノードのいずれかおよび１つまたは複数の追加のデバイス（例えば、ノードＡ）の組合せ）によって実装されてよい。方法５２０は、１つまたは複数のブロックチェーン・ノード（例えば、一次ノード）によって実装されてよい。方法５２０は、さまざまなハードウェアマシンおよび／またはソフトウェアを備えている合意システムまたはデバイス（例えば、コンピュータ、サーバ）によって実装されてよい。例えば、合意システムまたはデバイスは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、システムまたはデバイス（例えば、プロセッサ）に方法５２０を実行させるように１つまたは複数のプロセッサによって実行可能な命令を使用して構成された、１つまたは複数の非一時的コンピュータ可読記憶媒体（例えば、１つまたは複数のメモリ）とを備えてよい。以下で提示される方法５２０の動作は、例示的であるよう意図されている。実装に応じて、方法５２０は、さまざまな順序で、または並列に実行される、追加のステップ、より少ないステップ、または代替のステップを含んでよい。下で説明されているさまざまなブロックは、特に指定されない限り、図に示された順序で実行される必要はない。例えば、ブロック５２１は、ブロック５２２が開始された後に開始し、ブロック５２２が終了される前に終了してよい。同様に、ブロック５２４は、ブロック５２５が開始された後に開始し、ブロック５２５が終了される前に終了してよい。別の例を挙げると、ブロック５２２および５２３は、順序通りに、または並列に実行されてよい。
【００９３】
一部の実施形態では、方法５２０が、ある数（Ｎ）のノードによって維持されるブロックチェーン上で実装されてよく、ノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、方法５２０が一次ノードによって実行される。一次ノードおよびバックアップ・ノードは、ＰＢＦＴモデルにおいて定義されるノードであってよい。方法５２０は、１つまたは複数の要求（例えば、ブロックチェーン・トランザクション要求）の１回の合意検証に適用されてよい。方法５２０のさらなる詳細については、図１〜図４Ｂおよび関連する前述の説明を参照することができる。
【００９４】
ブロック５２１は、事前準備メッセージをバックアップ・ノードのうちの少なくとも一部にマルチキャストすることを含んでいる。一部の実施形態では、事前準備メッセージをバックアップ・ノードのうちの少なくとも一部にマルチキャストする前に、方法５２０は、１つまたは複数のトランザクション要求を、１つまたは複数のクライアント（例えば、軽量ノード）またはバックアップ・ノードのうちの１つまたは複数のうちの少なくとも１つから取得することをさらに含む。トランザクション要求は、合意検証を介してブロックチェーンに追加されるブロックチェーン・トランザクションを含んでよい。一実施形態では、事前準備メッセージは、１つまたは複数のトランザクション要求に対応する１つまたは複数のトランザクションの順序を含む。この順序は、トランザクション要求を実行するために事前準備メッセージをマルチキャストする一次ノードによって提案されてよい。この順序は、トランザクションを含んでいる提案された新しいブロックの一意のハッシュ値の識別に対応してよい。一次ノードおよびバックアップ・ノードは、提案された順序を検証し、合意に達しようと試みる。代替として、この要求は、１つまたは複数のコンピューティング・デバイスに対する、情報を提供すること、または別の機能を実行することの別の命令を含んでよい。
【００９５】
ブロック５２２〜５２５はブロック５１３〜５１６および関連する前述の説明に類似してよいが、一次ノードが機能しなくなった場合に、ビュー変更がトリガーされ、新しい一次ノードが選ばれるという点が異なる。
【００９６】
ブロック５２２は、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することを含んでおり、これらの準備メッセージは、対応するバックアップ・ノードによる事前準備メッセージの受容をそれぞれ示し、Ｑ（定数）は、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値になり、Ｆは、（Ｎ−１）／３を最も近い整数に切り下げた値になる。バックアップ・ノードは、準備メッセージをそれぞれマルチキャストしていてよい。一部の実施形態では、Ｆは、機能しているＮ個のノードの合意システムを維持するためにＮ個のノードのうちで許容される、機能していないノードの最大数を表す。例えば、方法５２０を実行しているノードは、Ｎ個のノードのうちの１つである。（Ｑ−１）個以上の準備メッセージは、個別のノードからであってよく、有効かつ一貫性があり、（Ｑ−１）個以上のバックアップ・ノードおよび一次ノードが事前準備メッセージに同意していることを示す。
【００９７】
ブロック５２３は、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することを含んでいる。例えば、（Ｑ−１）が２Ｆであり、３Ｆ個の準備メッセージが前のステップで取得された場合、ここで、事前準備メッセージおよび２Ｆ〜３Ｆ（２Ｆおよび３Ｆを含む）個の準備メッセージが格納されてよい。一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個の準備メッセージのみが格納される。例えば、（Ｑ−１）が２Ｆであり、３Ｆ個の準備メッセージが前のステップで取得された場合、ここで、事前準備メッセージおよび２Ｆ個の準備メッセージのみが格納されてよい。一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することが、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージのみを格納することを含む。例えば、事前準備メッセージおよび（Ｑ−１）個の準備メッセージのみが格納される。事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージ以外のメッセージは、格納されない。例えば、合意検証の各回で、コミット・メッセージは格納されない。同じことが、複数回の合意検証が実行される場合に適用されてよい。
【００９８】
一部の実施形態では、システムの再起動などのシステムのダウンタイムの回復後に、格納されたデータが取り出し可能である限り、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージが、さまざまな方式で格納されてよい。例えば、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージが、リレーショナル・データベース、非リレーショナル・データベース、文書システムなどに格納されてよい。例えば、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージが、永続的記憶装置に格納されてよい。本明細書に記載された格納ステップおよびその他のステップは、プログラミング言語によって制限されなくてよい。
【００９９】
一部の実施形態では、ブロック５２３は、ブロック５２２が満たされた場合にのみ、すなわち、（Ｑ−１）個以上の準備メッセージが取得された場合にのみ、実行されてよい。他の実施形態では、各事前準備メッセージまたは準備メッセージは、受信されたときにすぐに格納されてよい。
【０１００】
一部の実施形態では、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納した後で（ブロック５２３）、コミット・メッセージをマルチキャストする前に（ブロック５２４）、この方法は、システムの再起動を実行することと、格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含む。正常動作の中断（例えば、システム・クラッシュ、停電など）に応答して、システムの再起動が実行されてよい。中断は、ＰＢＦＴシステム内のノードのうちの１つまたは複数あるいはすべてに発生することがある。一部の実施形態では、最大でＮ個のノードすべてにクラッシュが発生し、Ｎ個のノードのうちの少なくともＱ個が、システムの再起動を実行し、対応する格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージをそれぞれ読み込む。次に、ビュー変更プロトコルがトリガーされてもされなくてもよい。
【０１０１】
一実施形態では、再起動がタイムアウトのトリガーを回避するほど十分に素早く、したがってシステムの再起動がビュー変更のトリガーを回避する場合、ビュー変更プロトコルがトリガーされなくてよい。それに応じて、ブロック５２４からの方法５２０の残りのステップが続いてよい。別の実施形態では、ビュー変更プロトコルがトリガーされてよく、ブロック５２４からの方法５２０の残りのステップが続かなくてよい。
【０１０２】
ブロック５２４は、コミット・メッセージをバックアップ・ノードのうちの少なくとも一部にマルチキャストすることを含んでおり、このコミット・メッセージは、一次ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す。一部の実施形態では、このコミット・メッセージは、一次ノードが（Ｑ−１）個以上の準備メッセージを取得したことを示す。一部の実施形態では、コミット・メッセージをそれぞれマルチキャストした後に、ブロック５２２で、バックアップ・ノードのうちの（Ｑ−１）個以上のうちの最大でＦ個が故障しているか、またはその他の方法で機能しておらず、システムの再起動を実行しない。例えば、コミットしたＦ個のノードでシステム・クラッシュが発生し、これらのノードが再起動せず、機能を再開しないことがある。それにもかかわらず、一貫性のない結果およびブロックチェーンの分岐を引き起こさずに、合意検証を適切に実行することができる。
【０１０３】
ブロック５２５は、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得することを含んでおり、これらのＱ個以上のコミット・メッセージは、マルチキャストされたコミット・メッセージを含んでいる。一部の実施形態では、このコミット・メッセージは、コミット・メッセージをマルチキャストした対応するノードが事前準備メッセージに同意し、（Ｑ−１）個以上の準備メッセージを取得したことを示す。Ｑ個以上のコミット・メッセージは、個別のノードからであってよく、有効かつ一貫性があり、Ｑ個以上のノードが順番に要求を実行する準備ができているということを示す。したがって、大部分のノードによって合意が達せられ、次の実行ステップを実行することができる。
【０１０４】
一部の実施形態では、コミット・メッセージをマルチキャストした後に（ブロック５２５）、要求を実行する前に、この方法は、システムの再起動を実行することと、格納された事前準備メッセージおよび格納された（Ｑ−１）個以上の準備メッセージを読み込むこととをさらに含む。システムの再起動は、自主的に、または選択の余地なく、実行されてよい。システムの再起動は、システム・クラッシュなどの、システムまたはデバイスの機能の中断によって引き起こされてよい。
【０１０５】
一部の実施形態では、方法５２０は、この順序に従って、１つまたは複数のトランザクションを、一次ノードによって維持されるブロックチェーンのローカル・コピーに詰め込むことをさらに含んでよい。例えば、少なくとも（Ｑ−Ｆ）個の善意のノード（Ｑ個のコミット・メッセージだが、最大でＦ個の機能していないノードを考慮している）がコミット・メッセージ内のダイジェストｄを検証したときに、要求の合意が検証されてよい（または一次ノードの場合、一次ノードがダイジェストｄを提案したため、検証を実行する必要がなくてよい）。その結果、十分な数のノードが対応するトランザクションを検証した場合、それらのトランザクションをブロックチェーンに詰め込むことができる。最初に要求を送信したクライアント（例えば、ノードＡ）に通知されてよい。
【０１０６】
図６Ａは、さまざまな実施形態に従って、合意システム６１０のブロック図を示している。合意システム６１０（例えば、コンピュータ・システム）は、前述したノード０、ノード１、ノード２、…、またはノードｉ、または類似するデバイス、あるいはノードのいずれかおよび追加のデバイス（例えば、ノードＡ）の組合せの実装の例であってよい。方法５１０は、合意システム６１０によって実装されてよい。合意システム６１０は、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、システムまたはデバイス（例えば、プロセッサ）に方法５１０を実行させるように１つまたは複数のプロセッサによって実行可能な命令を使用して構成された、１つまたは複数の非一時的コンピュータ可読記憶媒体（例えば、１つまたは複数のメモリ）とを備えてよい。合意システム６１０は、バックアップ・ノードにおいて実装されてよい。合意システム６１０は、命令（例えば、ソフトウェア命令）に対応するさまざまなユニット／モジュールを備えてよい。
【０１０７】
一部の実施形態では、合意システム６１０は、合意装置と呼ばれてよい。この合意装置はブロックチェーンを維持するためであってよく、ある数（Ｎ）のノードがブロックチェーンを維持し、Ｎ個のノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、この合意装置は、（Ｎ−１）個のバックアップ・ノードのうちの１つとして機能し、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、この装置に動作を実行させるために１つまたは複数のプロセッサによって実行可能な命令を使用して構成された１つまたは複数の非一時的コンピュータ可読メモリとを備える。この合意装置は、命令（例えば、ソフトウェア命令）に対応するさまざまなユニット／モジュールを備えてよい。この合意装置は、事前準備メッセージを一次ノードから取得するための第１の取得モジュール６１１と、準備メッセージを一次ノードおよび他の（Ｎ−２）個のバックアップ・ノードのうちの少なくとも一部にマルチキャストするための第１のマルチキャスト・モジュール６１２であって、この準備メッセージが事前準備メッセージの受容を示す、第１のマルチキャスト・モジュール６１２と、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得するための第２の取得モジュール６１３であって、Ｑ（定数）が、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆが（Ｎ−１）／３を最も近い整数に切り下げた値であり、（Ｑ−１）以上の準備メッセージがマルチキャストされた準備メッセージを含んでいる、第２の取得モジュール６１３と、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納するための格納モジュール６１４と、コミット・メッセージを、一次ノードおよび他のバックアップ・ノードのうちの少なくとも一部にマルチキャストするための第２のマルチキャスト・モジュール６１５であって、このコミット・メッセージが、１つのバックアップ・ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す、第２のマルチキャスト・モジュール６１５と、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得するための第３の取得モジュール６１６であって、Ｑ個以上のコミット・メッセージがマルチキャストされたコミット・メッセージを含んでいる、第３の取得モジュール６１６とを備えてよい。
【０１０８】
一部の実施形態では、第１の取得モジュール６１１または別のモジュールは、１つまたは複数のトランザクション要求を、１つまたは複数のクライアント、一次ノード、または他のバックアップ・ノードのうちの１つまたは複数のうちの少なくとも１つから取得するためでもある。この合意装置は、この順序に従って、１つまたは複数のトランザクションを、１つのバックアップ・ノードによって維持されるブロックチェーンのローカル・コピーに詰め込むための詰め込みモジュール６１７をさらに備えてよい。
【０１０９】
図６Ｂは、さまざまな実施形態に従って、合意システム６２０のブロック図を示している。合意システム６２０（例えば、コンピュータ・システム）は、前述したノード０、ノード１、ノード２、…、またはノードｉ、または類似するデバイス、あるいはノードのいずれかおよび追加のデバイス（例えば、ノードＡ）の組合せの実装の例であってよい。方法５２０は、合意システム６２０によって実装されてよい。合意システム６２０は、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、システムまたはデバイス（例えば、プロセッサ）に方法５２０を実行させるように１つまたは複数のプロセッサによって実行可能な命令を使用して構成された、１つまたは複数の非一時的コンピュータ可読記憶媒体（例えば、１つまたは複数のメモリ）とを備えてよい。合意システム６２０は、一次ノードにおいて実装されてよい。合意システム６２０は、命令（例えば、ソフトウェア命令）に対応するさまざまなユニット／モジュールを備えてよい。
【０１１０】
一部の実施形態では、合意システム６２０は、合意装置と呼ばれてよい。この合意装置はブロックチェーンを維持するためであってよく、ある数（Ｎ）のノードがブロックチェーンを維持し、Ｎ個のノードのうちの１つが一次ノードとして機能し、他の（Ｎ−１）個のノードがバックアップ・ノードとして機能し、この合意装置は、一次ノードとして機能し、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、この装置に動作を実行させるために１つまたは複数のプロセッサによって実行可能な命令を使用して構成された１つまたは複数の非一時的コンピュータ可読メモリとを備える。この合意装置は、命令（例えば、ソフトウェア命令）に対応するさまざまなユニット／モジュールを備えてよい。この合意装置は、事前準備メッセージをバックアップ・ノードのうちの少なくとも一部にマルチキャストするための第１のマルチキャスト・モジュール６２１と、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得するための第１の取得モジュール６２２であって、これらの準備メッセージが、対応するバックアップ・ノードによる事前準備メッセージの受容をそれぞれ示し、Ｑ（定数）が、（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆが（Ｎ−１）／３を最も近い整数に切り下げた値である、第１の取得モジュール６２２と、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納するための格納モジュール６２３と、コミット・メッセージを、バックアップ・ノードのうちの少なくとも一部にマルチキャストするための第２のマルチキャスト・モジュール６２４であって、このコミット・メッセージが、一次ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す、第２のマルチキャスト・モジュール６２４と、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得するための第２の取得モジュール６２５であって、Ｑ個以上のコミット・メッセージがマルチキャストされたコミット・メッセージを含んでいる、第２の取得モジュール６２５とを備えてよい。
【０１１１】
一部の実施形態では、この合意装置は、１つまたは複数のトランザクション要求を、１つまたは複数のクライアントまたはバックアップ・ノードのうちの１つまたは複数のうちの少なくとも１つから取得するための第３の取得モジュール６２６をさらに備えてよい。この合意装置は、この順序に従って、１つまたは複数のトランザクションを、一次ノードによって維持されるブロックチェーンのローカル・コピーに詰め込むための詰め込みモジュール６２７をさらに備えてよい。
【０１１２】
本明細書に記載された技術は、１つまたは複数の専用コンピューティング・デバイスによって実装される。それらの専用コンピューティング・デバイスは、デスクトップ・コンピュータ・システム、サーバ・コンピュータ・システム、ポータブル・コンピュータ・システム、ハンドヘルド・デバイス、ネットワーク・デバイス、あるいは本技術を実装するために配線論理および／またはプログラム論理を組み込む任意のその他デバイスまたはデバイスの組合せであってよい。それらの専用コンピューティング・デバイスは、パーソナル・コンピュータ、ラップトップ、携帯電話、カメラ付き携帯電話、スマートフォン、パーソナル・デジタル・アシスタント、メディア・プレーヤー、ナビゲーション・デバイス、電子メール・デバイス、ゲーム機、タブレット・コンピュータ、ウェアラブル・デバイス、またはこれらの組合せとして実装されてよい。コンピューティング・デバイスは、通常、オペレーティング・システム・ソフトウェアによって制御され、調整されてよい。従来のオペレーティング・システムは、特に、実行のためにコンピュータ・プロセッサを制御およびスケジューリングし、メモリ管理を実行し、ファイル・システム、ネットワーク接続、Ｉ／Ｏサービスを提供し、グラフィカル・ユーザ・インターフェイス（ＧＵＩ：ｇｒａｐｈｉｃａｌ  ｕｓｅｒ  ｉｎｔｅｒｆａｃｅ）などのユーザ・インターフェイス機能を提供する。本明細書に記載されたさまざまなシステム、装置、記憶媒体、モジュール、およびユニットは、専用コンピューティング・デバイス、あるいは１つまたは複数の専用コンピューティング・デバイスの１つまたは複数のコンピューティング・チップにおいて実装されてよい。一部の実施形態では、本明細書に記載された命令は、専用コンピューティング・デバイス上の仮想マシンにおいて実装されてよい。それらの命令は、実行されたときに、専用コンピューティング・デバイスに、本明細書に記載されたさまざまな方法を実行させてよい。この仮想マシンは、ソフトウェア、ハードウェア、またはこれらの組合せを含んでよい。例えば、仮想マシンは、イーサリアム内でスマート・コントラクト用の実行時環境を提供するイーサリアム仮想マシン（ＥＶＭ：Ｅｔｈｅｒｅｕｍ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ）ソフトウェアを含んでよい。
【０１１３】
図７は、本明細書に記載された実施形態のいずれかが実装されてよいコンピュータ・システム７００を示すブロック図である。システム７００は、本明細書に記載された方法（例えば、合意方法５１０、合意方法５２０）のいずれかを実行してよい。システム７００は、本明細書に記載されたシステム（例えば、合意システム６１０、合意システム６２０）のいずれかにおいて実装されてよい。システム７００は、本明細書に記載されたノードのいずれかにおいて実装されてよく、ブロックチェーン契約を実装するために、対応するステップを実行するように構成されてよい。コンピュータ・システム７００は、情報を伝達するためのバス７０２またはその他の通信機構、情報を処理するためにバス７０２に結合された１つまたは複数のハードウェア・プロセッサ７０４を含んでいる。ハードウェア・プロセッサ７０４は、例えば、１つまたは複数の汎用マイクロプロセッサであってよい。
【０１１４】
コンピュータ・システム７００は、情報およびプロセッサ７０４によって実行可能な命令を格納するためにバス７０２に結合された、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）などのメイン・メモリ７０６、キャッシュ、および／またはその他の動的記憶デバイスも含んでいる。メイン・メモリ７０６は、プロセッサ７０４によって実行可能な命令の実行中にテンポラリ変数またはその他の中間情報を格納するために使用されてもよい。そのような命令は、プロセッサ７０４によってアクセス可能な記憶媒体に格納された場合、コンピュータ・システム７００を、命令で指定された動作を実行するようにカスタマイズされた専用マシンにする。コンピュータ・システム７００は、プロセッサ７０４用の静的情報および命令を格納するためにバス７０２に結合された、読み取り専用メモリ（ＲＯＭ：ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）７０８またはその他の静的記憶デバイスをさらに含んでいる。磁気ディスク、光ディスク、またはＵＳＢサム・ドライブ（フラッシュ・ドライブ）などの記憶デバイス７１０が、情報および命令を格納するために提供され、バス７０２に結合される。
【０１１５】
コンピュータ・システム７００は、コンピュータ・システムと組み合わせてコンピュータ・システム７００が専用マシンになることを引き起こすか、または専用マシンになるようにプログラムする、カスタマイズされた配線論理、１つまたは複数のＡＳＩＣもしくはＦＰＧＡ、ファームウェア、および／またはプログラム論理を使用して、本明細書に記載された技術を実装してよい。一実施形態によれば、本明細書に記載された動作、方法、およびプロセスは、プロセッサ７０４がメイン・メモリ７０６に含まれている１つまたは複数の命令の１つまたは複数のシーケンスを実行することに応答して、コンピュータ・システム７００によって実行される。そのような命令は、記憶デバイス７１０などの別の記憶媒体からメイン・メモリ７０６に読み取られてよい。メイン・メモリ７０６に含まれている命令のシーケンスの実行は、プロセッサ７０４に、本明細書に記載されたプロセスのステップを実行させる。代替の実施形態では、ソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて、配線接続された回路が使用されてよい。
【０１１６】
メイン・メモリ７０６、ＲＯＭ７０８、および／または記憶装置７１０は、非一時的記憶媒体を含んでよい。「非一時的媒体」という用語および類似の用語は、本明細書において使用されるとき、マシンを特定の様式で動作させるデータおよび／または命令を格納する媒体を指しており、この媒体は、非一時的信号を除外する。そのような非一時的媒体は、不揮発性媒体および／または揮発性媒体を含んでよい。不揮発性媒体の例としては、記憶デバイス７１０などの、光ディスクまたは磁気ディスクが挙げられる。揮発性媒体の例としては、メイン・メモリ７０６などの、動的メモリが挙げられる。非一時的媒体の一般的形態の例としては、フロッピー・ディスク、フレキシブル・ディスク、ハード・ディスク、半導体ドライブ、磁気テープ、または任意のその他の磁気データ記憶媒体、Ｃ−ＲＯＭ、任意のその他の光データ記憶媒体、穴のパターンを有する任意の物理的媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、フラッシュＥＰＲＯＭ、ＮＶＲＡＭ、任意のその他のメモリ・チップまたはメモリ・カートリッジ、ならびにこれらのネットワーク化されたバージョンが挙げられる。
【０１１７】
コンピュータ・システム７００は、バス７０２に結合されたネットワーク・インターフェイス７１８も含んでいる。ネットワーク・インターフェイス７１８は、１つまたは複数のローカル・ネットワークに接続された１つまたは複数のネットワーク・リンクに結合している双方向データ通信を提供する。例えば、ネットワーク・インターフェイス７１８は、総合デジタル通信網（ＩＳＤＮ：ｉｎｔｅｇｒａｔｅｄ  ｓｅｒｖｉｃｅｓ  ｄｉｇｉｔａｌ  ｎｅｔｗｏｒｋ）カード、ケーブル・モデム、衛星モデム、または対応するタイプの電話回線とのデータ通信接続を提供するためのモデムであってよい。別の例として、ネットワーク・インターフェイス７１８は、互換性のあるＬＡＮとのデータ通信接続を提供するためのローカル・エリア・ネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）カード（またはＷＡＮと通信するためのＷＡＮコンポーネント）であってよい。無線リンクが実装されてもよい。いずれかのそのような実装では、ネットワーク・インターフェイス７１８は、さまざまなタイプの情報を表すデジタル・データ・ストリームを運ぶ電気信号、電磁信号、または光信号を送信および受信する。
【０１１８】
コンピュータ・システム７００は、ネットワーク、ネットワーク・リンク、およびネットワーク・インターフェイス７１８を介して、メッセージを送信し、プログラム・コードを含むデータを受信することができる。インターネットの例では、サーバが、インターネット、ＩＳＰ、ローカル・ネットワーク、およびネットワーク・インターフェイス７１８を介して、アプリケーション・プログラムの要求されたコードを送信してよい。
【０１１９】
受信されたコードは、受信されたときにプロセッサ７０４によって実行されてよく、かつ／または後で実行するために、記憶デバイス７１０またはその他の不揮発性記憶装置に格納されてよい。
【０１２０】
上記のセクションにおいて説明されたプロセス、方法、およびアルゴリズムの各々は、コンピュータ・ハードウェアを備えている１つまたは複数のコンピュータ・システムまたはコンピュータ・プロセッサによって実行されるコード・モジュールにおいて具現化され、完全に、または部分的に自動化されてよい。プロセスおよびアルゴリズムは、特定用途向け回路において部分的または全体的に実装されてよい。
【０１２１】
前述したさまざまな特徴およびプロセスが、互いに独立して使用されてよく、またはさまざまな手法で組み合わせられてよい。可能性のあるすべての組合せおよび部分的組合せが、本明細書の範囲に含まれるよう意図されている。加えて、一部の実装では、特定の方法またはプロセスのブロックが省略されてよい。また、本明細書に記載された方法およびプロセスは、いずれかの特定のシーケンスに限定されず、それらに関連するブロックまたは状態を、適切な他のシーケンスで実行することができる。例えば、説明されたブロックまたは状態は、具体的に開示された順序以外の順序で実行されてよく、あるいは複数のブロックまたは状態が、単一のブロックまたは状態に組み合わせられてよい。ブロックまたは状態の例は、直列、並列、または何らかのその他の方式で実行されてよい。ブロックまたは状態は、開示された実施形態に追加されるか、または開示された実施形態から削除されてよい。本明細書に記載されたシステムおよびコンポーネントの例は、説明された方法とは異なって構成されてよい。例えば、要素が、開示された実施形態に追加されるか、開示された実施形態から削除されるか、または開示された実施形態と比較して再配置されてよい。
【０１２２】
本明細書に記載された方法のさまざまな動作は、関連する動作を実行するように（例えば、ソフトウェアによって）一時的に構成されるか、または永続的に構成される１つまたは複数のプロセッサによって、少なくとも部分的に実行されてよい。一時的に構成されるか、または永続的に構成されるかにかかわらず、そのようなプロセッサは、本明細書に記載された１つまたは複数の動作または機能を実行するように動作するプロセッサ実装エンジンを構成してよい。
【０１２３】
同様に本明細書に記載された方法は、少なくとも部分的にプロセッサ実装であってよく、特定の１つまたは複数のプロセッサがハードウェアの例である。例えば、方法の動作のうちの少なくとも一部が、１つまたは複数のプロセッサまたはプロセッサ実装エンジンによって実行されてよい。さらに、１つまたは複数のプロセッサが、「クラウド・コンピューティング」環境内で、または「ＳａａＡ（Ｓｏｆｔｗａｒｅ  ａｓ  ａ  Ｓｅｒｖｉｃｅ）」として、関連する動作の実行をサポートするように動作してもよい。例えば、動作のうちの少なくとも一部は、（プロセッサを含んでいるマシンの例として）コンピュータのグループによって実行されてよく、それらの動作は、ネットワーク（例えば、インターネット）を介して、および１つまたは複数の適切なインターフェイス（例えば、アプリケーションプログラムインターフェイス（ＡＰＩ））を介してアクセス可能である。
【０１２４】
特定の動作の実行は、単一のマシン内に存在するだけでなく、複数のマシンにわたってデプロイされて、プロセッサ間で分散されてよい。一部の実施形態では、プロセッサまたはプロセッサ実装エンジンは、単一の地理的位置（例えば、住居環境内、オフィス環境内、またはサーバ・ファーム内）に配置されてよい。他の実施形態では、プロセッサまたはプロセッサ実装エンジンは、複数の地理的位置にわたって分散されてよい。
【０１２５】
本明細書全体を通じて、複数のインスタンスが、単一のインスタンスとして説明されたコンポーネント、動作、または構造を実装してよい。１つまたは複数の方法の個別の動作が別々の動作として示され、説明されているが、個別の動作のうちの１つまたは複数が同時に実行されてよく、各動作が、示された順序で実行される必要はない。構成において別々のコンポーネントとして提示された構造および機能は、組み合わされた構造またはコンポーネントとして実装されてよい。同様に、単一のコンポーネントとして提示された構造および機能は、別々のコンポーネントとして実装されてよい。これらおよびその他の変形、変更、追加、および改良は、本明細書における主題の範囲に含まれる。さらに、本明細書において使用されている関連性を表す用語（「第１の」、「第２の」、「第３の」など）は、どのような順序、高さ、または重要性も意味しておらず、ある要素を別の要素から区別するために使用されている。さらに、「１つの（ａ）」、「１つの（ａｎ）」、および「複数の」という用語は、本明細書では数量の制限を意味しておらず、言及されている物品のうちの少なくとも１つが存在することを意味している。
【０１２６】
主題の概要が特定の実施形態を参照して説明されているが、本明細書の実施形態のより広い範囲を逸脱することなく、それらの実施形態に対してさまざまな修正および変更が行われてよい。「発明を実施するための形態」は、制限する意味で受け取られるべきではなく、さまざまな実施形態の範囲は、添付の特許請求の範囲に資格が与えられるあらゆる同等のものと共に、添付の特許請求の範囲によってのみ定義される。
【要約】
合意システムのダウンタイムの回復のために、コンピュータ記憶媒体上でエンコードされたコンピュータ・プログラムを含んでいる、方法、システム、および装置。この方法のうちの１つは、事前準備メッセージをバックアップ・ノードの少なくとも一部にマルチキャストすることと、（Ｑ−１）個以上の準備メッセージをバックアップ・ノードのうちの（Ｑ−１）個以上からそれぞれ取得することであって、これらの準備メッセージが、対応するバックアップ・ノードによる事前準備メッセージの受容をそれぞれ示す、取得することと、事前準備メッセージおよび（Ｑ−１）個以上の準備メッセージを格納することと、コミット・メッセージを、バックアップ・ノードの少なくとも一部にマルチキャストすることであって、このコミット・メッセージが、一次ノードが（Ｑ−１）個以上の準備メッセージに同意していることを示す、マルチキャストすることと、一次ノードおよびバックアップ・ノードのうちのＱ個以上のノードから、対応するノードが対応するノードによって受信された（Ｑ−１）個以上の準備メッセージに同意していることをそれぞれ示す、Ｑ個以上のコミット・メッセージをそれぞれ取得することとを含む。【図１】
0006731123.tif 000002
【図２Ａ】
0006731123.tif 000003
【図２Ｂ】
0006731123.tif 000004
【図２Ｃ】
0006731123.tif 000005
【図３Ａ】
0006731123.tif 000006
【図３Ｂ】
0006731123.tif 000007
【図３Ｃ】
0006731123.tif 000008
【図４Ａ】
0006731123.tif 000009
【図４Ｂ】
0006731123.tif 000010
【図４Ｃ】
0006731123.tif 000011
【図４Ｄ】
0006731123.tif 000012
【図５Ａ】
0006731123.tif 000013
【図５Ｂ】
0006731123.tif 000014
【図６Ａ】
0006731123.tif 000015
【図６Ｂ】
0006731123.tif 000016
【図７】
0006731123.tif 000017