RFC992 日本語訳
0992 On communication support for fault tolerant process groups. K.P.Birman, T.A. Joseph. November 1986. (Format: TXT=52313 bytes) (Status: UNKNOWN)
プログラムでの自動翻訳です。
RFC一覧
英語原文
K. P. Birman (Cornell)
Network Working Group T. A. Joseph (Cornell)
Request for Comments: 992 November 1986
コメントを求めるK.P.バーマン(コーネル)ネットワークワーキンググループのT.A.ジョゼフ(コーネル)要求: 992 1986年11月
On Communication Support for Fault Tolerant Process Groups
フォルト・トレラントの過程グループのコミュニケーションサポートに関して
K. P. Birman and T. A. Joseph
Dept. of Computer Science, Cornell University
Ithaca, N.Y. 14853
607-255-9199
コンピュータサイエンス、コーネル大学イタケー、ニューヨーク14853 607-255-9199のK.P.バーマンとT.A.ジョゼフ部
1. Status of this Memo.
1. このMemoの状態。
This memo describes a collection of multicast communication primi- tives integrated with a mechanism for handling process failure and recovery. These primitives facilitate the implementation of fault- tolerant process groups, which can be used to provide distributed services in an environment subject to non-malicious crash failures. Unlike other process group approaches, such as Cheriton's "host groups" (RFC's 966, 988, [Cheriton]), our approach provides powerful guarantees about the behavior of the communication subsystem when process group membership is changing dynamically, for example due to process or site failures, recoveries, or migration of a process from one site to another. Our approach also addresses delivery ordering issues that arise when multiple clients communicate with a process group concurrently, or a single client transmits multiple multicast messages to a group without pausing to wait until each is received. Moreover, the cost of the approach is low. An implementation is be- ing undertaken at Cornell as part of the ISIS project.
このメモは取り扱い過程の失敗と回復のためにメカニズムについて統合しているマルチキャストコミュニケーションprimi- tivesの収集について説明します。 これらの基関数は欠点の許容性がある過程グループの実現を容易にします。(非悪意がある速成の失敗を条件として分配されたサービスを環境に提供するのにグループを使用できます)。 過程グループ会員資格がダイナミックに変化するとき、Cheritonの「ホストグループ」などの他の過程グループアプローチ(RFCの966、988[Cheriton])と異なって、私たちのアプローチはコミュニケーションサブシステムの振舞いに関して強力な保証を提供します、例えば、過程の過程、サイト失敗、回復、または別の1つのサイトからサイトまでの移動のため。 また、私たちのアプローチはそれぞれが受け取られているまで複数のクライアントが同時に過程グループとコミュニケートするか、または独身のクライアントが止まらないで複数のマルチキャストメッセージをグループに送るとき起こる問題を待つよう命令する配送を記述します。 そのうえ、アプローチの費用は低いです。 実現がそうである、存在、イシスプロジェクトの一部としてコーネルで引き受けられたing。
Here, we argue that the form of "best effort" reliability provided by host groups may not address the requirements of those researchers who are building fault tolerant software. Our basic premise is that re- liable handling of failures, recoveries, and dynamic process migra- tion are important aspects of programming in distributed environ- ments, and that communication support that provides unpredictable behavior in the presence of such events places an unacceptable burden of complexity on higher level application software. This complexity does not arise when using the fault-tolerant process group alterna- tive.
ここで、私たちは、ホストグループによって提供された「ベストエフォート型」の信頼性のフォームがフォルト・トレラントのソフトウェアを組立てている研究者の要件を記述しないかもしれないと主張します。 失敗、回復、およびダイナミックな過程migra- tionの再傾向がある取り扱いが分配されるところでプログラムを作る重要な一面がments、および、より高い平らなアプリケーション・ソフトの複雑さの容認できない負担をそのようなイベント場所の面前で予測できない振舞いに提供するそのコミュニケーションサポートを取り巻くということであるという私たちの根本的な前提があります。 フォールトトレラントの過程グループalterna- tiveを使用するとき、この複雑さは起こりません。
This memo summarizes our approach and briefly contrasts it with other process group approaches. For a detailed discussion, together with figures that clarify the details of the approach, readers are re- ferred to the papers cited below.
このメモは、私たちのアプローチをまとめて、簡潔に他の過程グループアプローチに対してそれを対照します。 詳細な論議において、アプローチの詳細をはっきりさせる数字と共に読者は以下で引用された書類に再ferredされます。
Distribution of this memo is unlimited.
このメモの分配は無制限です。
Birman & Joseph [Page 1] RFC 992 November 1986
バーマンとジョゼフ[1ページ]RFC992 1986年11月
2. Acknowledgments
2. 承認
This memo was adopted from a paper presented at the Asilomar workshop on fault-tolerant distributed computing, March 1986, and summarizes material from a technical report that was issued by Cornell Universi- ty, Dept. of Computer Science, in August 1985, which will appear in ACM Transactions on Computer Systems in February 1987 [Birman-b]. Copies of these paper, and other relevant papers, are available on request from the author: Dept. of Computer Science, Cornell Universi- ty, Ithaca, New York 14853. (birman@gvax.cs.cornell.edu). The ISIS project also maintains a mailing list. To be added to this list, contact M. Schmizzi (schiz@gvax.cs.cornell.edu).
このメモは、フォールトトレラント分散コンピューティング、1986年3月にAsilomarワークショップで寄贈された論文から採用されて、コーネルUniversi- tyによって発行された技術報告書から材料をまとめます、コンピュータScienceの部、1985年8月に。(それは、1987[バーマンb]年2月にコンピュータシステムズにACM Transactionsに現れるでしょう)。 紙、および他の関連書類が利用可能であるこれらのコピーは作者から以下を要求します。 コンピュータScience、コーネルUniversi- ty、イタケーニューヨーク 14853人の部。 ( birman@gvax.cs.cornell.edu 。) また、イシスプロジェクトはメーリングリストを維持します。 このリストに追加されるには、M.Schmizzi( schiz@gvax.cs.cornell.edu )に連絡してください。
This work was supported by the Defense Advanced Research Projects Agency (DoD) under ARPA order 5378, Contract MDA903-85-C-0124, and by the National Science Foundation under grant DCR-8412582. The views, opinions and findings contained in this report are those of the au- thors and should not be construed as an official Department of De- fense position, policy, or decision.
この仕事はARPA注文5378、Contract MDA903 85C0124の下における国防高等研究計画庁(DoD)と交付金DCR-8412582の下の国立科学財団によって支持されました。 このレポートに含まれた視点、意見、および調査結果を、Au thorsのものであり、De- fense位置、方針、または決定の公式の部に理解するべきではありません。
3. Introduction
3. 序論
At Cornell, we recently completed a prototype of the ISIS system, which transforms abstract type specifications into fault-tolerant distributed implementations, while insulating users from the mechan- isms by which fault-tolerance is achieved. This version of ISIS, re- ported in [Birman-a], supports transactional resilient objects as a basic programming abstraction. Our current work undertakes to pro- vide a much broader range of fault-tolerant programming mechanisms, including fault-tolerant distributed bulletin boards [Birman-c] and fault-tolerant remote procedure calls on process groups [Birman-b]. The approach to communication that we report here arose as part of this new version of the ISIS system.
コーネルでは、私たちは最近、イシスシステムの手本を完成しました。(システムは耐障害性が達成されるmechan主義からユーザを隔離している間、抽象型仕様をフォールトトレラントの分配された実現に変えます)。 [バーマンa]で再移植されたイシスのこのバージョンは基本的なプログラミング抽象化として取引の弾力がある物を支えます。 私たちの執筆中の作品が、引き受ける、親、参照、過程グループ[バーマンb]に関するフォールトトレラントの分配された掲示板[バーマンc]とフォールトトレラント遠隔手続き呼び出しを含むはるかに広い範囲のフォールトトレラントプログラミングメカニズム 私たちがここで報告するコミュニケーションへのアプローチはイシスシステムのこの新しいバージョンの一部として起こりました。
Unreliable communication primitives, such as the multicast group com- munication primitives proposed in RFC's 966 and 988 and in [Cheri- ton], leave some uncertainty in the delivery status of a message when failures and other exceptional events occur during communication. Instead, a form of "best effort" delivery is provided, but with the possibility that some member of a group of processes did not receive the message if the group membership was changing just as communica- tion took place. When we tried to use this sort of primitive in our original work on ISIS, which must behave reliably in the presence of such events, we had to address this aspect at an application level. The resulting software was complex, difficult to reason about, and filled with obscure bugs, and we were eventually forced to abandon the entire approach as infeasible.
失敗と他の例外的な出来事がコミュニケーションの間、起こると、RFCの966と988と[シェリートン]で提案されたマルチキャストグループcom- munication基関数などのあてにならないコミュニケーション基関数はメッセージの配送状態に何らかの不確実性を残します。 代わりに、「ベストエフォート型」の配送のフォームが提供しますが、ちょうどcommunica- tionが行われたようにグループ会員資格が変化したなら過程のグループのメンバーがメッセージを受け取らなかった可能性と共にあります。 そのような出来事の面前で確かに振る舞わなければならないイシスに対する私たちのオリジナルの仕事における原始のこの種類を使用しようとしたとき、私たちはアプリケーションレベルでこの局面を記述しなければなりませんでした。 結果として起こるソフトウェアは複雑でした、不鮮明なバグで推論して、満ちるのが難しく、私たちは結局、実行不可能であるとしてやむを得ず全体のアプローチを捨てました。
A wide range of reliable communication primitives have been proposed in the literature, and we became convinced that by using them, the complexity of our software could be greatly reduced. These range
さまざまな信頼できるコミュニケーション基関数が文学で提案されました、そして、私たちはそれらを使用することによって、私たちのソフトウェアの複雑さが大いに減少するかもしれないと確信するようになりました。 これらは及びます。
Birman & Joseph [Page 2] RFC 992 November 1986
バーマンとジョゼフ[2ページ]RFC992 1986年11月
from reliable and atomic broadcast [Chang] [Cristian] [Schneider] to Byzantine agreement [Strong]. For several reasons, however, the ex- isting work does not solve the problem at hand. The most obvious is that they do not provide a mechanism for sending a message to all the members of a group when the membership is changing dynamically (the "group addressing" problem). In addition, one can identify delivery ordering issues and questions regarding the detection of communica- tion failures that should be handled within the broadcast mechanism. These motivate a careful reexamination of the entire reliable broad- cast problem.
信頼できて原子の放送[チャン][クリスチャン][シュナイダー]から込み入った協定[強い]まで。 いくつかの理由で、しかしながら、仕事をistingする元の連れ合いは当面の問題を解決しません。 最も明白であるのは、彼らが会員資格がダイナミックに変化することであるとき(「グループ・アドレッシング」問題)グループのすべてのメンバーにメッセージを送るのにメカニズムを提供しないということです。 さらに、1つは放送メカニズムの中で扱われるべきであるcommunica- tionの故障の検出に関する問題と質問を注文する配送を特定できます。 これらは全体の信頼できる広いキャスト問題の慎重な再検討を動機づけます。
The multicast primitives we report here are designed to respect several sorts of ordering constraints, and have cost and latency that varies depending on the nature of the constraint required [Birman-b] [Joseph-a] [Joseph-b]. Failure and recovery are integrated into the communication subsystem by treating these events as a special sort of multicast issued on behalf of a process that has failed or recovered. The primitives are presented in the context of fault tolerant process groups: groups of processes that cooperate to implement some distri- buted algorithm or service, and which need to see consistent order- ings of system events in order to achieve mutually consistent behavior. Such groups are similar to the host groups of the V system and the ones described in RFC's 966 and 988, but provide guarantees of consistency in just the situations where a host group provides a "best effort" delivery which may sometimes be erroneous.
私たちが数種類の注文規制を尊敬して、規制の本質によって、異なる費用と潜在を持つように設計されていると報告するマルチキャスト基関数が必要です[バーマンb][ジョゼフ-a][ジョゼフ-b]。 失敗と回復は、失敗した過程を代表して発行された特殊活字のマルチキャストとしてこれらの出来事を扱うことによってコミュニケーションサブシステムと統合されるか、または回復されます。 基関数はフォルト・トレラントの過程グループの文脈に提示されます: 協力して、何らかのdistri- butedアルゴリズムかサービスを実行して、互いに一貫した振舞いを達成するためにシステムイベントの一貫したオーダーingsを見る必要がある過程のグループ。 そのようなグループはVシステムのホストグループとRFCの966と988で説明されたものと同様ですが、ホストグループが時々誤るかもしれない「ベストエフォート型」の配送を提供するところにまさしく状況における、一貫性の保証を提供してください。
It is helpful to think of our primitives as providing a logical or "virtual" form of reliability: rather than addressing physical delivery issues, they ensure that a client will never observe a sys- tem state "inconsistent" with the assumption that reliable delivery has occurred. Readers familiar with serializability theory may want to think of this as a weaker analog: in serializability, one allows interleaved executions of operations provided that the resulting sys- tem state is consistent with the assumption that execution was sequential. Similarly, reliable communication primitives permit de- viations from the reliable delivery abstraction provided that the resulting system state is indistinguishable from one in which reli- able delivery actually did occur.
論理的であるか「仮想」のフォームの信頼性を提供すると私たちの基関数を考えるのは役立っています: 物理的な配送問題を記述するよりむしろ、それらは、クライアントが信頼できる配信が起こったという仮定に「矛盾した」sys- tem状態を決して観測しないのを確実にします。 serializability理論に詳しい読者は、より弱いアナログとしてこれを考えたがっているかもしれません: serializabilityでは、結果として起こるsys- tem状態が実行が連続したという仮定と一致していれば、1つは操作のはさみ込まれた実行を許容します。 同様に、結果として起こるシステム状態がreliのできる配送が実際に起こったものから区別がつかなければ、信頼できるコミュニケーション基関数は信頼できる配信抽象化から反-viationsを可能にします。
Using our primitives, the ISIS system achieved both high levels of concurrency and suprisingly good performance. Equally important, its structure was made suprisingly simple, making it feasible to reason about the correctness of the algorithms that are needed to maintain high availability even when failures, recoveries, or process migra- tion occurs. More recently, we have applied the same approach to a variety of other problems in distributed computing, and even designed a consistent, fault tolerant, distributed bulletin board data struc- ture (a generalized version of the blackboards used in artificial in- telligence programs), with equally good results [Birman-c]. Thus, we feel that the approach has been shown to work in a variety of set- tings where unreliable primitives simply could not be used.
私たちの基関数を使用して、イシスシステムは高いレベルで合意とsuprisingly望ましい市場成果の両方を実現しました。 等しく、重要です、構造をsuprisinglyに簡単にしました、失敗でさえあるときに、高い有用性を維持するのに必要であるアルゴリズムの正当性に関して推論するのを可能にして、回復、または、過程migra- tionは現れます。 より最近、私たちは、分散コンピューティングにおける他のさまざまな問題への同じアプローチを適用して、一貫していた状態でaを設計さえしました、フォルト・トレラントです、分配された掲示板のデータstruc- ture(人工のコネtelligenceプログラムで使用される黒板の一般化されたバージョン)、等しく良い結果[バーマンc]で。 したがって、私たちは、アプローチがあてにならない基関数を絶対に使用できなかったところでさまざまなセットチリンチリンで働くために示されたと感じます。
Birman & Joseph [Page 3] RFC 992 November 1986
バーマンとジョゼフ[3ページ]RFC992 1986年11月
In the remainder of this memo we summarize the issues and alterna- tives that the designer of a distributed system is presented with, focusing on two styles of support for fault-tolerant computing: re- mote procedure calls coupled with a transactional execution facility, such as is used in the ARGUS system [Liskov], and the fault-tolerant process group mechanism mentioned above. We argue that transactional interactions are too restrictive to support the sort of mechanism needed, and then show how our primitives can be used to provide such a mechanism. We conclude by speculating on future directions in which this work might be taken.
このメモの残りでは、私たちは分散システムのデザイナーが与えられる問題とalterna- tivesをまとめます、フォールトトレラントコンピューティングのための2つのスタイルのサポートに焦点を合わせて: 再ちりの手順呼び出しはアルゴスシステム[Liskov]、および前記のようにフォールトトレラント過程グループメカニズムで使用されるような取引の死刑執行施設に結合しました。 私たちは、取引の相互作用がメカニズムの種類が必要としたサポートに制限し過ぎていると主張して、次に、そのようなメカニズムを提供するのにどう私たちの基関数を使用できるかを示しています。 私たちは、この仕事が取られるかもしれない将来の方向を推測することによって、結論を下します。
4. Issues in fault-tolerance
4. 耐障害性における問題
The difficulty of constructing fault-tolerant distributed software can be traced to a number of interrelated issues. The list that fol- lows is not exhaustive, but attempts to touch on the principal con- siderations that must be addressed in any such system:
フォールトトレラントの分配されたソフトウェアを構成するという困難を多くの相関的な問題にたどることができます。 安値をfolするリストは、徹底的ではありませんが、どんなそのようなシステムでも記述しなければならない主要なまやかし発症に触れるのを試みます:
[1]Synchronization. Distributed systems offer the potential for
large amounts of concurrency, and it is usually desirable to
operate at as high a level of concurrency as possible. However,
when we move from a sequential execution environment to a con-
current one, it becomes necessary to synchronize actions that may
conflict in their access to shared data or entail communication
with overlapping sets of processes. Thus, a mechanism is needed
for ordering conflicting events. Additional problems that can
arise in this context include deadlock avoidance or detection,
livelock avoidance, etc.
[1] 同期。 分散システムは多量の合意の可能性を提供します、そして、通常、合意のできるだけ高いレベルで作動するのは望ましいです。 しかしながら、私たちが連続した実行環境から現在のまやかしものまで移ると、過程のセットを重ね合わせるのにデータを共有するか、またはコミュニケーションを伴うために彼らのアクセスで闘争するかもしれない動作を同時にさせるのは必要になります。 したがって、メカニズムが闘争に出来事を命令するのに必要です。 起こることができる追加問題はこのような関係においてはデッドロック回避や検出、livelock回避などを含んでいます。
[2]Failure detection. It is usually necessary for a fault-
tolerant application to have a consistent picture of which com-
ponents fail, and in what order. Timeout, the most common mechan-
ism for detecting failure, is unsatisfactory, because there are
many situations in which a healthy component can timeout with
respect to one component without this being detected by some
another. Failure detection under more rigorous requirements
requires an agreement protocol that is related to Byzantine agree-
ment [Strong] [Hadzilacos]. Regardless of how this problem is
solved, some sort of reliable failure detection mechanism will be
needed in any fault-tolerant distributed system.
[2] 失敗検出。 通常、欠点の許容性があるアプリケーションにはどのcom- ponentsが失敗して、何で注文されるかに関する一貫した絵があるのが必要です。 タイムアウト(失敗を検出するための最も一般的なmechan主義)は不十分です、これのないいくつかによる別のもので検出されるあるコンポーネントに関してどのa健康なコンポーネント缶のタイムアウトに多くの状況があるかので。 より厳しい要件の下における失敗検出はビザンティウムの人と関係があるプロトコルが[強い]でmentに同意するという協定[Hadzilacos]を必要とします。 この問題がどう解決されているかにかかわらず、ある種の信頼できる失敗検出メカニズムがどんな無停止分散システムでも必要でしょう。
[3] Consistency. When a group of processes cooperate in a distri-
buted system, it is necessary to ensure that the operational
processes have consistent views of the state of the group as a
whole. For example, if process p believes that some property A
holds, and on the basis of this interacts with process q, the
state of q should not contradict the fact that p believes A to be
true. This problem is closely related to notions of knowledge and
consistency in distributed systems [Halpern] [Lamport]. In our
context, A will often be the assertion that a multicast has been
received by q, or that q saw some sequence of events occur in the
[3] 一貫性。 過程のグループがdistri- butedシステムと協調するとき、グループ全体の状態の一貫した視点が操作上の過程にあるのを保証するのが必要です。 例えば、過程pが、何らかの特性Aが過程qと保って、これに基づいて対話すると信じているなら、qの状態はpが、Aが本当であると信じているという事実に矛盾するべきではありません。 この問題は密接に分散システム[アルペルン]における知識と一貫性の概念に関連します[ランポート]。 私たちの文脈では、しばしばAはqでマルチキャストを受け取ったか、またはqが、出来事の何らかの系列が中に起こるのを見たという主張でしょう。
Birman & Joseph [Page 4] RFC 992 November 1986
バーマンとジョゼフ[4ページ]RFC992 1986年11月
same order as did p. Thus, it is necessary to be able to specify
the precise consistency constraints on a distributed software sys-
tem, and system support should be available to facilitate the
attainment of these constraints.
pのような同じオーダー。 したがって、分配されたソフトウェアsys- temで正確な一貫性制約を指定できるのが必要であり、システム支援は、これらの規制の到達を容易にするために利用可能であるべきです。
[4] Serializability. Many distributed systems are partitioned
into data manager processes, which implement shared variables, and
transaction manager processes, which issue requests to data
managers [Bernstein]. If transaction managers can execute con-
currently, it is desirable to ensure that transactions produce
serializable outcomes [Eswaren] [Papadimitrou]. Serializability
is increasingly viewed as an important property in "object-
oriented" distributed systems that package services as abstract
objects with which clients communicate by remote procedure calls
(RPC). On the other hand, there are systems for which serializa-
bility is either too strong a constraint, or simply inappropriate.
Thus, one needs a way to achieve serializability in applications
where it will be needed, without imposing system-wide restrictions
that would prevent the design of software subsystems for which
serializability is not needed.
[4] Serializability。 多くの分散システムがデータ管理ソフトウェアの過程と取引マネージャの過程に仕切られます。(過程は共用変数を実行します)。(過程はデータ管理ソフトウェア[バーンスタイン]に要求を出します)。 取引マネージャが現在まやかしを実行できるなら、取引が直列化可能結果[Eswaren][Papadimitrou]を作り出すのを保証するのは望ましいです。 Serializabilityはますます重要な特性として遠隔手続き呼び出し(RPC)でクライアントが交信する抽象的な物としてサービスをパッケージする「物の指向」の分散システムで見なされます。 他方では、serializa- bilityがどれであるかには、強過ぎる規制であるか、または単に不適当なシステムは、あります。 したがって、人はそれが必要であるアプリケーションでserializabilityを達成する方法を必要とします、serializabilityが必要でないソフトウェアサブシステムのデザインを防ぐシステム全体の制限を課さないで。
Jointly, these problems render the design of fault-tolerant distri- buted software daunting in the absence of adequate support. The correctness of any proposed design and of its implementation become serious, if not insurmountable, concerns. In Sec. 7, we will show how the primitives of Sec. 6 provide simple ways to overcome all of these issues.
共同で、これらの問題は適切が不在のときサポートを威圧するフォールトトレラントdistri- butedソフトウェアの設計をレンダリングします。 どんな提案されたデザインとその実現の正当性も重大であるか、打ち勝ちがたい関心になります。 秒のときに 7 私たちはSecに関する基関数をどのようにに示すつもりであるか。 6はこれらの問題のすべてに打ち勝つ簡単な方法を提供します。
5. Existing alternatives
5. 既存の代替手段
If one rules out "unreliable" communication mechanisms, there are basically two fault-tolerant alternatives that can be pursued.
人が「頼り無い」コミュニケーションメカニズムを除外するなら、追求できる2つのフォールトトレラント選択肢が基本的にあります。
The first approach is to provide mechanisms for transactional interactions between processes that communicate using remote pro- cedure calls [Birrell]. This has lead to work on nested transactions (due to nested RPC's) [Moss], support for transactions at the language level [Liskov], transactions within an operating systems kernel [Spector] [Allchin] [Popek] [Lazowska], and transactional access to higher-level replicated services, such as resilient objects in ISIS or relations in database systems. The primitives in a tran- sactional system provide mechanisms for distributing the request that initiates the transaction, accessing data (which may be replicated), performing concurrency control, and implementing commit or abort. Additional mechanisms are normally needed for orphan termination, deadlock detection, etc. The issue then arises of how these mechan- isms should themselves be implemented.
最初のアプローチはリモート親cedure要求[ビレル]を使用することで交信する過程の間の取引の相互作用にメカニズムを提供することです。 これには、入れ子にされた取引(入れ子にされたRPCのものによる)こけを扱うリードがあります、言語水準Liskovでの取引のサポート、オペレーティングシステムカーネルスペクターAllchin Popek Lazowskaの中の取引、そして、よりハイレベルへの取引のアクセスはサービスを模写しました、イシスの弾力がある物やデータベース・システムにおける関係のように; tran- sactionalシステムの基関数が取引を開始する要求を広げるのにメカニズムを提供して、データ(模写されるかもしれない)にアクセスする、合意コントロールを実行して、および実行は、公約するか、または中止になります。 通常、追加メカニズムが親のない終了、デッドロック検出などに必要です。 これらが主義をmechanするその時が起こる問題がそうするべきである、自分たち、実行されてください。
Our work in ISIS leads us to believe that whereas transactions are easily implemented on top of fault-tolerant process groups -- we have done so -- the converse is much harder. Moreover, transactions
取引はフォールトトレラント過程グループの上で容易に実行されます--私たちはそうしました--イシスでの私たちの仕事は、私たちがそれを信じているように導きますが、逆ははるかに困難です。 そのうえ、取引
Birman & Joseph [Page 5] RFC 992 November 1986
バーマンとジョゼフ[5ページ]RFC992 1986年11月
represent a relatively heavy-weight solution to the problems surveyed in the previous section, and might impose an unacceptable overhead on subsystems that need to run non-transactionally, for example because a pair of concurrent processes needs to interact on a frequent basis. (We are not saying that "transactional" mechanisms such as cobegins and toplevel actions can't solve this problem, but just that they yield a solution that is awkward and costly). This sort of reasoning has lead us to focus on non-transactional interaction mechanisms, and to treat transactions as a special class of mechanisms used when processes that have been designed to employ a transactional protocol interact.
例えば、1組の並行処理が、頻繁ベースで相互作用する必要があるので、前項で調査された問題の比較的ヘビー級の解決を表して、非取引を走らせる必要があるサブシステムに容認できないオーバーヘッドを課すかもしれません。 (私たちはcobeginsやtoplevel動作などの「取引」のメカニズムはこの問題を解決できるのではなく、まさしくそれを解決すると言わないで、厄介で高価な解決策をもたらすということです。) この種類の推理は私たちが非取引の相互作用メカニズムに焦点を合わせて、取引のプロトコルを使うように設計されている過程が相互作用するとき使用される特別なクラスのメカニズムとして取引を扱うように導かせます。
The second approach involves the provision of a communication primi- tive, such as atomic broadcast, which can be used as the framework on which higher level algorithms are designed. Such a primitive seeks to deliver messages reliably to some set of destinations, despite the possibility that failures might occur during the execution of the protocol. Above, we termed this the fault tolerant process group approach, since it lends itself to the organization of cooperating processes into groups, as described in the introduction. Process groups are an extremely flexible abstraction, and have been employed in the V Kernel [Cheriton] and in UNIX, and more recently in the ISIS system. A proposal to provide Internet support for host groups was raised in RFC's 966 and 988. However, the idea of adapting the pro- cess group approach to work reliably in an environment subject to the sorts of exception events and concurrency cited in the previous sec- tion seems to be new.
2番目のアプローチはコミュニケーションprimi- tiveの設備にかかわります、原子放送などのように。(より高い平らなアルゴリズムが設計されている枠組みとしてそれを使用できます)。 何らかのセットの送付先にメッセージを確かに届けるそのようなa原始のシーク、可能性にもかかわらず、その失敗力はプロトコルの実行の間起こります。 上では、私たちがフォルト・トレラントの過程グループアプローチとこれを呼びました、協調処理の組織にグループに適しているので、序論で説明されるように。 過程グループは、非常にフレキシブルな抽象化であり、V Kernel[Cheriton]、UNIX、および最近、イシスシステムのその他で使われました。 ホストグループのインターネットサポートを提供するという提案はRFCの966と988で提起されました。 しかしながら、前の秒のtionで引用された例外出来事と合意の種類を条件として環境で確かに働くために親課税グループアプローチを適合させるという考えは新しいように思えます。
As noted earlier, existing reliable communication protocols do not address the requirements of fault-tolerant process groups. For exam- ple, in [Schneider], an implementation of a reliable multicast primi- tive is described. Such a primitive ensures that a designated mes- sage will be transmitted from one site to all other operational sites in a system; if a failure occurs but any site has received the mes- sage, all will eventually do so. [Chang] and [Cristian] describe implementations for atomic broadcast, which is a reliable broadcast (sent to all sites in a system) with the additional property that messages are delivered in the same order at all overlapping destina- tions, and this order preserves the transmission order if messages originate in a single site.
より早く注意されるように、既存の信頼できる通信プロトコルはフォールトトレラント過程グループの要件を記述しません。 試験pleに関しては、[シュナイダー]では、信頼できるマルチキャストprimi- tiveの実現は説明されます。 基関数がmes賢人に指定されたそのaを確実にするそのようなaはシステムで、あるサイトから操作上の他のすべてのサイトまで送られるでしょう。 失敗が起こりますが、どれかサイトがmes賢人を受けたなら、すべてが結局、そうするでしょう。 [チャン]と[クリスチャン]はメッセージがdestina- tionsを全く重ね合わせる同次で渡される追加特性で信頼できる放送(システムのすべてのサイトに発信する)である原子放送のための実現について説明します、そして、メッセージがただ一つのサイトで起こるなら、このオーダーはトランスミッション命令を保存します。
Atomic broadcast is a powerful abstraction, and essentially the same behavior is provided by one of the multicast primitives we discuss in the next section. However, it has several drawbacks which made us hesitant to adopt it as the only primitive in the system. Most seri- ous is the latency that is incurred in order to satisfy the delivery ordering property. Without delving deeply into the implementations, which are based on a token scheme in [Chang] and an acknowledgement protocol in [Schneider], we observe that the delaying of certain mes- sages is fundamental to the establishment of a unique global delivery ordering; indeed, it is easy to prove on knowledge theoretic grounds
原子放送は強力な抽象化です、そして、私たちが次のセクションで議論するマルチキャスト基関数の1つで本質的には同じ振舞いを提供します。 しかしながら、それには、私たちを単にシステムの原始としてそれを採用するのをためらうようにしたいくつかの欠点があります。 ほとんどのseri- ousが特性を注文する配送を満たすために被られる潜在です。 [チャン]での象徴計画と[シュナイダー]の承認プロトコルに基づいている実現に深く探求しないで、私たちは、確信しているmes賢人の延着がユニークなグローバルな配送注文の設立に基本的であることを観測します。 本当に、知識で理論的な根拠を立証するのは簡単です。
Birman & Joseph [Page 6] RFC 992 November 1986
バーマンとジョゼフ[6ページ]RFC992 1986年11月
that this must always be the case. In [Chang] a primary goal is to minimize the number of messages sent, and the protocol given performs extremely well in this regard. However, a delay occurs while waiting for tokens to arrive and the delivery latency that results may be high. [Cristian] assumes that clocks are closely synchronized and that message transit times are bounded by well-known constants, and uses this to derive atomic broadcast protocols tolerant of increas- ingly severe classes of failures. The protocols explicitly delay delivery to achieve the desired global ordering on multicasts. For reasons discussed below, this tends to result in high latency in typ- ical local networking environments. An additional drawback of the atomic broadcast protocols is that no mechanism is provided for ensuring that all processes observe the same sequence of failures and recoveries, or for ensuring that failures and recoveries are ordered relative to ongoing multicasts. Since this problem arises in any setting where one process monitors another, we felt it should be addressed at the same level as the communication protocol. Finally, one wants a group oriented multicast protocol, not a site oriented broadcast, and this issue must be resolved too.
これはいつもそうであるに違いありません。 [チャン]では、第一の目標が送られたメッセージの数を最小にすることであり、与えられたプロトコルは非常によくこの点で働きます。 しかしながら、象徴が届くのを待っている間、遅れは起こります、そして、結果として生じる配送潜在は高いかもしれません。 [クリスチャン]が、時計が密接に連動すると仮定して、トランジット時間があるというそのメッセージは、increas- inglyの厳しいクラスの失敗において許容性がある原子放送プロトコルを引き出すのに周知の定数でバウンドして、これを使用します。 プロトコルは、マルチキャストで必要なグローバルな注文を達成するために明らかに配送を遅らせます。 以下で議論した理由で、これは、typ- icalの地方のネットワーク環境における高い潜在をもたらす傾向があります。 原子放送プロトコルの追加欠点はすべての過程が失敗と回復の同じ系列を観測するのを確実にするか、または失敗と回復が進行中のマルチキャストに比例して命令されるのを確実にするのにメカニズムを全く提供しないということです。 以来、この問題は1つの過程が別のものをモニターするどんな設定でも起きて、私たちは、それが通信プロトコルと同じレベルで記述されるべきであると感じました。 最終的に、人はグループの指向のマルチキャストプロトコルが欲しいです、そして、どんなサイトも放送を適応させませんでした、そして、また、この問題を解決しなければなりません。
6. Our multicast primitives
6. 私たちのマルチキャスト基関数
We now describe three multicast protocols - GBCAST, ABCAST, and CBCAST - for transmitting a message reliably from a sender process to some set of destination processes. Details of the protocols and their correctness proofs can be found in [Birman-b]. The protocols ensure "all or nothing" behavior: if any destination receives a mes- sage, then unless it fails, all destinations will receive it. Group addressing is discussed in Sec. 6.5.
私たちは、現在、確かに送付者の過程から何らかのセットの目的地の過程まで送信するために、3つのマルチキャストプロトコル(GBCAST、ABCAST、およびCBCAST)について説明します。 [バーマンb]でプロトコルの詳細とそれらの正当性の証明を見つけることができます。 プロトコルは「すべてか何でもない」に振舞いを確実にします: どんな目的地もmes賢人を受けて、失敗しないと、すべての目的地がそれを受けるでしょう。 Secでグループ・アドレッシングについて議論します。 6.5.
The failure model that one adopts has a considerable impact on the structure of the resulting system. We adopted the model of fail-stop processors [Schneider]: when failures occur, a processor simply stops (crashes), as do all the processes executing on it. We also assume that individual processes can crash, and that this is detected when it occurs by a monitoring mechanism present at each site. Further assumptions are sometimes made about the availability of synchronized realtime clocks. Here, we adopt the position that although reason- ably accurate elapsed-time clocks may be available, closely synchron- ized clocks probably will not be. For example, the 60Hz "line" clocks commonly used on current workstations are only accurate to 16ms. On the other hand, 4-8ms inter-site message transit times are common and 1-2ms are reported increasingly often. Thus, it is impos- sible to synchronize clocks to better than 32-48ms, enough time for a pair of sites to exchange between 4 and 50 messages. Even with advancing technology, it seems safe to assume that clock skew will remain "large" when compared to inter-site message transmission speed. In particular, this argues against time-based protocols such as the one used in [Cristian]
1つが採用する失敗モデルは結果として起こるシステムの構造にかなりの影響力を持っています。 私たちは停止に失敗したプロセッサ[シュナイダー]のモデルを採用しました: 失敗が起こると、プロセッサはそれで実行されるすべての過程のように単に止まります(墜落します)。 また、私たちは、独特の過程がクラッシュできて、各サイトの現在の監視メカニズムで起こるときこれが検出されると思います。 さらなる仮定は時々連動しているリアルタイムで時計の有用性に関してされます。 ここに、私たちは理由りっぱに正確な経過時間時計が利用可能であるかもしれませんが、密接に、synchron- ized時計がたぶん利用可能であるというわけではないという位置を採用します。 1-2 例えば、現在のワークステーションの上で一般的に使用される60Hzの「線」時計は単に他が手渡す16ms. Onに正確です、そして、4-8 ms相互サイトメッセージトランジット回数は一般的です、そして、msはますますしばしば報告されます。 したがって、それは時計を32-48 msより良く、1組のサイトが4〜50のメッセージを交換できるくらいの時間まで連動させるimpos- sibleです。 技術を進めさえしても、相互サイトメッセージ伝送速度と比べると時計斜行が「大きい」ままで残ると仮定するのは安全に思えます。 特に、これは中で使用されたものなどの時間ベースのプロトコルについて反対の議論をします。[クリスチャン]
Birman & Joseph [Page 7] RFC 992 November 1986
バーマンとジョゼフ[7ページ]RFC992 1986年11月
6.1 The GBCAST primitive
6.1 GBCAST基関数
GBCAST (group multicast) is the most constrained, and costly, of
the three primitives. It is used to transmit information about
failures and recoveries to members of a process group. A recov-
ering member uses GBCAST to inform the operational ones that it
has become available. Additionally, when a member fails, the
system arranges for a GBCAST to be issued to group members on its
behalf, informing them of its failure. Arguments to GBCAST are a
message and a process group identifier, which is translated into
a set of destinations as described below (Sec. 6.5).
GBCAST(グループマルチキャスト)は3つの基関数で最も強制的であって、高価です。 それは、失敗と回復の情報を過程グループのメンバーに伝えるのに使用されます。 recov- eringメンバーは、それが利用可能になったことを操作上のものに知らせるのにGBCASTを使用します。 さらに、メンバーが失敗すると、システムは、GBCASTがそのに代わってメンバーを分類するために発行されるように手配します、失敗について彼らを知らせて。 GBCASTへの議論は、メッセージと過程グループ識別子です。(その識別子は以下で説明されるように1セットの目的地に翻訳されます)。(秒 6.5).
Our GBCAST protocol ensures that if any process receives a multi-
cast B before receiving a GBCAST G, then all overlapping destina-
tions will receive B before G <1> This is true regardless of the
type of multicast involved. Moreover, when a failure occurs, the
corresponding GBCAST message is delivered after any other multi-
casts from the failed process. Each member can therefore main-
tain a VIEW listing the membership of the process group, updating
it when a GBCAST is received. Although VIEW's are not updated
simultaneously in real time, all members observe the same
sequence of VIEW changes. Since, GBCAST's are ordered relative
to all other multicasts, all members receiving a given multicast
will have the same value of VIEW when they receive it.
私たちのGBCASTプロトコルは、何か過程がマルチキャストを受けるとG<1>Thisがマルチキャストのかかわったタイプにかかわらず本当になる前に次に、GBCAST Gを受けて、destina- tionsをすべて重ね合わせる前のBがBを受けるのを確実にします。 失敗が起こるとき、そのうえ、いかなる他のマルチキャストの後にも失敗した過程から対応するGBCASTメッセージを送ります。 過程の会員資格を記載するそれぞれのメンバーの缶のしたがって、主なtain a VIEWが分類します、GBCASTが受け取られているとき、それをアップデートして。 リアルタイムで同時にVIEWのものをアップデートしませんが、すべてのメンバーがVIEW変化の同じ系列を観測します。 以来、他のすべてのマルチキャストに比例してGBCASTのものを注文して、彼らがそれを受けるとき、与えられたマルチキャストを受けるすべてのメンバーがVIEWの同じ値を持つでしょう。
Notice that GBCAST also provides a convenient way to change other
global properties of a group "atomically". In our work, we have
used GBCAST to dynamically change a ranking on the members of a
group, to request that group members establish checkpoints for
use if recovery is needed after all failure, and to implement
process migration. In each case, the ordering of GBCAST relative
to other events that makes it possible to perform the desired
action without running any additional protocol. Other uses for
GBCAST will no doubt emerge as our research continues.
また、GBCASTが「原子論的に」グループの他の巨視的性質を変える便利な方法を提供するのに注意してください。 仕事では、私たちは、グループのメンバーでダイナミックにランキングを変えて、回復がすべての失敗の後に必要であるならグループのメンバーが使用のためにチェックポイントを確立するよう要求して、過程移動を実行するのにGBCASTを使用しました。 その都度他の出来事に比例したどんな追加議定書も走らせないで必要な動作を実行するのを可能にするGBCASTの注文。 私たちの研究が続くようにGBCASTへの他の用途は間違いなく現れるでしょう。
Members of a process group can also use the value of VIEW to pick
a strategy for processing an incoming request, or to react to
failure or recovery without having to run any special protocol
first. Since the GBCAST ordering is the same everywhere, their
actions will all be consistent. Notice that when all the members
of a process group may have failed, GBCAST also provides an inex-
pensive way to determine the last site that failed: process group
members simply log each value of VIEW that becomes defined on
stable storage before using it; a simplified version of the algo-
rithm in [Skeen-a] can then be executed when recovering from
failure.
また、過程グループのメンバーは、処理のための戦略に入って来る要求を選ぶか、または最初にどんな特別なプロトコルも走らせる必要はなくて失敗か回復に反応するのにVIEWの値を使用できます。 GBCAST注文がいたる所で同じであるので、彼らの動作はすべて一貫するでしょう。 また、過程グループのすべてのメンバーが失敗したときGBCASTが失敗した最後のサイトを決定するinexの物思わしげな方法を提供するのに注意してください: 過程グループのメンバーは単にそれを使用する前に安定貯蔵のときに定義されるようになるVIEWの各値を登録します。 そして、失敗から回復するとき、[Skeen-a]の痛rithmの簡易型のバージョンを実行できます。
Birman & Joseph [Page 8] RFC 992 November 1986
バーマンとジョゼフ[8ページ]RFC992 1986年11月
6.2 The ABCAST primitive
6.2 ABCAST基関数
The GBCAST primitive is too costly to be used for general commun-
ication between process group members. This motivates the intro-
duction of weaker (less ordered) primitives, which might be used
in situations where a total order on multicast messages is not
necessary. Our second primitive, ABCAST (atomic multicast),
satisfies such a weaker constraint. Specifically, it is often
desired that if two multicasts are received in some order at a
common destination site, they be received in that order at all
other common destinations, even if this order was not predeter-
mined. For example, if a process group is being used to maintain
a replicated queue and ABCAST is used to transmit queue opera-
tions to all copies, the operations will be done in the same
order everywhere, hence the copies of the queue will remain mutu-
ally consistent. The primitive ABCAST(msg, label, dests) pro-
vides this behavior. Two ABCAST's having the same label are
delivered in the same order at all common destinations.
GBCAST、基関数が一般にcommunに使用できないくらい高価である、過程グループのメンバーの間で。 これは、より弱い(それほど命令されなかった)基関数の序奏ductionを動機づけます。(基関数はマルチキャストメッセージに関する注文合計が必要でない状況で使用されるかもしれません)。 私たちの2番目の基関数(ABCAST(原子マルチキャスト))はそのようなより弱い規制を満たします。 明確に、しばしば中に2つのマルチキャストを受け取るなら或るものが一般的な目的地サイトで注文されることが望まれている、それら、他のすべての一般的な目的地のそのオーダーに受け取ってください、このオーダーが採掘されたpredeterでなかったとしても。 例えば、模写された待ち行列を維持するのに過程グループを使用していて、待ち行列オペラtionsをすべてのコピーに伝えるのにABCASTを使用すると、いたる所で同次で操作するでしょう、したがって、待ち行列のコピーはmutu同盟国一貫していたままで残るでしょう。 原始のABCAST(msg、ラベル、dests)、親、参照、この振舞い。 すべての一般的な目的地の同次でABCASTが同じくらいにラベルさせる2を送ります。
6.3 The CBCAST primitive
6.3 CBCAST基関数
Our third primitive, CBCAST (causal multicast), is weakest in the
sense that it involves less distributed synchronization then
GBCAST or ABCAST. CBCAST(msg, dests) atomically delivers msg to
each operational dest. The CBCAST protocol ensures that if two
multicasts are potentially causally dependent on another, then
the former is delivered after the latter at all overlapping des-
tinations. A multicast B' is potentially causally dependent on a
multicast B if both multicasts originate from the same process,
and B' is sent after B, or if there exists a chain of message
transmissions and receptions or local events by which knowledge
could have been transferred from the process that issued B to the
process that issued B' [Lamport]. For causally independent mul-
ticasts, the delivery ordering is not constrained.
私たちの3番目の基関数(CBCAST(原因のマルチキャスト))がそれほど分配されなかった同期の当時のGBCASTにかかわるという意味が最も苦手であるか、またはABCAST. CBCAST(msg、dests)は原子論的にそれぞれの操作上のdestにmsgを渡します。 CBCASTプロトコルは、2つのマルチキャストに潜在的に別のものに原因となって依存しているなら前者が全く後者の後にdes- tinationsを重ね合わせながら送られるのを確実にします。 両方のマルチキャストが同じ過程から発して、Bの後にB'を送るか、または知識がBを発行した過程からB'[ランポート]を発行した過程まで移されたかもしれないメッセージ送信とレセプションかローカルイベントのチェーンが存在するなら、'マルチキャストB'は潜在的にマルチキャストBに原因となって依存しています。 原因となって独立しているmul- ticastsに関しては、配送注文は強制的ではありません。
CBCAST is valuable in systems like ISIS, where concurrency con-
trol algorithms are used to synchronize concurrent computations.
In these systems, if two processes communicate concurrently with
the same process the messages are almost always independent ones
that can be processed in any order: otherwise, concurrency con-
trol would have caused one to pause until the other was finished.
On the other hand, order is clearly important within a causally
linked series of multicasts, and it is precisely this sort of
order that CBCAST respects.
CBCASTはイシス、アルゴリズムが同時発生の計算を同時にさせるのに使用されるというどこ合意まやかしtrolのようなシステムで貴重であるか。 これらのシステムでは、2つの過程が同時に同じ過程で交信するなら、メッセージは順不同に処理できるほとんどいつも独立しているものです: さもなければ、もう片方が終わるまで、合意まやかしtrolは1つを止まらせたでしょう。 他方では、オーダーは原因となって繋がっているシリーズのマルチキャストの中で明確に重要です、そして、それは正確にCBCASTが尊敬するこの種類の注文です。
6.4 Other multicast primitives
6.4 他のマルチキャスト基関数
A weaker multicast primitive is reliable multicast, which pro-
vides all-or-nothing delivery, but no ordering properties. The
formulation of CBCAST in [Birman-b] actually includes a mechanism
for performing multicasts of this sort, hence no special
Aより弱いマルチキャスト原始的であるのが、信頼できるマルチキャストである、どれ、親、参照、オール、無、配送ですが、注文していない特性。 [バーマンb]でのCBCASTの定式化は実際にしたがって、この種類、特別番組がないマルチキャストを実行するためのメカニズムを含んでいます。
Birman & Joseph [Page 9] RFC 992 November 1986
バーマンとジョゼフ[9ページ]RFC992 1986年11月
primitive is needed for the purpose. Additionally, there may be
situations in which ABCAST protocols that also satisfy a CBCAST
ordering property would be valuable. Our ABCAST primitive could
be changed to respect such a rule, and we made use of a multicast
primitive that is simultaneously causal and atomic in our work on
consistent shared bulletin boards ([Birman-c]). For simplicity,
the presentation here assumes that ABCAST is completely orthogo-
nal to CBCAST, but a simple way to build an efficient "causal
atomic" multicast is described in our full-length paper. The
cost of this protocol is only slightly higher than that of
ABCAST.
基関数が目的に必要です。 さらに、また、特性を注文するCBCASTを満たすABCASTプロトコルが貴重である状況があるかもしれません。 そのような規則を尊敬するために私たちのABCAST基関数を変えることができました、そして、私たちは一貫した共有された掲示板([バーマンc])への私たちの作業で同時に、原因であって原子であるマルチキャスト基関数を利用しました。 簡単さのために、ここでのプレゼンテーションが、しかし、ABCASTが完全にCBCASTへのorthogo- nal、建てる簡単な方法であると仮定する、効率的である、「原因、原子、」 マルチキャストは私たちの省略のない紙で説明されます。 このプロトコルの費用はABCASTのものよりわずかにだけ高いです。
6.5 Group addressing protocol
6.5 グループ・アドレッシングプロトコル
Since group membership can change dynamically, it may be diffi-
cult for a process to compute a list of destinations to which a
message should be sent, for example, as is needed to perform a
GBCAST. In [Birman-b] we report on a protocol for ensuring that
a given multicast will be delivered to all members of a process
group in the same view. This view is either the view that was
operative when the message transmission was initiated, or a view
that was defined subsequently. The algorithm is a simple itera-
tive one that costs nothing unless the group membership changes,
and permits the caching of possibly inaccurate membership infor-
mation near processes that might want to communicate with a
group. Using the protocol, a flexible message addressing scheme
can readily be supported.
グループ会員資格がダイナミックに変化できるので、それは過程が例えばGBCASTを実行するのが必要である場合メッセージがそのままで送られるべきである目的地のリストを計算するためにはdiffiカルトであるかもしれません。[バーマンb]では、私たちは、与えられたマルチキャストが同じ視点における過程グループのすべてのメンバーに送られるのを確実にするためにプロトコルに関して報告します。 この視点は、メッセージ送信が開始されたとき影響を及ぼしている視点か次に定義された視点のどちらかです。 アルゴリズムはグループ会員資格がほぼグループとコミュニケートしたがっているかもしれない過程でことによると不正確な会員資格infor- mationのキャッシュを変えて、可能にしない場合何もかからない簡単なitera- tive1です。 プロトコルを使用して、容易にフレキシブルなメッセージアドレシング計画を支持できます。
Iterative addressing is only required when the process transmit-
ting a message has an inaccurate copy of the process group view.
In the implementation we are now building, this would rarely be
the case, and iteration is never needed if the view is known to
be accurate. Thus, iterated delivery should be very infrequent.
繰り返しのアドレシングは過程がチリンチリンを伝えるときだけ、必要であることで、メッセージには過程グループ視点の不正確なコピーがあるということです。 実現では、私たちは現在建てています、そして、めったにこれはそうでないでしょう、そして、視点が正直なところ知られているなら、繰り返しは決して必要ではありません。 このようにして繰り返された配送は非常に珍しいはずです。
6.6 Synchronous versus asynchronous multicast abstractions
6.6 非同期なマルチキャストに対する同期の抽象化
Many systems employ RPC internally, as a lowest level primitive
for interaction between processes. It should be evident that all
of our multicast primitives can be used to implement replicated
remote procedure calls [Cooper]: the caller would simply pause
until replies have been received from all the participants
(observation of a failure constitutes a reply in this case). We
term such a use of the primitives synchronous, to distinguish it
from from an asynchronous multicast in which no replies, or just
one reply, suffices.
多くのシステムが過程の間の相互作用における、原始の最も低いレベルとして内部的にRPCを使います。 模写された遠隔手続き呼び出し[クーパー]を実行するのに私たちのマルチキャスト基関数のすべてを使用できるのは明白であるべきです: 訪問者は参加者各位から回答を受け取るまで(失敗の観測はこの場合回答を構成します)単に止まるでしょう。 私たち、基関数の用語のそのようなa使用、同時である、回答、またはちょうど1つの回答がそれのノーで十分である非同期なマルチキャストとそれを区別するために。
In our work on ISIS, GBCAST and ABCAST are normally invoked syn-
chronously, to implement a remote procedure call by one member of
an object on all the members of its process group. However,
CBCAST, which is the most frequently used overall, is almost
never invoked synchronously. Asynchronous CBCAST's are the
イシスに対する私たちの仕事では、GBCASTとABCASTは、過程グループのすべてのメンバーの上で物の1人のメンバーで遠隔手続き呼び出しを実行するためには通常、呼び出されたsyn- chronouslyです。 しかしながら、CBCAST(全体的に見て最も頻繁に使用される)はほとんど同時呼び出されません。 非同期なCBCASTのものはそうです。
Birman & Joseph [Page 10] RFC 992 November 1986
バーマンとジョゼフ[10ページ]RFC992 1986年11月
primary source of concurrency in ISIS: although the delivery ord-
ering is assured, transmission can be delayed to enable a message
to be piggybacked on another, or to schedule IO within the system
as a whole. While the system cannot defer an asynchronous multi-
cast indefinitely, the ability to defer it a little, without
delaying some computation by doing so, permits load to be
smoothed. Since CBCAST respects the delivery orderings on which
a computation might depend, and is ordered with respect to
failures, the concurrency introduced does not complicate higher
level algorithms. Moreover, the protocol itself is extremely
cheap.
イシスでの合意の一次資料: 配送ord- eringは保証されますが、トランスミッションは、別のもので背負われるか、または全体でシステムの中でIOの計画をするメッセージを可能にするために遅れることができます。 システムは整えられるために無期限に、それを少し延期する能力(延着することのないそうするのによる何らかの計算)が可能にする非同期なマルチキャスト負荷を延期できませんが。 CBCASTが計算がよるかもしれなくて、失敗に関して注文される配送受注業務を尊敬するので、導入された合意は、より高い平らなアルゴリズムを複雑にしません。そのうえ、プロトコル自体は非常に安いです。
A problem is introduced by our decision to allow asynchronous
multicasts: the atomic reception property must now be extended to
address causally related sequences of asynchronous messages. If
a failure were to result in some multicasts being delivered to
all their destinations but others that precede them not being
delivered anywhere, inconsistency might result even if the desti-
nations do not overlap. We therefore extend the atomicity pro-
perty as follows. If process t receives a message m from process
s, and s subsequently fails, then unless t fails as well, all
messages m' that s received prior to its failure must be
delivered to their remaining operational destinations. This is
because the state of t may now depend on the contents of any such
m', hence the system state could become inconsistent if the
delivery of m' were not completed. The costs of the protocols
are not affected by this change.
非同期なマルチキャストを許容するという私たちの決定で問題は紹介されます: 今、非同期なメッセージの原因となって関連する系列を記述するために原子レセプションの特性を広げなければなりません。 失敗がそれらのすべての送付先に届けられるいくつかのマルチキャストにもかかわらず、何処にも渡されないことで彼らに先行する他のものをもたらすことである、desti国が重ならないでも、矛盾は結果として生じます。 したがって、私たちは以下の最小単位親pertyを広げます。 ''過程tが過程sからメッセージmを受けて、sが次に、失敗して、tはまた、そして、すべてのメッセージm失敗しない場合、失敗の前に受け取られたそのsを操作上の目的地のままで残っているのに渡さなければなりません。 'これによる'したがって、tの状態が現在どんなそのようなmのコンテンツにもよるかもしれないのでシステム状態がmの配送であるなら矛盾するようになるかもしれないということです'は完成しませんでした。 プロトコルのコストはこの変化で影響を受けません。
A second problem arises when the user-level implications of this
atomicity rule are considered. In the event of a failure, any
suffix of a sequence of aysnchronous multicasts could be lost and
the system state would still be internally consistent. A process
that is about to take some action that may leave an externally
visible side-effect will need a way to pause until it is
guaranteed that such multicasts have actually been delivered.
For this purpose, a flush primitive is provided. Occasional
calls to flush do not eliminate the benefit of using CBCAST asyn-
chronously. Unless the system has built up a considerable back-
log of undelivered multicast messages, which should be rare,
flush will only pause while transmission of the last few multi-
casts complete.
この最小単位規則のユーザレベル含意が考えられるとき、2番目の問題は起こります。 失敗の場合、aysnchronousマルチキャストの系列のどんな接尾語も負けられるかもしれません、そして、システム状態はまだ内部的に一貫しているでしょう。 外部的に目に見える副作用を残すかもしれない何らかの行動を取ろうとしていることになっている過程は実際にそのようなマルチキャストを送るのが保証されるまで止まる方法を必要とするでしょう。 このために、豊富な基関数を提供します。 洗い流すという時々の要求はCBCAST asyn- chronouslyを使用する利益を除去しません。 システムが完全な状態で「非-渡」されたマルチキャストメッセージのかなりの逆ログ(まれです、水洗が最後のわずかなマルチキャストのトランスミッションである間、止まるだけであるということであるべきである)を確立していない場合。
7. Using the primitives
7. 基関数を使用します。
The reliable communication primitives described above lead to simple solutions for the problems cited in Sec. 4:
信頼できるコミュニケーション基関数はSecで引用された問題の簡単な解決に上のリードについて説明しました。 4:
[1] Synchronization. Many synchronization problems are subsumed
into the primitives themselves. For example, consider the use of
GBCAST to implement recovery. A recovering process would issue a
GBCAST to the process group members, requesting that state
[1] 同期。 多くの同期問題が基関数自体に包括されています。 例えば、GBCASTの使用が回復を実行すると考えてください。 その状態を要求して、回復の過程は過程グループのメンバーにGBCASTを発行するでしょう。
Birman & Joseph [Page 11] RFC 992 November 1986
バーマンとジョゼフ[11ページ]RFC992 1986年11月
information be transferred to it. In addition to sending the
current state of the group to the recovering process, group
members update the process group view at this time. Subsequent
messages to the group will be delivered to the recovered process,
with all necessary synchronization being provided by the ordering
properties of GBCAST. In situations where other forms of syn-
chronization are needed, ABCAST provides a simple way to ensure
that several processes take actions in the same order, and this
form of low-level synchronization simplifies a number of higher-
level synchronization problems. For example, if ABCAST is used
to do P() and V() operations on a distributed semaphore, the
order of operations on the semaphore is set by the ABCAST, hence
all the managers of the semaphore see these operations in a fixed
order.
情報、それに移してください。 グループの現状を回復の過程に送ることに加えて、グループのメンバーはこのとき、過程グループ視点をアップデートします。 グループへのその後のメッセージを回復している過程に送るでしょう、GBCASTの注文の特性ですべての必要な同期を提供していて。syn- chronizationの他のフォームが必要である状況に、ABCASTはいくつかの過程が同次で行動を取るのを保証する簡単な方法を提供します、そして、この形式の低レベルである同期は多くの、より高いレベルを簡素化します。同期問題例えば; ABCASTが分配された腕木信号機でP()とV()に操作するのに使用されるなら、腕木信号機における操作の注文はABCASTによって設定されます、したがって、腕木信号機のすべてのマネージャが固定オーダーでこれらの操作を見ます。
[2] Failure detection. Consistent failure (and recovery) detec-
tion are trivial using our primitives: a process simply waits for
the appropriate process group view to change. This facilitates
the implementation of algorithms in which one processes monitors
the status of another process. A process that acts on the basis
of a process group view change does so with the assurance that
other group members will (eventually) observe the same event and
will take consistent actions.
[2] 失敗検出。 一貫した失敗(そして、回復)detec- tionは私たちの基関数を使用することで些細です: 過程は、適切な過程グループ意見が変化するのを単に待っています。 これは1つがモニターのために別の過程の状態を処理するアルゴリズムの実現を容易にします。 したがって、過程グループ視点に基づいた行為が変える過程は他のグループのメンバーが(結局、)同じ出来事を観測して、一貫した行動を取るという保証を処理します。
[3] Consistency. We believe that consistency is generally
expressible as a set of atomicity and ordering constraints on
message delivery, particularly causal ones of the sort provided
by CBCAST. Our primitives permit a process to specify the com-
munication properties needed to achieve a desired form of con-
sistency. Continued research will be needed to understand pre-
cisely how to pick the weakest primitive in a designated situa-
tion.
[3] 一貫性。 私たちは、一貫性が一般に1セットの最小単位として表現できてメッセージ配送のときに規制が規則正しいと信じています、と種類の特に原因の1つはCBCASTで前提としました。私たちの基関数は、過程が特性がまやかしsistencyの必要なフォームを達成する必要があったcom- municationを指定することを許可します。 継続的な研究が、プレciselyに最も弱いのを指定されたsitua- tionの原始の選ぶ方法を理解するのに必要でしょう。
[4] Serializability. To achieve serializability, one implements
a concurrency control algorithm and then forces computations to
respect the serialization order that this algorithm choses. The
ABCAST primitive, as observed above, is a powerful tool for
establishing an order between concurrent events, e.g. by lock
acquisition. Having established such an order, CBCAST can be
used to distribute information about the computation and also its
termination (commit or abort). Any process that observes the
commit or abort of a computation will only be able to interact
with data managers that have received messages preceding the com-
mit or abort, hence a highly asynchronous transactional execution
results. If a process running a computation fails, this is
detected when a failure GBCAST is received instead of the commit.
Thus, executions are simple and quite deterministic.
[4] Serializability。 serializabilityを達成するために、1つはこのアルゴリズムがchosesする連載命令を尊敬するa同時実行制御アルゴリズムと当時の力の計算を実行します。 上で同時発生の出来事の間には、オーダーを確立するための強力な道具があるのを観測する例えば、ロック獲得による原始のABCAST。 そのような注文を確立したので、計算の情報とその終了も広げるのにCBCASTを使用できます(公約するか、または中止になってください)。 見るどんな過程、も計算のアボートは、公約するか、com- mitに先行するメッセージを受け取ったデータ管理ソフトウェアと対話する、中止になることができるだけであって、したがって、非常に非同期な取引の実行は結果です。 の代わりにする、a失敗GBCASTが受け取られているとき、計算を走らせる過程が失敗するなら、これが検出される、公約してください。 したがって、実行は、簡単であって、かなり決定論的です。
If commit is conditional, CBCAST would be used to first interro-
gate participants to learn if they are prepared to commit, and
then to transmit the commit or abort decision (the usual two-
公約、条件付きです、CBCASTが彼らが公約して、そして、伝わるように準備されるかどうか学ぶのに最初に、interroゲート関係者に使用されるだろうということである、決定を遂行するか、または中止してください、(普通の2
Birman & Joseph [Page 12] RFC 992 November 1986
バーマンとジョゼフ[12ページ]RFC992 1986年11月
phase commit). On the other hand, conditional commits can often
be avoided using our approach. A method for building transac-
tions that will roll-forward after failure after failure is dis-
cussed in more detail in [Birman-a] [Joseph-a] [Joseph-b]. Other
forms of concurrency control, such as timestamp generation, can
similarly be implemented using ABCAST and CBCAST. We view tran-
sactional data storage as an application-level concern, which can
be handled using a version stack approach or a multi-version
store, or any other appropriate mechanism.
フェーズが公約する、) 他方では、条件付きである、避けられた使用が私たちのアプローチであったならしばしば缶を遂行します。 transac- tionsにそれを建てるための方法は失敗後失敗がさらに詳細に[バーマンa]で不-意地が悪くなった後に前進復帰[ジョゼフ-a][ジョゼフ-b]がそうするでしょう。 ABCASTとCBCASTを使用することで同様に他の形式のタイムスタンプ世代などの合意管理を実施されることができます。私たちはアプリケーションレベル関心かいかなる他の適切な手段であるともtran- sactionalデータ保存をみなします。(バージョンスタックアプローチかマルチバージョン店を使用することで関心を扱うことができます)。
8. Implementation
8. 実現
The communication primitives can be built in layers, starting with a bare network providing unreliable Internet datagrams. The software structure is, however, less mature and more complex than the one sug- gested in RFC's 966 and 988. For example, at this stage of our research we do not understand how to optimize our protocols to the same extent as for the unreliable host multicast approach described in those RFC's. Thus, the implementation we describe here should be understood to be a prototype. A particularly intriguing question, which we are investigating actively, concerns the use of a "best effort" ethernet or Internet multicast as a tool to optimize the implementation of our protocols.
層でコミュニケーション基関数を築き上げることができます、頼り無いインターネットデータグラムを提供しながらむき出しのネットワークから始まって。ソフトウェア構造は、RFCの966と988のうちの1sug- gestedよりしかしながら、発達していなくて複雑です。 例えば、私たちの研究のこの段階では、私たちはRFCのそれらのところで説明された頼り無いホストマルチキャストアプローチのように私たちのプロトコルを同じ範囲に最適化する方法を理解していません。 したがって、私たちがここで説明する実現は原型であることが理解されるべきです。 特に好奇心をそそる問題(私たちは活発に調査している)は私たちのプロトコルの実現を最適化するツールとして「ベストエフォート型」のイーサネットかインターネットマルチキャストの使用に関係があります。
Our basic approach is to view large area networks as a set of clus- ters of sites interconnected by high speed LAN devices and intercon- nected by slower long-haul links. We first provide protocols for use within clusters, and then extend them to run between clusters too. Network partitioning can be tolerated at all levels of the hierarchy in the sense that no incorrect actions can result after network par- titioning, although our approach will sometimes block until the par- tition is repaired. Our protocols also tend to block within a clus- ter while the list of operational sites for that cluster is being changed. In normal LAN's, this happens infrequently (during site failure or recovery), and would not pose a problem. (In failure intensive applications, alternative protocols might be needed to address this issue).
私たちの基本的なアプローチは、より遅い長期リンクのそばで高速LAN装置とintercon- nectedによってインタコネクトされたサイトのclus- tersの1セットであると広い地域ネットワークをみなすことです。 私たちは、最初にクラスタの中の使用にプロトコルを提供して、次に、クラスタの間をも走るためにそれらを広げます。 平価titionが修理されるまで、どんな不正確な動作も、私たちのアプローチが時々titioningしますが、titioningされるネットワーク平価の後の結果が妨げることができないという意味における、階層構造のすべてのレベルでネットワーク仕切りを許容できます。 また、私たちのプロトコルはそのクラスタのための操作上のサイトのリストを変えている間、clus- terの中でブロックの傾向があります。 正常なLANのものでは、これは、まれに(サイト失敗か回復の間)起こって、問題を設定しないでしょう。 (失敗の徹底的なアプリケーションでは、代替のプロトコルがこの問題を記述するのに必要であるかもしれません。)
The lowest level of our software uses a site-to-site acknowledgement protocol to convert the unreliable packet transport this into a sequenced, error-free message abstraction, using timeouts to detect apparent failures. TCP can also be used for this purpose, provided that a "filter" is placed on the incoming message stream and certain types of messages are handled specially. An agreement protocol is then used to order the site-failures and recoveries consistently. If timeouts cause a failure to be detected erroneously, the protocol forces the affected site to undergo recovery.
私たちのソフトウェアの最も低いレベルは、配列されて、エラーのないメッセージ抽象化にこれを輸送して、明らかな失敗を検出するのにタイムアウトを使用することで頼り無いパケットを変換するのにサイトからサイトへの承認プロトコルを使用します。 また、このためにTCPを使用できます、「フィルタ」が入力メッセージストリームに置かれて、あるタイプに関するメッセージが特に扱われれば。 そして、協定プロトコルは、一貫してサイト失敗と回復を命令するのに使用されます。 タイムアウトが誤って検出されないことを引き起こすなら、プロトコルによって、関係部位はやむを得ず回復を被ります。
Built on this is a layer that supports the primitives themselves. CBCAST has a very light-weight implementation, based on the idea of flooding the system with copies of a message: Each process buffers
これに建てられているのは、基関数自体を支持する層です。 CBCASTには、メッセージのコピーがあるシステムをあふれさせるという考えに基づいて非常に軽量の実現があります: それぞれがバッファを処理します。
Birman & Joseph [Page 13] RFC 992 November 1986
バーマンとジョゼフ[13ページ]RFC992 1986年11月
copies of any messages needed to ensure the consistency of its view of the system. If message m is delivered to process p, and m is potentially causally dependent on a message m prime, then a copy of m prime is sent to p as well (duplicates are discarded). A garbage collector deletes superfluous copies after a message has reached all its destinations. By using extensive piggybacking and a simple scheduling algorithm to control message transmission, the cost of a CBCAST is kept low -- often, less than one packet per destination. ABCAST employs a two-phase protocol based on one suggested to us by Skeen [Skeen-b]. This protocol has higher latency than CBCAST because delivery can only occur during the second phase; ABCAST is thus inherently synchronous. In ISIS, however, ABCAST is used rarely; we believe that this would be the case in other systems as well. GBCAST is implemented using a two-phase protocol similar to the one for ABCAST, but with an additional mechanism that flushes messages from a failed process before delivering the GBCAST announc- ing the failure. Although GBCAST is slower than ABCAST or CBCAST, it is used rarely enough so that performance is probably less of an issue here -- and in any case, even GBCAST could be tuned to give very high throughput. Preliminary performance figures appear in [Birman-b].
どんなメッセージのコピーも、システムの視点の一貫性を確実にする必要がありました。 pを処理するためにメッセージmを渡して、mが潜在的にメッセージmに主要な状態で原因となって依存しているなら、mのコピーが用意するその時によってまた、pに送られます(写しは捨てられます)。 メッセージがすべての目的地に達した後にごみ収集人は余計なコピーを削除します。 メッセージ送信を制御するのに大規模な便乗と簡単なスケジューリングアルゴリズムを使用することによって、CBCASTの費用は低くしばしば保たれます、1目的地あたり1つ未満のパケット。 ABCASTはSkeen[Skeen-b]によって私たちに勧められた1つに基づく二相プロトコルを使います。 このプロトコルには、配送が2番目の段階の間、起こることができるだけであるので、CBCASTより高い潜在があります。 その結果、ABCASTは本来同時です。 しかしながら、イシスでは、ABCASTはめったに使用されません。 私たちは、これがまた、他のシステムでそうであると信じています。 GBCASTはABCASTのためにものと同様の二相プロトコルを使用することで実行されますが、失敗をGBCAST announc- ingに渡す前に失敗した過程からのメッセージを洗い流す追加メカニズムで実行されます。 GBCASTがABCASTかCBCASTより遅いのですが、それが十分めったに使用されないので、ここの問題では性能はたぶんより少ないです、そして、非常に高いスループットを与えるためにGBCASTさえ調整できました。 予備の性能の数字は[バーマンb]に現れます。
Although satisfactory performance should be possible using an imple- mentation that sits on top of a conventional Internet mechanism, it should be noted that to achieve really high rates of communication the layers of software described above must reside in the kernel, because they run on behalf of large numbers of clients, run fre- quently, and tend to execute for very brief periods before doing I/O and pausing. A non-kernel implementation will thus incur high scheduling and context switching overhead. Additionally, it is not at all clear how to use ethernet style broadcast mechanisms to optim- ize the performance of this sort of protocol, although it should be possible. We view this as an interesting area for research.
それらはカーネル、多くのクライアントを代表して走って、fre- quentlyを走らせて、傾向があるので、立派な業績は入出力をして、止まる前に非常に簡潔な期間、実行するのにおいて従来のインターネットメカニズムの上に座るimple精神作用を使用して、本当に高い率に関するコミュニケーションを達成するために、上で説明されたソフトウェアの層がなければならないことに注意されるべきであるのが可能であるべきですが。 その結果、非カーネル実現は高いスケジューリングとコンテキストスイッチオーバーヘッドを被るでしょう。 さらに、この種類のプロトコルそれですが、イーサネットスタイル放送メカニズムをoptim- izeに使用するために、性能がどのように可能であるべきであるかは、全く明確ではありません。 私たちは調査のためにおもしろい領域であるとこれをみなします。
A forthcoming paper will describe higher level software that we are building on top of the basic fault-tolerant process group mechanism described above.
今度の紙は私たちが上で説明された基本的なフォールトトレラント過程グループメカニズムの上で組立てているより高い平らなソフトウェアについて説明するでしょう。
9. Conclusions
9. 結論
The experience of implementing a substantial fault-tolerant system left us with insights into the properties to be desired from a com- munication subsystem. In particular, we became convinced that to build a reliable distributed system, one must start with a reliable communication subsystem. The multicast primitives described in this memo present a simple interface, achieve a high level of concurrency, can be used in both local and wide area networks, and are applicable to software ranging from distributed database systems to the fault- tolerant objects and bulletin boards provided by ISIS. Because they are integrated with failure handling mechanisms and respect desired event orderings, they introduce a desirable form of determinism into
かなりのフォールト・トレラント・システムを実行する経験は、com- municationサブシステムから望まれるために特性への洞察を私たちに残しました。 特に、私たちは信頼できる分散システムを築き上げるために、信頼できるコミュニケーションサブシステムから始まらなければならないと確信するようになりました。 マルチキャスト基関数は、このメモプレゼントで簡単なインタフェースについて説明して、高いレベルで合意を達成して、ともに地方と広域ネットワークに使用できて、分散データベースシステムから欠点の許容性がある物とイシスによって提供された掲示板まで及ぶソフトウェアに適切です。 彼らが失敗取り扱いメカニズムについて統合していて、必要なイベント受注業務を尊敬するので、それらは望ましいフォームの決定論を紹介します。
Birman & Joseph [Page 14] RFC 992 November 1986
バーマンとジョゼフ[14ページ]RFC992 1986年11月
distributed computation without compromising efficiency. A conse- quence is that high-level algorithms are greatly simplified, reducing the probability of error. We believe that this is a very promising and practical approach to building large fault-tolerant distributed systems, and it is the only one we know of that leads to a rigorous form of confidence in the resulting software.
効率で妥協することのない分散型計算方式。 conse- quenceによる誤りの確率を減少させて、ハイレベルのアルゴリズムが大いに簡素化されるということです。 私たちは、これが大きい無停止分散システムを組立てることへの非常に有望で実用的なアプローチであると信じています、そして、それは結果として起こるソフトウェアにおける、厳しいフォームの信用につながる私たちが知っている唯一無二です。
NOTES:
注意:
<1> A problem arises if a process p fails without receiving some mes- sage after that message has already been delivered to some other pro- cess q: q's VIEW when it received the message would show p to be operational; hence, q will assume that p received the message, although p is physically incapable of doing so. However, the state of the system is now equivalent to one in which p did receive the message, but failed before acting on it. In effect, there exists an interpretation of the actual system state that is consistent with q's assumption. Thus, GBCAST satisfies the sort of logical delivery pro- perty cited in the introduction.
過程pが既にある他の親課税qにそのメッセージを送った後にmes賢人を受けないで失敗するなら、<の1>Aの問題は起こります: それがメッセージを受け取ったとき、qのVIEWは、pが操作上であることを示すでしょう。 したがって、pは肉体的にそうすることができませんが、qは、pがメッセージを受け取ったと仮定するでしょう。 しかしながら、システムの事情は現在、pがメッセージを受け取りましたが、それに影響する前に失敗したものに同等です。 事実上、qの仮定と一致した実際のシステム状態の解釈は存在しています。 したがって、GBCASTは親pertyが序論で引用した論理的な配送の種類を満たします。
Birman & Joseph [Page 15] RFC 992 November 1986
バーマンとジョゼフ[15ページ]RFC992 1986年11月
10. References
10. 参照
[RFC966] Deering, S. and Cheriton, D. Host groups: A multicast exten-
sion to the internet protocol. Stanford University, December
1985.
[RFC966] デアリングとS.とCheriton、D.Hostグループ: インターネットプロトコルへのマルチキャストexten- sion。 1985年12月のスタンフォード大学。
[RFC988] Deering, S. Host extensions for IP multicasting. Stanford
University, July 1986.
[RFC988]デアリング、IPマルチキャスティングのためのS.Host拡張子。 1986年7月のスタンフォード大学。
[Allchin] Allchin, J., McKendry, M. Synchronization and recovery of
actions. Proc. 2nd ACM SIGACT/SIGOPS Principles of Distributed
Computing, Montreal, Canada, 1983.
[Allchin] 動作のAllchin、J.、McKendry、M.Synchronization、および回復。 Proc。 分散コンピューティングの第2ACM SIGACT/シグオペ原則、モントリオール(カナダ)1983。
[Babaoglu] Babaoglu, O., Drummond, R. The streets of Byzantium: Network
architectures for fast reliable multicast. IEEE Trans. on
Software Engineering TSE-11, 6 (June 1985).
[Babaoglu] R. Babaoglu、O.、ドラモンド、ビザンティウムの通り: 速い信頼できるマルチキャストのためのネットワークアーキテクチャ。 IEEE、移-. ソフトウェア工学東京証券取引所-11、6(1985年6月)に関して。
[Bernstein] Bernstein, P., Goodman, N. Concurrency control algorithms
for replicated database systems. ACM Computing Surveys 13, 2
(June 1981), 185-222.
[バーンスタイン]バーンスタイン、P.、グッドマン、N.Concurrencyは模写されたデータベース・システムACM Computing Surveys13、2(1981年6月)、185-222のためにアルゴリズムを制御します。
[Birman-a] Birman, K. Replication and fault-tolerance in the ISIS sys-
tem. Proc. 10th ACM SIGOPS Symposium on Operating Systems Princi-
ples. Orcas Island, Washington, Dec. 1985, 79-86.
[バーマンa] イシスsys- temのバーマン、K.Replication、および耐障害性。 Proc。 Operating Systems Princi- plesの上の第10ACM SIGOPS Symposium。 オーカス島、ワシントン、1985年12月、79-86。
[Birman-b] Birman, K., Joseph, T. Reliable communication in the pres-
ence of failures. Dept. of Computer Science, Cornell Univ., TR
85-694, Aug. 1985. To appear in ACM TOCS (Feb. 1987).
[バーマンb] バーマン、K.、ジョゼフ、失敗のpres- enceのT.Reliableコミュニケーション。 コンピュータサイエンスの部、コーネル大学、TR85-694、1985年8月。 ACM TOCS(1987年2月)に現れるように。
[Birman-c] Birman, K., Joseph, T., Stephenson, P. Programming with
fault tolerant bulletin boards in asynchronous distributed sys-
tems. Dept. of Computer Science, Cornell Univ., TR 85-788, Aug.
1986.
[バーマンc] バーマン、K.、ジョゼフ、T.、スティーヴンソン、フォルト・トレラントの掲示板が非同期にあるP.Programmingはsys- temsコンピュータScienceの部を分配しました、コーネル大学、TR85-788、1986年8月。
[Birrell] Birrell, A., Nelson, B. Implementing remote procedure calls.
ACM Transactions on Computer Systems 2, 1 (Feb. 1984), 39-59.
[ビレル]ビレル、A.、ネルソン、B.Implementing遠隔手続き呼び出し。 39-59にコンピュータシステムズ2、1(1984年2月)におけるACM取引。
[Chang] Chang, J., Maxemchuck, M. Reliable multicast protocols. ACM
TOCS 2, 3 (Aug. 1984), 251-273.
[チャン]チャン、J.、Maxemchuck、M.Reliableマルチキャストプロトコル。 251-273にACMトックス2、3(1984年8月)。
[Cheriton] Cheriton, D. The V Kernel: A software base for distributed
systems. IEEE Software 1 12, (1984), 19-43.
D. [Cheriton]Cheriton、Vカーネル: 分散システムIEEE Software1 12、(1984)のための19-43にソフトウェア基盤。
[Cooper] Cooper, E. Replicated procedure call. Proc. 3rd ACM Symposium
on Principles of Distributed Computing., August 1984, 220-232.
(May 1985).
[クーパー]クーパー、E.Replicated手順呼び出し。 Proc。 分散コンピューティングのプリンシプルズに関する第3ACMシンポジウム、1984年8月、220-232。 (1985年5月。)
[Cristian] Cristian, F. et al Atomic multicast: From simple diffusion to
Byzantine agreement. IBM Technical Report RJ 4540 (48668), Oct.
1984.
[クリスチャン]クリスチャン、F.他のAtomicマルチキャスト: 単純拡散から込み入った協定まで。 1984年10月のIBM技術報告書RJ4540(48668)。
Birman & Joseph [Page 16] RFC 992 November 1986
バーマンとジョゼフ[16ページ]RFC992 1986年11月
[Eswaren] Eswaren, K.P., et al The notion of consistency and predicate
locks in a database system. Comm. ACM 19, 11 (Nov. 1976), 624-
633.
[Eswaren]Eswaren、K.P.、一貫性と述部の概念がデータベース・システムを閉じ込める他。 Comm。 ACM19、11(1976年11月)、624- 633。
[Hadzilacos] Hadzilacos, V. Byzantine agreement under restricted types
of failures (not telling the truth is different from telling of
lies). Tech. ARep. TR-19-83, Aiken Comp. Lab., Harvard University
(June 1983).
[Hadzilacos]Hadzilacos、制限されたタイプの失敗の下におけるV.の込み入った協定(本当のことを言わないのは偽りについて言うのと異なっています)。 科学技術。 ARep. TR-19-83、エーケンコンピュータ。 研究室、ハーバード大学(1983年6月)。
[Halpern] Halpern, J., and Moses, Y. Knowledge and common knowledge in
a distributed environment. Tech. Report RJ-4421, IBM San Jose
Research Laboratory, 1984.
分散環境における[アルペルン]アルペルン、J.、モーセ、Y.Knowledge、および周知の事実。 科学技術。 RJ-4421、IBMサンノゼ研究所、1984を報告してください。
[Joseph-a] Joseph, T. Low cost management of replicated data. Ph.D.
dissertation, Dept. of Computer Science, Cornell Univ., Ithaca
(Dec. 1985).
[ジョゼフ-a] ジョゼフ、T.Lowは複製データの管理かかります。 博士号論文、コンピュータScienceの部、コーネル大学、イタケー(1985年12月)。
[Joseph-b] Joseph, T., Birman, K. Low cost management of replicated
data in fault-tolerant distributed systems. ACM TOCS 4, 1 (Feb
1986), 54-70.
[ジョゼフ-b] ジョゼフ、T.、バーマン、K.Lowは無停止分散システムACM TOCS4、1(1986年2月)(54-70)での複製データの管理かかります。
[Lamport] Lamport, L. Time, clocks, and the ordering of events in a
distributed system. CACM 21, 7, July 1978, 558-565.
分散システムにおける出来事の[ランポート]ランポート、L.Time、時計、および注文。 1978年7月、558-565にCACM21、7。
[Lazowska] Lazowska, E. et al The architecture of the EDEN system.
Proc. 8th Symposium on Operating Systems Principles, Dec. 1981,
148-159.
[Lazowska]Lazowska、E.他、エデンシステムの構造。 Proc。 1981年12月、148-159にオペレーティングシステムプリンシプルズに関する第8シンポジウム。
[Liskov] Liskov, B., Scheifler, R. Guardians and actions: Linguistic
support for robust, distributed programs. ACM TOPLAS 5, 3 (July
1983), 381-404.
[Liskov] Liskov、B.、Scheifler、R.Guardians、および動作: 強健で、分配されたプログラムACM TOPLAS5、3(1983年7月)、381-404の言語学のサポート。
[Moss] Moss, E. Nested transactions: An approach to reliable, distri-
buted computing. Ph.D. thesis, MIT Dept of EECS, TR 260, April
1981.
[こけ]こけ、E.Nested取引: 信頼できるdistri- butedコンピューティングへのアプローチ。 博士論文、EECS、TR260、1981年4月のMIT部。
[Papadimitrou] Papadimitrou, C. The serializability of concurrent data-
base updates. JACM 26, 4 (Oct. 1979), 631-653.
C. [Papadimitrou]Papadimitrou、同時発生のデータベース最新版のserializability。 JACM26、4(1979年10月)、631-653。
[Popek] Popek, G. et al. Locus: A network transparent, high reliability
distributed system. Proc. 8th Symposium on Operating Systems
Principles, Dec. 1981, 169-177.
[Popek]Popek、G.他 場所: ネットワーク透明で、高い信頼性の分散システム。 Proc。 1981年12月、169-177にオペレーティングシステムプリンシプルズに関する第8シンポジウム。
[Schlicting] Schlicting, R, Schneider, F. Fail-stop processors: An
approach to designing fault-tolerant distributed computing sys-
tems. ACM TOCS 1, 3, August 1983, 222-238.
[Schlictingします] Schlicting、R、シュナイダー、F.Fail-停止プロセッサ: トックス1、1983年8月3日に、222-238にフォールトトレラント分散コンピューティングsys- tems. ACMを設計することへのアプローチ。
[Schneider] Schneider, F., Gries, D., Schlicting, R. Reliable multicast
protocols. Science of computer programming 3, 2 (March 1984).
[シュナイダー] シュナイダー、F.、グリース、D.、Schlicting、R.Reliableマルチキャストプロトコル。 コンピュータ・プログラミング3、2(1984年3月)の科学。
[Skeen-a] Skeen, D. Determining the last process to fail. ACM TOCS 3,
[Skeen-a]Skeen、最終が失敗するように処理するD.Determining。 ACMトックス3
Birman & Joseph [Page 17] RFC 992 November 1986
バーマンとジョゼフ[17ページ]RFC992 1986年11月
1, Feb. 1985, 15-30.
1 1985年2月、15-30。
[Skeen-b] Skeen, D. A reliable multicast protocol. Unpublished.
[Skeen-b]Skeen、D.のA信頼できるマルチキャストプロトコル。 未発表。
[Spector] Spector, A., et al Distributed transactions for reliable sys-
tems. Proc. 10th ACM SIGOPS Symposium on Operating Systems Prin-
ciples, Dec. 1985, 127-146.
[スペクター]スペクター、A.、信頼できるsys- tems. Procのための他のDistributed取引。 Operating Systemsプランciples、1985年12月、127-146の上の第10ACM SIGOPS Symposium。
[Strong] Strong, H.R., Dolev, D. Byzantine agreement. Digest of papers,
Spring Compcon 83, San Francisco, CA, March 1983, 77-81.
強い[強い]のH.R.、Dolev、D.の込み入った協定。 1983年のSpring Compcon83、サンフランシスコ(カリフォルニア)の行進、77-81に書類のダイジェスト。
Birman & Joseph [Page 18]
バーマンとジョゼフ[18ページ]
一覧
スポンサーリンク
