Stackless Python

Erlang is currently getting a lot of attention as a language that supports concurrent programming with a large number of simultaneous lightweight processes (or threads if you prefer). But there are few reasons its ~sibling - Stackless Python - should get less attention, some preliminary benchmarks support that.

During grad school some students and I used Stackless Python in combination with MPI to create a simple simulation of a large number of players and NPCs in multiplayer games on a cluster. The game world was divided onto machines in the cluster and on each machine a few thousand tasklets (also called microthreads) each representing individual players and NPCs ran. When they ran into each other they communicated using channels. When players or NPCs came to the boundary of the game world we sent the serialized state of the tasklet representing the player or NPC using MPI messages to the neighbor CPU world.

Stackless Python turned out to be a very nice language to code in, and in fact the students and I tried to start a company providing microsimulation consulting services using it. Unfortunately such services turned out to be of much less demand than anticipated so we had to stop our efforts in that direction. But that wasn't Stackless' fault, in fact I would recommend having a look at Stackless Python if you consider doing microsimulation.

Dining Philosophers and Quarreling Kids

Concurrency in general and in particular making concurrent processes smoothly share resources are hard programming problems. The classic problem illustrating concurrency is the dining philosophers problem where the shared resources are forks. The problems the philosophers can get include resource starvation, deadlock and livelock. (Note: dining philosophers has a slight resemblence of the game of musical chairs)

The quarreling kids problem
A much less classic but way more realistic concurrency problem is the quarreling kids problem, i.e. when providing N resources (e.g. food or toys) to M kids (who might be either spoiled, tired or hungry) several situations can occur:

1. N < M
• Typical result: Quarreling kids since some kids doesn't get any resources
  
2. N ≥ M and N mod M != 0
   
• Typical result: Quarreling kids since resources are unevenly distributed
  
3. N &ge M and N mod M == 0
• Can go smoothly, but can lead to quarreling kids if:
• the resources differ, e.g. in type, size, shape or color
  
• the order/speed resources are distributed in
• the resources doesn't match the recipient's expectations (stereotypical: the girl doesn't get the pink colored and the boy doesn't get the blue colored)

Solutions to the quarreling kids problem?
An obvious solution approach could be to let the kids select resources themselves, but that will typically make the kids that selects first happy and the rest less happy and start quarreling, and if the kids select resources at the same time that also typically leads to quarreling during selection process.
A second approach is to provide non-discrete resources that are of infinite divisible nature, but that has unfortunately practical lower boundaries.
A third approach is to provide personalized (heterogeneous) resources, so every kids gets what they anticipate, but this requires both detailed knowledge of each kids preference and is impractical due to either limited resource budget, limited resource availability or possibly other reasons (e.g. nutrition?).

So what might work?

A) Provide homogeneous resources (where N ≥ M and N mod M == 0) could work, this way the kids are likely to feel that they are fairly treated.

But what if there are fewer resources than kids (N < M)

B) Provide resources that supports and encourages communication and interaction, i.e. where sharing pays off (e.g. in a more or less continuous sport like soccer or a turn-based board game)

This sounds awfully politically correct, what is the point?

The point is that solving the quarreling kids problem most likely requires solutions that:

1. Avoids resource sharing by having dedicated resources to each kid (e.g. a pair of skates each), like in A above, or
   
2. Provides resources that are being competed for under a set of communicated and agreed-upon cooperative rules as in soccer, or waited for under as set of cooperative rules in a turn-based board game, like in B above. (Without cooperation quarreling about resources will occur)
   

From a programming perspective, the quarreling kids (processes) problem with dedicated resources don't have any sharing problems, and can entirely avoid complex synchronization mechanisms (e.g. locks and mutexes), communication between the kids (processes) are done using speech (messages). This approach is similar to message-based parallelism such as using (asyncronous) messages in MPI and Erlang or channels in Stackless Python.


But what is the computational analogy for solution 2?