*SIROCCO 2017:
Structural Information and Communication Complexity - 24th
International Colloquium, Porquerolles, France,
June 19-22, 2017, 263--282*

doi:
10.1007/978-3-319-72050-0_16

*SIROCCO 2017:
Structural Information and Communication Complexity - 24th
International Colloquium, Porquerolles, France,
June 19-22, 2017, 263--282*

doi:
10.1007/978-3-319-72050-0_16

In the context of distributed synchronous computing,
processors perform in rounds, and the time-complexity of a
distributed algorithm is classically defined as the number of
rounds before all computing nodes have output. Hence, this
complexity measure captures the running time of the slowest
node(s). In this paper, we are interested in the running time of
the ordinary nodes, to be compared with the running time of the
slowest nodes. The *node-averaged* time-complexity of a
distributed algorithm on a given instance is defined as the
average, taken over every node of the instance, of the number of
rounds before that node output. We compare the node-averaged
time-complexity with the classical one in the standard LOCAL
model for distributed network computing. We show that there can
be an exponential gap between the node-averaged time-complexity
and the classical time-complexity, as witnessed by, e.g., leader
election. Our first main result is a positive one, stating that,
in fact, the two time-complexities behave the same for a large
class of problems on very sparse graphs. In particular, we show
that, for LCL problems on cycles, the node-averaged time
complexity is of the same order of magnitude as the ``slowest
node'' time-complexity.

In addition, in the LOCAL model, the time-complexity is
computed as a worst case over all possible identity assignments
to the nodes of the network. In this paper, we also investigate
the *ID-averaged* time-complexity, when the number of
rounds is averaged over all possible identity assignments. Our
second main result is that the ID-averaged time-complexity is
essentially the same as the expected time-complexity of
*randomized* algorithms (where the expectation is taken
over all possible random bits used by the nodes, and the number
of rounds is measured for the worst-case identity assignment).

Finally, we study the node-averaged ID-averaged time-complexity. We show that 3-colouring the $n$-node ring requires $\Theta(\log^*n)$ rounds if the number of rounds is averaged over the nodes, or if the number of rounds is averaged over the identity assignments. In contrast, we show that 3-colouring the ring requires only $O(1)$ rounds if the number of rounds is averaged over the nodes, and over the identity assignments.