Papers Reading List

DONE:

1. Implementing Remote Procedure Calls. ANDREW D. BIRRELL and BRUCE JAY NELSON Xerox Palo Alto Research Center
2. The Role of Distributed State. John K. Ousterhout
3. Time, Clocks and the Ordering of Events in a Distributed System. Leslie Lamppost
4. Defining Liveness. 

Here are some notes on N.O. 3 Lamport Clock:
1) A distributed system is a distributed set of processes that can communicate with each other through messages channels.

2) There are 3 kinds of events that can happen in distributed system: internal events within a process, sending a message to another process and receiving a message from another process. 

3) There two axioms in distributed system in terms of the order of events: within a process, internal events happen in serial; A single message must be sent first before it can be received by another process (The communication channels amongst processes cannot create messages out of thin air) 

4) For a system of events in a distributed system, it is the partial order of these events governed by the before-mentioned axioms that matters. To see why, think of events that we cannot establish partial order amongst them. The order in which concurrent events happened does not affect the progression of the overall state of the distributed system, and it  can change depending on the relative speed of the processes where the events occurred.

5) In distributed system, a global clock is absent and we cannot depend on each process's own physical clock because they can drift over time. To correctly capture the partial order within the distributed system, Lamport devised a system of logical clocks.

6) In lamport's logical clock, the partial order is preserved by designing the clock to satisfy the Clock condition:     if a->b, then C(a) < C(b)

7) For concurrent events, the order of their assigned clock value does not matter and therefore can be in arbitrarily order.