Clustering strategies for cluster timestamps
Paul A. S. Ward, Ting C. Huang, DAVID J. TAYLOR · 2004
Distributed-system observation tools require an efficient data structure to store and query the partial-order of execution. Such data structures typically use vector timestamps to efficiently answer precedence queries. Many current vector-timestamp algorithms either have a poor time/space complexity tradeoff or are static. This limits the scalability of such observation tools. The self-organizing hierarchical cluster timestamp, introduced by Ward and Taylor, potentially has a good time/space tradeoff provided that the clusters accurately capture communication locality. However, the problem of accurately capturing communication locality has not been adequately addressed. In particular, the only clustering algorithm for which results have been presented is the merge-onfirst-communication approach. That strategy has limited applicability, as it is very sensitive to the order of event processing and to the maximum cluster size permitted. In this paper we evaluate alternate clustering strategies. We first studied a simple static clustering algorithm. This was chosen to confirm the basic premise of cluster timestamps, namely that good clustering will yield significant space saving. We then assessed the merge-on-Nth-communication approach, as a dynamic alternative to mergeon-first-communication. We present detailed results for the strategies evaluated, and offer recommendations for future work in clusteralgorithm selection for cluster timestamps. I.