Consider an asynchronous network in a shared-memory environment consisting ofn nodes. Assume that up to f of the nodes might be Byzantine (n > 12f), wherethe adversary is full-information and dynamic (sometimes called adaptive). Inaddition, the non-Byzantine nodes may undergo transient failures. Nodes advancein atomic steps, which consist of reading all registers, performing somecalculation and writing to all registers. This paper contains three main contributions. First, the clock-functionproblem is defined, which is a generalization of the clock synchronizationproblem. This generalization encapsulates previous clock synchronizationproblem definitions while extending them to the current paper's model. Second,a randomized asynchronous self-stabilizing Byzantine tolerant clocksynchronization algorithm is presented. In the construction of the clock synchronization algorithm, a building blockthat ensures different nodes advance at similar rates is developed. Thisfeature is the third contribution of the paper. It is self-stabilizing andByzantine tolerant and can be used as a building block for different algorithmsthat operate in an asynchronous self-stabilizing Byzantine model. The convergence time of the presented algorithm is exponential. Observe thatin the asynchronous setting the best known full-information dynamic Byzantineagreement also has expected exponential convergence time, even though currentlythere is no known reduction between the two.
展开▼