Due: Tuesday, March 5, 2024 at 6:30pm
Consider a high-level protocol for supporting multikey transactions on top of the partitioned key-value store, where a transaction can access keys that are assigned to different groups. The protocol is based on two-phase commit using locks, as discussed in lecture. By default, assume a version of the protocol where a transaction that attempts to acquire a lock that is already held immediately aborts.
Each problem is worth 10 points.
Suppose we "optimize" the protocol by removing two-phase commit entirely. Instead, the coordinating group simply executes the constituent operations separately, collects their results, and when they are all done, sends them back to the client. (In lecture, this is what we called the "straw proposal".)
Give an example of an execution that violates linearizability. In 1-2 sentences, explain why your execution is not linearizable.
Suppose we "simplify" the protocol by removing the part that aborts a transaction that tries to acquire a lock that is already held. (And suppose we do not add any other way to detect or avoid deadlock.)
Give an example execution that deadlocks forever. In other words, there is at least one transaction which is guaranteed never to finish executing, even if there are no failures from now on.
Once a participant group has received and acknowledged the coordinator's decision about a transaction, the participant is done with its role in that transaction and can move on. For example, it could then reconfigure to a new configuration where it no longer owns the relevant data for the transaction.
Suppose that the participant's acknowledgment gets dropped. The coordinator retransmits the decision (commit/abort), but the participant has already reconfigured to a new configuration and no longer holds the relevant data.
Explain how the participant can safely respond to the retransmitted coordinator decision message so that the coordinator is not blocked forever.
In class, we discussed a version of the protocol where reconfigurations cannot happen "in the middle" of a transaction. (In other words, a group that is currently participating in or coordinating a transaction does not immediately reconfigure, but waits until the transaction is complete before reconfiguring.)
Suppose we "optimize" the protocol by allowing reconfigurations in the middle of a transaction, but we do this in a very naive way, where we simply don't change any of the transactional logic nor the reconfiguration logic.
Describe at a high level an execution where the system either violates linearizability or deadlocks.
(Hint: Reconfigurations move data. Transactions write data. Move the data out from under a pending write.)