Data coherence protocols: the home update protocol

Authors:Williams, C, Department of Computer ScienceUniversity of Virginia Reynolds, PF, Department of Computer ScienceUniversity of Virginia de, Supinski, Department of Computer ScienceUniversity of Virginia

We describe a class of directory coherence protocols called delta coherence protocols that use network guarantees to support a new and highly concurrent approach to maintain a consistent shared memory. Delta coherence protocols are more concurrent than other coherence protocols in that they allow processes to pipeline memory accesses without violating sequential consistency; support multiple concurrent readers and writers to the same cache block; and allow processes to access multiple shared variables atomically without invalidating copies held by other processes or otherwise obtaining exclusive access to the referenced variables. Delta protocols include both update and invalidate protocols. In this paper we describe the simplest, most basic delta protocol, an update protocol called the home update protocol. Delta protocols are based on isotach network guarantees. An isotach network maintains a logical time system that allows each process to predict and control the logical time at which its messages are received. We prove the home update protocol is correct using logical time to reason about the order in which requests are executed.

All rights reserved (no additional license for public reuse)
Source Citation:

Williams, C, PF Reynolds, and Supinski de. "Data coherence protocols: the home update protocol." University of Virginia Dept. of Computer Science Tech Report (2000).

University of Virginia, Department of Computer Science
Published Date: