Multi-Version Read Repair (Vector Clocks)

A read from a replicated system can return multiple versions of a key. Each replica reports its value with a vector clock. Versions can be ordered by vector clock dominance.

Rules:

• A version dominates another if its vector clock is >= in every component and > in at least one component.
• A version is a winner if it is not dominated by any other version.
• If two winners have the same vector clock:
  • If their values are the same, keep only the one with the lowest ReplicaID.
  • If their values differ, keep the lowest ReplicaID as the winner and treat the others as stale (repair to the winner).
• A replica is stale if its version is dominated by any winner.

Return the list of winning replica IDs and the list of stale replica IDs. Both lists must be sorted ascending.

Types

type ReplicaVersion struct {
    ReplicaID int
    Value     string
    VC        []int
}

Function signature

func MultiVersionReadRepair(replicas []ReplicaVersion) (winners []int, repair []int)

Example

replicas = [
  {ID:0, Value:"a", VC:[1,0]},
  {ID:1, Value:"b", VC:[2,0]},
  {ID:2, Value:"c", VC:[1,1]},
]

winners = [1,2]
repair  = [0]

Constraints

• 0 <= len(replicas) <= 2000
• Vector clocks may differ in length; missing entries are treated as 0.

Notes

• If replicas is empty, return (nil, nil).