辅导案例-COMPSCI 711 1-Assignment 3
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: lamport = max ( lamport, max (mi.lamport) ) + 1 o Before sending messages mj: 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 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 10 1 1 3 1 0 10 1 1 4 1 0 10 2 4 3 2 0 20 1 4 3 2 0 20 2 3 2 2 0 30 1 3 2 2 0 30 2 2 1 2 0 40 1 2 1 2 0 40 4 10 0 0 2 1 2 1 0 1 0 2 1 3 1 0 1 0 2 1 4 1 0 1 1 1 1 2 1 0 2 1 2 2 3 1 0 3 2 1 2 3 1 0 4 2 2 3 1 1 0 5 2 2 3 4 1 0 5 3 1 3 1 1 0 6 3 1 3 4 1 0 6 3 2 4 1 1 0 7 4 1 4 1 1 0 8 10 1 1 3 1 0 6 10 1 1 4 1 0 8 10 2 4 3 2 0 9 20 1 4 3 2 0 10 20 2 3 2 2 0 11 30 1 3 2 2 0 12 30 2 2 1 2 0 13 40 1 2 1 2 0 14 40 4 10 0 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: // amount fwd_pay ret_pay snap_lamport 100 10 20 5 ... nodes 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): nodes-count init-amount fwd_pay ret_pay total-init-amount total-snap-amount snap_lamport 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. COMPSCI 711 4 radu/2020 A#3.2 output for test #1: 0 2 1 2 1 10 1 0 2 1 3 1 10 1 0 2 1 4 1 10 1 1 1 1 2 1 10 2 1 2 2 3 1 10 3 2 1 2 3 1 10 4 2 2 3 1 1 10 5 2 2 3 4 1 10 5 3 1 3 1 1 10 6 3 1 3 4 1 10 6 3 2 4 1 1 10 7 4 1 4 1 1 10 8 10 1 1 3 1 10 6 10 1 1 4 1 10 8 10 2 4 3 2 20 9 20 1 4 3 2 20 10 20 2 3 2 2 20 11 30 1 3 2 2 20 12 30 2 2 1 2 20 13 40 1 2 1 2 20 14 41 2 1 0 9 80 14 41 2 2 0 9 100 13 41 2 4 0 9 120 9 41 2 3 0 9 100 11 4 100 10 20 400 400 5 Note: 4*100 = 400 = 400 = 80+100+120+100