An improved upperbound for distributed election in bidirectional rings of processors

We present a distributed algorithm for electing a leader (i. e., breaking symmetry) in bidirectional rings ofN processors with no global sense of orientation, that uses at most 1.44 ...N logN+O(N) messages in the worst case.Jan van Leeuwen received his M. Sc. degree in 1969 (cum laude) and the Ph.D. degree in 1972 from the University of Utrecht, Utrecht, The Netherlands. He held a postdoctorate fellowship in computer science at the University of California at Berkeley (1972–1973), visiting assistant professorship in computer science at the State University of New York at Buffalo (1973–1974, 1975–1976), and a visiting associate professorship in computer science at The Pennsylvania State University, University Park (1976–1977). In 1977 he was appointed Associate Professor of Computer Science at the University of Utrecht and became head of the new Department of Computer Science at this university. He is presently Full Professor of Computer Science. Dr. van Leeuwen is active in many disciplines within computer science. His primary research interests are fundamental studies in varied areas of computer science, viz. the analysis and complexity of computer algorithms, in both a theoretical and an applied sense (e. g. data structures, machine models, VLSI, parallel and distributed computing, and cryptography).Richard B. Tan is an Associate Professor of Mathematics and Computer Science at the University of Sciences and Arts of Oklahoma. He spends his summers at the University of Utrecht, the Netherlands. His research interests are in distributed computation and graph algorithms. He received the B. Sc. in Physics from Beloit College, WI., the M.S. in Computer Science and the Ph.D. (in 1980) in Mathematics from the University of Oklahoma.This work was done while the second author was visiting the University of Utrecht, supported by a grant of the Netherlands Organization for the Advancement of Pure Research (ZWO)