A Series of Indicative Votes
Kirk Martinez Leonardo Aniello Corina Cîrstea
April 14, 2020
1 Introduction
The purpose of this assignment is to implement a consensus protocol that tolerates participant failures. The protocol involves two types of processes: a coordinator, whose role is to initiate a run of the consensus algorithm and collect the outcome of the vote; and a participant, which contributes a vote and communicates with the other participants to agree on an outcome. Your application should consist of 1 coordinator process and N participant processes, out of which any number of participants may fail during the run of the consensus algorithm. The actual consensus algorithm is run among the participant processes, with the coordinator only collecting outcomes from the participants. The behaviour of the two types of processes is described below. Furthermore, your application should include a logger server where the other processes send log messages over the UDP protocol.
Note that the IRC (Internet Relay Chat) example provided may prove useful in parsing messages and managing sockets.
Course:
COMP2207
A.Y.:
2019-20
Document version:
1.4
2
1.
2.
Protocol for Participant
Register with coordinator. The participant establishes a TCP connection with the coordinator and sends the following byte stream:
JOIN hporti
Where hporti is the port number that this partcipant is listening on. This will be treated as the identier of the participant. For example, the participant listening on port 12346 will send the message:
JOIN 12346
Get details of other participants from coordinator. The participant should wait to receive a message from the coordinator with the details of all other participants (i.e. read from the same socket connection):
DETAILS [hporti]
Where [hporti] is a list of the port numbers (aka. identiers) of all other particpants. (Note that we do not want a participant sending its vote to itself.) For example, a participant with identier/port 12346 may receive information about two other participants:
1
DETAILS 12347 12348
3. Get vote options from coordinator. The participant should wait again to receive a message from the coordinator with the details of the options for voting:
VOTE_OPTIONS [hoptioni]
Where [hoptioni] is the list of voting options for the consensus protocol. For example, there
may be two options, A and B:
VOTE_OPTIONS A B
Then decide on own vote, from the options received.
4. Execute a number of rounds by exchanging messages directly with the other participants using the TCP protocol.
Round 1 The participant will send and receive messages of the following structure in the rst round:
VOTE hporti hvotei
Where hporti is the sender’s port number/identier, and hvotei is one of the vote options (i.e. that agent’s vote).
For example, if we have 3 participants listening on ports 12346, 12347 and 12348, and their votes are A, B and A respectively, and there are no failures, then the messages passed between participants will be:
12346 to 12347: VOTE 12346 A 12346 to 12348: VOTE 12346 A 12347 to 12346: VOTE 12347 B 12347 to 12348: VOTE 12347 B 12348 to 12346: VOTE 12348 A 12348 to 12347: VOTE 12348 A
Round j > 1 The participant will send and receive messages of the following structure in all subsequent rounds:
VOTE hport 1i hvote 1i hport 2i hvote 2i …hport ni hvote ni
Where hport ii and hvote ii are the port (identier) and vote of any new votes received in the previous round.
5. Decide vote outcome using majority. In case of a tie, pick the rst option according to an ascendant lexicographic order of the options with the majority of votes.
For example, if there are three options A, B and C with 2, 2 and 1 votes, respectively, then there is a tie between A and B; this tie should be resolved by sorting the majority options (i.e. A and B) by lexicographic order (i.e. [A,B]) and picking the rst one (i.e. A).
6. Inform coordinator of the outcome. The following message should be sent to the coordinator on the same connection established during the intial stage:
OUTCOME houtcomei [hporti]
Where houtcomei is the option that this participant has decided is the outcome of the vote, and [hporti] is the list of participants that were taken into account in settling the vote. For example, participant 12346 in the above example should send this message to the coordinator:
OUTCOME A 12346 12347 12348
In other words, agent 12346 has taken into account its own vote and those of 12347 and 12348
and come to the conclusion that A is the outcome by majority vote.
2
3
1.
2.
Protocol for the Coordinator
Wait for the number of participants specied to join. The number of participants should be
given as a parameter to the main method of the coordinator (see below). JOIN hporti
Where hporti is the port number of the participant.
Send participant details to each participant once all participants have joined:
DETAILS [hporti]
Where [hporti] is a list of the port numbers (aka. identiers) of all other particpants.
3. Send request for votes to all participants:
VOTE_OPTIONS [hoptioni]
Where [hoptioni] is the list of voting options for the consensus protocol. The voting options
should be given as a parameter to the main method of the coordinator (see below).
4. Receive votes from participants:
OUTCOME houtcomei [hporti]
Where houtcomei is the option that this participant has decided is the outcome of the vote, and
[hporti] is the list of participants that were taken into account in settling the vote.
4 Logging
Participant and Coordinator processes should log their operations in two dierent ways. They should (i) use two ad-hoc classes provided by us to log to a le and (ii) implement a logger process that receives messages via UPD and stores them in a le. The following two subsections describe these two logging approaches in more detail, and a third subsection explains how to use the provided logger classes.
4.1 Logger classes
You should use the public methods provided by the classes ParticipantLogger and
CoordinatorLogger to log the main actions that coordinator and participant processes take.
For example, right after the coordinator accepted a connection from a participant, the method connectionAccepted() of CoordinatorLogger should be invoked. As another example, as soon as a participant detects the failure of another participant (i.e. the corresponding connection has been interrupted), the method participantCrashed() of ParticipantLogger should be invoked.
4.2 Logger server
You should implement a UDPLoggerServer class that starts a server process which listens for UPD log messages on a specic port, given as input parameter when the server process is started. Whenever a new message is received by the server, an acknowledgement is sent back to the sender process and the message is stored in a log le by the server. The acknowledge message is the string ACK, without quotes. As this is using UDP the client should timeout if it did not receive an ACK
3
and resend up to three times. The log messages sent by the coordinator and participant processes have the following format:
id msg
where id is the TCP port where the sender process is listening on and msg is the log message.
For each log message id msg sent by a process id at time t, the log le should include an entry formatted in this way:
id t msg
The method System.currentTimeMillis() should be used to obtain the current time. For example, if log message 12346 [P12346] JOIN sent to Coordinator on port 12345 is sent by the participant listening on port 12346 and is received by the Logger server at time 1583508972566, then the log le should include the following entry:
12346 1583508972566 [P12346] JOIN sent to Coordinator on port 12345
The name of the log le must be logger_server_hti.log, where hti is to be replaced with the time the Logger server was started. For example, if the Logger server was launched at time 1583508972566, then the name of the log le should be logger_server_1583508972566.log.
You should also implement a UDPLoggerClient class that coordinator and participants will use to send log messages to the logger server using UDP protocol. In the specic, this class will provide a single method logToServer(String message) that will be invoked internally by all the public methods of ParticipantLogger and CoordinatorLogger classes. This means that you do not need to invoke logToServer() explicitly in your code. The implementation of logToServer() method should retransmit the message to the Logger Server if an acknowledge is not received within a specic timeout, given as input parameter to coordinator and participant processes when they are launched. If no acknowledge is received after three retransmissions, then the logToServer() method should throw an IOException. A skeleton of UDPLoggerClient is provided, with a constructor, three nal attributes (i.e. loggerServerPort, processId and timeout) and their corresponding getter methods. Note that the processId attribute represents the TCP port that the Coordinator/Participant is listening on.
4.3 How to Use Logger Classes
ParticipantLogger (CoordinatorLogger) class is implemented as a singleton, i.e. there is at most one instance for each Participant (Coordinator) process, and that instance can be conveniently retrieved by invoking the ParticipantLogger.getLogger() (CoordinatorLogger.getLogger()) static method. Before retrieving the singleton and invoking its public methods, the ParticipantLogger (CoordinatorLogger) must be initialised. The initialisation requires three parameters, namely the UDP port that the Logger Server is listening on, the TCP port that the Participant (Coordinator) process is listening on and the socket timeout (in milliseconds).
For example, if the Participant (Coordinator) process is listening on TCP port 12346, the Logger server is listening on UDP port 12345 and the timeout is 500 milliseconds, then the ParticipantLogger.initLogger(12345, 12346, 500) (CoordinatorLogger.initLogger(12345, 12346, 500)) static method should be invoked. Note that either using the public methods of ParticipantLogger (CoordinatorLogger) before initialising it, or initialising it more than once will throw a RuntimeException.
ParticipantLogger (CoordinatorLogger) instantiates a UDPLoggerClient object when initialised, and uses it to forward log messages to the Logger Server by invoking its logToServer() method.
4
The ParticipantLogger methods votesSent() and votesReceived() expect a List
Note that ParticipantLogger, CoordinatorLogger and Vote classes must not be modied.
5 Submission Requirements Submission checklist:
You should write your solution using Java Version 8 Update 241 (released January 14, 2020).
Your submission should include the following les:
Coordinator.java
Participant.java
UDPLoggerServer.java UDPLoggerClient.java Vote.java
Coordinator.class
Participant.class
UDPLoggerServer.class UDPLoggerClient.class Vote.class
Note that you must include any other les in your submission that you wish to rely on, and references to these les must be relative. You may assume that the current directory is in your CLASSPATH.
These les should be contained in a single zip le.
There should be no package structure to your java code; i.e. no statements in the Java source
les such as package comp2207.irc as in the IRC example.
When extracted from the zip le, all .class les should be located in the current directory.
The UDPLoggerServer class le will be executed at the Unix/Linux/DOS command line as follows:
java UDPLoggerServer hporti
Where hporti is the port number that the logger server is listening on. For example, if we want
to start the logger server listening on port 12344, then it will be executed as:
java UDPLoggerServer 12344
The Coordinator class le will be executed at the Unix/Linux/DOS command line as follows: java Coordinator hporti hlporti hpartsi htimeouti [hoptioni]
5
Where hporti is the port number that the coordinator is listening on, and hlporti is the port number that the logger server is listening on, and hpartsi is the number of participants that the coordinator expects, and [hoptioni] is a set (no duplicates) of options separated by spaces. The timeout should be used by the coordinator when waiting for a message from a participant, in order to decide whether that participant has failed. For example, if we want to start the coordinator listening on port 12345, expecting the logger server listening on port 12344, expecting 4 participants, with a timeout of 500 milliseconds and where the options are A, B and C, then it will be executed as:
java Coordinator 12345 12344 4 500 A B C
The Participant class le will be executed at the Unix/Linux/DOS command line as follows: java Participant hcporti hlporti hpporti htimeouti
Where hcporti is the port number that the coordinator is listening on, and hlporti is the port number that the logger server is listening on, hpporti is the port number that this participant will be listening on, htimeouti is a timeout in milliseconds. The timeout should be used by a participant when waiting for a message from another process, in order to decide whether that process has failed.
For example, if we want to start a participant that operates with a timeout of 500 milliseconds and that is listening on port 12346 with the coordinator listening on port 12345 and the logger server on 12344 as above, this will be executed as:
java Participant 12345 12344 12346 500
When you submit your solution, the zip le will be unpacked, the les will be checked (i.e. location of .class les, use of Java Version 8 Update 241), and they will be run with various numbers of participants with various inputs. We will test your solution both with the provided logger classes and with variants of these classes that simulate participant failures.
For example, a Shell script for a simple test where there are no failures may be:
1 #!/bin/sh 2
3 java UDPLoggerServer 12344 &
4 echo “Waiting for logger server to start…”
5 sleep 5
6 java Coordinator 12345 12344 4 500 A B &
7 echo “Waiting for coordinator to start…”
8 sleep 5
9 java Participant 12345 12344 12346 500 &
10 sleep 1
11 java Participant 12345 12344 12347 500 &
12 sleep 1
13 java Participant 12345 12344 12348 500 &
14 sleep 1
15 java Participant 12345 12344 12349 500 &
The consensus outcome for a majority vote will be one of A or B in this case because with 3 participants there will always be 2 that agree assuming all vote (no failures).
It is your responsibility to use available logger classes to accurately indicate what your system is doing.
6
6 Marking
The marking scheme is:
> 40% The protocol operates as expected, and the coordinator reports some outcome. The outcome is not necessarily correct (i.e. not all participants agree).
> 50% The protocol operates as expected and the coordinator reports the correct outcome in all cases in which there are no participant failures.
> 60% Your solution operates as above, and is robust to one participant failure.
> 70% Your solution operates as above, and is robust to any number of participant failures.
> 80% Your solution operates as above, and is robust to participants and coordinator starting in any order.
up to additional 10% Your solution correctly sends and receives UDP log messages.
7