Parallel Programming: Vector Clocks

Groups of nodes act together, can send messages (multicast) to a group, and the messages are received by all the nodes that are in the group (Sandén, 2011).  If there is a broadcast, all nodes in the system get the same message.  In a multicast, the messages can reach the nodes in a group in a different order: First In First Out order, casual order, or total order (atomic multicast if it is reliable).

Per Sandén (2011), a multicast can occur if the source is a member of the group, but it cannot span across groups in causal order. Two-phase, total order multicast systems can look like a vector clock but they are not, and each message sends or receive will increment on this system by one as they talk between the systems.

Below is an example of a vector clock:

To G1

  • m1 suggested time at 6 and  m2 suggested time at 11
  • m1 commit time at 7 and m2 commit time at 12

To G2

  • m1 suggested time at 7 and  m2 suggested time at 12
  • m1 commit time at 8 and m2 commit time at 13vectorclock


Parallel Programming: Locks

A lock for a Node could be for the latest service request. Nodes in a group have to agree on which one of them holds the lock during any one moment of time, which can be seen on a vector graph if we note which one holds the lock. A node can release and request a lock.

Mutual exclusion algorithms can have a centralized coordinator node that handles the requests for the lock, which then means if that node fails so will the program (Sandén, 2011). Mutual exclusion algorithms can allow for a contention-based exclusion where nodes compete for the lock equally, and a queue is created for pending requests.  Finally, controlled exclusions have a logical piece of code to visit each node at a regulated interval of time to lend them the lock.

Lamport’s clock can help order the contention-based scenario where every node is trying to get the lock and it can only be had through a queue (Sandén, 2011). The queue tracks their request through a timestamp. Nodes can earn a lock if it has all the reply messages it needs to run its task and it’s on the top of the list in its queue.

Sandén (2011), states that multicast is done to all nodes that the lock has been released, and abolishing this message can optimize the process. Thus, the node should get the request from the next in the queue and postpone it until is done with the lock.