In theory of distributed systems, I understand message complexity and time complexity are common performance measures, with the first being the number of messages sent in the overall execution of the algorithm, and the time being the number of "steps" it takes to complete the algorithm.
My question is, with asynchronous distributed algorithms, where we assume that at least one message is received and processed per step, how can the time complexity differ from the message complexity? If I have to send m messages to complete the algorithm, it seems to me the worst case time complexity would be $m$, sending one message per time step. For example, the time complexity of an async flood algorithm is $O(n)$ while the message complexity is $O(m)$. Why is the time complexity not $O(m)$ too? Here $m$ is the number of edges and $n$ is the number of vertices. Same goes for constructing a rooted spanning tree.
Again, this is for async systems where messages don't have to be received in parallel.
