  We study the distributed message-passing model in which a communication
network is represented by a graph G=(V,E). Usually, the measure of complexity
that is considered in this model is the worst-case complexity, which is the
largest number of rounds performed by a vertex v\in V. While often this is a
reasonable measure, in some occasions it does not express sufficiently well the
actual performance of the algorithm. For example, an execution in which one
processor performs r rounds, and all the rest perform significantly less rounds
than r, has the same running time as an execution in which all processors
perform the same number of rounds r. On the other hand, the latter execution is
less efficient in several respects, such as energy efficiency, task execution
efficiency, local-neighborhood efficiency and simulation efficiency.
Consequently, a more appropriate measure is required in these cases. Recently,
the vertex-averaged complexity was proposed by \cite{Feuilloley2017}. In this
measure, the running time is the worst-case sum of rounds of communication
performed by all of the graph's vertices, averaged over the number of vertices.
Feuilloley \cite{Feuilloley2017} showed that leader-election admits an
algorithm with a vertex-averaged complexity significantly better than its
worst-case complexity. On the other hand, for O(1)-coloring of rings, the
worst-case and vertex-averaged complexities are the same. This complexity is
O\left(\log^{*}n\right) [12]. It remained open whether the vertex-averaged
complexity of symmetry-breaking in general graphs can be better than the
worst-case complexity. We answer this question in the affirmative, by showing a
number of results with improved vertex-averaged complexity.
