About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Computer and System Sciences
Paper
Finding the median distributively
Abstract
We consider the problem of computing the median of a bag of 2n numbers by using communicating processes, each having some of the numbers in its local memory. The memories are assumed to be disjoint. For two processes an algorithm is given. Its time and space complexity is linear while the communication complexity is 2 log2 n. A lower bound of log2 n on the communication complexity is derived. Thus the algorithm is optimal up to a constant. © 1982.