Marching to Many Distant Drummers
Leslie Lamport, Timothy Mann · 1997
We address the problem of determining the time in a network where a node may obtain information indirectly from primary time sources via intermediate nodes. Our key idea is to transmit and store each time datum as a pair, consisting of a time interval and a "failure predicate", a boolean expression that indicates precisely which combinations of node failures could invalidate the interval. We describe some techniques based on this idea, but not a complete system design or implementation. Contents 1 Introduction 1 2 A Calculus of Time Data 1 2.1 Node predicates . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.2 Time data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.1 Extracting failure knowledge from time data . . . . . 5 2.2.2 Extracting one time datum from many . . . . . . . . . 5 2.3 Fault-tolerance versus reliability: a digression . . . . . . . . . 7 3 Manipulating Time Data 8 3.1 Maintaining time data at a node . . . . . . . . . . . . . . . . 8 3.2 Transm...