Assignment 1 – CS324 Distributed Systems 2024 Due Date:23rd September 2024,11:55 pm
Learning Outcome:Develop a software system using distributed platforms
This assignment asks you to implement adistributed system based on the so-called Leader Election protocol.
Plagiarism
Please state clearly in your write-up and program who are your group members.If we find that you copied work from others-people who are not on your group-it will be considered plagiarism.
It’s not plagiarism to discuss the assignment with other students and consider solutions to the problems together.However,it is plagiarism for you to copyallor part of each other’swrite-up or models.
Questions
If you have problem with the assignment please ask.First use the forum,because this will also help other students with the same question.
Ring Algorithm for Leader Election
TheRingAlgorithm isaleader electionprotocol usedin distributedsystemswherenodesarearranged in a logical ring. The main goal of the algorithm is to ensure that a single leader orcoordinator is elected among the nodes in a distributed system, even in the presence of nodefailures.
Key Characteristics:
- LogicalRing:
- Nodesareorganizedin alogicalring structurewhereeach nodeknows onlytheidentityof its immediateneighbor in thering.
- Communicationintheringisunidirectional,meaningthatmessagesarepassedinonedirection (either clockwiseor counterclockwise) aroundthering.
Unique Identifiers:
- Each node in the ring has a unique identifier (ID). The election process aims toselectthenodewith thehighest IDas the leader.
Steps of the Ring Algorithm:
- ElectionTrigger:
- Theelectionprocessistriggeredwhenanodedetectsthatthecurrentleader hasfailed(e.g.,by notreceivingmessages fromtheleader foracertainperiod).
- Thenodethatdetects thefailurebecomes theinitiator oftheelection process.
Election Message:
- Theinitiator nodesendsanElectionmessagecontaining its own ID to itsimmediateneighbor in thering.
- Theneighbornode comparesits ownID withtheID in theElectionmessage.
- If the neighbor's ID is higher, it replaces the ID in the message with itsownand forwards themessageto thenext node inthe ring.
- Iftheneighbor'sIDislower, itsimplyforwards themessagewithoutchangingtheID.
Message Circulation:
- TheElectionmessagecontinuesto circulatearound thering, with each nodeforwardingthe message aftercomparingIDs.
- Whenthe Electionmessage makesafull circle and returns totheinitiator, it willcontainthe highestID inthe ring.
Leader Declaration:
- Thenode whose IDis in the Electionmessagewhen it returnsto theinitiator iselected as the leader.
- Theinitiatorthen sendsaCoordinatormessage(or Leadermessage)containingtheelectedleader'sID toallnodesin thering,confirmingthe electionresults.
Completion:
- Uponreceiving the Coordinatormessage,all nodes in the ring acknowledgethenewleader.
- Theleaderbeginsitsduties,andnormaloperationresumes
Example Scenario:
- Consideraring offivenodes with IDs:1,3, 5, 7, 9 arrangedin a clockwisering.
- Node 5 detects that the current leader (Node 9) has failed and starts an election bysendingan ElectionmessagewithID 5 to Node 7.
- Node7seesthatitsID(7) is higherthan 5,so it replaces theIDin theElectionmessagewith7 and forwards it to Node9.
- Node 9 would replace the ID with 9 if it were still active, but since it’s down, Node 1receivesthe messagewith ID 7.
- Node1, witha lower ID,forwardsthemessageunchanged toNode3.
- Node3,with alowerID than 7,forwards themessageunchangedto Node 5.
- When Node 5 receives the message back, it knows that Node 7 has the highest ID in thering.
- Node5thensends aCoordinatormessagewithID7 to all nodes, declaring Node7 asthenew leader.
Thisassignment hasthreeparts.
PART1:Write-up
Exercise 1
IstheLeaderElectionprotocolacentralizedordecentralizedsystem?Isitastructuredorunstructurednetwork?Explain your answerinlessthan 300 words.
| CBOK | Unsatisfactory(0%-49%) | Satisfactory(50%-75%) | Good(76%-100%) |
| Communication |
|
| IV. Allsatisfactory |
Exercise 2
Is it possible to implement Leader Election Protocol using RPC calls? If yes, explain which RPC calls youwouldneed. If no,explainwhyitcannotbe implemented viaRPC.
| CBOK | Unsatisfactory (0%-49%) | Satisfactory (50%- 75%) | Good (76% -100%) |
| Communication |
|
| VIII. Allsatisfactory |
PART2:Implementing Leader Election Protocol using RMI
ThispartoftheassignmentasksyoutoimplementtheLeaderElectionprotocolforanetworkwiththenumberof nodesas described intheproblemabove.
Exercise1:Communication and electingaleader
Youmustensurethefollowing:
- Communication must beinaringtopology.
- All nodes should not execute methods for other nodes.This should be restricted to allow communication in Ring topology.
- The program design depends on your group.
- Once the leaderi selected; the leader should in form all participants.
| CBOK | Unsatisfactory(0%-49%) | Satisfactory(50%-75%) | Good(76%-100%) |
| Programming |
| I.Able to write acomplexcodeforaloosely definedproblem | IX. Allsatisfactory anddemonstr atevery |
|
| goodprogrammingskills. |
PART 3: Implementing Leader Election Protocol with Peer Register using RMIExercise1
Modify the program given in Exercise 1 to include a peer register. All peers needs to register with a nodecalled “peer register”. This “peer register” node does not take part in the election process as it is only inchargeofregisteringpeersand ensuring which peerisconnectedto which oneinaring topology.
Therearesomerulesforpeer registration:
- A peercan onlyregister whenthereisnoelectioni.e.apeercannotregisterwhenanelectionisinprogress.
- The“peerregister” nodedecides whichnodesareconnected inaringtopology.
Your program should electa leader attheendand the leader shouldinformtheparticipants.
| CBOK | Unsatisfactory (0%-49%) | Satisfactory (50%- 75%) | Good (76% -100%) |
| Programming |
|
|
|
encapsulation,inheritance orpolymorphism for object-oriented programming
handling
| practicessuchasmodularity, lowcoupling, highcohesionetc.
| standard ofprogrammingpracticessuch asmodularitywithappropriatearchitecture, lowcoupling,highcohesion,standarddocs(eg. Javadoc)etc. Appropriate testing isdone. |