The common randomness capacity of a network of discrete memoryless channels

In this paper, we generalize our previous results on generating common rand omness at two terminals to a situation where any finite number of agents, i nterconnected by an arbitrary network of independent, point-to-point, discr ete memoryless channels, wish to generate common randomness by interactive communication over the network. Our main result is an exact characterizatio n of the common randomness capacity of such a network, i.e., the maximum nu mber of bits of randomness that all the agents can agree on per step of com munication. As a by-product, we also obtain a purely combinatorial result, viz,, a characterization of (the incidence vectors of) the spanning arbores cences rooted at a specified vertex in a digraph, and having exactly one ed ge exiting the root, as precisely the extreme points of a certain unbounded convex polyhedron, described by a system of linear inequalities.