Lamport's Algorithm

• based on two rules that define how to increment each process's local clock
• Notation
  • processes are named Pi
  • local clock for corresponding process named Ci
  • clock time for event a is Ci(a)
• Rule 1: if a and b are two successive events in Pi and a --> b, then Ci(b) = Ci(a) + d, where d > 0
• Rule 2: if a is a send event on Pi, and b on Pj is its corresponding receive event, then the message is assigned a timestamp Ci(a)
• Limitations: a --> b implies C(a) < C(b)
  but C(a) < C(b) does not imply a --> b

Vector Clocks

• Each process has a vector clock, which contains its idea of the clock of all processes
• Implication:
• a --> b iff C(a) < C(b)
• if two events are not comparable, then they are concurrent

Sockets

• A two way conduit through which you can shove data
• Java: we put streams over sockets
  this gives a "higher level" of i/o
• Java: implies a "master/slave" relationship,
  because one thread must initiate the socket