Calculs approchés de la borne inférieure de valeurs réparties

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.