home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc992 < prev    next >
Text File  |  1991-04-21  |  51KB  |  1,061 lines

  1.  
  2.                                                        K. P. Birman (Cornell)
  3. Network Working Group                                  T. A. Joseph (Cornell)
  4. Request for Comments: 992                              November 1986
  5.  
  6.  
  7.  
  8.        On Communication Support for Fault Tolerant Process Groups
  9.  
  10.                      K. P. Birman and T. A. Joseph
  11.              Dept. of Computer Science, Cornell University
  12.                            Ithaca, N.Y. 14853
  13.                               607-255-9199
  14.  
  15.  
  16. 1. Status of this Memo.
  17.  
  18.    This memo describes a collection of multicast communication primi-
  19.    tives integrated with a mechanism for handling process failure and
  20.    recovery.  These primitives facilitate the implementation of fault-
  21.    tolerant process groups, which can be used to provide distributed
  22.    services in an environment subject to non-malicious crash failures.
  23.    Unlike other process group approaches, such as Cheriton's "host
  24.    groups" (RFC's 966, 988, [Cheriton]), our approach provides powerful
  25.    guarantees about the behavior of the communication subsystem when
  26.    process group membership is changing dynamically, for example due to
  27.    process or site failures, recoveries, or migration of a process from
  28.    one site to another.  Our approach also addresses delivery ordering
  29.    issues that arise when multiple clients communicate with a process
  30.    group concurrently, or a single client transmits multiple multicast
  31.    messages to a group without pausing to wait until each is received.
  32.    Moreover, the cost of the approach is low.  An implementation is be-
  33.    ing undertaken at Cornell as part of the ISIS project.
  34.  
  35.    Here, we argue that the form of "best effort" reliability provided by
  36.    host groups may not address the requirements of those researchers who
  37.    are building fault tolerant software.  Our basic premise is that re-
  38.    liable handling of failures, recoveries, and dynamic process migra-
  39.    tion are important aspects of programming in distributed environ-
  40.    ments, and that communication support that provides unpredictable
  41.    behavior in the presence of such events places an unacceptable burden
  42.    of complexity on higher level application software.  This complexity
  43.    does not arise when using the fault-tolerant process group alterna-
  44.    tive.
  45.  
  46.    This memo summarizes our approach and briefly contrasts it with other
  47.    process group approaches.  For a detailed discussion, together with
  48.    figures that clarify the details of the approach, readers are re-
  49.    ferred to the papers cited below.
  50.  
  51.    Distribution of this memo is unlimited.
  52.  
  53.  
  54.  
  55.  
  56. Birman & Joseph                                                 [Page 1]
  57.  
  58. RFC 992                                                    November 1986
  59.  
  60.  
  61. 2. Acknowledgments
  62.  
  63.    This memo was adopted from a paper presented at the Asilomar workshop
  64.    on fault-tolerant distributed computing, March 1986, and summarizes
  65.    material from a technical report that was issued by Cornell Universi-
  66.    ty, Dept. of Computer Science, in August 1985, which will appear in
  67.    ACM Transactions on Computer Systems in February 1987 [Birman-b].
  68.    Copies of these paper, and other relevant papers, are available on
  69.    request from the author: Dept. of Computer Science, Cornell Universi-
  70.    ty, Ithaca, New York 14853. (birman@gvax.cs.cornell.edu).  The ISIS
  71.    project also maintains a mailing list.  To be added to this list,
  72.    contact M. Schmizzi (schiz@gvax.cs.cornell.edu).
  73.  
  74.    This work was supported by the Defense Advanced Research Projects
  75.    Agency (DoD) under ARPA order 5378, Contract MDA903-85-C-0124, and by
  76.    the National Science Foundation under grant DCR-8412582.  The views,
  77.    opinions and findings contained in this report are those of the au-
  78.    thors and should not be construed as an official Department of De-
  79.    fense position, policy, or decision.
  80.  
  81. 3. Introduction
  82.  
  83.    At Cornell, we recently completed a prototype of the ISIS system,
  84.    which transforms abstract type specifications into fault-tolerant
  85.    distributed implementations, while insulating users from the mechan-
  86.    isms by which fault-tolerance is achieved.  This version of ISIS, re-
  87.    ported in [Birman-a], supports transactional resilient objects as a
  88.    basic programming abstraction.  Our current work undertakes to pro-
  89.    vide a much broader range of fault-tolerant programming mechanisms,
  90.    including fault-tolerant distributed bulletin boards [Birman-c] and
  91.    fault-tolerant remote procedure calls on process groups [Birman-b].
  92.    The approach to communication that we report here arose as part of
  93.    this new version of the ISIS system.
  94.  
  95.    Unreliable communication primitives, such as the multicast group com-
  96.    munication primitives proposed in RFC's 966 and 988 and in [Cheri-
  97.    ton], leave some uncertainty in the delivery status of a message when
  98.    failures and other exceptional events occur during communication.
  99.    Instead, a form of "best effort" delivery is provided, but with the
  100.    possibility that some member of a group of processes did not receive
  101.    the message if the group membership was changing just as communica-
  102.    tion took place.  When we tried to use this sort of primitive in our
  103.    original work on ISIS, which must behave reliably in the presence of
  104.    such events, we had to address this aspect at an application level.
  105.    The resulting software was complex, difficult to reason about, and
  106.    filled with obscure bugs, and we were eventually forced to abandon
  107.    the entire approach as infeasible.
  108.  
  109.    A wide range of reliable communication primitives have been proposed
  110.    in the literature, and we became convinced that by using them, the
  111.    complexity of our software could be greatly reduced.  These range
  112.  
  113.  
  114.  
  115. Birman & Joseph                                                 [Page 2]
  116.  
  117. RFC 992                                                    November 1986
  118.  
  119.  
  120.    from reliable and atomic broadcast [Chang] [Cristian] [Schneider] to
  121.    Byzantine agreement [Strong].  For several reasons, however, the ex-
  122.    isting work does not solve the problem at hand.  The most obvious is
  123.    that they do not provide a mechanism for sending a message to all the
  124.    members of a group when the membership is changing dynamically (the
  125.    "group addressing" problem).  In addition, one can identify delivery
  126.    ordering issues and questions regarding the detection of communica-
  127.    tion failures that should be handled within the broadcast mechanism.
  128.    These motivate a careful reexamination of the entire reliable broad-
  129.    cast problem.
  130.  
  131.    The multicast primitives we report here are designed to respect
  132.    several sorts of ordering constraints, and have cost and latency that
  133.    varies depending on the nature of the constraint required [Birman-b]
  134.    [Joseph-a] [Joseph-b].  Failure and recovery are integrated into the
  135.    communication subsystem by treating these events as a special sort of
  136.    multicast issued on behalf of a process that has failed or recovered.
  137.    The primitives are presented in the context of fault tolerant process
  138.    groups: groups of processes that cooperate to implement some distri-
  139.    buted algorithm or service, and which need to see consistent order-
  140.    ings of system events in order to achieve mutually consistent
  141.    behavior.  Such groups are similar to the host groups of the V system
  142.    and the ones described in RFC's 966 and 988, but provide guarantees
  143.    of consistency in just the situations where a host group provides a
  144.    "best effort" delivery which may sometimes be erroneous.
  145.  
  146.    It is helpful to think of our primitives as providing a logical or
  147.    "virtual" form of reliability: rather than addressing physical
  148.    delivery issues, they ensure that a client will never observe a sys-
  149.    tem state "inconsistent" with the assumption that reliable delivery
  150.    has occurred.  Readers familiar with serializability theory may want
  151.    to think of this as a weaker analog: in serializability, one allows
  152.    interleaved executions of operations provided that the resulting sys-
  153.    tem state is consistent with the assumption that execution was
  154.    sequential.  Similarly, reliable communication primitives permit de-
  155.    viations from the reliable delivery abstraction provided that the
  156.    resulting system state is indistinguishable from one in which reli-
  157.    able delivery actually did occur.
  158.  
  159.    Using our primitives, the ISIS system achieved both high levels of
  160.    concurrency and suprisingly good performance.  Equally important, its
  161.    structure was made suprisingly simple, making it feasible to reason
  162.    about the correctness of the algorithms that are needed to maintain
  163.    high availability even when failures, recoveries, or process migra-
  164.    tion occurs.  More recently, we have applied the same approach to a
  165.    variety of other problems in distributed computing, and even designed
  166.    a consistent, fault tolerant, distributed bulletin board data struc-
  167.    ture (a generalized version of the blackboards used in artificial in-
  168.    telligence programs), with equally good results [Birman-c].  Thus, we
  169.    feel that the approach has been shown to work in a variety of set-
  170.    tings where unreliable primitives simply could not be used.
  171.  
  172.  
  173.  
  174. Birman & Joseph                                                 [Page 3]
  175.  
  176. RFC 992                                                    November 1986
  177.  
  178.  
  179.    In the remainder of this memo we summarize the issues and alterna-
  180.    tives that the designer of a distributed system is presented with,
  181.    focusing on two styles of support for fault-tolerant computing: re-
  182.    mote procedure calls coupled with a transactional execution facility,
  183.    such as is used in the ARGUS system [Liskov], and the fault-tolerant
  184.    process group mechanism mentioned above.  We argue that transactional
  185.    interactions are too restrictive to support the sort of mechanism
  186.    needed, and then show how our primitives can be used to provide such
  187.    a mechanism.  We conclude by speculating on future directions in
  188.    which this work might be taken.
  189.  
  190. 4. Issues in fault-tolerance
  191.  
  192.    The difficulty of constructing fault-tolerant distributed software
  193.    can be traced to a number of interrelated issues.  The list that fol-
  194.    lows is not exhaustive, but attempts to touch on the principal con-
  195.    siderations that must be addressed in any such system:
  196.  
  197.       [1]Synchronization.  Distributed systems offer the potential for
  198.       large amounts of concurrency, and it is usually desirable to
  199.       operate at as high a level of concurrency as possible.  However,
  200.       when we move from a sequential execution environment to a con-
  201.       current one, it becomes necessary to synchronize actions that may
  202.       conflict in their access to shared data or entail communication
  203.       with overlapping sets of processes.  Thus, a mechanism is needed
  204.       for ordering conflicting events.  Additional problems that can
  205.       arise in this context include deadlock avoidance or detection,
  206.       livelock avoidance, etc.
  207.  
  208.       [2]Failure detection.  It is usually necessary for a fault-
  209.       tolerant application to have a consistent picture of which com-
  210.       ponents fail, and in what order. Timeout, the most common mechan-
  211.       ism for detecting failure, is unsatisfactory, because there are
  212.       many situations in which a healthy component can timeout with
  213.       respect to one component without this being detected by some
  214.       another.  Failure detection under more rigorous requirements
  215.       requires an agreement protocol that is related to Byzantine agree-
  216.       ment [Strong] [Hadzilacos].  Regardless of how this problem is
  217.       solved, some sort of reliable failure detection mechanism will be
  218.       needed in any fault-tolerant distributed system.
  219.  
  220.       [3] Consistency.  When a group of processes cooperate in a distri-
  221.       buted system, it is necessary to ensure that the operational
  222.       processes have consistent views of the state of the group as a
  223.       whole.  For example, if process p believes that some property A
  224.       holds, and on the basis of this interacts with process q, the
  225.       state of q should not contradict the fact that p believes A to be
  226.       true.  This problem is closely related to notions of knowledge and
  227.       consistency in distributed systems [Halpern] [Lamport].  In our
  228.       context, A will often be the assertion that a multicast has been
  229.       received by q, or that q saw some sequence of events occur in the
  230.  
  231.  
  232.  
  233. Birman & Joseph                                                 [Page 4]
  234.  
  235. RFC 992                                                    November 1986
  236.  
  237.  
  238.       same order as did p.  Thus, it is necessary to be able to specify
  239.       the precise consistency constraints on a distributed software sys-
  240.       tem, and system support should be available to facilitate the
  241.       attainment of these constraints.
  242.  
  243.       [4] Serializability.  Many distributed systems are partitioned
  244.       into data manager processes, which implement shared variables, and
  245.       transaction manager processes, which issue requests to data
  246.       managers [Bernstein].  If transaction managers can execute con-
  247.       currently, it is desirable to ensure that transactions produce
  248.       serializable outcomes [Eswaren] [Papadimitrou].  Serializability
  249.       is increasingly viewed as an important property in "object-
  250.       oriented" distributed systems that package services as abstract
  251.       objects with which clients communicate by remote procedure calls
  252.       (RPC).  On the other hand, there are systems for which serializa-
  253.       bility is either too strong a constraint, or simply inappropriate.
  254.       Thus, one needs a way to achieve serializability in applications
  255.       where it will be needed, without imposing system-wide restrictions
  256.       that would prevent the design of software subsystems for which
  257.       serializability is not needed.
  258.  
  259.    Jointly, these problems render the design of fault-tolerant distri-
  260.    buted software daunting in the absence of adequate support.  The
  261.    correctness of any proposed design and of its implementation become
  262.    serious, if not insurmountable, concerns.  In Sec. 7, we will show
  263.    how the primitives of Sec. 6 provide simple ways to overcome all of
  264.    these issues.
  265.  
  266. 5. Existing alternatives
  267.  
  268.    If one rules out "unreliable" communication mechanisms, there are
  269.    basically two fault-tolerant alternatives that can be pursued.
  270.  
  271.    The first approach is to provide mechanisms for transactional
  272.    interactions between processes that communicate using remote pro-
  273.    cedure calls [Birrell].  This has lead to work on nested transactions
  274.    (due to nested RPC's) [Moss], support for transactions at the
  275.    language level [Liskov], transactions within an operating systems
  276.    kernel [Spector] [Allchin] [Popek] [Lazowska], and transactional
  277.    access to higher-level replicated services, such as resilient objects
  278.    in ISIS or relations in database systems.  The primitives in a tran-
  279.    sactional system provide mechanisms for distributing the request that
  280.    initiates the transaction, accessing data (which may be replicated),
  281.    performing concurrency control, and implementing commit or abort.
  282.    Additional mechanisms are normally needed for orphan termination,
  283.    deadlock detection, etc.  The issue then arises of how these mechan-
  284.    isms should themselves be implemented.
  285.  
  286.    Our work in ISIS leads us to believe that whereas transactions are
  287.    easily implemented on top of fault-tolerant process groups -- we have
  288.    done so -- the converse is much harder.  Moreover, transactions
  289.  
  290.  
  291.  
  292. Birman & Joseph                                                 [Page 5]
  293.  
  294. RFC 992                                                    November 1986
  295.  
  296.  
  297.    represent a relatively heavy-weight solution to the problems surveyed
  298.    in the previous section, and might impose an unacceptable overhead on
  299.    subsystems that need to run non-transactionally, for example because
  300.    a pair of concurrent processes needs to interact on a frequent basis.
  301.    (We are not saying that "transactional" mechanisms such as cobegins
  302.    and toplevel actions can't solve this problem, but just that they
  303.    yield a solution that is awkward and costly).  This sort of reasoning
  304.    has lead us to focus on non-transactional interaction mechanisms, and
  305.    to treat transactions as a special class of mechanisms used when
  306.    processes that have been designed to employ a transactional protocol
  307.    interact.
  308.  
  309.    The second approach involves the provision of a communication primi-
  310.    tive, such as atomic broadcast, which can be used as the framework on
  311.    which higher level algorithms are designed.  Such a primitive seeks
  312.    to deliver messages reliably to some set of destinations, despite the
  313.    possibility that failures might occur during the execution of the
  314.    protocol.  Above, we termed this the fault tolerant process group
  315.    approach, since it lends itself to the organization of cooperating
  316.    processes into groups, as described in the introduction.  Process
  317.    groups are an extremely flexible abstraction, and have been employed
  318.    in the V Kernel [Cheriton] and in UNIX, and more recently in the ISIS
  319.    system.  A proposal to provide Internet support for host groups was
  320.    raised in RFC's 966 and 988.  However, the idea of adapting the pro-
  321.    cess group approach to work reliably in an environment subject to the
  322.    sorts of exception events and concurrency cited in the previous sec-
  323.    tion seems to be new.
  324.  
  325.    As noted earlier, existing reliable communication protocols do not
  326.    address the requirements of fault-tolerant process groups.  For exam-
  327.    ple, in [Schneider], an implementation of a reliable multicast primi-
  328.    tive is described.  Such a primitive ensures that a designated mes-
  329.    sage will be transmitted from one site to all other operational sites
  330.    in a system; if a failure occurs but any site has received the mes-
  331.    sage, all will eventually do so.  [Chang] and [Cristian] describe
  332.    implementations for atomic broadcast, which is a reliable broadcast
  333.    (sent to all sites in a system) with the additional property that
  334.    messages are delivered in the same order at all overlapping destina-
  335.    tions, and this order preserves the transmission order if messages
  336.    originate in a single site.
  337.  
  338.    Atomic broadcast is a powerful abstraction, and essentially the same
  339.    behavior is provided by one of the multicast primitives we discuss in
  340.    the next section.  However, it has several drawbacks which made us
  341.    hesitant to adopt it as the only primitive in the system.  Most seri-
  342.    ous is the latency that is incurred in order to satisfy the delivery
  343.    ordering property.  Without delving deeply into the implementations,
  344.    which are based on a token scheme in [Chang] and an acknowledgement
  345.    protocol in [Schneider], we observe that the delaying of certain mes-
  346.    sages is fundamental to the establishment of a unique global delivery
  347.    ordering; indeed, it is easy to prove on knowledge theoretic grounds
  348.  
  349.  
  350.  
  351. Birman & Joseph                                                 [Page 6]
  352.  
  353. RFC 992                                                    November 1986
  354.  
  355.  
  356.    that this must always be the case.  In [Chang] a primary goal is to
  357.    minimize the number of messages sent, and the protocol given performs
  358.    extremely well in this regard.  However, a delay occurs while waiting
  359.    for tokens to arrive and the delivery latency that results may be
  360.    high.  [Cristian] assumes that clocks are closely synchronized and
  361.    that message transit times are bounded by well-known constants, and
  362.    uses this to derive atomic broadcast protocols tolerant of increas-
  363.    ingly severe classes of failures.  The protocols explicitly delay
  364.    delivery to achieve the desired global ordering on multicasts.  For
  365.    reasons discussed below, this tends to result in high latency in typ-
  366.    ical local networking environments.  An additional drawback of the
  367.    atomic broadcast protocols is that no mechanism is provided for
  368.    ensuring that all processes observe the same sequence of failures and
  369.    recoveries, or for ensuring that failures and recoveries are ordered
  370.    relative to ongoing multicasts.  Since this problem arises in any
  371.    setting where one process monitors another, we felt it should be
  372.    addressed at the same level as the communication protocol.  Finally,
  373.    one wants a group oriented multicast protocol, not a site oriented
  374.    broadcast, and this issue must be resolved too.
  375.  
  376. 6. Our multicast primitives
  377.  
  378.    We now describe three multicast protocols - GBCAST, ABCAST, and
  379.    CBCAST - for transmitting a message reliably from a sender process to
  380.    some set of destination processes.  Details of the protocols and
  381.    their correctness proofs can be found in [Birman-b].  The protocols
  382.    ensure "all or nothing" behavior: if any destination receives a mes-
  383.    sage, then unless it fails, all destinations will receive it.  Group
  384.    addressing is discussed in Sec. 6.5.
  385.  
  386.    The failure model that one adopts has a considerable impact on the
  387.    structure of the resulting system.  We adopted the model of fail-stop
  388.    processors [Schneider]: when failures occur, a processor simply stops
  389.    (crashes), as do all the processes executing on it.  We also assume
  390.    that individual processes can crash, and that this is detected when
  391.    it occurs by a monitoring mechanism present at each site.  Further
  392.    assumptions are sometimes made about the availability of synchronized
  393.    realtime clocks.  Here, we adopt the position that although reason-
  394.    ably accurate elapsed-time clocks may be available, closely synchron-
  395.    ized clocks probably will not be.  For example, the 60Hz "line"
  396.    clocks commonly used on current workstations are only accurate to
  397.    16ms.  On the other hand, 4-8ms inter-site message transit times are
  398.    common and 1-2ms are reported increasingly often.  Thus, it is impos-
  399.    sible to synchronize clocks to better than 32-48ms, enough time for a
  400.    pair of sites to exchange between 4 and 50 messages.  Even with
  401.    advancing technology, it seems safe to assume that clock skew will
  402.    remain "large" when compared to inter-site message transmission
  403.    speed.  In particular, this argues against time-based protocols such
  404.    as the one used in [Cristian]
  405.  
  406.  
  407.  
  408.  
  409.  
  410. Birman & Joseph                                                 [Page 7]
  411.  
  412. RFC 992                                                    November 1986
  413.  
  414.  
  415.    6.1 The GBCAST primitive
  416.  
  417.        GBCAST (group multicast) is the most constrained, and costly, of
  418.        the three primitives.  It is used to transmit information about
  419.        failures and recoveries to members of a process group.  A recov-
  420.        ering member uses GBCAST to inform the operational ones that it
  421.        has become available.  Additionally, when a member fails, the
  422.        system arranges for a GBCAST to be issued to group members on its
  423.        behalf, informing them of its failure.  Arguments to GBCAST are a
  424.        message and a process group identifier, which is translated into
  425.        a set of destinations as described below (Sec. 6.5).
  426.  
  427.        Our GBCAST protocol ensures that if any process receives a multi-
  428.        cast B before receiving a GBCAST G, then all overlapping destina-
  429.        tions will receive B before G <1> This is true regardless of the
  430.        type of multicast involved.  Moreover, when a failure occurs, the
  431.        corresponding GBCAST message is delivered after any other multi-
  432.        casts from the failed process.  Each member can therefore main-
  433.        tain a VIEW listing the membership of the process group, updating
  434.        it when a GBCAST is received.  Although VIEW's are not updated
  435.        simultaneously in real time, all members observe the same
  436.        sequence of VIEW changes.  Since, GBCAST's are ordered relative
  437.        to all other multicasts, all members receiving a given multicast
  438.        will have the same value of VIEW when they receive it.
  439.  
  440.        Notice that GBCAST also provides a convenient way to change other
  441.        global properties of a group "atomically".  In our work, we have
  442.        used GBCAST to dynamically change a ranking on the members of a
  443.        group, to request that group members establish checkpoints for
  444.        use if recovery is needed after all failure, and to implement
  445.        process migration.  In each case, the ordering of GBCAST relative
  446.        to other events that makes it possible to perform the desired
  447.        action without running any additional protocol.  Other uses for
  448.        GBCAST will no doubt emerge as our research continues.
  449.  
  450.        Members of a process group can also use the value of VIEW to pick
  451.        a strategy for processing an incoming request, or to react to
  452.        failure or recovery without having to run any special protocol
  453.        first.  Since the GBCAST ordering is the same everywhere, their
  454.        actions will all be consistent.  Notice that when all the members
  455.        of a process group may have failed, GBCAST also provides an inex-
  456.        pensive way to determine the last site that failed: process group
  457.        members simply log each value of VIEW that becomes defined on
  458.        stable storage before using it; a simplified version of the algo-
  459.        rithm in [Skeen-a] can then be executed when recovering from
  460.        failure.
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469. Birman & Joseph                                                 [Page 8]
  470.  
  471. RFC 992                                                    November 1986
  472.  
  473.  
  474.    6.2 The ABCAST primitive
  475.  
  476.        The GBCAST primitive is too costly to be used for general commun-
  477.        ication between process group members.  This motivates the intro-
  478.        duction of weaker (less ordered) primitives, which might be used
  479.        in situations where a total order on multicast messages is not
  480.        necessary.  Our second primitive, ABCAST (atomic multicast),
  481.        satisfies such a weaker constraint.  Specifically, it is often
  482.        desired that if two multicasts are received in some order at a
  483.        common destination site, they be received in that order at all
  484.        other common destinations, even if this order was not predeter-
  485.        mined.  For example, if a process group is being used to maintain
  486.        a replicated queue and ABCAST is used to transmit queue opera-
  487.        tions to all copies, the operations will be done in the same
  488.        order everywhere, hence the copies of the queue will remain mutu-
  489.        ally consistent.  The primitive ABCAST(msg, label, dests) pro-
  490.        vides this behavior.  Two ABCAST's having the same label are
  491.        delivered in the same order at all common destinations.
  492.  
  493.    6.3 The CBCAST primitive
  494.  
  495.        Our third primitive, CBCAST (causal multicast), is weakest in the
  496.        sense that it involves less distributed synchronization then
  497.        GBCAST or ABCAST.  CBCAST(msg, dests) atomically delivers msg to
  498.        each operational dest.  The CBCAST protocol ensures that if two
  499.        multicasts are potentially causally dependent on another, then
  500.        the former is delivered after the latter at all overlapping des-
  501.        tinations.  A multicast B' is potentially causally dependent on a
  502.        multicast B if both multicasts originate from the same process,
  503.        and B' is sent after B, or if there exists a chain of message
  504.        transmissions and receptions or local events by which knowledge
  505.        could have been transferred from the process that issued B to the
  506.        process that issued B' [Lamport].  For causally independent mul-
  507.        ticasts, the delivery ordering is not constrained.
  508.  
  509.        CBCAST is valuable in systems like ISIS, where concurrency con-
  510.        trol algorithms are used to synchronize concurrent computations.
  511.        In these systems, if two processes communicate concurrently with
  512.        the same process the messages are almost always independent ones
  513.        that can be processed in any order: otherwise, concurrency con-
  514.        trol would have caused one to pause until the other was finished.
  515.        On the other hand, order is clearly important within a causally
  516.        linked series of multicasts, and it is precisely this sort of
  517.        order that CBCAST respects.
  518.  
  519.    6.4 Other multicast primitives
  520.  
  521.        A weaker multicast primitive is reliable multicast, which pro-
  522.        vides all-or-nothing delivery, but no ordering properties.  The
  523.        formulation of CBCAST in [Birman-b] actually includes a mechanism
  524.        for performing multicasts of this sort, hence no special
  525.  
  526.  
  527.  
  528. Birman & Joseph                                                 [Page 9]
  529.  
  530. RFC 992                                                    November 1986
  531.  
  532.  
  533.        primitive is needed for the purpose.  Additionally, there may be
  534.        situations in which ABCAST protocols that also satisfy a CBCAST
  535.        ordering property would be valuable.  Our ABCAST primitive could
  536.        be changed to respect such a rule, and we made use of a multicast
  537.        primitive that is simultaneously causal and atomic in our work on
  538.        consistent shared bulletin boards ([Birman-c]).  For simplicity,
  539.        the presentation here assumes that ABCAST is completely orthogo-
  540.        nal to CBCAST, but a simple way to build an efficient "causal
  541.        atomic" multicast is described in our full-length paper.  The
  542.        cost of this protocol is only slightly higher than that of
  543.        ABCAST.
  544.  
  545.    6.5 Group addressing protocol
  546.  
  547.        Since group membership can change dynamically, it may be diffi-
  548.        cult for a process to compute a list of destinations to which a
  549.        message should be sent, for example, as is needed to perform a
  550.        GBCAST.  In [Birman-b] we report on a protocol for ensuring that
  551.        a given multicast will be delivered to all members of a process
  552.        group in the same view.  This view is either the view that was
  553.        operative when the message transmission was initiated, or a view
  554.        that was defined subsequently.  The algorithm is a simple itera-
  555.        tive one that costs nothing unless the group membership changes,
  556.        and permits the caching of possibly inaccurate membership infor-
  557.        mation near processes that might want to communicate with a
  558.        group.  Using the protocol, a flexible message addressing scheme
  559.        can readily be supported.
  560.  
  561.        Iterative addressing is only required when the process transmit-
  562.        ting a message has an inaccurate copy of the process group view.
  563.        In the implementation we are now building, this would rarely be
  564.        the case, and iteration is never needed if the view is known to
  565.        be accurate.  Thus, iterated delivery should be very infrequent.
  566.  
  567.    6.6 Synchronous versus asynchronous multicast abstractions
  568.  
  569.        Many systems employ RPC internally, as a lowest level primitive
  570.        for interaction between processes.  It should be evident that all
  571.        of our multicast primitives can be used to implement replicated
  572.        remote procedure calls [Cooper]: the caller would simply pause
  573.        until replies have been received from all the participants
  574.        (observation of a failure constitutes a reply in this case).  We
  575.        term such a use of the primitives synchronous, to distinguish it
  576.        from from an asynchronous multicast in which no replies, or just
  577.        one reply, suffices.
  578.  
  579.        In our work on ISIS, GBCAST and ABCAST are normally invoked syn-
  580.        chronously, to implement a remote procedure call by one member of
  581.        an object on all the members of its process group.  However,
  582.        CBCAST, which is the most frequently used overall, is almost
  583.        never invoked synchronously.  Asynchronous CBCAST's are the
  584.  
  585.  
  586.  
  587. Birman & Joseph                                                [Page 10]
  588.  
  589. RFC 992                                                    November 1986
  590.  
  591.  
  592.        primary source of concurrency in ISIS: although the delivery ord-
  593.        ering is assured, transmission can be delayed to enable a message
  594.        to be piggybacked on another, or to schedule IO within the system
  595.        as a whole.  While the system cannot defer an asynchronous multi-
  596.        cast indefinitely, the ability to defer it a little, without
  597.        delaying some computation by doing so, permits load to be
  598.        smoothed.  Since CBCAST respects the delivery orderings on which
  599.        a computation might depend, and is ordered with respect to
  600.        failures, the concurrency introduced does not complicate higher
  601.        level algorithms.  Moreover, the protocol itself is extremely
  602.        cheap.
  603.  
  604.        A problem is introduced by our decision to allow asynchronous
  605.        multicasts: the atomic reception property must now be extended to
  606.        address causally related sequences of asynchronous messages.  If
  607.        a failure were to result in some multicasts being delivered to
  608.        all their destinations but others that precede them not being
  609.        delivered anywhere, inconsistency might result even if the desti-
  610.        nations do not overlap.  We therefore extend the atomicity pro-
  611.        perty as follows.  If process t receives a message m from process
  612.        s, and s subsequently fails, then unless t fails as well, all
  613.        messages m' that s received prior to its failure must be
  614.        delivered to their remaining operational destinations.  This is
  615.        because the state of t may now depend on the contents of any such
  616.        m', hence the system state could become inconsistent if the
  617.        delivery of m' were not completed.  The costs of the protocols
  618.        are not affected by this change.
  619.  
  620.        A second problem arises when the user-level implications of this
  621.        atomicity rule are considered.  In the event of a failure, any
  622.        suffix of a sequence of aysnchronous multicasts could be lost and
  623.        the system state would still be internally consistent.  A process
  624.        that is about to take some action that may leave an externally
  625.        visible side-effect will need a way to pause until it is
  626.        guaranteed that such multicasts have actually been delivered.
  627.        For this purpose, a flush primitive is provided.  Occasional
  628.        calls to flush do not eliminate the benefit of using CBCAST asyn-
  629.        chronously.  Unless the system has built up a considerable back-
  630.        log of undelivered multicast messages, which should be rare,
  631.        flush will only pause while transmission of the last few multi-
  632.        casts complete.
  633.  
  634. 7. Using the primitives
  635.  
  636.    The reliable communication primitives described above lead to simple
  637.    solutions for the problems cited in Sec. 4:
  638.  
  639.        [1]  Synchronization.  Many synchronization problems are subsumed
  640.        into the primitives themselves.  For example, consider the use of
  641.        GBCAST to implement recovery.  A recovering process would issue a
  642.        GBCAST to the process group members, requesting that state
  643.  
  644.  
  645.  
  646. Birman & Joseph                                                [Page 11]
  647.  
  648. RFC 992                                                    November 1986
  649.  
  650.  
  651.        information be transferred to it.  In addition to sending the
  652.        current state of the group to the recovering process, group
  653.        members update the process group view at this time.  Subsequent
  654.        messages to the group will be delivered to the recovered process,
  655.        with all necessary synchronization being provided by the ordering
  656.        properties of GBCAST.  In situations where other forms of syn-
  657.        chronization are needed, ABCAST provides a simple way to ensure
  658.        that several processes take actions in the same order, and this
  659.        form of low-level synchronization simplifies a number of higher-
  660.        level synchronization problems.  For example, if ABCAST is used
  661.        to do P() and V() operations on a distributed semaphore, the
  662.        order of operations on the semaphore is set by the ABCAST, hence
  663.        all the managers of the semaphore see these operations in a fixed
  664.        order.
  665.  
  666.        [2]  Failure detection.  Consistent failure (and recovery) detec-
  667.        tion are trivial using our primitives: a process simply waits for
  668.        the appropriate process group view to change.  This facilitates
  669.        the implementation of algorithms in which one processes monitors
  670.        the status of another process.  A process that acts on the basis
  671.        of a process group view change does so with the assurance that
  672.        other group members will (eventually) observe the same event and
  673.        will take consistent actions.
  674.  
  675.        [3]  Consistency.  We believe that consistency is generally
  676.        expressible as a set of atomicity and ordering constraints on
  677.        message delivery, particularly causal ones of the sort provided
  678.        by CBCAST.  Our primitives permit a process to specify the com-
  679.        munication properties needed to achieve a desired form of con-
  680.        sistency.  Continued research will be needed to understand pre-
  681.        cisely how to pick the weakest primitive in a designated situa-
  682.        tion.
  683.  
  684.        [4]  Serializability.  To achieve serializability, one implements
  685.        a concurrency control algorithm and then forces computations to
  686.        respect the serialization order that this algorithm choses.  The
  687.        ABCAST primitive, as observed above, is a powerful tool for
  688.        establishing an order between concurrent events, e.g. by lock
  689.        acquisition.  Having established such an order, CBCAST can be
  690.        used to distribute information about the computation and also its
  691.        termination (commit or abort).  Any process that observes the
  692.        commit or abort of a computation will only be able to interact
  693.        with data managers that have received messages preceding the com-
  694.        mit or abort, hence a highly asynchronous transactional execution
  695.        results.  If a process running a computation fails, this is
  696.        detected when a failure GBCAST is received instead of the commit.
  697.        Thus, executions are simple and quite deterministic.
  698.  
  699.        If commit is conditional, CBCAST would be used to first interro-
  700.        gate participants to learn if they are prepared to commit, and
  701.        then to transmit the commit or abort decision (the usual two-
  702.  
  703.  
  704.  
  705. Birman & Joseph                                                [Page 12]
  706.  
  707. RFC 992                                                    November 1986
  708.  
  709.  
  710.        phase commit).  On the other hand, conditional commits can often
  711.        be avoided using our approach.  A method for building transac-
  712.        tions that will roll-forward after failure after failure is dis-
  713.        cussed in more detail in [Birman-a] [Joseph-a] [Joseph-b].  Other
  714.        forms of concurrency control, such as timestamp generation, can
  715.        similarly be implemented using ABCAST and CBCAST.  We view tran-
  716.        sactional data storage as an application-level concern, which can
  717.        be handled using a version stack approach or a multi-version
  718.        store, or any other appropriate mechanism.
  719.  
  720. 8. Implementation
  721.  
  722.    The communication primitives can be built in layers, starting with a
  723.    bare network providing unreliable Internet datagrams.  The software
  724.    structure is, however, less mature and more complex than the one sug-
  725.    gested in RFC's 966 and 988.  For example, at this stage of our
  726.    research we do not understand how to optimize our protocols to the
  727.    same extent as for the unreliable host multicast approach described
  728.    in those RFC's.  Thus, the implementation we describe here should be
  729.    understood to be a prototype.  A particularly intriguing question,
  730.    which we are investigating actively, concerns the use of a "best
  731.    effort" ethernet or Internet multicast as a tool to optimize the
  732.    implementation of our protocols.
  733.  
  734.    Our basic approach is to view large area networks as a set of clus-
  735.    ters of sites interconnected by high speed LAN devices and intercon-
  736.    nected by slower long-haul links.  We first provide protocols for use
  737.    within clusters, and then extend them to run between clusters too.
  738.    Network partitioning can be tolerated at all levels of the hierarchy
  739.    in the sense that no incorrect actions can result after network par-
  740.    titioning, although our approach will sometimes block until the par-
  741.    tition is repaired.  Our protocols also tend to block within a clus-
  742.    ter while the list of operational sites for that cluster is being
  743.    changed.  In normal LAN's, this happens infrequently (during site
  744.    failure or recovery), and would not pose a problem.  (In failure
  745.    intensive applications, alternative protocols might be needed to
  746.    address this issue).
  747.  
  748.    The lowest level of our software uses a site-to-site acknowledgement
  749.    protocol to convert the unreliable packet transport this into a
  750.    sequenced, error-free message abstraction, using timeouts to detect
  751.    apparent failures.  TCP can also be used for this purpose, provided
  752.    that a "filter" is placed on the incoming message stream and certain
  753.    types of messages are handled specially.  An agreement protocol is
  754.    then used to order the site-failures and recoveries consistently.  If
  755.    timeouts cause a failure to be detected erroneously, the protocol
  756.    forces the affected site to undergo recovery.
  757.  
  758.    Built on this is a layer that supports the primitives themselves.
  759.    CBCAST has a very light-weight implementation, based on the idea of
  760.    flooding the system with copies of a message: Each process buffers
  761.  
  762.  
  763.  
  764. Birman & Joseph                                                [Page 13]
  765.  
  766. RFC 992                                                    November 1986
  767.  
  768.  
  769.    copies of any messages needed to ensure the consistency of its view
  770.    of the system.  If message m is delivered to process p, and m is
  771.    potentially causally dependent on a message m prime, then a copy of m
  772.    prime is sent to p as well (duplicates are discarded).  A garbage
  773.    collector deletes superfluous copies after a message has reached all
  774.    its destinations.  By using extensive piggybacking and a simple
  775.    scheduling algorithm to control message transmission, the cost of a
  776.    CBCAST is kept low -- often, less than one packet per destination.
  777.    ABCAST employs a two-phase protocol based on one suggested to us by
  778.    Skeen [Skeen-b].  This protocol has higher latency than CBCAST
  779.    because delivery can only occur during the second phase; ABCAST is
  780.    thus inherently synchronous.  In ISIS, however, ABCAST is used
  781.    rarely; we believe that this would be the case in other systems as
  782.    well.  GBCAST is implemented using a two-phase protocol similar to
  783.    the one for ABCAST, but with an additional mechanism that flushes
  784.    messages from a failed process before delivering the GBCAST announc-
  785.    ing the failure.  Although GBCAST is slower than ABCAST or CBCAST, it
  786.    is used rarely enough so that performance is probably less of an
  787.    issue here -- and in any case, even GBCAST could be tuned to give
  788.    very high throughput.  Preliminary performance figures appear in
  789.    [Birman-b].
  790.  
  791.    Although satisfactory performance should be possible using an imple-
  792.    mentation that sits on top of a conventional Internet mechanism, it
  793.    should be noted that to achieve really high rates of communication
  794.    the layers of software described above must reside in the kernel,
  795.    because they run on behalf of large numbers of clients, run fre-
  796.    quently, and tend to execute for very brief periods before doing I/O
  797.    and pausing.  A non-kernel implementation will thus incur high
  798.    scheduling and context switching overhead.  Additionally, it is not
  799.    at all clear how to use ethernet style broadcast mechanisms to optim-
  800.    ize the performance of this sort of protocol, although it should be
  801.    possible.  We view this as an interesting area for research.
  802.  
  803.    A forthcoming paper will describe higher level software that we are
  804.    building on top of the basic fault-tolerant process group mechanism
  805.    described above.
  806.  
  807. 9. Conclusions
  808.  
  809.    The experience of implementing a substantial fault-tolerant system
  810.    left us with insights into the properties to be desired from a com-
  811.    munication subsystem.  In particular, we became convinced that to
  812.    build a reliable distributed system, one must start with a reliable
  813.    communication subsystem.  The multicast primitives described in this
  814.    memo present a simple interface, achieve a high level of concurrency,
  815.    can be used in both local and wide area networks, and are applicable
  816.    to software ranging from distributed database systems to the fault-
  817.    tolerant objects and bulletin boards provided by ISIS.  Because they
  818.    are integrated with failure handling mechanisms and respect desired
  819.    event orderings, they introduce a desirable form of determinism into
  820.  
  821.  
  822.  
  823. Birman & Joseph                                                [Page 14]
  824.  
  825. RFC 992                                                    November 1986
  826.  
  827.  
  828.    distributed computation without compromising efficiency.  A conse-
  829.    quence is that high-level algorithms are greatly simplified, reducing
  830.    the probability of error.  We believe that this is a very promising
  831.    and practical approach to building large fault-tolerant distributed
  832.    systems, and it is the only one we know of that leads to a rigorous
  833.    form of confidence in the resulting software.
  834.  
  835. NOTES:
  836.  
  837.    <1> A problem arises if a process p fails without receiving some mes-
  838.    sage after that message has already been delivered to some other pro-
  839.    cess q: q's VIEW when it received the message would show p to be
  840.    operational; hence, q will assume that p received the message,
  841.    although p is physically incapable of doing so.  However, the state
  842.    of the system is now equivalent to one in which p did receive the
  843.    message, but failed before acting on it.  In effect, there exists an
  844.    interpretation of the actual system state that is consistent with q's
  845.    assumption.  Thus, GBCAST satisfies the sort of logical delivery pro-
  846.    perty cited in the introduction.
  847.  
  848.  
  849.  
  850.  
  851.  
  852.  
  853.  
  854.  
  855.  
  856.  
  857.  
  858.  
  859.  
  860.  
  861.  
  862.  
  863.  
  864.  
  865.  
  866.  
  867.  
  868.  
  869.  
  870.  
  871.  
  872.  
  873.  
  874.  
  875.  
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882. Birman & Joseph                                                [Page 15]
  883.  
  884. RFC 992                                                    November 1986
  885.  
  886.  
  887. 10. References
  888.  
  889. [RFC966] Deering, S. and Cheriton, D.  Host groups: A multicast exten-
  890.       sion to the internet protocol.  Stanford University, December
  891.       1985.
  892.  
  893. [RFC988] Deering, S.  Host extensions for IP multicasting.  Stanford
  894.       University, July 1986.
  895.  
  896. [Allchin] Allchin, J., McKendry, M.  Synchronization and recovery of
  897.       actions.  Proc. 2nd ACM SIGACT/SIGOPS Principles of Distributed
  898.       Computing, Montreal, Canada, 1983.
  899.  
  900. [Babaoglu] Babaoglu, O., Drummond, R.  The streets of Byzantium: Network
  901.       architectures for fast reliable multicast.  IEEE Trans. on
  902.       Software Engineering TSE-11, 6 (June 1985).
  903.  
  904. [Bernstein] Bernstein, P., Goodman, N.  Concurrency control algorithms
  905.       for replicated database systems.  ACM Computing Surveys 13, 2
  906.       (June 1981), 185-222.
  907.  
  908. [Birman-a] Birman, K.  Replication and fault-tolerance in the ISIS sys-
  909.       tem.  Proc. 10th ACM SIGOPS Symposium on Operating Systems Princi-
  910.       ples.  Orcas Island, Washington, Dec. 1985, 79-86.
  911.  
  912. [Birman-b] Birman, K., Joseph, T.  Reliable communication in the pres-
  913.       ence of failures.  Dept. of Computer Science, Cornell Univ., TR
  914.       85-694, Aug. 1985.  To appear in ACM TOCS (Feb. 1987).
  915.  
  916. [Birman-c] Birman, K., Joseph, T., Stephenson, P.  Programming with
  917.       fault tolerant bulletin boards in asynchronous distributed sys-
  918.       tems.  Dept. of Computer Science, Cornell Univ., TR 85-788, Aug.
  919.       1986.
  920.  
  921. [Birrell] Birrell, A., Nelson, B.  Implementing remote procedure calls.
  922.       ACM Transactions on Computer Systems 2, 1 (Feb. 1984), 39-59.
  923.  
  924. [Chang] Chang, J., Maxemchuck, M. Reliable multicast protocols.  ACM
  925.       TOCS 2, 3 (Aug. 1984), 251-273.
  926.  
  927. [Cheriton] Cheriton, D. The V Kernel: A software base for distributed
  928.       systems.  IEEE Software 1 12, (1984), 19-43.
  929.  
  930. [Cooper] Cooper, E. Replicated procedure call.  Proc. 3rd ACM Symposium
  931.       on Principles of Distributed Computing., August 1984, 220-232.
  932.       (May 1985).
  933.  
  934. [Cristian] Cristian, F. et al Atomic multicast: From simple diffusion to
  935.       Byzantine agreement.  IBM Technical Report RJ 4540 (48668), Oct.
  936.       1984.
  937.  
  938.  
  939.  
  940.  
  941. Birman & Joseph                                                [Page 16]
  942.  
  943. RFC 992                                                    November 1986
  944.  
  945.  
  946. [Eswaren] Eswaren, K.P., et al The notion of consistency and predicate
  947.       locks in a database system.  Comm. ACM 19, 11 (Nov. 1976), 624-
  948.       633.
  949.  
  950. [Hadzilacos] Hadzilacos, V.  Byzantine agreement under restricted types
  951.       of failures (not telling the truth is different from telling of
  952.       lies).  Tech. ARep. TR-19-83, Aiken Comp. Lab., Harvard University
  953.       (June 1983).
  954.  
  955. [Halpern] Halpern, J., and Moses, Y.  Knowledge and common knowledge in
  956.       a distributed environment.  Tech. Report RJ-4421, IBM San Jose
  957.       Research Laboratory, 1984.
  958.  
  959. [Joseph-a] Joseph, T.  Low cost management of replicated data.  Ph.D.
  960.       dissertation, Dept. of Computer Science, Cornell Univ., Ithaca
  961.       (Dec. 1985).
  962.  
  963. [Joseph-b] Joseph, T., Birman, K.  Low cost management of replicated
  964.       data in fault-tolerant distributed systems.  ACM TOCS 4, 1 (Feb
  965.       1986), 54-70.
  966.  
  967. [Lamport] Lamport, L.  Time, clocks, and the ordering of events in a
  968.       distributed system.  CACM 21, 7, July 1978, 558-565.
  969.  
  970. [Lazowska] Lazowska, E. et al The architecture of the EDEN system.
  971.       Proc. 8th Symposium on Operating Systems Principles, Dec. 1981,
  972.       148-159.
  973.  
  974. [Liskov] Liskov, B., Scheifler, R. Guardians and actions: Linguistic
  975.       support for robust, distributed programs.  ACM TOPLAS 5, 3 (July
  976.       1983), 381-404.
  977.  
  978. [Moss] Moss, E.  Nested transactions: An approach to reliable, distri-
  979.       buted computing.  Ph.D. thesis, MIT Dept of EECS, TR 260, April
  980.       1981.
  981.  
  982. [Papadimitrou] Papadimitrou, C.  The serializability of concurrent data-
  983.       base updates.  JACM 26, 4 (Oct. 1979), 631-653.
  984.  
  985. [Popek] Popek, G. et al.  Locus: A network transparent, high reliability
  986.       distributed system.  Proc. 8th Symposium on Operating Systems
  987.       Principles, Dec. 1981, 169-177.
  988.  
  989. [Schlicting] Schlicting, R, Schneider, F.  Fail-stop processors: An
  990.       approach to designing fault-tolerant distributed computing sys-
  991.       tems.  ACM TOCS 1, 3, August 1983, 222-238.
  992.  
  993. [Schneider] Schneider, F., Gries, D., Schlicting, R.  Reliable multicast
  994.       protocols.  Science of computer programming 3, 2 (March 1984).
  995.  
  996. [Skeen-a] Skeen, D.  Determining the last process to fail.  ACM TOCS 3,
  997.  
  998.  
  999.  
  1000. Birman & Joseph                                                [Page 17]
  1001.  
  1002. RFC 992                                                    November 1986
  1003.  
  1004.  
  1005.       1, Feb. 1985, 15-30.
  1006.  
  1007. [Skeen-b] Skeen, D.  A reliable multicast protocol.  Unpublished.
  1008.  
  1009. [Spector] Spector, A., et al  Distributed transactions for reliable sys-
  1010.       tems.  Proc. 10th ACM SIGOPS Symposium on Operating Systems Prin-
  1011.       ciples, Dec. 1985, 127-146.
  1012.  
  1013. [Strong] Strong, H.R., Dolev, D. Byzantine agreement. Digest of papers,
  1014.       Spring Compcon 83, San Francisco, CA, March 1983, 77-81.
  1015.  
  1016.  
  1017.  
  1018.  
  1019.  
  1020.  
  1021.  
  1022.  
  1023.  
  1024.  
  1025.  
  1026.  
  1027.  
  1028.  
  1029.  
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.  
  1040.  
  1041.  
  1042.  
  1043.  
  1044.  
  1045.  
  1046.  
  1047.  
  1048.  
  1049.  
  1050.  
  1051.  
  1052.  
  1053.  
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059. Birman & Joseph                                                [Page 18]
  1060.  
  1061.