×

Lower bounds for distributed maximum-fiding algorithms. (English) Zbl 0628.68046

This paper establishes several lower bounds of the form \(\Omega\) (n log n) for the number of messages needed to find the maximum label in a circular configuration of n labeled processes with no central controller.

MSC:

68Q25 Analysis of algorithms and problem complexity
68N25 Theory of operating systems
PDFBibTeX XMLCite
Full Text: DOI