Efficient vector time with dynamic process creation and termination

doi:10.1006/jpdc.1998.1493

Efficient vector time with dynamic process creation and termination

1998-11-01

6

PRE

AI

G

Golden G. Richard *

DOI：10.1006/jpdc.1998.1493

Original

Original request for help

Save

Abstract

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.

Keywords:

DISTRIBUTED SYSTEMS

CLOCKS

Efficient vector time with dynamic process creation and termination

Abstract

Journal

Organization