Citation:
K. Birman, A. Schiper, and P. Stephenson, "Lightweight Causal and Atomic Group
Multicast", ACM Transactions on Computer Systems, August 1991, pp. 272-314.

* Summary

The ISIS toolkit is a distributed programming environment based on virtually
synchronous process groups and group communication. To support this model,
a family of protcols are presented. A multicast primitive known as CBCAST
implements fault-tolerant, causally ordered message delivery, and is central
to the model. Another primitive called ABCAST is an extension to CBCAST that
allows a totally ordered multicast.

* System Model

The system is composed of processes with disjoint memory spaces. When processes
need to cooperate, they can be structured into process groups. Each process
group has a name and a set of member processes, who join and leave dynamically.
The communication protocols assume that processes only multicast to groups
that they are members of, and all multicasts are directed to a full group
membership. A view of a process group is a list of its members, and a view
sequence is a list of views where the difference between successive views
is a single process addition or deletion. Failures of processes are only
noticed by changes in group views, not through direct observation. The execution
of a process is a partially ordered sequence of events, as in [L78]. For 
liveness, it is assumes that any message sent is eventually received unless the
sender or destination fails, and that failures are detected and eventually
reflected in a new group view.

* Virtual Synchrony

ISIS is a virtually synchronous programming environment, so that users can
program as if the system scheduled one distributed event at a time. In
actuality, operations are often performed concurrently and multicasts are often
issued asynchronously. Virtual synchrony encompasses two major aspects.
(1) Address expansion: group identifiers are used as the destination of a
    multicast; the protocol expands identifiers into destination lists and
    delivers messages such that
  - all the recipients are in identical group views when the message arrives
  - the destination list consists of precisely the members of that view
(2) Delivery atomicity and order: either all operational destinations receive
    a copy of a message, or if the sender fails none do; when multiple
    destinations receive the same message, they observe consistent delivery 
    orders with respect to causally-related messages.

Causal delivery ordering for messages m and m' can be defined as:
-  if m -> m', then for all p in dests(m) intersect dests(m'), deliver(m) -> 
   deliver(m') at p
CBCAST provides only causal ordering, and does not restrict the deliver ordering
of concurrent messages. ABCAST extends the causal ordering into a total one,
such that the delivery ordering at all destinations is the same.
-  if there exists m and m' such that a process p in group g has deliver(m) ->
   deliver(m'), then for all proceses q in group g, deliver(m) -> deliver(m')
   at q

* Vector Time

The ISIS delivery protocol is based on a logical clock called a vector clock.
A vector time for a process p, denoted VT(p), is a vector of length n = |P|
indexed by process id. The rules for maintaining the vector clock are:
(1) when p starts execution, VT(p) is initialized to all zeros
(2) for each send event at p_i, VT(p_i)[i] is incremented
(3) each message is timestamped with the incremented value of VT(p_i)
(4) when process q delivers a message from p containing VT(m), q modifies its
    vector clock in the following manner: 
    -  for k = 1 to n, VT(q)[k] = max(VT(q)[k], VT(m)[k])

The rules for comparing timestamps are:
(1) VT1 <= VT2 iff for all i, VT1[i] <= VT2[i]
(2) VT1 < VT2 if VT1 <= VT2 and there exists an i such that VT1[i] < VT2[i]

The vector timestamp assigned to a message m thus represents the number of 
messages, on a per-sender basis, that causally precede m. It can be shown that
given messages m and m', m -> m' iff VT(m) < VT(m').

* CBCAST

To implement CBCAST, a receiver of a message m will delay m until VT(m)[k]
messages have been delivered from p_k. The protocol acts as follows:
(1) before sending m, process p_i increments VT(p_i)[i] and timestamps m
(2) on reception of message m from p_i, p_j != p_i delays delivery until
    for all k !=i, VT(m)[k] <= VT(p_j)[k], and VT(m)[i] = VT(p_j)[i] + 1
(3) when a message m is delivered, VT(p_j) is updated according to the vector
    time protocol
 
* ABCAST

The ABCAST provided by ISIS provides a total ordering that conforms with
causality, such that when a process sends a message m using ABCAST, then sends
m' using CBCAST and some recipient of m' sends m" using ABCAST, then
m -> m' -> m" and m will always be delivered before m".

To implement ABCAST, there is a token holder process associated with each view 
of a process group. To ABCAST a message m, a process holding the token uses 
CBCAST to transmit m in the normal manner. If the sender does not hold the
token, the ABCAST procedes in stages:
(1) the sender CBCASTs m but marks it undeliverable, so that processes other
    than the token holder will not deliver the message even when all
    causally-precedent messages have been delivered
(2) the token holder treats incoming ABCASTs as it would treat CBCASTs, but
    also records the uid of each ABCAST
(3) after delivering one or more ABCASTs, the token holder CBCASTs a sets-order 
    message giving a list of one or more messages, identified by uid, and 
    ordered in the delivery order it used in step 2. The sending of the
    sets-order CBCAST can be delayed to batch them, but must be sent before
    any subsequent ABCAST or CBCAST by the token holder.
(4) on receipt of a sets-order message, a process places it on the CBCAST delay
    queue in the normal manner. eventually, all ABCAST messages referred to in
    the sets-order message will be received, and all CBCAST messages that
    causally-precede the sets-order will have been delivered. the ABCASTs are
    now reordered according to the order in the sets-order, and marks them as
    deliverable
(5) deliverable ABCASTs can be delivered off the front of the queue