Lamport’s (Physical) Clock Synchronization Algorithm

550 views Asked by At

As it's such a famous computer science paper, I decided to read Lamport's Time, Clocks, and the Ordering of Events in a Distributed System. Besides his often-cited remarks on logical clocks, he also proposes an algorithm for synchronizing physical clocks (starting on page 562). I think I get the idea of that algorithm, however, on page 563, he lists two implementation rules that every process has to follow. I just can't seem to figure out what IR1 is supposed to mean:

IR 1'. For each i, if Pi does not receive a message at physical time t, then Ci is differentiable at t and dCi(t)/dt > 0.

What does he mean with "Ci is differentiable"? Differentiable from what? And why does dCi(t)/dt have to be greater than 0? Don't we try to get it as close to 0 as possible after all?

Maybe this is a really dumb question that comes with a really obvious answer, but as of now I can't figure it out. So, help is much appreciated...

1

There are 1 answers

0
jperl On BEST ANSWER

What this is saying, is that Ci(t) is a mathematically differentiable function of t; that is, the derivative of Ci(t) exists at t. (AKA the value of Ci(t) is changing by some measurable amount at t)

dCi(t)/dt > 0 just means that the derivative of Ci(t) is greater than zero. (AKA The rate at which Ci(t) changes is positive at t)

This is just a definition of Ci(t) as a function whose value increases whenever Pi does not receive a message.