  In this paper, we study distributed graph algorithms in networks in which the
nodes have a limited communication capacity. Many distributed systems are built
on top of an underlying networking infrastructure, for example by using a
virtual communication topology known as an overlay network. Although this
underlying network might allow each node to directly communicate with a large
number of other nodes, the amount of communication that a node can perform in a
fixed amount of time is typically much more limited. We introduce the
Node-Capacitated Clique model as an abstract communication model, which allows
us to study the effect of nodes having limited communication capacity on the
complexity of distributed graph computations. In this model, the $n$ nodes of a
network are connected as a clique and communicate in synchronous rounds. In
each round, every node can exchange messages of $O(\log n)$ bits with at most
$O(\log n)$ other nodes. When solving a graph problem, the input graph $G$ is
defined on the same set of $n$ nodes, where each node knows which other nodes
are its neighbors in $G$. To initiate research on the Node-Capacitated Clique
model, we present distributed algorithms for the Minimum Spanning Tree (MST),
BFS Tree, Maximal Independent Set, Maximal Matching, and Vertex Coloring
problems. We show that even with only $O(\log n)$ concurrent interactions per
node, the MST problem can still be solved in polylogarithmic time. In all other
cases, the runtime of our algorithms depends linearly on the arboricity of $G$,
which is a constant for many important graph families such as planar graphs.
