Abstract
In this paper we study timestamping for the dynamic analysis of events ordering in message-passing systems. We use the partial order theory to shed new light on classical timestamping algorithms. Consequently we present a new stamp technique based on a special class of order: interval orders. This technique gives better results than the Lamport's logical clocks for the same cost. Lastly we characterize executions for which our timestamping is optimum.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Charron-Bost. Concerning the size of logical clocks in distributed systems. Information Processing Letters, 39(1):11–16, July 1991.
W.A. Cook, M. Kress, and M. Seiford. An axiomatic approach to distance on partial orderings. R.A.I.R.O. Recherche opérationnelle/Operations Research, 20(2):115–122, Mai 1986.
R.P Dilworth. A decomposition theorem for partially ordered sets. Annals of Math., 51:161–165, 1950.
J. Fidge. Timestamps in message passing systems that preserve the partial ordering. In Proc. 11th Australian Computer Science Conference, pages 55–66, 1988.
P.C Fishburn. Interval orders and interval graphs. Wiley, New York, 1985.
L. Lamport. Time, clocks and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.
F. Mattern. Virtual time and global states of distributed systems. In Cosnard, Quinton, Raynal, and Robert, editors, Proc. Int. Workshop on Parallel and Distributed Algorithms Bonas, France, Oct. 1988, North Holland, 1989.
R.H. Möhring. Computationally tractable classes of ordered sets. In Algorithms and Order, pages 105–193, Kluwer Academic Publishers, 1989.
C. H. Papadimitriou and M. Yannakakis. Scheduling interval-ordered task. Siam J. Comput., 8(3):405–409, August 1979.
J.X. Rampon. Mesures de concurrence et extensions d'intervalles. Ph. D Thesis, University of Montpellier II, February 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Diehl, C., Jard, C. (1992). Interval approximations of message causality in distributed executions. In: Finkel, A., Jantzen, M. (eds) STACS 92. STACS 1992. Lecture Notes in Computer Science, vol 577. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55210-3_197
Download citation
DOI: https://doi.org/10.1007/3-540-55210-3_197
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55210-9
Online ISBN: 978-3-540-46775-5
eBook Packages: Springer Book Archive