Presentation points for Chapter 15:

Replication

Objectives

To appreciate the advantages and costs of replicating data: the potential improvement in response times and reliability, and the extra communication costs involved in keeping data consistent.

To understand group communication and view-synchronous communication. To understand the passive and active architectures for fault-tolerant services. To understand the meaning of a highly available service and the gossip, Bayou and Coda architectures for realising such a service.

To understand the architectures for transactions on replicated data, and the techniques for dealing with network partitions in such systems.

Points to emphasize

We replicate data to achieve performance enhancement, fault tolerance and high availability. Replication should be transparent to clients of a replicated service, but it is not normally transparent to front ends and replica managers.

A fault-tolerant service is one that always behaves correctly despite up to a given number and type of failures, whereas a highly available service is one that continues to provide a possibly degraded service despite a certain number and type of process failures and despite disconnected operation.

Linearizability and sequential consistency capture notions of correctness for replicated objects. (Chapter 17 gives some weaker notion sof consitency for distributed shared memory systems.)

Whatever the type of replication, we can identify the five stages of request, coordination, execution, agreement and response.

The services considered in Sections 15.2-15.4 deal at the level of individual operations upon replicated shared data - they are not transactional.

Group communication adds group (membership) management to multicast communication, studied in Chapter 12. View-synchronous communication enables us to reason about the sets of messages that have been delivered when a failure occurs.

The relative advantages of active and passive replication should be brought out.

The gossip architecture is not widely used but was chosen for its elegant implementation of ordering constraints and to show that, in general, replication is about more than multicast. Bayou uses operational transformation to deal with conflicts in an application-specific manner. Coda, like gossip, adopts a generic approach to consistency and keeps track of updates through vector timestamps. The timestamps may report a conflict when none exists at the application level.

Replication schemes must deal with network partitions. Pessimistic schemes permit operations to continue in only one partition. Quorum consensus schemes allow partitions to decide independently which one can continue. The virtual partition algorithm combines the performance of available copies replication with the ability to handle network partitions.

Possible difficulties

The concepts of linearizability and sequential consistency are hard.

The concept of view-synchronous communication is a difficult one for somebody who has not tried to program an application that relies upon it.

The application of one-copy serializability in the available copies algorithm is hard.

Teaching hints

Relate the material on vector timestamps in Chapter 11 to Coda Version Vectors. Remind the students what they learned about multicast communication guarantees in Chapter 12.

The architecture for transactions with replicated data can be compared with the architectures of Sections 15.2 and 15.3.