Distributed monitoring of election winners (Q2289007)

This paper presents communication-efficient protocols for maintaining approximate winners in distributed vote streams. The communication complexity of general techniques for designing such protocols (namely, sampling-based protocols, protocols based on checkpoints, and protocols based on counting frequencies) have their communication complexity analyzed. Conditions are established under which, using communication which is logarithmic in the number of voters, upon a query at any time the center can immediately return a candidate which is guaranteed to be an approximate winner with high probability. For various single winner voting rules, including variants of approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules, an analysis of how to choose which protocol to use at which scenario, depending on the specific parameters of the problem at hand, is developed. The effect that the number of voters, the number of candidates, the number of sites and the required approximation have on the communication complexity of the protocols is studied. Lower bounds are obtained. An almost tight lower bound for plurality-winner-tracking is derived. It improves the state-of-the-art lower bound for count-tracking. An almost tight lower bound for deterministic protocols for approval-winner-tracking is also derived.