Question

To what extent is scalability of atomic multicast important? Also, explain why totally ordered multicast using Lamport’s global logic clocks does not scale.

Answer 1

It really depends on how many processes are contained in a group. The
important thing to note is, that if processes are replicated for fault tolerance,
having only a few replicas may be enough. In that case, scalability is hardly an
issue. When groups of different processes are formed, scalability may become
an issue. When replicating for performance, atomic multicasting itself may be
overdone.

Totally Ordered Multicast

• We need to guarantee that concurrent updates on a replicated database are seen in the same order everywhere. This requires a totally‐ordered multicast – Update 1: add $100 to an account (initial value = $1000) – Update 2: add 1% interest to account – In absence of proper synchronization: replica 1 = $1111, replica 2 = $1110 • Lamport’s logical clocks can be used to implement totally‐ordered multicast in a completely distributed fashion.

Implementing Totally Ordered Multicast • Assumptions: – No messages are lost – Messages from the same sender are received in the order they were sent • Process Pi sends timestamped message mi to all others. The message itself is put in a local queuei . • Any incoming message at Pj is queued in queuej , according to its timestamp, and ACKed to every other process. • Pj passes a message mi to its application if – mi is at the head of queuej – mi has been ACKed by each other process • Observation: all processes will eventually have the same copy of the local queue, therefore, all messages are delivered in the same order everywhere.