# Discussion for: Kenneth Birman, André Schiper, and Pat Stephenson, "Lightweight Causal and Atomic Group Multicast" (TOCS, 1991)

## Paper overview

This paper addresses the challenges of distributed systems, focusing on various types of process groups, such as Peer, client/server, diffusion, and hierarchical. First, some issues with the ISIS toolkit are discussed. The authors introduce two protocols, CBCAST and ABCAST, as additions to the ISIS toolkit, to ensure causally ordered and totally ordered multicast communication.

The CBCAST protocol uses vector timestamps to maintain causal ordering, ensuring that messages are delivered in a manner consistent with causality, even in the presence of concurrent events. ABCAST tries to extend this causality into total ordering, allowing for a better ordering of concurrent messages.

The paper emphasizes the importance of confirming that a multicast message reaches all intended recipients for Multicast Stability. To reduce data in each multicast message, the paper discusses Vector Timestamp (VT) compression, which only sends altered fields. Finally, the paper suggests using virtually synchronous addressing and efficient flush coordinator strategies to maintain atomicity in distributed systems during group membership alterations or failures.

However, the paper does raise some potential concerns, particularly regarding process failures or departures from a group, which are addressed through the concept of “flushing” the group. Additionally, it’s crucial to note that the protocols assume a lossless, uncorrupted, and sequenced message delivery at the transport layer, which is a significant assumption. Despite these challenges, the paper provides insights into achieving reliable and ordered message delivery in distributed systems.

## Discussion questions

### Q1

*Contributed by Yunqian Cheng*

The paper mentions that delivery ordering can be total without being causal. In section 5.2, the authors used an example with m, m', and m'' to explain this, but I don't quite understand it. Can you give an example (possibly by drawing a Lamport diagram) of an execution in which message delivery is totally ordered, but *not* causally ordered?

#### Discussion summary for Q1

An example of an execution in which message delivery is totally ordered but not causally ordered would be: the system has a process A that broadcasts two messages to process B and C, who received and delivered these two messages in the same reversed order. In this example, since both of the message-delivering processes - B and C - delivered the message in the same order, this is a totally ordered message delivery. However, this execution violates the FIFO and causal delivery since two messages from the same process A were delivered in an order different from the one in which they were sent.

We found that many people in the class were confused about the definition of a totally ordered delivery. The confusion mainly centered around why the order in which the messages are sent is not considered while determining whether the message delivery is totally ordered. We believe the key is the word “message delivery” in “totally ordered message delivery.” Literally, it only considers the message delivery.

### Q2

*Contributed by Zackary Jorquera*

ABCAST guarantees a total message delivery ordering in the sense that all messages are delivered in the same order on all processes. But, if the order of delivery of concurrently sent messages is arbitrary (i.e., the issues seen in class justifying the need for causal delivery, like the "bob smells" one, don't apply), then what use cases would require an ABCAST protocol? My first guess is in resource management, similar to the use case of a total ordering in the Lamport paper. Is this also the use case for ABCAST?

#### Discussion summary for Q2

One key use case for ABCAST is in distributed databases where the order of operations/queries must be consistent across all machines. For example, if two requests are made concurrently, say i <- 2 and i <- i + 1, then it is arbitrary which is delivered first, but it does matter that all machines making up the database apply them in the same order to ensure a consensus of the data stored in the database. More generally, the problem of achieving consensus among all machines would also require a total message delivery order.

In the Lamport paper, a total ordering (for happens-before) was used to “determine” which process sent the resource access request first. This was in an effort to be consistent with causality while maintaining a consensus on who gets to access the resource. While ABCAST guarantees a total message delivery order, which gives a consensus, it doesn’t, in general, give a causal ordering, which is arguably more important. So, while it can be seen as a necessary condition for the resource management described in the Lamport paper, it is not a sufficient condition.

### Q3

The CBCAST protocol does the "usual vector clock thing" of merging the received vector clock (VC) with the local VC by taking their *pointwise maximum* whenever a message is delivered, and then updating the local VC to this new, merged value. This happens in step (3) of the protocol in section 5.1, which says that the local VC is updated "in accordance with the vector time protocol from Section 4.3." Turning to section 4.3, the pointwise maximum computation happens in step (4) of the protocol described there.

However, a small optimization to this protocol is possible, so you don't have to take the pointwise maximum. Can you think of what the optimization is, and why is it OK to do in CBCAST? (It is not discussed in the paper, as far as I can tell!)

#### Discussion summary for Q3

One optimization we thought of is that: When a message is sent, the VT of that sender process is incremented by 1, and when it is delivered on the receiving endpoint, both timestamps from the sender and the one at the receiving endpoint are compared, in that case the sender’s timestamp is going always to be the maximum as it was incremented by 1 before sending the message. So here, we can just accept the sender’s VT and skip the “pointwise maximum”.

Another way of doing optimization is from the “grouping” idea: The process only tracks some subsets (small groups) of the entire causal relationship, in other words, it cares about the VT of a consistent local area in the network.

In CBCAST, the goal is to maintain causal order, not total order. The optimization still respects the causal dependencies, as it ensures that messages are delivered in a causally consistent order. Taking direct values from the sender's VC for its own messages respects this causal order, as messages are sent and timestamped by the sender in the order they are generated. Furthermore, we can try to reduce the dimension of VT, that is, each process only cares about itself and the clocks of the processes it interacts with. This can greatly reduce the dimensions of VT, thereby reducing communication overhead.

## Errata

Typos or other issues found in the paper:

N/A due to time limit.

## Other

Any interesting points or questions from the group discussion that didn't fit
above:

N/A due to time limit.