POSSIBLE AND IMPOSSIBLE SELF-STABILIZING DIGITAL CLOCK SYNCHRONIZATION IN GENERAL GRAPHS

We study digital clock synchronization for multiprocessor systems, whe re processors are triggered by a common clock pulse and communicate wi th others via shared memory. A self-stabilizing digital clock synchron ization protocol for systems with a general communication graph is pre sented. The protocol can commence in an arbitrary non-consistent syste m state and converges to a legitimate state in which the clocks are sy nchronized and incremented by one in every subsequent pulse. To enhanc e the fault-tolerance of our protocol, we allow that during and follow ing convergence processors may stop operating. Crash failures may part ition the communication graph into several connected components. Our p rotocol synchronizes the clocks of the processors in every such connec ted component. For the case in which faulty processors can exhibit Byz antine behavior, we prove that there is no digital clock synchronizati on protocol that tolerates even one single faulty processor.