COMPSCI 711 1 radu/2020
Assignment 3
Assignment 1 required the design and develop a faithful sequential emulation of the Echo algorithm, based on classical function calls (no real distribution required), extended
to determine the size of the network.
Assignment 3 requires two sequential versions of Assignment 1, still based on functions calls (no real distribution required), without the size extension, and with the following additions:
1. EchoLamport = Echo plus Lamport time
2. EchoLamportMoney = Echo plus Lamport time and Money Count
A#3.1 EchoLamport
The Message object is right extended with a new integer component, lamport, that
indicates the Lamport time.
Lamport time is printed as a new rightmost column, after all previous message components. Lamport time must be properly determined by the Nodes, without any interference from Arcs. For A#3.1, the pay will be zero on all messages.
In contrast with A#1, in this assignment, Echo messages are printed by Node’s themselves, NOT by Arcs. Note that Arcs should NOT bother about the local Lamport time at the receiving Node – that would be logical mistake!
As an extension of the textbook Lamport clock, all messages received (respectively sent) at the same time by a given Node have the same Lamport time.
Node formulas
o When receiving messages mi:
o Before sending messages mj:
lamport = max ( lamport, max (mi.lamport) ) + 1
lamport = lamport + 1 mj.lamport = lamport
COMPSCI 711 2 radu/2020
Left: A#1 output for test #1, where pay=0 (NOT Size)
Right: A#3.1 output for test #1, with pay=0, and appended Lamport times
02 02 02 1 12 2 22 22 3
3 32 4
10
10
10 2
20
20 2
30
30 2
40
40 4
1210 1310 1410
11210 2310 12310 3110 3410 13110 13410 4110
02 02 02 1 12 2 22 22 3
3
12101 13101 14101
112102 23103 123104 31105 34105 131106 134106 41107 141108 113106 114108 4 3209 1 4 32010 3 22011 1 3 22012 2 12013 1 2 12014
10 0
32 14110 4 11310 10 11410 10
4 320 10
1 4 320 20
3 220 20
1 3 220 30
2 120 30
1 2 120 40
10 0
40 4
2 2 2
COMPSCI 711 3 radu/2020
A#3.2 EchoLamportMoney
The Message type is further extended with a new token, TokSnap=9, that indicates an account request or response.
The Node constructor has four additional parameters:
• amount: the initial amount in the node’s account;
• fwd_pay: the amount transferred with each forward token (as pay);
• ret_pay: the amount transferred with each return token (as pay);
• snap_lamport: the Lamport time for taking the snapshot.
These values come from an extended config file, remain fixed for the duration of the algorithm, and are the same for all nodes. The first non-comment non-empty line contains the above four parameters, in the given order:
After the normal completion of Echo, Arcs prints a blank line and queries the Nodes to report their amounts, using TokSnap. The Node responses are printed, in the config node order (cf. complete output on next page).
At the end, Arcs prints again a blank line and a summary line, includes the snap grand total (which hopefully did not change):
In this part, we use a slightly simplified version of the textbook MoneyCount, based on Lamport clock, where TokReturn is also a marker that indicates the end of the Echo message flow. After this, no other Echo specific messages can arrive, only Arcs will send a TokSnap, to report the amount that was available at the given snap_lamport time.
// amount fwd_pay ret_pay snap_lamport 100 10 20 5
… nodes
nodes-count init-amount fwd_pay ret_pay total-init-amount total-snap-amount snap_lamport
COMPSCI 711 4 radu/2020
A#3.2 output for test #1:
02 02 02 1 12 2 22 22 3
3 32 4
10
10
10 2
20
20 2
30
30 2
40
41 2
41 2
41 2
41 2
4100
121101 131101 141101
1121102 231103 1231104 311105 341105 1311106 1341106 411107 1411108
1 1
1 1 1
131106 141108 432209 4 3 22010 3 2 22011 3 2 22012 2 1 22013 2 1 22014
1 0 98014 20910013 4091209 30910011
10 20400400 5
Note: 4*100 = 400 = 400 = 80+100+120+100