Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems
Baruch Awerbuch · 1987
This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. Those problems include Minimum-Weight Spanning Tree (MST), Leader Election, counting the number of network nodes, and computing a sensitive decomposable function (e.g. majority, parity, maximum, OR, AND).