Logical Time Coherence Maintenance 491 views

We apply techniques based on isotach logical time to the problem of maintaining a coherent shared memory. In isotach logical time systems, processes can predict and control the logical times at which their messages are received. This control over the logical receive time of messages provides a powerful basis for implementing coherence protocols. Existing isotach-based memory coherence protocols are more concurrent than other protocols, but are limited in the topologies on which they work and the reference patterns for which they are suited. We define a new framework for isotach shared memory systems that supports protocols that work for arbitrary topologies and are suited to a wide range of reference patterns. By extending isotach protocols to a wider class of applications and networks, we contribute to the solution of the memory coherence problem. In addition to extending isotach-based coherence protocols, we advance the theory of isotach systems. We redefine isotach systems to be consistent with potential causality, a new relation among events that captures causality in a less conservative way than Lamport's happens before relation. This redefinition expands the class of correct implementations of isotach systems. We introduce the flex algorithm, a new implementation of isotach logical time that allows different links to be assigned different logical distances. We expect that increased flexibility in assigning logical distances will improve the performance of isotach systems in cases in which links have significantly different real time latencies.

PHD (Doctor of Philosophy)

All rights reserved (no additional license for public reuse)

1998-05-29