  The node-averaged complexity of a distributed algorithm running on a graph
$G=(V,E)$ is the average over the times at which the nodes $V$ of $G$ finish
their computation and commit to their outputs. We study the node-averaged
complexity for some distributed symmetry breaking problems and provide the
following results (among others):
  - The randomized node-averaged complexity of computing a maximal independent
set (MIS) in $n$-node graphs of maximum degree $\Delta$ is at least
$\Omega\big(\min\big\{\frac{\log\Delta}{\log\log\Delta},\sqrt{\frac{\log
n}{\log\log n}}\big\}\big)$. This bound is obtained by a novel adaptation of
the well-known KMW lower bound [JACM'16]. As a side result, we obtain the same
lower bound for the worst-case randomized round complexity for computing an MIS
in trees -- this essentially answers open problem 11.15 in the book of
Barenboim and Elkin and resolves the complexity of MIS on trees up to an
$O(\sqrt{\log\log n})$ factor. We also show that, $(2,2)$-ruling sets, which
are a minimal relaxation of MIS, have $O(1)$ randomized node-averaged
complexity.
  - For maximal matching, we show that while the randomized node-averaged
complexity is
$\Omega\big(\min\big\{\frac{\log\Delta}{\log\log\Delta},\sqrt{\frac{\log
n}{\log\log n}}\big\}\big)$, the randomized edge-averaged complexity is $O(1)$.
Further, we show that the deterministic edge-averaged complexity of maximal
matching is $O(\log^2\Delta + \log^* n)$ and the deterministic node-averaged
complexity of maximal matching is $O(\log^3\Delta + \log^* n)$.
  - Finally, we consider the problem of computing a sinkless orientation of a
graph. The deterministic worst-case complexity of the problem is known to be
$\Theta(\log n)$, even on bounded-degree graphs. We show that the problem can
be solved deterministically with node-averaged complexity $O(\log^* n)$, while
keeping the worst-case complexity in $O(\log n)$.
