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.
No takes yet. Share an insight, caveat, or question.
Randolph Franklin (1982) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: