Abstract
We define a measure of parallelism of a distributed computation which evaluates the interactions between the processes in this computation. This measure assesses the structure of the exchanges of messages, rather than the quantity of exchanged information. This measure is easy to compute and provides a criterion to compare and to analyse distributed computations. We check the relevance of this definition by computing this measure for particular cases and by studying its behaviour with respect to operators which are defined on the distributed computations.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Bougé L., Thèse de doctorat d'état, Univ. Paris 7, (March 87).
Beauquier J., Berard B., Thiomonier L., On a concurrency measure, Rept. 288, L.R.I., Univ. Paris-Sud, Orsay (June 1986).
Charron-Bost B., Mesure du parallélisme d'un calcul réparti, Rept. 88-8, L.I.E.N.S., Ecole Norm. Sup., Paris (July 1988).
Chandy M., Misra J., How processes learn, Distributed computing 1, Springer-Verlag (1986), 40–52.
Elrald T., Francez N., Decomposition of distributed programs into communication-closed layers, Science Comp. Prog 2 (1982), 155–173.
Lamport L., Time, clocks and the orderings of events in a distributed system, Comm. ACM 21,7 (1978) 558–564.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Charron-Bost, B. (1989). Measure of parallelism of distributed computations. In: Monien, B., Cori, R. (eds) STACS 89. STACS 1989. Lecture Notes in Computer Science, vol 349. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029005
Download citation
DOI: https://doi.org/10.1007/BFb0029005
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-50840-3
Online ISBN: 978-3-540-46098-5
eBook Packages: Springer Book Archive