baijia - papers and notes

Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (Jul. 1978), 558-565.

ACM entry: http://doi.acm.org/10.1145/359545.359563

@article{lamport78time,
author = {Lamport, Leslie},
title = {Time, clocks, and the ordering of events in a distributed system},
journal = {Commun. ACM},
volume = {21},
number = {7},
year = {1978},
issn = {0001-0782},
pages = {558--565},
}

Whether we can use the algorithm in this paper to generate incremental version
numbers (each time a new request get a number that is larger than any number
generated before) in a distributed way (several nodes cooperate to generate the
version numbers) ? The existence of the concurrency makes it hard even though
the events can be totally ordered. This is also hard to achieve with the help of
the physical clocks because of the time difference in PC2.

Generating incremental numbers by one node (process) is easy and should be
enough for lots systems. But generating incremental numbers by distributed
processes seems more complex.

The Paxos algorithm can be used to generate the incremental numbers: each time a
new request comes, the system get the latest version number, add 1 to it and
propose the new version number with the proposer's ID (avoid two proposer
propose the same version number), gives the client the new version number after
finishing the accept phase successfully. However, inside Paxos, there is a
incremental number generator assumed, which can be implemented in one single
process. But this number generator does not have higher performance than the one
inside Paxos.

I can't get a good solution to this problem by now, I will look more into it.
Anyone has a better idea (or from any paper) is welcome for discussion.

Timing is a critical issue in the distributed system. We do not care too
much about the physical clocks in the distributed system, instead, the
logical clocks and ordering are our main concern.

In the paper, Lamport first design a relation of "happened before" ("->").
Suppose we have three events a,b,c. If a and b are in the same process, and
a comes before b, a is defined to be "happened before" b (a->b). For two
events b and c, if at b, a proccess sends a message, and another process
receives it at c, then b->c. If a->b and b->c, then a->c. For two events
e,f, if neither e->f nor f->e, the two events are defined to be concurrent.
These are the base of the paper.

With this definations, the logic clock can be defined. A logic clock can be
considered as an order. Each event occupies a unique place in the order.
For each process, it is relatively easy to define its own event order.
However, it is not so easy to define a global order for the distributed
system. Use the notion C<a> for the clock of event a. Similar to the
defination of "->", if a->b, then C<a> < C<b>. To generate the clock for
each event, the author defines two rules: 1, increase C every time after an
event happen.2, When sending a message, the current clock of the sender is
included, the receiver should move its clock forward to the sender's clock
if it is left behind. Then, when ordering the events totally, we may have
some events already ordered. For the events which has no "->"
relationships, we use an arbitrary total ording -< of the process. Then the
relation of "=>" can be defined as following. a=>b iff 1) Ci<a> < Cj<b> or
2) Ci<a>=Cj<b> and Pi -< Pj. There should be different "=>"s based on the
different "-<" chosen.