A method and system are disclosed for implementing a distributed lock manager comprising a plurality of nodes that coordinate with one another to maintain a shared state by agreeing to transitions using a distributed consensus protocol and applying those agreed to transitions. A given node of the system periodically propagates a local time from a local clock of the given node to the other nodes. When agreeing to a transition, the system associates the transition with the propagated local clock time. The given node later calculates a maximum staleness of the transition based at least on the current time of the node's local clock and the propagated local time associated with the transition.