  We study common randomness generation problems where $n$ players aim to
generate same sequences of random coin flips where some subsets of the players
share an independent common coin which can be tossed multiple times, and there
is a publicly seen blackboard through which the players communicate with each
other. We provide a tight representation of the optimal communication rates via
linear programming, and more importantly, propose explicit algorithms for the
optimal distributed simulation for a wide class of hypergraphs. In particular,
the optimal communication rate in complete hypergraphs is still achievable in
sparser hypergraphs containing a path-connected cycle-free cluster of
topologically connected components. Some key steps in analyzing the upper
bounds rely on two different definitions of connectivity in hypergraphs, which
may be of independent interest.
