Further Work
Handling Stale Reads
Currently, Donut can detect stale reads but has no mechanism for alleviating stale reads. Several concurrent writes to the same key can leave that key in an inconsistent state between replicas.
For example, suppose that R = 3 (keeping three replicas at the service level). Two or more concurrent writes may begin but can fail before writing to all R replicas or the writes can interleave. Both cases potentially could leave the R replicas in three different states, v (data before the writes), v’ (data from one writer) and v’’ (data from another writer). In this case, a consensus about the current value does not exist, preventing Donut from providing future successful reads of the value.
One solution to interleaving writes is utilizing a deterministic ordering of writes to the replicas. For example, write to the hashed key k, then k + i * K / R … k + (R – 1) * K / R, where i is the ith replica. Ordering writes allows Donut to guess at the most recently agreed upon consensus. The middle key in the order of writes will be the last key to have successfully written to over half of the R nodes. In a stale state when R = 3, the first node is the most recently written, the second is the most recently written with a consensus, and the third is the only write that completed writing to all nodes.
Ordering client level replication requires the puts to be completed serially, effectively tripling the time to write.
Once a stale read is detected, it can be correct by the request handler retrying the write request. Even with the proposed write order above, the procedure to get for a conflicted key should return a notification identifying that corrective action must be taken to bring the key into a stable, non-stale state.
Byzantine Fault Tolerance
In researching the direction the Donut, we began to address the problem of byzantine fault tolerance and transient inconsistencies of finger tables (or dynamism). Chord inherently relies on the predecessor of a key to correctly return the final successor. In several of the papers we perused, the common fix is to implement a routing mechanism that ensures multiple paths to reach each node. Therefore, to implement byzantine fault tolerance Donut would most likely need to switch its overlay network from Chord to a more robust solution such as Kademlia or Inverse de Bruijn overlay network8.