  Consider a distributed system N in which each agent has an input value and
each communication link has a weight. Given a global function, that is, a
function f whose value depends on the whole network, the goal is for every
agent to eventually compute the value f(N). We call this problem global
function computation. Various solutions for instances of this problem, such as
Boolean function computation, leader election, (minimum) spanning tree
construction, and network determination, have been proposed, each under
particular assumptions about what processors know about the system and how this
knowledge can be acquired. We give a necessary and sufficient condition for the
problem to be solvable that generalizes a number of well-known results. We then
provide a knowledge-based (kb) program (like those of Fagin, Halpern, Moses,
and Vardi) that solves global function computation whenever possible. Finally,
we improve the message overhead inherent in our initial kb program by giving a
counterfactual belief-based program that also solves the global function
computation whenever possible, but where agents send messages only when they
believe it is necessary to do so. The latter program is shown to be implemented
by a number of well-known algorithms for solving leader election.
