An <i>O</i> ( <i>n</i> log <i>n</i> ) Unidirectional Algorithm for the Circular Extrema Problem

Abstract

Hirschberg and Sinclair recently published a solution to the circular extrema-finding (or election) problem which requires O (n log n) message passes in two directions around the ring. They conjecture that 12(n 2) message passes are required in the unidirectional case. This conjecture is shown to be false. The algorithms presented here are unidirectional, simpler than the Hirschberg and Sinclair solution, use fewer (in fact, optimal) distinct messages, have many fewer total message passes, and require less time.