Further clarify fairness and starvation w.r.t. multiple blocking waits

[syg]

Waldemar raises the point that the line-cutting of blocking waits in WaiterList would result in starvation. That is, if one agent's blocking wait keeps cutting in line of another agent's blocking wait in WaiterList.

We could fix this by, e.g., have WaiterList items with null promises only cut ahead of those with non-null promises. I imagine that's already the intent of the following language:

Insert (W, null) into the list of waiters in WL directly before the first other entry (W, x) in the list, or to the end of the list if there is no such entry.

Perhaps all that's needed is a note. Otherwise let's spell it out fully.

[lars-t-hansen]

It's a good point and I think it's actually somewhat serious and might require more careful design. Suppose the WL for location L is [(A,P),(B,null)] where A and B are agents and P is a promise. Suppose an agent C periodically performs wake(1) on L thinking that this will cdr down L's WL. A can prevent B from ever being woken by doing a blocking wait on L - thus transforming the list into [(A,null),(A,P),(B,null)] - and re-entering the wait whenever it is woken.

The current language was not meant to avoid that. All it meant to say was that if the WL looked like this before A's wait: [(D,null),(A,P),(B,null)] then it would be transformed into [(D,null),(A,null),(A,P),(B,null)] as opposed to, say, [(A,null),(D,null),(A,P),(B,null)]. This was intended to provide some fairness in that A could not preempt D, but it does not fix Waldemar's problem.

The easy fix is to abandon the priority scheme and just put (A,null) at the end, thus bringing back the wakeup-order anomaly but that's a very modest cost, really.

A more complicated fix would be to shift the list of A entries so that we don't insert a new element but move them. At the time A waits, the last element for A in the list would be made the last element in the list (where A's wait would have been inserted in the naive order); the next-to-last takes the place of the one that was moved last; etc; and then the new (A,null) entry takes the place of the first of A's former entries. So we'd end up with [(A,null),(B,null),(A,P)].

In a cleaner spec sense this transforms the WL into a set of lists: the WL tracks waiters [A,B,A] - these are just agents and so an agent can appear multiple times - and then there are separate per-agent lists of priority, where A's is [null,P] and B's is [null]. Now we see that inserting a waiter on the WL is just appending it to the end of the first list (always) and then either to the beginning or the end of the secondary list for that agent.

The resulting wakeup order can be fairly complex IMO, so we can discuss whether it's really worth it, but spec-wise I think it would be pretty clean.

cc @waldemarhorwat

[syg]

If we try to preserve the blocking wait preemption behavior, I agree the "set of lists" mechanism is much cleaner than the in-place move. It seems analogous to my previous thought about having a separate sync WL and an async WL.

@lars-t-hansen I'm still convinced by your example that the preemption behavior for blocking waits is desired. IMO the wake up ordering in web reality would already be complex as it uses the Promise queue, so I think it's better to arrive a simple mental model for programmers to work out the ordering when in doubt than to arrive an always-simple ordering. It'd be even nicer if the programmer mental model is also the spec mechanism.

[syg]

The list-of-lists approach was written for the spec.