Ability to Count Is Worth $\Theta(\Delta)$ Rounds

Hella et al. (PODC 2012, Distributed Computing 2015) identified seven\ndifferent models of distributed computing - one of which is the port-numbering\nmodel - and provided a complete classification of their computational power\nrelative to each other. However, one of their simulation results involves an\nadditive overhead of $2\\Delta-2$ communication rounds, and it was not clear, if\nthis is actually optimal. In this paper we give a positive answer: there is a\nmatching linear-in-$\\Delta$ lower bound. This closes the final gap in our\nunderstanding of the models, with respect to the number of communication\nrounds.\n