Synchronizing clocks in a system resilient to a wide class of failures

Abstract

A more realistic range of models of distributed computing was recently introduced in which processors may fail either by crashing or by exhibiting arbitrary behavior. In these models, the total number of faulty processors is bounded from above by a constant subject to the proviso that no more than b ≤ t of these processors fail arbitrarily. We examine a fundamental problem of distributed computing in these new models: synchronizing clocks. We establish the necessary relationship among the total number of processors, t and b, for the problem to be solvable, and present two clock-synchronization protocols, one of which matches the above bound.