Algorithms for Distributed Systems

Everything that has to be adapted in the code has a # Fill in in the same line

Table of Contents

1. Berkeley
2. Chord System
3. Crypto System
4. Diffie Hellman
5. Greedy Server Placement
6. Lamport's Logical Clocks
7. Read Write Quorums
8. Vector Clock

Berkeley

The Berkeley algorithm is a method of clock synchronisation in distributed computing which assumes no machine has an accurate time source.

How to use?

Every time has to be typed in the following format: 3:30pm = 1530 | 11:20am 1120

1. Start the Berkeley.py program
2. First type in how many servers exist
3. Secondly type in the time for each server using the right time format explained above
4. Thirdly type in which server should be the time daemon

Example:

(Source: ResearchGate)

(Back to Top)

Chord System

In computing, Chord is a protocol and algorithm for a peer-to-peer distributed hash table. A distributed hash table stores key-value pairs by assigning keys to different computers (known as "nodes"); a node will store the values for all the keys for which it is responsible. Chord specifies how keys are assigned to nodes, and how a node can discover the value for a given key by first locating the node responsible for that key.

How to use?

1. Start the ChordSystem.py program
2. First you have to type in the amount of nodes which is saved in "nodes_length" (In the given Example it would be 32)
3. Secondly you have to add the "bid_id" which is the bit identifier (In the given example it is represented by the length of each finger table which is 5)
4. The first two steps are to create a working Chord System, however if you want to find a path from one node to another with a key the next two steps have to be typed in as well (If you don't want to create a path just let the "start_node" and "key" free by just pressing enter)
5. If you want to create a path just type in the "start_node" and the "key" (In the given example one case would be k=12 and start_node=28

Example:

(Source: Reddit)

(Back to Top)

Crypto System

This Crypto System is just to send and receive messages from A(Sender) to B(Receiver), which consists of 3 factors:

1. Confidentiality
2. Authenticity
3. Integrity

How to use?

1. Start the DiffieHellman.py program
2. Type in the Public Key of A = ka_pu
3. Type in the Private Key of A = ka_pr
4. Type in the Modules of A = na
5. Type in the Public Key of B = kb_pu
6. Type in the Private Key of B = kb_pr
7. Type in the Modules of B = nb
8. Type in the Message = m
9. Type in the Hash function value = h

Example:

(Source: eduCBA)

(Back to Top)

Diffie Hellman

Diffie–Hellman key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived.

How to use?

1. Start the DiffieHellman.py program
2. Type in the modulo value n (in the example n is P)
3. Type in the base value g
4. Type in the a value
5. Type in the b value

Example:

(Source: Research Gate)

(Back to Top)

Greedy Server Placement

How to use?

1. Fill in each column in the options array (would look like this related to given example: [[1, 10, 10], [10, 5, 3], [10, 6, 5]])
2. Start the GreedyServerPlacement.py program

Example:

(Back to Top)

Lamport's Logical Clocks

The Lamport timestamp algorithm is a simple logical clock algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method.

How to use?

1. The first step is to fill in all messages by adapting the "messages" array in the LamportsLogicalClocks.py file (In the given example it would look like this messages = [[1,2,2],[2,3,3],[2,1,6],[3,2,7]])
   1. case: [1,2,2]
   2. The first number represents from which processor we are sending the message, the range is 1-processors, which in this case is P1(1)
   3. The second number represents to which processor we are sending the message, the range is 1-processors, which in this case is P2(2)
   4. The third number represents the row we are sending the number from the first given process, which in this case is 2
2. Start the LamportsLogicalClocks.py program
3. First you have to type in the amount of processors existing, which in this case would be 3
4. Secondly you have to type in the amount of rows existing, which in this case would be 9
5. Lastly just type in the number sequences for each processor, which in this case would be 5,8,10

Example:

(Source: Thomas Wiki)

(Back to Top)

Read Write Quorums

Read-write quorums define two configurable parameters, R and W. R is the minimum number of nodes that must participate in a read operation, and W the minimum number of nodes that must participate in a write operation. There are 2 main rules included in the system:

1. It is a read quorum (read is important)
1. The read part is 1 and the write part is n
2. Otherwise
1. The write part is calculated as following: random number between n/2 && n
2. The read part is calculated as following: random number between n - writeQuorum + 1 && n

How to use?

1. Start the ReadWriteQuorums.py program
2. First enter the amount of numbers existing which is represented in the variable n, which in the example would be 12
3. Secondly type in "1" if reading is important, if not just type in any other value

Example:

(Source: Lass)

(Back to Top)

Vector Clock

A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's logical clock.

How to use?

1. Change the start values ("vectors" array), if they differ from yours or add more array entries to the list if you have more than 3 vector clocks
2. Fill in the "task_list" array
• Example for the given provided resource below: task_list = [["13", "2"], ["32"], ["21", "3"], ["31"]]
• Each entry in the array is one time step and each time step has a list of execution commands, which are either an increment(one number) or a message(two numbers)
• If you want to add a message in the time step then the first number is from which clock to which clock, both from and to are in the range of 1-(amount of vectorClocks)
• If you want to add an e step which is an increment you just have to add the specific vector clock which starts from 1 upwards
3. Start the VectorClock.py program

Example:

(Back to Top)