CS 711留学生代做、代写C++设计、代做algorithm、代写C/C++编程设计

日期：2019-10-09 10:54

CS 711 1 radu/2019

Assignment 3 – v0

Assignment 3 requires one practical project: A process-based emulation of Cidon’s

distributed depth-first search algorithm, with logical time delays, extended to

determine the size of the network.

The network is bidirectional and is described by a text configuration file. Eg, the sample

network used in the lectures can be described by the following text, say config4.txt:

// string -> int dictionary

// nodes

0 8090 // net/network port 8090

1 8081 // node 1 port 8081

2 8082

3 8083

4 8084

// network arcs

- 10 // default delay (for unspecified reverse arcs)

1-3 3000

1-4 6000 // arc 1-4 delay 6000ms

2-1 1000

3-2 1000

4-3 1000

In fact, this config file describes a conceptual string-to-int dictionary, to be used by all

instances of your solution, with the following interpretations:

o Net “node” 0 is a process listening at port 8090 (more about this later).

o Node 1 is a process listening at port 8081

o Node 2 is a process listening at port 8082

o For unspecified arcs, the default static delay is 10ms (immutable).

o Arc 1-3 has a static delay of 3000ms (immutable).

o Arc 3-1 (unspecified) has a default static delay of 10ms (immutable).

Two slashes (//) introduce line comments that must be discarded, together with any

extra spaces and blank lines.

CS 711 2 radu/2019

The config file may contain comments and extra spaces or lines. Comment, blank and

empty lines must be discarded, as well as extra spaces. This could be the actual

dictionary parsed from the above sample config file.

The node and net (network abbreviated) processes must be called node.exe and

net.exe, respectively. These will be started in the following way, to ensure that stdout’s

are recorded:

set config=config4.txt

start "node1" cmd /k node.exe %config% 1 2 3 4 ^> node1.log

start "node2" cmd /k node.exe %config% 2 1 3 ^> node2.log

start "node3" cmd /k node.exe %config% 3 1 2 4 ^> node3.log

start "node4" cmd /k node.exe %config% 4 1 3 ^> node4.log

rem 2>&1

net.exe %config% > net.log

To help the markers, stderr will still be sent to the command console, but we will

duplicate the same messages to stdout.

The first command-line argument of all processes is the config file. Nodes have one or

more numerical arguments: the first is the node number, followed by adjacent node

numbers.

CS 711 3 radu/2019

We recommend that messages are bundled as strings with the following format, where

time, from, to, tok, and pay are integers (use commas between messages and single

spaces for separation):

time from to tok pay, time from to tok pay, …

Nodes (including the net “node”) should print incoming and outgoing messages using

the following formats, exactly (but extra spaces and additions allowed at the end):

Console.WriteLine($"... {Millis():F2} {ThisNode} < {from} {to} {tok} {pay}");

Console.WriteLine($"... {Millis():F2} {ThisNode} > {from} {to} {tok} {pay}");

Where Millis() is function which returns time of the day in milliseconds (or higher

precision):

Func<double> Millis = () => DateTime.Now.TimeOfDay.TotalMilliseconds;

You can write out other lines, if you wish/need so, but please do NOT write any other

lines with the same four chars prefix “… “ (three dots and one space). This convention

will be used to trace the overall message flow, and determine its consistency.

In the above WriteLine calls:

o ThisNode : the current node number, receiver or sender

o time : logical time (see appendix)

o from : sender node number

o to : target node number

o tok : token kind

o 1 = forward (assume that this include vis)

o 2 = vis (only)

o 3 = return

o pay: the payload, here the computed size (partial or total)

In our sample scenario, node numbers are in the range 0..4, where 0 is the net “node”.

CS 711 4 radu/2019

Let’s now discuss the critical roles of the net.exe process. We can also call it “network

manager” or “asynchroniser”. This critical process will intercept all messages and

forward them after the associated delays, as defined in the config file.

In other words, the conceptual message from node x -> node y will follow a longer path:

node x -> net -> node y, with a required time delay being added in the net process.

Net process 0 is started last and will start Cidon’s algorithm, by sending a first forward

message to the already started node process 1. The distributed algorithm will end after

node process 1 sends a return message to net process 0 – the payload of this last

message should contain the size of the whole network.

Thus, net process 0 plays a critical double role:

o Intercepting all node messages and ensuring their specified delays

o Acting as dummy parent for the start node 1, starting and stopping the algorithm

For consistency (and fair marking), we require that these processes (node and net) are

implemented in C# or F#, as self-hosted services, using the Nancy framework. Each

process must be completely developed in one single file. The files must be respectively

called node.cs and net.cs (C#), or node.fs and net.fs (F#). Please only use standard

libraries extant in the labs plus the Nancy libraries (no other libraries are allowed).

However you develop these, the files must be compilable using the command lines

compilers, e.g.

csc /r: Nancy.dll /r: Nancy.Hosting.Self.dll node.cs

csc /r: Nancy.dll /r: Nancy.Hosting.Self.dll net.cs

Please submit your two source files (node and net) to the university ADB assignment

dropbox, following the instructions on Canvas and ADB itself. Please ensure that your

submission is compilable and runs properly in our labs (the same environment which

will be used by the markers).

Submission deadline: Week #11 Sat 6 pm. After this deadline, submissions will be still

accepted for 4 more days, with gradually increasing penalties, of 0.5% for each hour

late.

CS 711 5 radu/2019

Appendix – Net implementation hints

One thread-safe “queue” (or priority queue), sorted on cumulated logical delays. This

ensures well controlled logical delays (small delay differences should count).

Note: In this algorithm, at any given time, there is only one active node, that holds the

forward token (only one exists) and sends out messages (one or more). To ensure

proper processing, all outgoing messages should be sent grouped in a bundle.

Warning: concurrency is possible, on Net and on each Node

Critical regions? If needed, use lock { … } ?

CS 711 6 radu/2019

Example. Consider the following scenario:

Logical time 0:

o Active node a sends out a bundle of two messages: x:0; y:0 – where numbers

indicated logical time

o Messages x:0 and y:0 are received by net and queued according to their sending

time plus their config delays, say 2 for a->b and 5 for a->d, thus: [y:5; x:2]

Logical time 2:

o Message x:2 is popped out, forwarded, and arrives at b. At this time, the net

queue contains [y:3]

o Node b receives and processes x:2, becomes the active node, and then sends out

message z:2

o Message z:2 is received by net and queued according to its sending time plus its

config delay, say 2 for b->c, thus: [y:5; z:4] (ahead of older message y)

Logical time 4:

o Message z:3 is popped out, forwarded, and arrives at c. At this time, the net

queue contains [y:5]