Node and Edge Averaged Complexities of Local Graph Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kühn, Dennis Olivetti · 2022
We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. 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 of the central distributed symmetry breaking problems.