Read Repair

A read from a replicated system returns values from multiple replicas. Each replica stores a value with a timestamp. The client should return the value with the highest timestamp and repair any stale replicas.

Given a slice of replica values, return:

• the selected value (highest timestamp; if tied, choose the lowest index)
• the indices of replicas that are stale (timestamp < max)

Types

type ReplicaValue struct {
    Value     string
    Timestamp int
}

Function signature

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

Example

values = [{"a",1}, {"b",3}, {"b",3}, {"a",2}]
value  = "b"
repair = [0,3]

Constraints

• 0 <= len(values) <= 100000
• 0 <= Timestamp

Notes

• If values is empty, return "" and nil.