Detection of Mutual Inconsistency in Distributed Systems

TLDR

Distributed systems increasingly rely on redundant copies of data to maintain reliability, yet network partitions can cause inconsistencies that are hard to detect and manage. The authors propose a new method that uses version vectors and origin points to detect mutual inconsistency among multiple copies of a single file. This approach monitors and compares version vectors and origin points across replicas to identify inconsistencies efficiently. The technique was successfully implemented in UCLA’s LOCUS local network operating system, demonstrating effective detection of inconsistent copies.

Abstract

Many distributed systems are now being developed to provide users with convenient access to data via some kind of communications network. In many cases it is desirable to keep the system functioning even when it is partitioned by network failures. A serious problem in this context is how one can support redundant copies of resources such as files (for the sake of reliability) while simultaneously monitoring their mutual consistency (the equality of multiple copies). This is difficult since network faiures can lead to inconsistency, and disrupt attempts at maintaining consistency. In fact, even the detection of inconsistent copies is a nontrivial problem. Naive methods either 1) compare the multiple copies entirely or 2) perform simple tests which will diagnose some consistent copies as inconsistent. Here a new approach, involving version vectors and origin points, is presented and shown to detect single file, multiple copy mutual inconsistency effectively. The approach has been used in the design of LOCUS, a local network operating system at UCLA.