History Clipping in Event-driven Distributed Systems


The problem of managing event histories is at the core of distributed computing algorithms used for distributed run-time monitoring and distributed data replication using logs. As a distributed program executes, individual histories of process execution are diffused through the systems by a technique known as gossiping. In this way, each process has a view of the actions of other processes in the system and can monitor their behavior for correctness or security. Unfortunately, the size of the histories grows without bound. Bernstein originally proposed clipping the history of gossip messages when the history becomes known to every process in the system. However, when used in distributed monitoring, even though every process may know about an event history, it is not a sufficient condition to clip that part of event history, as it might still be useful to monitor future event occurrences. What is needed is a way to clip the histories only when they have both been disseminated through the system and the monitoring process no longer needs them. In this paper, we propose the concept of clipping histories in event-driven systems for the purposes of monitoring. The core of this work is the observation that event-driven systems transition through many semi-stable states, then periodically return to stable, recurrent states as each action is completed. We propose an algorithm to clip histories only when the system has returned to a stable, recurrent state and the monitor no longer has use for the collected histories. The effectiveness of the algorithm is demonstrated by the reduction of history size in monitoring an event-driven maneuver drawn from an automated highway system.


Computer Science

Keywords and Phrases

Distributed; Events; History Maintenance; Monitoring

Document Type

Article - Conference proceedings

Document Version


File Type





© 2000 International Society for Computers and Their Applications (ISCA), All rights reserved.

Publication Date

01 Aug 2000

This document is currently not available here.