  The execution time of programs is a key element in many areas of computer
science, mainly those where achieving good performance (e.g., scheduling in
cloud computing) or a predictable one (e.g., meeting deadlines in embedded
systems) is the objective. Despite being random variables, execution times are
most often treated as deterministic in the literature, with few works taking
advantage of their randomness; even in those, the underlying distributions are
assumed as being normal or uniform for no particular reason. In this work we
investigate these distributions in various machines and algorithms. A
mathematical problem arises when dealing with samples whose populational
minimum is unknown, so a significant portion of this monograph is dedicated to
such problem. We propose several different effective or computationally cheap
ways to overcome the problem, which also apply to execution times. These
methods are tested experimentally, and results point to the superiority of our
proposed inference methods. We demonstrate the existence of execution time
distributions with long tails, and also conclude that two particular
probability distributions were the most suitable for modelling all execution
times. While we do not discuss direct applications to stochastic scheduling, we
hope to promote the usage of probabilistic execution times to yield better
results in, for example, task scheduling.
