Anti-Entropy Reconciliation

Two replicas exchange state during anti-entropy. For each key, you need to:

• Decide what vector-clock reconciliation says (A wins, B wins, conflict, or equal).
• Decide what last-write-wins (LWW) would choose based on timestamps.

Vector clock rules:

• A dominates B if A.VC[i] >= B.VC[i] for all i and at least one >.
• If A dominates B -> VCAction = "A"
• If B dominates A -> VCAction = "B"
• If equal -> VCAction = "equal"
• Otherwise -> VCAction = "conflict"

LWW rule:

• Higher timestamp wins.
• If timestamps tie, return "equal" if values match, otherwise prefer "A".

Return results for all keys (union of A and B), sorted by key.

Types

type Version struct {
    Value     string
    Timestamp int
    VC        []int
}

type Item struct {
    Key     string
    Version Version
}

type Reconcile struct {
    Key      string
    VCAction string // "A", "B", "equal", "conflict"
    LWW      string // "A", "B", "equal"
}

Function signature

func ReconcileKeys(a, b []Item) []Reconcile

Example

a: key "k" VC [2,0] ts 5
b: key "k" VC [1,1] ts 6

VCAction = conflict
LWW = "B"

Constraints

• 0 <= len(a), len(b) <= 100000
• Vector clocks may differ in length; missing entries are treated as 0.

Notes

• Missing keys are treated as version {VC: all zeros, Timestamp: -1, Value:""}.