# Scatter

Two-phase commit across multiple PAXOS groups.

1. The coordinator group replicates the decision to initiate the transaction.
2. The coordinator group broadcasts a transaction prepare message to the nodes of the participant groups.
3. Upon receiving the prepare message, a participant group decides whether or not to commit the proposed transaction and replicates its vote.
4. A participant group broadcasts a commit or abort message to the nodes of the coordinator group.
5. When the votes of all participant groups is known, the coordinator group replicates whether or not the transaction was committed.
6. The coordinator group broadcasts the outcome of the transaction to all participant groups.
7. Participant groups replicate the transaction outcome.
8. When a group learns that a transaction has been committed then it executes the steps of the proposed transaction, the particulars of which depend on the multi-group operation.



- Two-phase commit across paxos groups
![two-phase](scatterTwoPhase.png)

![two-phase](scatterConflict.png)


### Notes
- distributed replication plays the role of write-ahead logging to stable storage in the classic 2PC protocol

![two-phase](scatterKeys.png)

![two-phase](scatterPrimaries.png)

# Comments

OpenDHT is based on chord, and is well-known to be *horrible*, both in performance and in correctness.


- why is chord the norm rather than scatter? - daniel

- how relevant is a ring structure in a distributed storage? It is highly unscalable because of nodes failures. So I don't think this is used in any practical storage system - guowei

- High availability and linearizability consistency: These two are usually in direct conflict if network partition could happen. Though with groups, we can assume communication failure never happen. It still looks to be unrealistic. Any read of not-yet-updated data will either be unavailable or inconsistent. So I am wondering what they mean by consistency semantics and high availability. - guowei

- disappointing to see them punt on security concerns, robustness concerns, and linearizability with multi-key transactions - allen

<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
<p>
&nbsp;
# Oceanstore

- favorite part is actually the randomized algorithm for locating a nearby node containing the data
- system clearly will perform terribly for Facebook
- don't see as ever getting implemented
- hand-wavey about the encryption
