*Theoretical Computer Science*

volume 811, pages 42-55 (2020)

doi:10.1016/j.tcs.2019.01.023

*Invited paper for SIROCCO 2017.*

*Theoretical Computer Science*

volume 811, pages 42-55 (2020)

doi:10.1016/j.tcs.2019.01.023

*Invited paper for SIROCCO 2017.*

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.

A preliminary version of this work appeared as a brief announcement at PODC 2015. See this page.

A second version of this paper appeared as a conference paper at SIROCCO 2017. See here. The main differences, in content, between the BA and the conference version are a generalization of the lower bound for the average on the nodes, and the addition of a part about average on the IDs. There is a error in this version in the randomized part. We describe this error in a later paragraph of these notes.

The current version is the one published in *Theoretical Computer
Science* special issue for the conference. In addition to
correcting the error of the conference version, it contains the
few proofs that were omitted in the conference version, and more
reader-friendly versions of the main proofs.

The error in the conference version is in Theorem 3. This
theorem does not hold in general. In the proof, the step where
the randomized algorithm simulates the deterministic one requires
some nodes (the ones that see twice the same ID) to wait until
they see the whole graph and then to choose a proper output to
complete the current output. This is not possible in general,
and requires an additional hypothesis: the language must be
*completable*. See the journal version for more details.

I gave the talks at PODC 2015 in San Sebastian and SIROCCO 2017
in Porquerolles. An interesting question at SIROCCO
was: "What if, instead of the average, one studies the
median?". I cannot answer in general, but for the leader election
algorithm, the complexity of the median node is constant, even for the worst
ID assignment. Indeed for each couple of adjacent nodes,
one has an ID smaller than the other, and stops after the first
round, therefore at least half of the nodes stop after the first round.
Also it was noted that there exists a logarithmic lower bound for
leader election in a related context
here.

A recent paper by Barenboim and Tzur, Distributed Symmetry-Breaking with Improved Vertex-Averaged Complexity (ICDCN 2019), shows (among other results) that there is an exponential gap between worst-node and average-node complexity in general graphs for a colouring problem.

In a PODC 2020 paper, Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity Chatterjee, Gmyr, and Pandurangan considered a similar model, and proved that it is possible to design an MIS algorithm where every node in average is active only a constant number of rounds.

In a PODC 2022 paper, Node and Edge Averaged Complexities of Local Graph Problems Balliu, Ghaffari, Kuhn and Olivetti prove among other things that the KMW lower bound holds for the average measure, which implies results on the worst-case complexity too.