Time

[libreamartists]

Timing, Clocks, and the Order of Events in a Distributed System by Lamport

• timestamps
• vlocks

[libreamartists]

Threshold Logical Clocks for Asynchronous Distributed Coordination and Consensus by Bryan Ford, EPFL (book coming soon)

1. Tolerating Byzantine node failures and asynchronous network conditions makes consensus protocols complex and fragile, while relying on synchrony assumptions and timeouts can make consensus protocols vulnerable to performance and routing-based attacks.
2. This work presents a new approach to asynchronous consensus that decomposes the handling of time from the consensus process itself. The protocol is simple, provides clean layering, and requires no common coins or trusted dealers.
3. Inspired in part by Lamport clocks, vector clocks, and matrix clocks, a new Threshold Logical Clock (TLC) protocol is introduced that synthesizes a virtual notion of time on an asynchronous network and operates in the presence of failed or Byzantine nodes, allowing other protocols such as threshold signing, randomness beacons, and consensus to be built more simply atop it, as if on a synchronous network.
4. To explore TLC’s capabilities, a “propose, gossip, decide” approach is developed such that participants each (i) propose a potential value to agree on then simply wait a number of TLC time steps, (ii) record and gossip their observations at each step, and finally (ii) decide independently on the basis of public randomness and the history they observed whether the consensus round succeeded and, if so, which value was agreed on.
5. To handle network asynchrony, including adversarial scheduling, it is sufficient to associate random tickets with each proposed value or block for symmetry-breaking, while ensuring that the network adversary cannot learn the random ticket values until the communication pattern defining the consensus round has been completed and indelibly fixed.
6. To tolerate f-Byzantine nodes colluding with the network adversary, this work relies on gossip and digital signatures, treating all participants as accountable state machines to handle equivocation and other detectable misbehavior by faulty nodes.
7. Furthermore, threshold public randomness via secret sharing is used to ensure that the adversary can neither learn nor bias proposal ticket values until the round has completed.