(RFC means "request for comments". This is a brainstorm discussion on a topic I consider to be an open question with no recommended design pattern at this time.)
This is a (long) question about systems with multiple actors that are more than just command processors -- actors that have their own state machine behaviors that they work on when not receiving messages. These are actors that have overridden Actor Core.vi so they can do work independent of the directives of their caller. This is a large dump of my knowledge of the problem space and questions about best practices in this arena. If I've missed anything (because I have not had to write systems like these but once or twice in my life), please chime in to correct me.
First Situation: You have an actor to control a robot (there are various nested actors for its subsystems, but those are internal to the robot's operation so we'll ignore them and assume the main actor is coordinating all internal operations). The robot grabs a widget from a conveyor belt whenever one appears (no regular schedule). The widget is missing parts. The robot analyzes the widget, goes to a wall of available part bins, finds the missing part and adds it to the widget, then puts the widget back on the belt. Exactly which part is missing is different for each widget, and sometimes there's more than one part missing.
Commentary: This is a straightforward actor to write. I'm definitely not saying that control systems are easy to write. I am saying that the state machine for the robot is straightforward to conceive and the set of external messages is small: "widget arrives" and "stop" are about the only messages that have to be sent to the actor. It's output is likewise small, limited to things like "need to order more parts".
Second Situation: Two such robots, each with its own conveyor belt and with its own wall of part bins.
Commentary: Programming this is the same as the first... you launch two copies of the same actor, one for each robot. There's no additional complexity.
Third Situation (the interesting case): Two such robots, but grabbing widgets from the same conveyor belt and taking parts from the same wall.
Commentary: Now we have a more interesting messaging situation. The external messages remain the same, although the external system probably needs to handle the possibility of both robots sending the "order more parts" message at the same time to avoid double ordering parts. But the internal situation is massively more complex. To begin with, they need to negotiate which one will grab a given part off of the conveyor belt. This is likely easy ... if the first robot is working on a widget already, let the part go to the second robot in line -- a kind of priority ordering. But then they need to not collide when going to the wall of parts. Each robot needs to the part it needs efficiently. The exact part that each robot needs isn't known in advance, and sometimes a robot needs more than one part, so its path to the wall may involve moving along the wall before it returns to the conveyor belt.
Although it might not seem like it at first, this is a resource allocation problem, where the resource in question is "empty space". This problem is identical to problems of claiming other system resources, like exclusively using a particular DAQ channel or broadcasting on a particular frequency without others being on the same frequency. It can even be mapped to data manipulation problems, like claiming a table in a database, a file on disk, or a region of a graph data structure. Somehow these actors must coordinate their activities.
The strategies that I know of divide into two broad categories: the strategies that avoid collision and the strategies that allow collision and deal with it.
Allow Collision And Deal With It
Most famous of these strategies is the most common solution to the "two wireless devices both need to talk on the same frequency". This strategy is called the "Exponential Backoff Algorithm". Device A starts talking on the channel. If no cross-talk occurs during an initial test broadcast, it assumes everyone else heard the test broadcast and won't start talking themselves, so Device A proceeds with the main content of its message. But suppose Device B starts talking at the same time as Device A? Now both devices hear cross-talk. The solution? All other devices heard the cross-talk, so they know to stay silent until the all-clear is signaled. The two* colliding devices both stop sending and pick a random number of milliseconds to wait, and then try again. If one of them rolls a lower random number than the other, it will start broadcasting and the other will stay quiet. If they collide again, they each pick a new random number, but this time they square the range. So if the first roll was 1 through 10, the second is 1 through 100. This increases the probability that they will not roll the same number. Repeat until a collision is avoided.
If you've ever seen two people try to walk through the same door or try to dip their chips in the same bowl of salsa, you've probably seen this algorithm in action.
The list of collision detection algorithms is long. But from an actor perspective, these are quite straightforward -- the only new message that gets added to the system is "collision occurred" and then the actor deals with it. There may be some messages to work out the details between the colliding actors, but these are nicely scoped and do not represent a continuous message-passing burden on the system as a whole. You don't even have to let the robots actually physically touch -- seeing that a robot has entered a zone around another robot is the same.
But consider this: the impact sensors or vision sensors that allow one robot to know it hit another robot are just another form of message passing. The message may be passed by photons or vibrations, but it is passed. And when you don't have sensors that can see the impact and generate messages that the collision occured, you have to write that messaging system yourself. An easy example is two actors, each wanting to pick a unique identifier for itself. How does one actor "see" that another actor has picked the same identifier? You have to introduce some system where an actor announces "I picked this identifier". As soon as you start building that, your problem is now functionally equivalent to the collision avoidance algorithms.
* various amendments to this strategy handle three or more devices colliding.
Avoid The Collision Entirely
Here's where things get more interesting. To have collision avoidance (which is functionally equivalent to computing collision detection), you need some way to allocate resources among actors. And this is where the open questions start, for me. I have two actors. Is there a most efficient strategy for resource allocation? Is it the same strategy if I have three or more actors to coordinate? If there is not a general efficient strategy, what are the strategy options and what use cases would lend themselves best to which strategies? If there are two co-equal strategies, is one easier to program than another?
Here are the strategies that I know about for resource allocation:
- Central actor as resource allocator. An actor sends a reserve request to the central repository when it needs the resource. The repository responds with "yes you may use that resource" or "no, that resource is in use". Slight variant where actor sends a reserve request to the central repositiory to say "give me one of these" and central repository doesn't reply back until one becomes available.
- Central actor as resource planner. An actor sends a "flight plan" to the central repository saying "these are the resources I will need and the times I will need them". The repository replies back with an adjusted flight plan that has waits inserted into it to account for already-filed flight plans of other actors. Slight variation allows the central actor to send out "flight plan updates" to actors that are already executing their flight plan to tell them to add or remove waits from their schedules as other actors change their minds about their needs.
- Chain of command. In this model, there is no central actor. Each actor has a priority level. When an actor wants a resource, it asks the next higher priority actor for permission to take it. That actor asks the next higher priority, and so on, up to the highest priority, which says yes or no. The highest priority just takes resources as it needs them and denies requests that would get in its way. Each lower level denies requests that would get in its own way. This model allows the high-priority actor to quit and the other actors keep going.
- Ask permission from others. Very similar to the coordination of the exponential backoff algorithm mentioned above. There is no central actor. An actor announces "I want that resource" to all other actors. It waits for all other actors to reply back with "ok" and then it takes the resource. While it is waiting, it might hear an "I want that resource" from another actor. All the actors that replied with "ok" treat the resource as already allocated until some actor says "I'm done". The two (or more) actors that both said "I want that resource" have some way to resolve the problem. If all the actors share a synchronized clock, you can have the prize go to the actor that announced first, but it is often hard to have a synchronized clock between systems, so attaching a random number to the end of the "I want that resource" can serve instead. Alternatively, actors could have an assigned priority. A variation allows actors to only talk to the other actors in its immediate vicinity if the resource is something local, instead of establishing a global broadcast.
- Token ring. The first actor to start up gets all the resources. As soon as there are more actors in play, the actor starts passing all resources that it is not using to the other actors. Actors continually pass off to other actors any resource that they receive but do not currently need. When an actor gets a resource it needs, it holds onto it until it is done using it. Generally this requires some sort of hierarchy among the *resources* to avoid the Dining Philosophers deadlock problem... Suppose an actor needs resource 3 and resource 7 to do its job. Resource 7 is passed to it first. It cannot hold onto 7 but has to pass it along because it does not yet have 3. Once it has 3, then it waits until 7 comes back around. If you don't do this, you can end up with one actor holding resource 3 waiting on 7 and another holding resource 7 waiting on 3... deadlock.
- Sign-up sheet. Each resource has a sign-up sheet attached to it. When Actor Alpha wants Resource X, it announces to all the others, "I want Resource X". Actor Beta has Resource X. It adds Alpha's name to the end of the sign-up sheet. When Beta is done with X, it passes it to whichever actor's name is at the top of the sign-up sheet. If no one wants it, Beta just holds onto the resource until someone requests it. Lots less noisy than a Token Ring, but requires a broadcast mechanism, whereas the Token Ring just requires an actor to know its nearest neighbors.
- Every Resource Is An Actor. (suggested by drjdpowell) Create an actor to represent every individual resource. That resource coordinates its own interactions with every actor that wants to use it, servicing requests as needed.
- Merge actors into one. At some point, the interplay between actors becomes so complex that it is better to have just one actor in control of all the parts, making local decisions instead of trying to pretend that these are independent actors that need occassional coordination. Video games often have a single event loop to update all the parts of the model instead of having independent executing elements act on their own because assigning tasks is less intensive than trying to resolve competing requests. It's hard to merge actors that aren't on the same hardware, but you still merge the execution strategies onto a central actor, leaving only the shell of a command processor (e.g. the basic Actor Core.vi with no overrides) on the peripherals.
There are variants that combine several of these strategies, but this list covers all the basic strategies I can recall learning about. Do you know more that could be added to the list? Do you have recomendations? Pros/cons?
