Abstract
A fundamental problem in distributed computing consists in tracking causal dependencies between relevant events occurring during the computation, named observable events. Several methods have been proposed so far in order to track these dependencies on line. They require to propagate information among processes participating in the computation, by piggybacking additional control data to the computation messages. All these methods have to face the problem of the size of piggybacked information that could become prohibitive. However, bounding the size of piggybacked information may lead to the irremediable loss of causal dependencies, if the set of observable events is not correctly chosen. The challenge is to determine the minimal size of piggybacked information, in function of a given set of observable events, allowing to track all causal dependencies. This paper provides an answer to this previously open problem. This answer is based on the construction of a weighted graph modelizing the given computation with its observable events. Although the minimal value can be known only when all the computation is known, it can be used off line to perform a posteriori analysis of a computation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Baldoni, M. Mechelli and G. Melideo. A General Scheme for Dependency Tracking in Distributed Computations, Technical Report no. 17-99, Dipartimento di Informatica e Sistemistica, Roma, 1999.
P. Baldy, H. Dicky, R. Medina, M. Morvan and J.-M. Vilarem. Efficient Reconstruction of the Causal Relationship in Distributed Systems. Proc. 1st Canada-France Conference on Parallel and Distributed Computing, LNCS 805, pp. 101–113, 1994.
B. Charron-Bost. Concerning the size of logical clocks in distributed systems, Information Processing Letters, 39, 11–16, 1991.
G. Fidge. Timestamps in message passing system that preserve the partial ordering, Proc. 11th Australian Computer Science Conf., 55–66, 1988.
J. Fowler and W. Zwanepoel. Causal Distributed Breakpoints, Proc. 10th IEEE Int. Conf. on Distributed Computing Systems, pp.134–141, 1990.
E. Fromentin, C. Jard, G.-V. Jourdan and M. Raynal. On-the-fly Analysis of Distributed Computations, Information Processing Letters, 54:267–274, 1995.
J.M. Hélary and G. Melideo. Minimal Size of Piggybacked Information for Tracking Causality: a Graph-Based Characterization, Research Report # 1300, IRISA, Université de Rennes 1, February 2000. http://www.irisa.fr/EXTERNE/bibli/pi/1300/1300.html.
C. Jard and G.V. Jourdan. Incremental Transitive Dependency Tracking in distributed computations. Parallel Processing Letters 63, 427–435, 1996.
L. Lamport. Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, 217, 558–564, 1978.
F. Mattern. Virtual time and global states of distributed systems, M. Cosnard and P. Quinton eds., Parallel and Distributed Algorithms 215–226, 1988.
P. Panangaden, K. Taylor. Concurrent Common Knowledge: Defining Agreement for Asynchronous Systems, Distributed Computing 6(2), 73–93, 1992.
R. Schwarz and F. Mattern. Detecting causal relations in distributed computations: in search of the holy grail, Distributed Computing 7(3), 149–174, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hélary, J.M., Melideo, G. (2000). Minimal Size of Piggybacked Information for Tracking Causality: A Graph-Based Characterization. In: Brandes, U., Wagner, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2000. Lecture Notes in Computer Science, vol 1928. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40064-8_21
Download citation
DOI: https://doi.org/10.1007/3-540-40064-8_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41183-3
Online ISBN: 978-3-540-40064-6
eBook Packages: Springer Book Archive