Async Distributed Algorithm Time Complexity
In a distributed system, messages can be sent in parallel.  Vertex #1 can send a message at the same time as vertex #2 is sending a message.  So, the total amount of time to complete the algorithm might be much less than the total number of messages sent.