CSE 552 Spring 2019 Problem Set 2

Due Friday, May 10 at 5pm

Problem 1
On page 1, the Corfu paper highlights "enabling new designs that are impractical on disk or RAM infrastructure." Is Corfu sensible if its backing store is disk storage instead of flash? Why or why not? Is Corfu sensible if its backing store is RAM storage instead of flash? (ignore durability; assume the RAM is battery-backed)? Why or why not?
Problem 2
When implementing a trusted log with TrInc, you have the choice of assigning semantic meaning to counters or not assigning semantic meaning. An example of assigning semantic meaning is (as A2M does) to say that, in a log representing COMMIT messages sent by a node, the first $x$ bits of the log entry number represent the view number and the remaining $y$ bits represent the command sequence number. An example of not assigning semantic meaning is just having the $n$th message in the log assigned counter value $n$.

Give one advantage and one disadvantage to assigning semantic meaning to counter values.
Problem 3
In Bitcoin, a transaction can be invalid for various reasons, including representing an attempt to spend a unit of currency a second time. Miners check validity of transactions before putting them on the chain, and clients refuse to accept blocks that contain invalid transactions. Why do they do this, instead of just treating such transactions as no-ops during execution?
Problem 4
On page 9, the Chord paper says: "Since the number of queries handled by a node is roughly proportional to the total identifier space covered by that node, the worst-case number of queries handled by a node does not change."

What important assumption is embedded in this assertion that's often false in real workloads? What's a more reasonable assumption, and how do you predict it would affect a Chord deployment?