Efficient vector time with dynamic process creation and termination

Golden G. Richard

doi:10.1006/jpdc.1998.1493

1998-11-01

PRE

Golden G. Richard *

DOI：10.1006/jpdc.1998.1493

原文链接

摘要

En 中文

Many distributed algorithms require knowledge of the causal relationships between events. Examples include optimistic recovery protocols, distributed debugging systems, and causal distributed shared memory. Determining causal relationships can be difficult, however, because there is no global clock and local clocks cannot be perfectly synchronized. Vector time is a useful abstraction for capturing the causal relationships between events and, unlike Lamport's logical clocks, allows identification of concurrent events. Some drawbacks of vector time include transmission and logging overhead, since the size of a vector clock is linear in the number of processes. This paper presents a technique to reduce these overheads for applications that dynamically create and destroy processes and log event information with attached vector timestamps. The reduction in logging overhead comes at the expense of a more complicated timestamp comparison protocol and more sophisticated data structures for maintaining vector time. Distributed process recovery mechanisms and debugging systems that require on-the-fly causality information can benefit directly from the proposed technique. (C) 1998 Academic Press.

Keyword:

DISTRIBUTED SYSTEMS

CLOCKS