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.
M. Chittajallu and B. M. McMillin, "History Clipping in Event-driven Distributed Systems," ISCA 13th International Conference on Parallel and Distributed Computing Systems, ISCA, Aug 2000.
Keywords and Phrases
Distributed; Events; History Maintenance; Monitoring
Article - Conference proceedings
© 2000 ISCA, All rights reserved.