The approximate calculus of the lower bound of distributed values. (Calculs approchés de la borne inférieure de valeurs réparties.) (French) Zbl 0892.68042

Summary: The distributed infinimum approximation (or DIA, for short) problem is to compute or approximate a lower bound on a set of values distributed over different sites and channels of a distributed system. The values themselves change in time, but according to some rules implying monotonicity of their lower bound. We demonstrate that approximation of the global virtual time (GVT) and distributed termination detection are instances of DIA. We propose several classes of distributed solutions for the DIA problem, corresponding to different assumptions about the communication subsystem (synchronous, FIFO, causal order, unrestricted). All algorithms need to determine observation periods during which the local control algorithm observes the local basic computation (including its communications). It is demonstrated that wave algorithms can be used as a building block inside DIA algorithms for the determination of observation periods, for combining the local observation results, and for disseminating the subsequent approximations of the lower bound.


68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI EuDML


[1] 1. K. M. CHANDY et L. LAMPORT, Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst., 1985, 3, 1, p. 63-75.
[2] 2. B. CHARRON-BOST, Mesures de la Concurrence et du Parallélisme des Calculs Répartis. Thèse de doctorat, Université Paris VII, 1989.
[3] 3. B. CHARRON-BOST, F. MATTERN et G. TEL, Synchronous, asynchronous, and causally ordered communication, Distributed Computing, 1996, 9, 4, p. 173-191. MR1380838
[4] 4. E. W. DIJKSTRA, W. H. J. FEIJEN et A. J. M. VAN GASTEREN, Derivation of a termination detection algorithm for distributed computations. Inf. Process. Lett., 1983, 16, 5, p. 217-219. MR709657 · Zbl 0566.68025
[5] 5. E. W. DIJKSTRA et C. S. SCHOLTEN, Termination detection for diffusing computations. Inf. Process. Lett., 1980, 11, 1, p. 1-4. Zbl0439.68039 MR585394 · Zbl 0439.68039
[6] 6. J. HUGHES, A distributed garbage collection algorithm. Dans Functional Programming Language and Computer Architecture, 1985, p. J. P. Jouannaud, Ed., tome 201 de Lecture Notes in Computer Science, Springer-Verlag, p. 256-272.
[7] 7. D. JEFFERSON, Virtual time. ACM Trans. Program. Lang. Syst., 1985, 7, 3, p. 404-425.
[8] 8. T. H. LAI et T. H. YANG, On distributed snapshots. Inf. Process. Lett., 1987, 25, p. 153-158. Zbl0653.68008 MR896409 · Zbl 0653.68008
[9] 9. L. LAMPORT, Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 1978, 21, p. 558-564. Zbl0378.68027 · Zbl 0378.68027
[10] 10. F. MATTERN, Algorithms for distributed termination detection. Distributed Computing, 1987, 2, 3, p. 161-175.
[11] 11. F. MATTERN, H. MEHL, A. A. SCHOONE et G. TEL, Global virtual time approximation with distributed termination detection algorithms. Rapport RUU-CS-91-32, Dept d’Informatique, Université d’Utrecht, Pays Bas, Sept. 1991.
[12] 12. S. K. SARIN et N. A. LYNCH, Discarding obsolete information in a replicated database system. IEEE Trans. Softw. Eng. SE-13, 1987, p. 39-47.
[13] 13. A. SCHIPER, J. EGGLI et A. SANDOZ, A new algorithm to implement causal ordering. Dans Int. Workshop on Distributed Algorithms, 1989, p. J.-C. Bermond et M. Raynal, Eds., tome 392 de Lecture Notes in Computer Science, Springer-Verlag, p. 219-232.
[14] 14. R. Schwartz et F. MATTERN, Detecting causal relationships in distributed computations: In search of the holy grail. Distributed Computing, 1994, 7, 3, p. 149-174. Zbl0813.68096 · Zbl 0813.68096
[15] 15. G. TEL, Topics in Distributed Algorithms, tome 1 de Cambridge Int. Series on Parallel Computation. Cambridge University Press, Cambridge, 1991. Zbl0755.68062 · Zbl 0755.68062
[16] 16. G. TEL, Introduction to Distributed Algorithms. Cambridge University Press, Cambridge, 1994. Zbl0826.68056 · Zbl 0826.68056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.