” 写作COMP212编程、 辅导Java语言程序Department of Computer ScienceCOMP212 – 2021 – CA Assignment 1Coordination and Leader ElectionSimulating and Evaluating Distributed Protocols in JavaAssessment InformationAssignment Number 1 (of 2)Weighting 15%Assignment Circulated 15th February 2021Deadline 15th March 2021, 17:00 UK Time (UTC)Submission Mode Electronic via CANVASLearning outcomes assessed (1) An appreciation of the main principles underlyingdistributed systems: processes, communication, naming,synchronisation, Consistency, fault tolerance, andsecurity. (3) Knowledge and understanding of the essentialfacts, concepts, principles and theories relatingto Computer Science in general, and Distributed Computingin particular. (4) A sound knowledge of the criteriaand mechanisms whereby traditional and distributedsystems can be critically evaluated and analysed to determinethe extent to which they meet the criteria de-fined for their current and future development.Purpose of assessment This assignment assesses the understanding of coordinationand leader election in distributed systems and implementing,simulating, and evaluating distributed protocolsby using the Java programming language.Marking criteria Marks for each question are indicated under the correspondingquestion.Submission necessary in order Noto satisfy Module requirements?Late Submission Penalty Standard UoL Policy.11 Overall marking schemeThe coursework for COMP212 consists of two assignments contributing altogether 30% ofthe final mark. The contribution of the individual assignments is as follows:Assignment 1 15%Assignment 2 15%TOTAL 30%2 ObjectivesThis assignment requires you to implement in Java two distributed algorithms for leaderelection in a ring network and then to experimentally validate their correctness and evaluatetheir performance.3 Description of CourseworkThroughout this coursework, the network on which our algorithms are to be executed is abidirectional ring, as depicted in Figure 1.Figure 1: A bidirectional ring network on n processors.In our setting, all processors execute the same algorithm, do not know the number n ofprocessors in the system in advance, but they do know the structure of the network andare equipped with unique ids. The ids are not necessarily consecutive and for simplicityyou can assume that they are chosen from {1, 2, . . . , n}, where 1 is a small constant(e.g., for = 3, the n processors will be every time assigned unique ids from {1, 2, . . . , 3n 1, 3n}). Additionally, every processor can distinguish its clockwise from its counterclockwiseneighbour, so that, for example, it can choose to send to only one of them or to send a2different message to each of them. Processors execute in synchronous rounds, as in everyexample we have discussed so far in class.3.1 Implementing the LCR Algorithm30% of the assignmentmarkAs a first step, you are required to implement the LCR algorithm for leader election in aring. The pseudocode of the non-terminating version of LCR can be found in the lecturenotes and is also given here for convenience (Algorithm 1).Algorithm 1 LCR (non-terminating version)Code for processor ui, i {1, 2, . . . , n}:Initially:ui knows its own unique id stored in myIDisendIDi:= myIDistatusi:= unknown1: if round = 1 then2: send hsendIDii to clockwise neighbour3: else// Rround 14: upon receiving hinIDi from counterclockwise neighbour5: if inID myIDi then6: sendIDi:= inID7: send hsendIDii to clockwise neighbour8: else if inID = myIDi then9: statusi:= leader10: else if inID myIDi then11: do nothing12: end if13: end ifYou are required to implement a terminating version of the LCR algorithm inwhich all processors eventually terminate and know the id of the elected leader.3.2 Implementing the HS Algorithm30% of the assignmentmarkNext, you are required to implement another algorithm for leader election on a ring, knownas the HS algorithm. As LCR, HS also elects the processor with the maximum id. Themain difference is that HS instead of trying to send ids all the way around in one direction(which is what LCR does), it has every processor trying to send its id in both directions some3distance away (e.g., k) and then has the ids turn around and come back to the originatingprocessor. As long as a processor succeeds, it does so repeatedly (in phases) to successivelygreater distances (doubling the distance to be travelled each time, e.g., 2k). See Figure 2 foran illustration.Figure 2: Trajectories of successive phases originating at processor u4 (imagine the rest ofthe processors doing something similar in parallel, but not depicted here). The id transmittedby u4 aims to travel some distance out in both directions and then return back. If it succeeds,then u4 doubles the aimed distance and repeats.Informally, each processor ui operates in phases l = 0, 1, . . . (where each phase l consistsof one or more rounds). In each phase l, processor ui sends out a token (i.e., a message)containing its id idiin both directions. These are intended to travel distance 2l(that is,as in Figure 2, distance 20 = 1 for l = 0, distance 21 = 2 for l = 1, distance 22 = 4 forl = 2, and so on) and then return to their origin. If both tokens manage to return back thenui goes to the next phase, otherwise it stops to produce its own tokens (and only performsfrom that point on the Rest of the algorithms operations). A token is discarded if it evermeets a processor with greater id while travelling outwards (away from its origin). Whiletravelling inwards (back to its origin), a token is forwarded by all processors without anycheck. The termination criterion is as follows: If a token travelling outwards meets its ownorigin ui (meaning that this token managed to perform a complete turn of the whole ringwhile travelling outwards), then ui elects itself as the leader. Observe that in order for tokensto know how far they should travel each time and in which direction, this information has tobe included inside the transmitted messages (that is, apart from the id being transmitted,4the messages should also contain this auxiliary information).The pseudocode of the non-terminating version of HS is given in Algorithm 2. As withLCR, you are required to implement a terminating version of the HS algorithm inwhich all processors eventually terminate and know the id of the elected leader.3.3 Experimental Evaluation, Comparison Report40% of theassignment markAfter implementing the terminating LCR and HS algorithms, the next step is to conductan experimental evaluation of their correctness and performance.Correctness. Execute each algorithm in rings of varying size (e.g., n = 3, 4, . . . , 1000, . . .;actually, up to a point where simulation does take too much time to complete) and startingfrom various different id assignments for each given ring size. For instance, you couldexecute them on both specifically constructed id assignments (e.g., ids ascending clockwiseor counterclockwise) and random id assignments. In each execution, your simulatorshould check that eventually precisely one leader is elected. Of course, this will not be areplacement of a formal proof that the algorithms are correct as you wont be able to testthem on all possible combinations of ring sizes and id assignments, but at least it will be afirst indication that they may do as intended.Performance. Execute, as above, each algorithm in rings of varying size and starting fromvarious different id assignments for each given ring size. For each execution, your simulatorshould record the number of rounds and the total number of messages transmitteduntil termination.1. Execute both algorithms in rings of varying size for the case in which ids are alwaysclockwise ordered.2. Execute both algorithms in rings of varying size for the case in which ids are alwayscounterclockwise ordered.3. Execute both algorithms in rings of varying size and various random id assignmentsfor each given ring size. Note here that both algorithms should be simulated (e.g.,one after the other) on every Given choice of ring size and id assignment, so that acomparison of their performance makes sense.In Summary: For both correctness validation and performance evaluation a suggestionis to simulate both algorithms (for all types of id assignments mentioned above) in ringscontaining up to at least 1000 processors. Specifically in the case of random id assignments,for each ring size n repeat the simulation for many different id assignments (e.g., at least100 distinct simulations) and record the correctness and the worst, the best, and the averageperformance so that you get meaningful results.5Algorithm 2 HS (non-terminating version)Messages are triples of the form hID, direction, hopCounti, where direction {out, in} andhopCount positive integer.Code for processor ui, i {1, 2, . . . , n}:Initially:ui knows its own unique id stored in myIDisendClocki containing a message to be forwarded clockwise or null, initiallysendClocki:= hmyIDi, out, 1isendCounterclocki containing a message to be forwarded counterclockwise or null, initiallysendCounterclocki:= hmyIDi, out, 1istatusi {unknown,leader}, initially statusi:= unknownphasei recording the Current phase number, nonnegative integer, initially phasei = 01: upon receiving hinID, out, hopCounti from counterclockwise neighbour2: if inID myIDi and hopCount 1 then3: sendClocki:= hinID, out, hopCount 1i4: else if inID myIDi and hopCount = 1 then5: sendCounterclocki:= hinID, in, 1i6: else if inID = myIDi then7: statusi:= leader8: end if9:10: upon receiving hinID, out, hopCounti from clockwise neighbour11: if inID myIDi and hopCount 1 then12: sendCounterclocki:= hinID, out, hopCount 1i13: else if inID myIDi and hopCount = 1 then14: sendClocki:= hinID, in, 1i15: else if inID = myIDi then16: statusi:= leader17: end if18:19: upon receiving hinID, in, 1i from counterclockwise neighbour, in which inID 6= myIDi20: sendClocki:= hinID, in, 1i21:622: upon receiving hinID, in, 1i from clockwise neighbour, in which inID 6= myIDi23: sendCounterclocki:= hinID, in, 1i24:25: upon receiving hinID, in, 1i From both clockwise and counterclockwise neighbours, inboth of which inID = myIDi holds26: phasei:= phasei + 127: sendClocki:= hmyIDi, out, 2phasei i28: sendCounterclocki:= hmyIDi, out, 2phasei i29:30: // The following to be always executed by all processors, i.e.,31: // also in round 1 in which no message has been received32: send hsendClockii to clockwise neighbour33: send hsendCounterclockii to counterclockwise neighbourAfter gathering the simulation data, plot them as follows. In each plot, the x-axis willrepresent the (increasing) size of the ring and the y-axis will represent the complexity measure(e.g., number of rounds or number of messages). You may produce individual plotsdepicting the performance of each algorithm (possibly comparing against standard complexityfunctions, like n, n log n, or n2) and you are required to produce plots comparing theperformance of both algorithms in identical settings. For example, when measuring the totalnumber of messages in the case of counterclockwise increasing ids, a plot would show atthe same time the performance of both algorithms for increasing ring size n, using curves ofdifferent colours and possibly also a legend with explanations. Then, for each given ring size,the corresponding point of each curve will represent the total number of messages generatedby the algorithm (indicated on the y-axis). You can use gnuplot, JavaPlot or any otherplotting software that you are familiar with.The final crucial step is to prepare a concise report (at most 5 pages including plots)clearly describing your main implementation choices, the main functionality of your simulator,the set of experiments conducted, and the findings of your experimental evaluationof the above algorithms. In Particular, in the latter part you should try to draw conclusionsabout (i) the algorithms correctness and (ii) the performance (time and messages)of each algorithm individually (e.g., what was the worst/best/average performance of eachalgorithm as a function of n? For example, we know from the lectures that the worst-casecommunication complexity of LCR is O(n2): can you verify this experimentally?) and whenthe two algorithms are being compared against each other (e.g., which one performs betterand in which settings?).4 Deadline and Submission Instructions The deadline for submitting this assignment is Monday, 15th March 2021, 17:00UK time (UTC).7 Submit(a) The Java source code for all your programs,(b) A README file (plain text) describing how to compile/run your code to producethe various results required by the assignment, and(c) A concise self-contained report (at most 5 pages including everything) describingyour implementation choices, experiments, and conclusions in PDF format.Compress all of the above files into a single ZIP file (the electronic submission systemwont accept any other file formats) and specify the filename as Surname-NameID.zip.It is extremely important that you include in the Archive all the files describedabove and not just the source code! Submission is via the Assignments tab of COMP212-202021 course on CANVAS.Good luck to all!如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
