Models and Software Model Checking of a Distributed File Replication System - Formal Methods and Hybrid Real-Time Systems - page 3

DFS-R. The problem that DFS-R solves is to maintain mirror copies of selected
directories across large networks of servers. The directories that are selected for
replication are called replicated folders . Files and directories within these di-
rectories may be created, modified, deleted, moved, or renamed at any of the
mirror sites. It is the job of DFS-R to distribute changes, detect and reconcile
conflicts automatically when they arise. Distributed replication systems can be
categorized according to what problems they solve and how they solve them.
Figure 1 summarizes some of the main design choices one has when designing a
replication system.

Pessimistic

Single master

Operations transfer

State transfer

Multi master

Optimistic

Fig. 1. Replication system ontologies

Multi Master Replication. DFS-R is a multi-master replication system. Any
machine may participate in changing resources, and their updates will have to be
reconciled with updates from any other machine. A (selective) single-master sys-
tem only replicates changes from a set of selected machines. All other machines
are expected to maintain a mirror copy of the masters. This would mean that
file system changes on non-masters would have to be reverted. If there is a des-
ignated master, one can even choose to maintain truth centrally. The challenge
there is managing fail-over and network disconnects.

Optimistic Replication. To support wide area networks (spanning the globe)
DFS-R supports optimistic updates to files. This means that any machine may
submit updates to resources without checking first whether the update is in
conflict with other updates. Pessimistic replication schemes avoid concurrent
update conflicts by serializing read and write operations using locking schemes.

State and Operation Transfer. A file system state is the result of the file
operations (create, update, delete, move) that are performed on it. This suggests
two approaches to realize file replication: intercept and replay the file operations,
called operation transfer, or capture the file system state and replicate it as it
is, called state transfer. DFS-R implements a state transfer protocol. There are
several hard challenges with operations-transfer based systems. One is merging
operations into a consistent serialization. Another, is space, as operations are
not necessarily amenable to garbage collection.

Perspective. There is no single choice of design parameters that handles all
customer scenarios. In some configurations, corporations wish to designate ma-
chines as read-only, and can manage the additional constraints this leaves on