Page 1

ECE428 Homework 4

This assignment has 4 questions with 60 points in total. The solutions must be typed, and

submitted via Blackboard. However, the diagrams can be hand-drawn. You must acknowledge

any sources used to arrive at your solutions, other than the course materials and textbook. All

homework assignments are expected to be an individual work, so no collaborations are allowed.

Question 1: Transactions in Distributed System [25 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) (3 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) (3 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: 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 time-stamped 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.