Fencing Tokens

Fencing tokens prevent stale leaders from performing writes after losing a lock. Each lock grant produces a monotonically increasing token per resource. An operation is valid only if it carries the latest token for that resource.

You are given a sequence of events:

• grant: a lock grant with a token
• op: a write operation carrying a token

Rules:

• Track the latest token per resource from grant events.
• An op is accepted if its token equals the latest token for that resource.
• Otherwise it is rejected.

Return a slice of booleans for each op event, in order.

Types

type Event struct {
    Kind     string // "grant" or "op"
    Resource string
    Client   int
    Token    int
}

Function signature

func FencingDecisions(events []Event) []bool

Example

[grant r1 t1, op r1 t1, op r1 t0, grant r1 t2, op r1 t2]
=> [true, false, true]

Constraints

• 0 <= len(events) <= 100000
• Token >= 0

Notes

• If an op arrives before any grant for its resource, it is rejected.