辅导案例-COMPSCI 711 1-Assignment 1

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
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 // node 1 has neighbours 2 3 4
2 1 3
4 3 1
3 1 2 4
.
// arc delays
1 3 10 // arc 1-3 delay 10 time units
1 4 10
2 1 10
3 2 10
4 3 10
0 0 1 // default delay for unspecified arcs, 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).
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).
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.
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
0 2 1 2 1 0
0 2 1 3 1 0
0 2 1 4 1 0
1 1 1 2 1 0
1 2 2 3 1 0
2 1 2 3 1 0
2 2 3 1 1 0
2 2 3 4 1 0
3 1 3 1 1 0
3 1 3 4 1 0
3 2 4 1 1 0
4 1 4 1 1 0


COMPSCI 711 3 radu/2020
time code from to tok pay
10 1 1 3 1 0
10 1 1 4 1 0
10 2 4 3 2 1
20 1 4 3 2 1
20 2 3 2 2 2
30 1 3 2 2 2
30 2 2 1 2 3
40 1 2 1 2 3

40 4 10 4
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
0 2 x y a a
0 2 x z b b
1 1 x y a a
1 2 y w c c
2 1 x z b b
2 2 z w d d
3 1 y w c c
3 1 z w d d

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:
4 3 1
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.
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468