[SOLVED] SER321 Assignment 5- Distributed Algorithms

Prerequisites

1. The assigned readings in module 5 on Canvas
2. Lecture videos from Canvas/ or class

Learning outcomes of this assignment are:

1. Understand the basics of Distributed Algorithms
2. Evaluate Distributed Algorithms
3. Understand the basics of Consensus algorithms

Preliminary things

I strongly advise you to work on Git and GitHub, to version control and also to practice. If you work on GitHub make sure your repository is private.

Submit your assignment as always on GitHub in the appropriated directory and as zip file on Canvas.

What you definitely need:

1. A README.md for your project
2. Design your calls and user interaction in a way that they are easy. Remember we have a lot of assignments to grade; design it so it is easy for you, most of this is given anyway.
3. Explain how we can call your program and use it correctly.
4. More details for the README.md will follow later.

1      Activity: Simplified Consensus Algorithm 100

The task is to implement a simplified consensus algorithm between a number of nodes. We assume there is one leader node which all the other nodes can talk to. We will skip the part where each node can potentially talk to all the other nodes, so no peer to peer network here.

Basic structure: Client sends a request to the one Leader node, the Leader then asks the other Nodes for consent, receives the answers and handles things accordingly.

You do not start off with starter code for this task. You must start from scratch in this case and build the whole system yourself. You can of course use any of the sources provided in the example repository if you like.

Tip: draw things out at the beginning, think about your structure. The system is not very complicated but there is a lot of communication going on, think all your connections through and spend time on coming up with how and when which message is send.

Your Client (command line) is the one used by a person and that Client should communicate only with the Leader node. The Client can ask for a credit (loan) of a specific amount or pay back some or all of their existing credit. We skip things like the banks making more money and getting percentages when giving credit to simplify things.

As always you should make sure that your code is as robust as possible, does not crash, the data is persistent and the user interface is easy to use.

The protocol you use for your communication is totally up to you but it has to be well defined.

Points add up to a bit more than the max points.

1. You will need a README.md which contains the following (most goes to the protocol):
   1. (4 points) A short screencast where you show your project in action and explain everything we need to know about it. (if you do not include a screencast you might loose more points if we cannot see some of your features)
   2. (3 points) Explain your project and which requirements you were able to fulfill.
   3. (3 points) Explain how to start your project and which Gradle commands to use
   4. (6 points) Explain your protocol.
2. (4 points) Project is well structured and easy to understand.
3. (5 points) We can run the project as specified in the Readme, we only need to copy and paste the commands and things connect correctly.
4. (4 points) It is possible to start one Client, one Leader and at least 2 Nodes. All of these are connected correctly.
5. (3 points) It is possible to start up to 5 Nodes.
6. (3 points) Leader will ask the Client for their clientID, which should be provided by the client. You can just use a number if you like and you can assume the number entered is correct. This id will be sent to the Leader.
7. (3 points) Client will then have the choice between requesting a line of credit or paying part of an existing loan. This should be a Client-side choice that is followed by input for the amount of “credit” or “payback”.
8. (3 points) The leader receives the request (“credit”, “payback” – or however you want to call this) with the amount. See below for details on each operation.
9. Credit:
   1. (4 points) If the client wants credit, then the leader sends all known Nodes the information that a specific client wants a credit of that amount (clientID, amount).
   2. (4 points) Nodes will check if that client already has credit with them and if the node (each representing a bank) has enough money available. If the client with that ID does not have credit with them yet and the bank has at least 150% of what the client wants available (yes we want the bank to have more than what the client wants), they respond with a “yes”. If that is not the case, they respond with a “no”.
   3. (4 points) If the majority of nodes (so if two nodes are connected, both have to answer yes) say “yes”, then the credit is granted to the client.
   4. (4 points) The leader will split up the amount as evenly as possible between the nodes and notify them that this client now has this amount of credit with them.
   5. (4 points) Nodes and the Leader should store the value of the credit given to a specific Client. The Nodes will have to persistently save that amount and clientID. The Client is informed that they get the credit and the leader stores the amount persistently as well.
   6. (3 points) Nodes will decrease their available money based on how much they gave to the Client.
   7. (2 points) If the majority vote “no”, the Client will be informed that they do not get any credit and the Nodes will not decrease their available money.
   8. (6 points) The Leader asking for votes should be threaded. As an example of why this is necessary, let’s assume a Node takes a while to respond with a yes/no, such as a delay of 10 seconds. If there are 4 Nodes then it would take at least 30 seconds (majority) until we can actually count if we got a majority vote. This is how it would work in a single-threaded program where the Leader asks one Node at a time. We don’t want to wait that long. Come up with a way that the Nodes can actually “work” in parallel so in this hypothetical situation we would not be more than 30 seconds but just about 10 seconds instead.
10. Pay back:
    1. (3 points) If the client wants to pay money back, then the Leader informs the Nodes that this client wants to pay money back.
    2. (3 points) Nodes will check how much the client owes and return how much that clients owes to them to the Leader.
    3. (3 points) If the client wants to pay back more than is owed, they will just get an error message which the leader will send to the client.
    4. (6 points) If the client pays back partially or all of their existing credit, the Leader will split up the amount to each Node. You can split it up 2/3 1/3 if you like. You should of course not pay back more than is owed to a Node. The Nodes will update their records, the Leader will update its records and the Client will be informed about how much debt is still owed.
11. (5 points) You should make sure that when a node crashes the whole system does not go down. If the Leader crashes then of course a restart might be needed but the data should be persistent.
12. (5 points) If a restart is needed, the first thing the leader should do when a node connects to it is check in with the node and verify their records, e.g. client=1 owes=100 based on leader, node1 says client=1 owes=50, node2 says client=1 owes=20. In this case something went wrong and you might want to check what happened. Maybe have the leader keep track of all transactions so you can roll back.
13. (5 points) This gets interesting if more than one client can interact with the leader and make requests. The system will need to make sure it handles them correctly (like preventing the common multi-threading issues that we learned about) and the order of transactions is still correct.

Examples:

• Assume node1 starts with 1000 and node2 with 2000 “money”. I will omit the currency here. No transactions happened.
• Now client1 wants to get a credit of 500 and contacts the leader. The leader will forward this to the nodes. In this case both nodes will respond with yes, since both have more than 750 and this client does not have credit with them yet. The leader splits up the credit 50/50 so 250 node1, 250 node2, and node1 will save that client1:250, same for node2, the leader will store 500 for that client. They will also decrease their money. node1: 750, node2: 1750,
• client2 wants to get a credit of 700. Same process but now node1 would decline since they do not have enough money anymore. So the client will not receive money.
• client1 wants another credit. Would also be declined, since they already owe money.
• client3 wants 301 credit. This would be accepted by both, so the leader would split up the amount into 150/151 (if you want to you can also split it up so that node2 will give more since it has more money available – I leave this up to you). So now node1 client1:250, client2:150 and node2 client1: 250, client2:151.
• client1 wants to pay back some of their credit 200. The leader will ask each node how much this client owes. So the nodes would each return 250 (remember it might be different for each node depending on the split up). The leader can now decide how to pay back. You could have the nodes also return the money they have and then do the payback depending on how much money the bank has, e.g. node1 would get more in that case, or you can do it evenly. Up to you. So now node1 and node2 would update their records for client1.
• It gets interesting if you have more than 2 nodes. Since now 3 nodes might say yes and another one says no. Still the majority, so now the credit is split up between only the nodes that said yes.

Submission

Push your Assignment 5 folder to GitHub and make sure that you also include the link to the folder on Canvas in your submission also make sure you submit your zip file on Canvas.