Ability to count messages is worth Θ(Δ) rounds in distributed computing

Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different message-passing models of distributed computing – one of which is the port-numbering model – and provided a complete classification of their computational power relative to each other. However, their method for simulating the ability to count incoming messages causes an additive overhead of 2Δ–2 communication rounds, and it was not clear if this is actually optimal. In this paper we give a positive answer, by using bisimulation as our main tool: there is a matching linear-in-Δ lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds. By a previously identified connection to modal logic, our result has implications to the relationship between multimodal logic and graded multimodal logic.