Search

Caching data can reduce access latency and improve data availability, but it also raises the problem of how to maintain consistency among copies of writable data. The problem appears in different guises in different contexts: it appears as the cache coherence problem in multiprocessors, as the problem of maintaining a distributed shared memory in distributed computations, and as the replica control problem in distributed databases. This article describes the home update protocol, a member of the class of coherence protocols called delta coherence protocols that uses isotach guarantees to solve the coherence problem in a new and highly concurrent way. (Due to space constraints, and to avoid obscuring the basic concept of the protocols, we describe the protocol at a high level and do not address practical implementation issues.) Our goal is to show how isotach guarantees are useful in solving the coherence problem and in reasoning about coherence protocols. The coherence problem is difficult, because it requires coordinating events across nodes. The traditional approach to the problem is to reduce the coordination required by limiting concurrency or weakening the correctness criteria. Hardware based coherence protocols are traditionally divided into two classes: snoopy protocols, which require a shared bus, and directory protocols, intended for point-to-point networks. A shared bus serializes memory requests. This serialization readily yields an agreed total order among requests, but it limits concurrency and scalability. Directory protocols are more scalable, but existing directory protocols that enforce sequential consistency (SC) require that nodes execute requests one at a time and invalidate or lock copies while executing write requests. Delta protocols use isotach guarantees to coordinate accesses, an approach that lets delta protocols enforce SC without limiting concurrency. However, delta protocols require isotach guarantees., Sponsored in part by DOE under Contract No. w-7405-ENG-48. Published in the Jnl. of IEEE Concurrency Jul-Sep 2000 Issue, p23-28.