Causal Broadcast Delivery Order

You are implementing a causal broadcast receiver. Messages arrive in a buffer out of order. Each message has a sender index and a vector clock.

A message from sender s is deliverable if:

• msg.Clock[s] == local[s] + 1
• For all i != s, msg.Clock[i] <= local[i]

When you deliver a message, update the local clock element-wise: local[i] = max(local[i], msg.Clock[i]) for all i.

Repeatedly deliver any deliverable messages until no more progress can be made. If multiple messages are deliverable at the same time, deliver the lowest index first.

Return the list of message indices (from the input slice) in the order they are delivered.

Types

type Message struct {
    Sender int
    Clock  []int
}

Function signature

func CausalDeliverOrder(local []int, msgs []Message) []int

Example

local = [0,0]
msgs  = [
  {Sender:0, Clock:[1,0]},
  {Sender:1, Clock:[1,1]},
  {Sender:0, Clock:[2,1]},
]
output = [0,1,2]

Constraints

• 0 <= len(msgs) <= 2000
• 1 <= len(local) == len(msg.Clock) <= 50
• 0 <= Sender < len(local)
• 0 <= Clock[i] <= 1_000_000

Notes

• Messages that never become deliverable are ignored.