On an improved algorithm for decentralized extrema finding in circular configurations of processors

Abstract

This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2 N *floor(lg N ) + 3 N messages in the worst case, compared to Chang and Roberts' N ( N + 1)/2 and Hirschberg and Sinclair's 8 N + 8*ceiling( N lg N ) messages. The technique is a selective elimination of possible processes, which then merely relay future messages between the remaining contenders.