A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion



We present a local distributed algorithm for a general Majority Voting problem in large-scale dynamic systems. The algorithm combines a novel, efficient anytime spanning forest algorithm, which may also have applications elsewhere, with a ``charge fusion'' algorithm that roots trees at nodes with excess ``charge'' (derived from a node's vote), and subsequently transfers charges along tree links to oppositely charged roots for fusion. At any instant, every node has an ad hoc belief regarding the outcome. Once all changes have ceased, the correct majority decision is reached by all nodes, within a time that in many cases is independent of the graph size. The algorithm's correctness and salient properties are proved, and experiments with up to a million nodes provide further validation and actual numbers. To our knowledge, this is the first locality-sensitive solution to the Majority Vote problem for arbitrary, dynamically changing communication graphs.