What is this pattern/algo called? Getting a random order of subscribers to an event that only one can react to at a time

Question

I've got a problem where I have an event publisher in c# serving up a global resource to a bunch of subscribers. The resource is a rival good, so it is possible that there won't be enough of it for all the consumers.

The model to imagine is a shipment of ingredients arriving at a market. A number of chefs are waiting for each ingredient and must decide whether to buy some of each as each is served up. The chefs agree that everyone should have a shot at each ingredient, and they don't want a race for each item, so they decide some kind of priority system should exist.

1) Is there a name for this kind of scenario?

2) What is a good way to implement this in a fair way, so each subscriber has an equal chance of getting the ingredient? Keep in mind that the decision on whether to ask for the resource is dependent on the subscriber.

3) Note that priority does not necessitate fixed priority. If you had a dice roll before each event, you could create an order each time. You could also precalculate this. Are there any drawbacks to such a solution?

Anyway, this isn't a homework question. Just wondering if someone has seen this or is able to cast a common solution into a form that solves this.

Answer 1

1) Is there a name for this kind of scenario?

Yes, it is called Round-robin (if I got it correctly)

2) What is a good way to implement this in a fair way, so each subscriber has an equal chance of getting the ingredient?

The more complex the system, the easier you should make a solution, KISS works really well here. Implement a round-robin algorithm.

3) Note that priority does not necessitate fixed priority. If you had a dice roll before each event, you could create an order each time. You could also recalculate this. Are there any drawbacks to such a solution?

This problem has been around for many years in large scalable systems and networking (for example see this thread). People tried many things, but unless you really know what you doing, use a simple one-shot-each-in-a-round strategy.

Round robin is not perfect and definitely has its own drawbacks, but it is also the easiest solution.

Answer 2

Sounds like a draft system of sorts. In some predetermined order, all subscribers are given a right of acceptance or refusal of the resource until the resource is fully leveraged. The trick is how to determine that order.

If this were my project, I think I'd start simple. Start with the first subscriber who subscribed, and proceed through the list in that order until the resource is fully leveraged. Then, as additional resources become available, the first subscriber who did not get to choose (because you ran out of resource) gets right of first refusal, and it continues from there. When you reach the end, cycle back around to the start. This is a good model to use when there are a lot of batches of resource, just not quite enough of each to go around. The chef's ingredient model would work well with this system; the first chef who shows up that day gets first pick, and so on around the kitchen, and if a chef gets left out, no worries, he'll get a shot at the next batch.

Another possible method is order-independent. Ask all subscribers whether they want a particular resource. If there are more who want it than there are available resources, put all subscribers' names into a hat and choose X of them; they get the resource. The ones who do not get the resource keep their names in that hat, thus giving them an extra chance to get the next resource. This is the better model to use when batches of resources are small and most or all are highly desirable, to avoid the last subscriber having to wait forever to get the chance at something good. The WoW loot system probably works somewhat like this (with the simplification that all party members "opt-in" for each item; I don't play WoW so I've never seen the loot system work).