## Abstract

We consider the problem of finding the largest of a set of n uniquely numbered processors, arranged in a ring, by means of an asynchronous distributed algorithm without a central controller. Processors are identical, except for their unique number (identity). Using a technique of Frederickson and Lynch we show that arbitrary algorithms that solve this problem on rings where processors know the ring size cannot have a better worst-case number of messages than algorithms that use only comparisons between identities. We show a similar type of result for rings, where the ring size is not known. We use these results to answer a question, posed by Korach, Rotem, and Santoro in 1981 whether each extrema-finding algorithm that uses time n on a ring of n processors must use a quadratic number of messages; and to show a lower bound of 0.683 n log(n) on the worst-case number of messages for unidirectional rings with known ring size n. Also, we give a lower bound of 1 2n log(n) on the average number of messages for algorithms that use only comparisons on rings with known ring size n.

Original language | English |
---|---|

Pages (from-to) | 97-118 |

Number of pages | 22 |

Journal | Journal of Computer and System Sciences |

Volume | 42 |

Issue number | 1 |

Publication status | Published - 1 Feb 1991 |