Finding a Majority Among N Votes.
Michael J. Fischer, Steven L. Salzberg · Defense Technical Information Center (DTIC) · 1982
A commonly-used technique for fault-tolerant computing is to perform n redundant computations and then vote on the results, choosing on the majority value if one exists. We present an algorithm for carrying out the voting which uses (3n/2) -2 comparisons, and we prove the algorithms optimal. This solves Problem 81-5 posed in the Journal of Algorithms, June 1981. (Author)