The time it takes for an algorithm to perform its task is a central question in computer science. It has been extensively studied for (centralized) sequential algorithms, while a comprehensive treatment of time complexity in the distributed setting is still lacking. In synchronous round-based distributed algorithms, the number of rounds until the problem is solved represents a performance measure analogous to standard time complexity (Newtonian real-time), but puts under the rug the many intricacies that occur in a round due to faults, message passing, timing uncertainties due to asynchrony etc. This thesis provides a novel framework for analyzing distributed systems running multiple independent distributed algorithms simultaneously on a shared message passing communication infrastructure. In particular, the previously mentioned timing uncertainties are addressed, and the performance of the executed algorithms are analyzed with respect to Newtonian real-time. To do so, the internals of a round, that is, transmitting and receiving messages, must be taken into account. We study these mechanisms with different mathematical tools. On the transmitter side, a real-time scheduler responsible for scheduling the messages of multiple algorithms on the shared communication channels. Since suitable fault-tolerance techniques allow to deal with dropped messages in a synchronous distributed algorithm, messages can be modeled as firm deadline jobs with the end of a round as their deadline. Obviously, a good scheduling algorithm maximizes the cumulative utility gained by the successfully scheduled jobs. The quality of a scheduler is usually characterized by its competitive factor, that is, the performance of the scheduler with respect to an optimal clairvoyant scheduler, that knows the future. This thesis lays the foundation for a new approach to automatically perform the competitive analysis of scheduling algorithms with respect to given task sets. This is done by using a reduction to the problem of finding minimum mean-weight-cycles in multi-objective graphs. In addition, albeit being computationally hard, algorithmic game theory also allows to synthesize optimal scheduling algorithms. On the receiver side, a synchronizer algorithm can be used to maintain a consistent round structure by compensating messages dropped by the scheduler. The performance of a distributed algorithm running atop of such a thus synchronizer directly depends on the performance of the synchronizer. Abstracting dropped (and otherwise lost) messages by a probabilistic link failure model allows to calculate the expected round duration using Markov theory. By analyzing the series of the starting times of the rounds generated by the synchronizer, and by modeling its execution as a Markov chain, this thesis finally develops results regarding the expected round duration.