Distributed System Algorithms

1. Lamport Logical Clock in C++

The Lamport Timestamp, also known as the Lamport Logical Clock, is a simple yet effective algorithm that helps determine the order of events in a distributed system.

The algorithm is quite straightforward. Each process increments its counter before every event in the process. When a process sends a message, it includes its counter value with the message. Upon receiving a message, the recipient updates its counter, if necessary, to the greater of its current counter or the timestamp in the received message. The counter is then incremented by 1 before the message is considered received.

The algorithm for sending:

time = time+1;
time_stamp = time;
send(message, time_stamp);

The algorithm for receiving:

(message, time_stamp) = receive();
time = max(time_stamp, time)+1;

Here's a C++ simulation of the Lamport Logical Clock using POSIX threads. The two threads simulate two processes and a pipe is used to send and receive message:

[code]

#include <unistd.h>     /* Symbolic Constants */
#include <stdio.h>      /* Input/Output */
#include <pthread.h>    /* POSIX Threads */
#include <algorithm>    /* max */

pthread_t thread_a;
pthread_t thread_b;

int channela[2];

void * handlerA(void *) {
    int ltime  = 0;
    int timestamp;
    while(1) {
        usleep(150000);
        ltime ++;
        timestamp = ltime;
        write(channela[1], (void *) &timestamp, sizeof(int));
        printf("Program A Physical clock: %d\t", ltime);
    }
}

void * handlerB(void *) {
    int ltime = 0; 
    int timestamp;

    while(1) {
        usleep(200000); ltime++;
        printf("Program B Physical clock: %d\t", ltime);
        read(channela[0], &timestamp, sizeof(int));
        ltime = max(timestamp, ltime) + 1;
        printf("Received clock: %d, so the Logical clock: %d\n", timestamp, ltime);

    }
}

int main(void)
{

     pipe(channela);
     pthread_create(&thread_a, NULL, handlerA, NULL);
     pthread_create(&thread_b, NULL, handlerB, NULL);

     pthread_join(thread_a, NULL);
     pthread_join(thread_b, NULL);

}

2. Distributed System Mutual Exclusion Algorithm in C++

Mutual exclusion is a key concept in concurrent programming. In the context of distributed systems, there are mainly two categories of mutual exclusions: Message-Passing based and Shared-Memory based.

One commonly used algorithm for achieving mutual exclusion is Peterson's algorithm. This algorithm allows two or more processes to share a single-use resource without conflict, using only shared memory for communication.

Here's an implementation of Peterson's algorithm in C++:

The are majorly two categories of mutual exclusions: Message-Passing based and Shared-Memory based, typical message passing based algorithms are:

1. Ricart-Agrawala algorithm
2. Raymond’s algorithm
3. Agrawal-El Abbadi algorithm
typical shared memory based algorithms are:
1. Peterson’s algorithm
2. Bakery algorithm
3. Fischer’s algorithm

Peterson's algorithm is a classical solution for ensuring mutual exclusion in concurrent systems. In case you need a more detailed explanation or have any questions about the algorithm, please feel free to ask. Here's a summary of how the algorithm works:

1. Declare interest: Each process that wishes to enter the critical section sets its flag to indicate its interest.

2. Yield priority: Each process also records which of the two processes should be given priority in case of contention. If both processes try to enter the critical section at the same time, the one that should yield is determined by this priority variable.

3. Wait if necessary: Before entering the critical section, each process checks the flag of the other process. If the other process is also interested in entering the critical section (its flag is set) and it has priority, the current process waits.

4. Enter the critical section: Once a process sees that either the other process is not interested in entering the critical section or it has priority, it enters the critical section.

5. Exit the critical section: After leaving the critical section, a process clears its flag to indicate it's no longer interested in entering the critical section.

This simple yet effective algorithm ensures that only one process can enter the critical section at a time, providing mutual exclusion. However, it's worth noting that this algorithm assumes that reads and writes to shared variables are atomic, which isn't always the case in real-world computer systems. It's also limited to two processes:

[code] 

int flag[2];
int turn;
const int MAX = 100;
int ans = 0;

void lock_init()
{
    flag[0] = flag[1] = 0;
    turn = 0;
}

// Lock before entering critical section
void lock(int self)
{
    // Set flag[self] = 1 to acquire lock
    flag[self] = 1;

    // But, first give the other thread the chance to
    // acquire lock
    turn = 1-self;

    // Wait until the other thread looses the desire
    // to acquire lock or it is your turn to get the lock.
    while (flag[1-self]==1 && turn==1-self) ;
}

// Unlock after leaving critical section
void unlock(int self)
{
    // You do not desire to acquire lock in future.
    // This will allow the other thread to acquire
    // the lock.
    flag[self] = 0;
}

void* func(void *s)
{
    int i = 0;
    int self = *(int *)s;

    while(1) {
         printf("Thread Number: %d\t", self);
         lock(self);
         printf("Locked \t");
         // Critical section
         for (i=0; i<MAX; i++) ans++;
         printf("Current value is %d\t", ans);
         printf("Unlock \n");

         unlock(self);
         if (ans > 1e7) break;
   }
                                                                                                                                                        
int main()
{
    pthread_t p1, p2;
    int pv1 = 0, pv2 = 1;
    lock_init();

    pthread_create(&p1, NULL, func, (void*)&pv1);
    pthread_create(&p2, NULL, func, (void*)&pv2);

    pthread_join(p1, NULL);
    pthread_join(p2, NULL);

    return 0;
}

3. Vector Clock in C++

A vector clock is an algorithm used for generating a partial ordering of events in a distributed system and for detecting causality violations. It's essentially an array of N logical clocks, one clock per process, and a local copy of this global clock-array is kept in each process.

The rules for clock updates in a vector clock are as follows:

• Initially, all clocks are zero.
• Each time a process experiences an internal event, it increments its own logical clock in the vector by one.
• Each time a process prepares to send a message, it sends its entire vector along with the message being sent.
• Each time a process receives a message, it increments its own logical clock in the vector by one and updates each element in its vector by taking the maximum of the value in its own vector clock and the value in the vector in the received message.

For a detailed explanation of the vector clock and a corresponding C++ implementation,

[code] (TBD)