Description
Question 1: Transactions in Distributed System [23 points]
Consider the following interleaving of three transactions T1, T2 and T3, where the reads and
writes to variables are explicitly labeled. The lowercase variables are local to each transaction.
T1 T2 T3
1: x = read(A)
2: z = read(D)
3: w = read(C)
4: write(B, w+2)
5: y = read(B)
6: write(C, x+y)
7: write(A, z+1)
8: write(E, z-1)
9: write(D, w-2)
(a) (3 points) Identify all conflicts among the interleaved transactions. For instance, you can
specify the pairs of operation numbers.
(b) (2 points) Consider the following interleaving of just two transactions T1 and T2 that
follows the same ordering as the full interleaving shown above, i.e.:
T1 T2
x = read(A) z = read(D)
y = read(B)
write(C, x+y)
write(A, z+1)
write(E, z+1)
Is this interleaving serially equivalent, and why or why not?
(c) (3 points) Consider now part (b) with interleaving just T1 and T3, and then also with
interleaving just T2 and T3. Are these other interleavings serially equivalent, and again,
why or why not?
(d) (2 points) Let the local variables be initialized to A = 1, B = 2, C = 3, D = 4, and E = 5.
What are the final values of these variables after running T1, T2, T3 after the full 3- transaction interleaving given in part (a)?
(e) (3 points) Now consider all six possible serial interleavings of T1, T2, and T3,i.e., T1-T2- T3, T2-T3-T1, T1-T3-T2 and so forth. For each such interleaving, compute the final
value of variables A, B, C, D, and E with the same initial values as in part (d).
(f) (2 points) Explain how you can tell that a given interleaving is not serially equivalent
without doing the computations as you did in the previous parts above.
Page 2
(g) (2 points) How could the serially non-equivalent interleaving be prevented using a strict
two-phase locking with reader/writer locks?
(h) (2 points) How could the serially non-equivalent interleaving be prevented using
timestamps concurrency, if T1, T2, T3 have timestamps 1, 2, and 3, respectively?
(i) (4 points) Write down a serially equivalent execution of T1, T2, T3 where all three
transactions overlap, i.e., there is a point in time when each of T1, T2, and T3 have
executed at least one operation, but none of the transactions have yet completed.
Explain why it guarantees to be serially equivalent.
Question 2: Bitcoin [10 points]
Consider a Bitcoin network with N = 100 nodes. Let us model the propagation of a newly mined
block assuming a simplified model that disregards several complexities of the actual protocol.
Thus, at time t, there are Nt nodes that have a copy of the block, and N0 = 1. Each node picks at
random another node to send the block to (in a real Bitcoin network, the nodes only send blocks
to random neighbors). The node already has the block with the probability (Nt −1)/(N −1), so it
does not have the block with the probability (N −Nt)/(N −1). Therefore, the expected number of
nodes that receive the block are Nt(N − Nt)/(N − 1). This can be described using the recurrence:
Nt+1 = ⌊Nt + Nt(N − Nt)/(N − 1)⌋
(a) (3 points) Starting with N0 = 1, how many rounds are required until all nodes receive the
block?
(b) (5 points) Calculate the probability that a chain split occurs. In each round, each node
which has not yet received the block will mine a conflicting block with the probability
1/(600 × N). You can use a simulation to calculate this probability, in which case make
sure to include the simulation code in your answer, and use enough trials to get the
accurate estimate.
(c) (2 points) Unrelated to above, find a number n such that echo NETID n | sha256sum
results in string with at least 5 leading zeros assuming your own NETID. For example,
$ echo nikita 90242 | sha256sum
00000b8556ab757a1a7a6a3ab4b43ff0045975e439593b98a8281f244ab4a772 –
Question 3: Banking Transactions [7 points]
Consider a bank processing financial transactions. There are two types of transactions: (i)
DEPOSIT account amount, which adds the amount to the account balance, and (ii) WITHDRAW
account amount, which subtracts the amount from the account balance. Each transaction also
has a consistency check where the transaction is aborted, provided that at the end of the
transaction any account balance would become negative.
Consider the following transactions:
T1: DEPOSIT A 30; DEPOSIT B 30; DEPOSIT C 50
T2: WITHDRAW A 10; DEPOSIT B 10; WITHDRAW C 60
T3: WITHDRAW A 30; WITHDRAW C 10
T4: WITHDRAW B 40; WITHDRAW C 10
(a) (4 points) If the transactions are executed serially in the order T1, T2, T3, then T4,
which of them will be committed and which will be aborted?
(b) (3 points) What are the final balances of accounts A, B, and C?
Page 3
Question 4: Understanding Paxos [22 points]
Below are the lists of 128 nodes and their 32-bit ID’s specified in hexadecimal and decimal
formats; the ID’s can be also downloaded as JSON at:
https://courses.grainger.illinois.edu/cs425/fa2021/assets/hw/chord-ids.json
Hexadecimal:
0271f7e5 051c3474 06fd9230 077e9532 0874e37d 09da6a01 0b14eab9 0d3671ea
0d8ea9bb 1452f156 154e3073 16632b1c 1b004f11 1cdf7c10 1d0fcd17 252c7750
2949d3af 29904e42 2d8f8345 2f0bb425 2fdf22c5 36a153cf 378aa66f 38c7f02c
3b403605 3f6462cd 414dd380 417e4d3a 4241cc88 42cd3bda 449cf8b1 4673c47e
46c2b3ce 4aa139c4 4b2dd547 4d4a537f 4e78adba 4e94ec32 4ffbf451 5252d6bd
53b97550 54cf8e1a 5c3477de 5d0a981c 5ddd7d7e 5e7f885d 601e02e3 62c2a9e0
66cdadff 673a8811 6890c79a 690ca3be 6927e4cf 69d971bc 6b4f81af 6bd7973a
6f0f09f9 70be1b30 73c68a3e 746e0df2 75590e12 78b8991f 78dc974c 791b40d1
81076d4a 81852191 82b4544c 87828ed1 8826367a 8a0d6bc7 8a7dc915 8b8a10d3
8ef06a66 8fa97eaa 9058438b 96fe0b06 9a437b40 9b83586a 9e887088 9ea42a42
9eea232f 9eef19e9 9fb56c3f a18e07c6 a20af51f a3a7ddc0 a6160a54 a81593c0
ace69076 b098241c b2ae3134 b4135d63 b7ba8f93 b94919c8 ba052703 ba1342d0
bc6600c2 bd0a2417 bf015ef4 c8289ed2 cc484247 ccc15960 cdf675e0 d0a3916a
d1d6a00e d38e2a77 d53d73bc d690274a d8084341 db1778be dc579a99 dcf3ae76
df41085f df5db463 e24cf6c3 e2c969b2 e58813f8 e8d724e2 ec838ca1 ee0d25c7
efdc2e2c f1ca7e2a f2d51880 f3f4eca9 f5fefe85 f63c195a fd39eaa5 feecd1d5
Decimal:
41023461 85734516 117281328 125736242 141878141 165308929 185920185 221671914
227453371 340980054 357445747 375597852 453005073 484408336 487574807 623671120
692704175 697323074 764379973 789296165 803152581 916542415 931833455 952627244
994063877 1063543501 1095619456 1098796346 1111608456 1120746458 1151137969 1181992062
1187165134 1252080068 1261294919 1296716671 1316531642 1318382642 1341912145 1381160637
1404663120 1422888474 1546942430 1560975388 1574796670 1585416285 1612579555 1656924640
1724755455 1731889169 1754318746 1762436030 1764222159 1775858108 1800372655 1809291066
1863256569 1891506992 1942391358 1953369586 1968770578 2025363743 2027722572 2031829201
2164747594 2172985745 2192856140 2273480401 2284205690 2316135367 2323499285 2341081299
2398120550 2410249898 2421703563 2533231366 2588113728 2609076330 2659741832 2661558850
2666144559 2666469865 2679467071 2710439878 2718627103 2745687488 2786462292 2819986368
2900791414 2962760732 2997760308 3021167971 3082456979 3108575688 3120899843 3121824464
3160801474 3171558423 3204538100 3358105298 3427287623 3435223392 3455481312 3500380522
3520503822 3549309559 3577574332 3599771466 3624420161 3675748542 3696728729 3706957430
3745581151 3747460195 3796694723 3804850610 3850900472 3906413794 3968044193 3993839047
4024184364 4056579626 4074051712 4092914857 4127129221 4131133786 4248431269 4276933077
(a) (9 points) List the fingers of the following three nodes:
484408336 (0x1cdf7c10), 1095619456 (0x414dd380) and 3500380522 (0xd0a3916a).
(b) (1 point) How many distinct fingers would each node have, if all nodes were equally
spaced?
(c) (2 points) Which of the three nodes in part (a) above will have stored the most keys, on
expectation? Which node will store the fewest?
(d) (5 points) List the set of nodes that will be contacted if the node 3500380522
(0xd0a3916a) searches for the key 0x12345678?
(e) (5 points) Suppose that a power outage took out all nodes with ids that are a perfect
multiple of 3, and no stabilization has been run. What nodes would be contacted by the
same search as in part (d)? When the Chord routing algorithm encounters a node that
has failed, it tries using the next smallest finger entry, and so forth, until it finds one that
is alive. If this does not work, it will use its successor, and then the successor’s
successor, and so on.
Page 4
Question 4: More Transactions in Distributed Systems [18 points]
Consider these two transactions:
T1: read A; write B; write A; read C; write E
T2: read C; write D; read A; read E; write B
(a) (4 points) Write a non-serial interleaving of T1 and T2 that would be feasible using the
strict two-phase locking with reader/writer locks.
(b) (4 points) Write down a partial interleaving of T1 and T2 that would lead to a deadlock, if
the strict two-phase locking with reader/writer locks are used. State what lock and in
which mode is being requested by each transaction.
(c) (2 points) Write down interleaving of T1 and T2 that is serially equivalent, but otherwise
impossible with the strict two-phase locking (assuming reader/writer locks). Explain, why
it is impossible with the strict two-phase locking.
(d) (4 points) Write down a (potentially partial) interleaving of T1 and T2 that would cause
T1 to be aborted, if timestamped ordering were used. Assume that T1 and T2 have the
transaction timestamps 1 and 2, respectively, show how the timestamps are updated.
Explain, why the abort happens.
(e) (4 points) Write down a non-serial interleaving of T1 and T2 that could happen if the
timestamped ordering were used, where both T1 and T2 successfully commit. T1 and
T2 should have the transaction timestamps 1 and 2, respectively. Show how the
timestamps are updated during the transaction execution.
