  We describe a protocol for the average consensus problem on any fixed
undirected graph whose convergence time scales linearly in the total number
nodes $n$. The protocol is completely distributed, with the exception of
requiring all nodes to know the same upper bound $U$ on the total number of
nodes which is correct within a constant multiplicative factor.
  We next discuss applications of this protocol to problems in multi-agent
control connected to the consensus problem. In particular, we describe
protocols for formation maintenance and leader-following with convergence times
which also scale linearly with the number of nodes.
  Finally, we develop a distributed protocol for minimizing an average of
(possibly nondifferentiable) convex functions $ (1/n) \sum_{i=1}^n
f_i(\theta)$, in the setting where only node $i$ in an undirected, connected
graph knows the function $f_i(\theta)$. Under the same assumption about all
nodes knowing $U$, and additionally assuming that the subgradients of each
$f_i(\theta)$ have absolute values upper bounded by some constant $L$ known to
the nodes, we show that after $T$ iterations our protocol has error which is
$O(L \sqrt{n/T})$.
