Logical Clocks refer to implementing a protocol on all machines within your distributed system so that the machines are able to maintain the consistent ordering of events within some virtual timespan. A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Distributed systems may have no physically synchronous global clock, so a logical clock allows global ordering on events from different processes in such systems.

Example:

If we go outside then we have made a full plan that at which place we have to go first, second, and so on. We don’t go to second place at first and then the first place. We always maintain the procedure or an organization that is planned before. In a similar way, we should do the operations on our PCs one by one in an organized way.

Suppose, we have more than 10 PCs in a distributed system and every PC is doing its own work but then how do we make them work together. There comes a solution to this i.e. LOGICAL CLOCK.

Method-1:

To order events across processes, try to sync clocks in one approach.

This means that if one PC has a time of 2:00 pm then every PC should have the same time which is quite not possible. Not every clock can sync at one time. Then we can’t follow this method.

Method-2:

Another approach is to assign Timestamps to events.

Taking the example into consideration, this means if we assign the first place as 1, second place as 2, third place as 3, and so on. Then we always know that the first place will always come first and then so on. Similarly, If we give each PC their individual number then it will be organized in a way that 1st PC will complete its process first and then second, and so on.

BUT, Timestamps will only work as long as they obey causality.

Lamport’s Logical Clock was created by Leslie Lamport. It is a procedure to determine the order of events occurring. It provides a basis for the more advanced Vector Clock Algorithm. Due to the absence of a Global Clock in a Distributed Operating System Lamport, Logical Clock is needed.

Algorithm:

Happened before relation(->): a -> b, means ‘a’ happened before ‘b’. Logical Clock: The criteria for the logical clocks are: Reference:

Process: Pi Event: Eij, where i is the process in number and j: jth event in the ith process. TM: vector time span for message m. Ci vector clock associated with process Pi, the jth element is Ci[j] and contains Pi‘s latest value for the current time in process Pj. d: drift time, generally d is 1. Implementation Rules[IR]:

Below is the C program to implement Lamport’s Logical Clock:

// C++ program to illustrate the Lamport's
// Logical Clock

#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum timestamp
// between 2 events
int max1(int a, int b)
{
    // Return the greatest of th two
    if (a > b)
        return a;
    else
        return b;
}

// Function to display the logical timestamp
void display(int e1, int e2,
             int p1[5], int p2[3])
{
    int i;

    cout << "\nThe time stamps of "
         "events in P1:\n";

    for (i = 0; i < e1; i++) {
        cout << p1[i] << " ";
    }

    cout << "\nThe time stamps of "
         "events in P2:\n";

    // Print the array p2[]
    for (i = 0; i < e2; i++)
        cout << p2[i] << " ";
}

// Function to find the timestamp of events
void lamportLogicalClock(int e1, int e2,
                         int m[5][3])
{
    int i, j, k, p1[e1], p2[e2];

    // Initialize p1[] and p2[]
    for (i = 0; i < e1; i++)
        p1[i] = i + 1;

    for (i = 0; i < e2; i++)
        p2[i] = i + 1;
    cout << "\t";
    for (i = 0; i < e2; i++)
        cout << "\te2" << i + 1;

    for (i = 0; i < e1; i++) {

        cout << "\n e1" << i + 1 << "\t";

        for (j = 0; j < e2; j++)
            cout << m[i][j] << "\t";
    }

    for (i = 0; i < e1; i++) {
        for (j = 0; j < e2; j++) {

            // Change the timestamp if the
            // message is sent
            if (m[i][j] == 1) {
                p2[j] = max1(p2[j], p1[i] + 1);
                for (k = j + 1; k < e2; k++)
                    p2[k] = p2[k - 1] + 1;
            }

            // Change the timestamp if the
            // message is received
            if (m[i][j] == -1) {
                p1[i] = max1(p1[i], p2[j] + 1);
                for (k = i + 1; k < e1; k++)
                    p1[k] = p1[k - 1] + 1;
            }
        }
    }

    // Function Call
    display(e1, e2, p1, p2);
}

// Driver Code
int main()
{
    int e1 = 5, e2 = 3, m[5][3];

    // message is sent and received
    // between two process

    /*dep[i][j] = 1, if message is sent
                   from ei to ej
    dep[i][j] = -1, if message is received
                    by ei from ej
    dep[i][j] = 0, otherwise*/
    m[0][0] = 0;
    m[0][1] = 0;
    m[0][2] = 0;
    m[1][0] = 0;
    m[1][1] = 0;
    m[1][2] = 1;
    m[2][0] = 0;
    m[2][1] = 0;
    m[2][2] = 0;
    m[3][0] = 0;
    m[3][1] = 0;
    m[3][2] = 0;
    m[4][0] = 0;
    m[4][1] = -1;
    m[4][2] = 0;

    // Function Call
    lamportLogicalClock(e1, e2, m);

    return 0;
}