Distributed Operating Systems - Project 2

Gossip Algorithm

Group Members-

• Anurag Patil
• Pratik Kamble

Problem Definition

• Gossip type algorithms can be used both for group communication and for aggregate computation.
• The goal of this project is to determine the convergence of such algorithms through a simulator based on actors written in Erlang.
• Since actors are fully asynchronous, the particular type of Gossip implemented is the so-called Asynchronous Gossip.

Gossip Algorithm for information propagation

The Gossip algorithm involves the following:

• Starting: A participant(actor) told/sent a rumor (fact) by the main process
• Step: Each actor selects a random neighbor and tells it the rumor.
• Termination: Each actor keeps track of rumors and how many times he has heard the rumor. It stops transmitting once it has heard the rumor 10 times (10 is arbitrary, you can select other values).

Push-Sum algorithm for sum computation

• State: Each actor Ai maintains two quantities: s and w. Initially, s = xi = i (that is actor number i has value i, play with other distribution if you so desire) and w = 1
• Starting: Ask one of the actors to start from the main process.
• Receive: Messages sent and received are pairs of the form (s, w). Upon receiving, an actor should add the received pair to its own corresponding values. Upon receiving, each actor selects a random neighbor and sends it a message.
• Send: When sending a message to another actor, half of s and w is kept by the sending actor, and half is placed in the message.
• Sum Estimate: At any given moment of time, the sum estimate is s/w where s and w are the current values of an actor.
• Termination: If an actor's ratio s/w did not change more than 10−10 in 3 consecutive rounds the actor terminates. WARNING: the values s and w independently never converge, only the ratio does.

Steps to run the code

• Clone this repository and install erlang.
• cd Gossip-Algorithm
• erl
• c(main_process).
• main_process:start_main_process(NumNodes, Topology, Algorithm).
• 3 parameters in the above command are:
  1. NumNodes : Number of Desired Nodes
  2. Topology : One of the following 4 Topologies ["Full", "Line", "2D", "Imperfect 3D"]
  3. Algorithm: One of the following 2 Algorithms ["Gossip", "Push Sum"]

Conclusions and Results

1. What is working:

   1. We have implemented 2 Algorithms, Gossip Algorithm and Push Sum Algorithm as mentioned in the problem definition section above.

   2. File gossip.erl has the Gossip Algorithm and File push_sum_computation.erl has the Push Sum Algorithm.

   3. File main_process.erl is the main file where the execution starts.

   4. Each Algorithm is implemented for 4 Topologies:

      1. Full Network: Every actor is a neighbor of all other actors. That is, every actor can talk directly to any other actor.
      2. 2D Grid: Actors form a 2D grid. The actors can only talk to the grid neighbors
      3. Line: Actors are arranged in a line. Each actor has only 2 neighbors (one left and one right, unless you are the first or last actor).
      4. Imperfect 3D Grid: Grid arrangement but one random other neighbor is selected from the list of all actors (8+1 neighbors).

   5. Please check gossip-1.txt, gossip-1.txt files, push-sum-1.txt in Test Case Directory in this Project for verification outputs for each of the above Topologies.

   6. Sreenshot 1: Snippet of Output for "Line" Topology for Gossip Algorithm showing Actor ID and Received Actor ID proving that it is getting message from line neighbors.

   7. Sreenshot 2: Snippet of Output for "2D" Topology for Push Sum Algorithm showing Actor ID and Received Actor ID proving that it is getting message from 2D neighbors.

   8. In Gossip Algorithm, when each actor receives 10 messages it stops transmitting. This counter can be easily updated to test for other values.

   9. In Push Sum Algorithm, S is initialized to index of the actor and W to 1.

2. The largest network we managed to deal with for each type of topology and algorithm is follows:

   1. We used MacBook Air with M1 processor and Lenovo Legion with i7 processor.
   2. 3D Imperfect Topology performed best for Gossip Algorithm.
   3. Full Network Topology performed best for Push Sum Algorithm.
   4. Line Topology performed the worst for both the algorithms.