Abstract: 
Consider a fullyconnected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous Ccounting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C>1. In the selfstabilising firing squad problem, the task is to eventually guarantee that all nonfaulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the nottoodistant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for selfstabilising Byzantine firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions.
