COMPSCI 711 1 radu/2020
Assignment 1
Design and develop a faithful emulation of the Echo algorithm, extended to determine
the size of the network.
The input is a text configuration file, given via stdin, which describes the network as a weighted graph: a first paragraph for the nodes and their neighbourhoods, and a second paragraph for the arc transit times (non-normalised delays); the two paragraphs are separated by one line consisting of one single dot (.).
For example, the following configuration could describe our lecture example, with non- normalised transit times:
// node IDs and neighbourhoods
1 2 3 4 213 431 3124 .
// arc delays 1310
1 4 10
2 1 10
3 2 10 4 3 10 0 0 1
//node1hasneighbours234
// arc 1-3 delay 10 time units
//defaultdelayforunspecifiedarcs,i.e.1-2,3-1,4-1,2-3,3-4
Discarding comments, the actual contents are unsigned integer numbers, separated by whitespaces. Lines in each paragraph do not need to be sorted in any order.
Node IDs are non-zero numbers, but not necessarily in a closed range. Here they are 1, 2, 4, 3; but could as well be 10, 20, 40, 30. The first listed node is the source (initiator).
Note that each edge has two arc transit times, one for each direction. Arc transit times are fixed, but this resulting asynchronicity is enough for the purpose of this assignment.
As mentioned, the configuration transit time are not normalised. After normalisation, 10 becomes 1, and 1 becomes 0.1 (this could be the ε used in the lecture sample).
Hopefully, this commented example is enough to infer the underlying grammar of our configuration files.
The neighbours order indicates a preference order, significant for choosing the parent
among several forward tokens arriving at the same logical time (see FAQ at the end).
COMPSCI 711 2 radu/2020
The output must be written to stdout, in two paragraphs, separated by one single empty line. In the first paragraph, each output line indicates a message sent or received (delivered), containing the following items (in order):
o Time: logical time (time units from start) o Code: 1=received, 2=sent
o From: sender node
o To: receiving node (destination)
o Token: 1=forward, 2=return (one token is enough, but using two distinct tokens improves the readability)
o Payload: for forward tokens 0, for return tokens the subtree size
The second paragraph consist of one single line, containing (in order): the total logical time unnormalised, the total logical time normalised (integer division), the total number of messages, the network size.
For readability, each number should be formatted on three positions, with one extra space at the start. Additionally, the set codes should be followed by four spaces, and the received code should be preceded by four spaces.
The output should appear sorted – sufficient on the first four columns, in order.
This is the output expected for our lecture sample, assuming the preceding configuration:
time code from to tok pay
02 1210 02 1310 02 1410 1 11210 12 2310 2 12310 22 3110 22 3410 3 13110 3 13410 32 4110 4 14110
COMPSCI 711 3 radu/2020
time code from to tok pay
10 11310 10 11410 10 2 4 3 2 1 20 14321 20 2 3 2 2 2 30 13222 30 2 2 1 2 3 40 12123
404 4
10
The output format is very important, as the program will be automatically assessed by the automarker, where each space and comma counts. Stdout output must not contain anything else.
Suggestion to use stderr for any additional output that you may temporarily need, e.g. for debugging/tracing, as stderr is ignored by automarker.
Development language and platform
C#, for .NET Core 3.1.X (which is free, open source, cross-platform, and LTS).
Your program is a command-line program and must be entirely contained in one single C# source file.
Submission
For this assignment, we use the automarker:
https://www.automarker.cs.auckland.ac.nz/student.php
Submit just your C# source file, after changing its extension from .cs to .dcs.
The standard C# extension is .cs. However, the current automarker requires non- standard extensions for .NET Core programs, e.g. .dcs for C#, to differentiate these from files that require the old .NET Framework.
The required project file, .csproj, will be automatically provided by automarker, so do not worry about this.
COMPSCI 711 4 radu/2020
Program design
Our program must follow the following conventions, which encourage a faithful design, able to run on an actual distributed system with minor transformations – mainly, replacing function calls by HTTP/REST request.
Each node must be instantiated from a top-level class call Node, and the main program must be in another top-level class called Arcs.
All communications must solely occur by way of method Process (), which implements one macro-step (using a state machine design). There must be no other data flow or sharing.
All nodes are instantiated by Arcs. Nodes know the numbers (ids) of their neighbours, but do not have pointers to them. Consequently, there is no direct messaging between nodes. All messaging is relayed via Arc, and Arcs is in the best position to output traces.
The actual distributed algorithm starts by Arcs calling the Process () method of the source node indicated in the configuration, which learns this way that it is the initiator.
Ad-hoc example Left: direct messages; right: relayed messages (via Arcs)
Arcs output traces
02 xyaa 02 xzbb 1 1xyaa 12 ywcc 2 1xzbb 22 zwdd 3 1ywcc 3 1zwdd
COMPSCI 711 5 radu/2020
// public struct Message { public class Message {
public int time; public int code;
public int from; public int to;
public int tok; public int pay;
public Message (…) { … } // optional constructor
public readonly int ForwardTok = 1; // optional immutable literals // …
}
public class Node {
public Node (int self, int[] neigh) { …}
public Message[] Process (Message [] msgs) {
receive inbound messages process
returns outbound messages
} }
public class Arcs {
logical time clock
. priority queue for organising messages
public static void Main () {
read and store configuration from stdin
initialise nodes
sends and receives messages on behalf of nodes,
adding required delays, and tracing stop
} }
COMPSCI 711 6 radu/2020
FAQ
Q. How to ensure a completely predictable/deterministic execution and output trace?
What happens if node receives more than one message at the same logical time, in which order are these processed? This is critical, if a previously unexplored node receives two forward tokens at the same logical time, i.e. from two potential parents – which one is chosen as parent?
A. To make this deterministic, the messages are conceptually processed according to the sender’s position in the receiving node’s neighbourhood list (not according to their IDs).
Consider the following configuration line, where node 4 has neighbours 3 and 2:
Because of the indicated preference order, node 4 will conceptually give priority to the messages coming from node 3, over messages coming from node 1.
Q. When and how to start the emulation?
A. The emulation should start as soon as Arcs has read and parsed the configuration, and instantiated all nodes. We do not prescribe any specific way. Arcs could: send a null; send an empty array of messages, send a forward token from itself, conventionally assuming number 0 (not available to other nodes).
Q. When and how to stop the emulation?
A. A program that does not promptly stop will be considered wrong by the automarker,
even if its unclosed output trace is otherwise perfect.
(i) The system could stop when a Process () call returns an empty message list, while the message queue is also empty. Obviously, in this case, there is nothing more to do…
For example, after deciding, the initiator could return an empty list of messages, and queue should be empty at this stage.
In this scenario (i), Arcs should always scan the messages and retain the last payload (3 in the example), otherwise it won’t be able to print the last line with the actual size (4).
(ii) Alternatively, after deciding, the initiator could return one more message (possibly with a new stop token, e.g. code 3), with a payload indicating the final size (3+1=4).
In this scenario (ii), there will be two meta-messages that are not part of the actual algorithm: the wakeup message sent to the initiator, and the last stop message returned from the initiator.
Your choice here.
431