Read Repair

A read from a replicated system returns values from multiple replicas. Each replica stores a value with a timestamp. Larger timestamps are treated as newer.

Return:

• the selected value with the highest timestamp
• the indices of replicas that are stale

If multiple replicas tie for the highest timestamp, choose the lowest index.

Types

type ReplicaValue struct {
    Value     string
    Timestamp int
}

Function signature

func ReadRepair(values []ReplicaValue) (value string, repair []int)

Example

values = [
  {Value:"a", Timestamp:1},
  {Value:"b", Timestamp:3},
  {Value:"b", Timestamp:3},
  {Value:"a", Timestamp:2},
]

value  = "b"
repair = [0,3]

Replica indices 0 and 3 are stale because their timestamps are lower than 3.

Constraints

• 0 <= len(values) <= 100_000
• 0 <= Timestamp

Notes

If values is empty, return "" and nil.

This problem intentionally uses timestamps to keep the first repair problem simple. Later problems introduce version vectors to handle concurrency more honestly.

Expected complexity

O(n) time and O(k) output space.