A randomized algorithm that always produces correct results, with the only variation from one run to another being its running time.