The use of distributed databases and Internet communication has many of the features of parallel processing, so can be expected to yield faster algorithms for problems than those yielded by serial computation. The authors have analyzed algorithms for finding maxima, and for sorting where the n pieces of data are distributed in n different locations and communicate through broadcast channels. They analyze algorithms described by previous authors, and give only sketchy descriptions for them, concentrating on the mathematical analysis of the number of rounds of communication needed for completing the tasks. They yield &THgr;(n) complexity for the algorithms. The calculations of the constants involved are matters of considerable mathematical complexity, and that is where the authors devote most of their efforts. Some of the calculations yield slowly convergent series for the constants. They exhibit a general method for accelerating these.

The methods developed here may have applications outside the field of application discussed, and therefore have mathematical significance. Since this paper is in the application area, it will be of more interest to specialists than to the general reader. Those interested in the details of the algorithms should consult the references provided in the paper.