Actor Tree vs Network Routing [Branch of "Classifying Actor Messages by their Intent" thread]

[drjdpowell]

Daklu wrote (in the original post):

My theory is benign messages can safely violate the hierarchical message tree without risking race conditions, deadlocks, or any of the other bugaboos that make concurrency hard (since no important functional decisions are made based upon the message.)

Hi Daklu.  Just thought I'd point out that a "message tree" is not an assumed standard of "actors".  That's a specialization you (and AQ's AF) are using.  Actors have been used in telecomunication systems, for example, where the extra network hops involved in routing up and down a tree would be unacceptable, even for "control" messages, and "race conditions" and the like must be handled in other ways.  Does your control/benign division have meaning beyond the message tree assumption?

-- James

[AristosQueue (NI)]

James:

I'd like your feedback on the following perspective.

Theory: The actor tree is more fundamental insofar as it underlies the network layer.

Simplifying greatly: A packet arrives at a machine. The machine checks its routing table. If it knows where to route it, it sends it there. If it doesn't, it passes the packet along to a more central node, i.e., a gateway. Once a path is found, messages may come back down from the gateway so that routing tables may get updated to reflect a new, more direct path. We also have DNS servers, which is essentially sending a packet up to a central machine and getting back from that machine "here is a way to route directly to the machine you're looking for."

Both the basic routing and the DNS lookup are essentially "start with a tree and then allow messages that create direct cross connections within the tree for performance." The actor tree in the AF allows an actor to send a message to a child that says "here, this is the queue for some other actor in the system that you do not have direct contact with." That is equivalent to updating the routing tables and updating the DNS tables so that messages no longer have to bounce up to the central server.

But the tree itself is still preserved -- physical connections between machines do not get changed by these packets, so even though a system may think, "Now I am sending up to the DNS Server, now I am sending to the machine directly", that's just an updated viewpoint -- in reality, packets still switch through the system from edge-of-network machines through their gateways, up to ISPs, across the big links, and back down again to some other edge-of-network machine. And along the way, the packets are updated in various ways to update TTL, aliasing, and other information, even though what we think of as the real packet contents are unchanged.

From that point of view, starting with the AF tree and then allowing actors to send out connections is exactly analagous to the setup used by networks for communication. And although I've never done it, I see no reason why you couldn't implement the various network protocols on top of an AF tree if you wanted to create that system.

Thoughts?

[Daklu]

drjdpowell wrote:

Hi Daklu.  Just thought I'd point out that a "message tree" is not an assumed standard of "actors".  That's a specialization you (and AQ's AF) are using. 

Yeah, I know, but I'm glad you pointed that out.  As long as my posts typically are, believe it or not I do engage in self-editing and try to limit the scope of what I say.  (Not very successfully, I might add.)  One of the difficulties with discussing actor theory is it is very abstract and can be applied to many different types of systems.  OOP is abstract as well, but (afaik) it's applicability is restricted to software systems.  The actor model can be applied to any system where information is passed around between independently executing processes, whether it's software, hardware, mechanical, human, or something else.  Whenever actors get discussed we have to decide if we're talking about general actor theory, actors implemented in Labview, actors implemented with the AF, etc. 

Hierarchical messaging is not the only valid way to link actors, or even necessarily the best way.  I do think it is a reasonably good place to start since it can be used in many situations and other topologies add more complexity to the code.

(Interestingly, in the general actor model message transports--queues, events, notifiers, etc.--don't exist.  There are only actors, messages, and addresses.  Transports (he calls them channels in the video) are another actor.  Since Labview provides us with transports I have no issue with using them in my actor models.)

drjdpowell wrote:

Does your control/benign division have meaning beyond the message tree assumption?

I believe it does, but I don't know that it does.  That's why my posts are so long, so I can explain what I'm thinking, why I think it, and open the door for others to point out things I haven't considered. 

I see two distinct concepts in play:  the control topology and the messaging topology.  The messaging topology is the graph of all actors linked by a message transport.  The control topology is the graph of all actors managing the activity of other actors.  The control topology is necessarily a subset of the messaging topology, since messages must be used to manage the activities of other actors.  It seems to me the control topology should be a tree structure.  Having two actors trying to manage the activities of a single sub actor sounds like a design ripe for lots of confusion.  I don't claim the control tree necessarily should be static for the lifetime of the application, but I'm having a hard time imagining how a non-tree control topology provides a benefit over a tree topology, and it seems to add complexity.

If the control topology should be a tree, then having the messaging topology follow the same topology is, in general, the simplest solution.  When lots of non-control messages have to travel far across the tree, it may make sense to link two actors with a transport for those non-control messages rather than writing all the code to route the messages along each hop.  When I say "hierarchical messaging" I'm referring to a system where all messages follow the control topology.

I think control/benign has meaning beyond a hierarchical messaging system because the distinction helps you figure out exactly what messages you can send across the tree.  If there's anywhere control/benign is meaningless, it's in the context of a strictly hierarchical messaging system ("message tree"), because all messages already follow the control tree.

[drjdpowell]

Thoughts?

True, if one starts a program from one point then there is always a tree of who calls who.  And you can certainly go from that tree to any communication setup you want by passing queues around, but Daklu is arguing against doing that for the subset of "control" messages, due to the resulting uncertainty in the order of message arrival.  But, one cannot always avoid doing that (imagine a network of actors running a power transmission grid). 

Also (this is for Daklu as well) I'm not sure a tree is really proof against race conditions due to uncertain order of message arrival.  Imaging an Actor-A that sends message-1 to it's caller and then message-2 to Actor-B (of the same caller).  And imaging the Caller responds to A's message by sending a response-1 to B.  If A messages B directly, then there is uncertainty in the order of arrival of response-1 and message-2, a possible race condition.  If message-2 is instead routed through Caller, then there is no uncertainty; it will always be response-1 then message-2.  A victory for the tree.

But, imagine instead that message-1 goes to Actor-C (again, same caller), who sends the response to B.  Then, even if all communication routes through the Caller, there is an uncertainty in order of arrival of response-1 and message-2.

The "Actor" theory solution, I believe, is to design actors so that they are robust against uncertainty in the arrival order of messages, even control messages.  Can't say that I actually do that, myself, but that's the most general theory. 

[Daklu]

drjdpowell wrote:

I'm not sure a tree is really proof against race conditions due to uncertain order of message arrival...

But, imagine instead that message-1 goes to Actor-C (again, same caller), who sends the response to B.  Then, even if all communication routes through the Caller, there is an uncertainty in order of arrival of response-1 and message-2.

I'm not sure I understand the scenario you're describing, but I don't think the two situations are analogous.  Here's a grahic I created illustrating my interpretation of what you're describing.

In the first scenario, presumably Msg2 should only be sent if A responds to Msg1 as expected.  That's why the caller is waiting for a response before sending Msg2, right?  Msg2 is conditionally dependent on the success of Msg1.

In the second scenario, Msg2 is independent of Msg1.  It will be sent regardless of the success or failure of Msg1.  Yes, the arrival order of Resp1 and Msg2 is indeterminate, but if B is receiving control messages from both the caller and C, it isn't a tree.

drjdpowell wrote:

But, one cannot always avoid doing that (imagine a network of actors running a power transmission grid).

I don't know much about power transmission grids; however, that might not be the best example to use.  AFAIK power transmission grids are still heavily controlled by humans, not computers.  How would the actors interact in a way that directs the flow of power around the grid?

In principle, I can imagine an actor written as a Windows service could be part of a system without being under the direct control of the system.  The service falls outside of the system's control tree.  I believe underconnected actors (with respect to control) is achievable and probably practical in some situations.  I can't think of a situation where overconnected actors (receiving control messages from more than one source) is desirable.

drjdpowell wrote:

The "Actor" theory solution, I believe, is to design actors so that they are robust against uncertainty in the arrival order of messages, even control messages.  Can't say that I actually do that, myself, but that's the most general theory.

No... well, yes, but only within the context of that particular actor (and its subactors.)  You should make an actor robust against message arrival order only in those cases where receiving messages out of order will break the actor itself.  The actor should not be concerned with its behavior in the higher level system it is part of.  I believe you will get far more value out of an actor that does not overspecify its behavior.

Let's say I have a Car actor that models starting an automatic transmission car and putting it into gear.  For safety reasons, we don't want to allow people to shift out of Park before starting the engine.  (People often step on the accelerator while starting the car, and it would be bad if the car were in gear.)  So we write the actor in a way that it only accepts a ShiftToDrive or ShiftToReverse message if it has already received a StartEngine message and is in the EngineRunning state. 

Now if we created this actor as part of a "LeaveGarageAndDriveToWork" application, we might very well be tempted to write the actor so that after the car is started it must receive a ShiftToReverse message before it will accept a ShiftToDrive message.  (We're trying to be helpful and prevent drivers from plowing through the back of their garage, right?)  What happens when the driver backs into the garage after work in the evening?  The next day he starts the car, then has to put it in reverse before putting it into drive and exiting the garage forward.

My point is both ShiftIntoDrive and ShiftIntoReverse are control messages that will affect the behavior of the system as a whole in very important ways.  But the Car actor doesn't have the information necessary to impose a rational constraint on the order of arrival of those two messages.  In particular, it doesn't know which direction the driver should go.  The logic for deciding what gear to put the car in after starting it up belongs in a Driver actor, not the Car actor.

[AristosQueue (NI)]

drjdpowell wrote:

Also (this is for Daklu as well) I'm not sure a tree is really proof against race conditions due to uncertain order of message arrival.

I agree. It is not proof against all race conditions. It is proof against a couple classes of race conditions, like the first situation you described. It is my hypothesis that several of the remaining categories are more amenable to programmers thinking about them in this format. For example...

drjdpowell wrote:

But, imagine instead that message-1 goes to Actor-C (again, same caller), who sends the response to B.  Then, even if all communication routes through the Caller, there is an uncertainty in order of arrival of response-1 and message-2.

... if I understand the situation you paint here, you have four messages...

• Message 1 from B to caller to A
• Response 1 from A to caller to B
• Message 2 from B to caller to C
• Response 2 from C to caller to B

... and you posit that they may be reordered...

• Message 1 from B to caller to A
• Message 2 from B to caller to C
• Response 2 from C to caller to B
• Response 1 from A to caller to B

Thus B sends the message out in one order and gets the replies back in reverse order (or other arbitrary shuffling if more messages are involved).

Yes, this can happen. But under my hypothesis:

1. Reasoning about the arrival of messages from processes with different amounts of time is easy, and likely something that the programmer has at the forefront of his/her mind. Thus this is a more expected-and-thus-prepared-for race condition than A sends two messages and B receives them in reverse order. This one is also more easily tested since by the very nature of taking different amounts of time, the responses are often reordered, whereas in transmission, reordering occurs only when the system is under load (generally, packets tend to arrive in the order they were sent).
2. If the responses do need to come back ordered, B could implement an awareness to not process received messages until the ones before it are received (similar to the guarantees that TCP adds to raw network traffic). But caller also exists and can serve as a general point of straightening out for *all* actors if that's desired. Thus it becomes easier to program a solution to this kind of race condition.

Totally theoretical. No proof. Just seems that people reason better about these situations in an environment of well-defined traffic patterns than they do in an environment of ad hoc traffic patterns.

drjdpowell wrote:

The "Actor" theory solution, I believe, is to design actors so that they are robust against uncertainty in the arrival order of messages, even control messages.  Can't say that I actually do that, myself, but that's the most general theory. 

Up to a point. At some point, the design becomes, "Add the next network layer so that from the point of view of the application, packets arrive in order." 🙂 Since the AF is entirely application-level actors, I'm just assuming that layer is already there. The utility of actors that can maintain what I think of as quantum superposition -- executing as if all possible message orderings were actually happening until we figure out which one is really happening -- is minimal as far as I can tell and they're damn hard to even think about, much less implement. 🙂

[David_Staab]

Daklu wrote:

When lots of non-control messages have to travel far across the tree, it may make sense to link two actors with a transport for those non-control messages rather than writing all the code to route the messages along each hop.

One of my challenges in AF is that even when I want to do this, I still have to make a series of messages that share the queue of the target actor with the sending actor. (See my Data Broadcasting library...the token is used to share the recipient's "address" and has to be passed around the "control tree".) So in AF, there is no code size benefit to bypassing the tree.

Could AF benefit from adding a registry of named actor queues so anyone can send a non-control message to anyone else by name? (It could be made fancier by treating the name as an interface and allowing a message to be sent to multiple recipients registered for that interface.)

[AristosQueue (NI)]

David Staab wrote:

Could AF benefit from adding a registry of named actor queues so anyone can send a non-control message to anyone else by name?

Embedding something like that into all actors would completely "void the warranty" for most of the behavior guarantees that AF provides as no one would be able to make any guarantees about the movement of messages through the system. At that point, we might as well move to an observer model and not AF at all. What issues we might save in terms of setting up the communications lines we would trade for the very issues that lead to the creation of AF in the first place.

I'm not saying you should never create that registry. For communication among *independent* actor trees (ie. ones who run as separate processes and have to announce their existence and/or look up the existence of others), you probably need something like that. But I would hope that would be something you would create as the next layer of architecture up from the AF, not embed in the AF, and something that would be used only for actor trees that are not within the same process. And only the root actor of any given tree would be registered into that system.

David Staab wrote:

So in AF, there is no code size benefit to bypassing the tree.

True. It only provides a possible performance benefit, a benefit that, if you want the correctness guarantees of the AF, you should only use when performance testing proves that you have a hot-spot there. If you can compensate for the loss of those guarantees, you can use it more ubiquitously.

[David_Staab]

(Quoting you out of order...)

AristosQueue wrote:

David Staab wrote:

So in AF, there is no code size benefit to bypassing the tree.

True. It only provides a possible performance benefit...

Code is a liability in any design, and AF carries a massive weight of boilerplate. Any opportunity to reduce the amount of code I have to write (or auto-generate and later edit by hand, in the case of roughly 20% of my message classes) is incredibly interesting to me.

Embedding something like that into all actors would completely "void the warranty" for most of the behavior guarantees that AF provides as no one would be able to make any guarantees about the movement of messages through the system.

But, as I think it's been stated, only Command-type messages need the warranty of a tree. "Benign" messages don't benefit from it. If a lot of boilerplate can be removed from a big percentage of all messages in the system without considerable design risk, I'm all for it.

[Daklu]

Daklu wrote:

drjdpowell wrote:

But, imagine instead that message-1 goes to Actor-C (again, same caller), who sends the response to B.  Then, even if all communication routes through the Caller, there is an uncertainty in order of arrival of response-1 and message-2.

I'm not sure I understand the scenario you're describing...

Ahh... thanks to AQ's comment I realized I misunderstood the scenario you're describing.  Here's a revised graphic of my interpretation, which is a little bit different than AQ's interpretation.  Note "m1.x" and "m2.x" represent a message chain triggered by the initial message 1 and message 2 sent from A.  Looking at the tree topology, the chain for message 1 is A -> Caller -> C -> Caller -> B.  The chain for message 2 is A -> Caller -> B.

You are correct, the arrival order of the messages at B is indeterminate in both the tree and direct topologies.  That is an inherent difficulty with concurrent computing and I don't think you can completely avoid it without eliminating concurrency altogether.  Still, there are a couple things in your scenario that jump out at me:

1. Your scenario implies the system will behave different depending on the order in which B receives the messages.  It also suggests that A is making the decision on what the desired behavior will be.  In other words, since A is sending m1 followed by m2, it is expecting B to receive m1 followed by m2.  This is, imo, an error in your model.  In general the actor model does not guarantee messages arrive in the order they are sent.  In Labview we can often safely assume Caller will receive m1.1 before it will receive m2.1, simply because queues or user events are often used as a transport, and they have FIFO behavior.  (Conversely, if the transport were implemented as a stack all bets are off.) 
   
   However, that assumption is only possible when two message chains are identical (and even then it's not guaranteed.)  As soon as the chains diverge the order of delivery at the destination is indeterminate.  It doesn't matter what topology you are using.  Sequential dependencies in messages will cause no end of problems.  Avoid it where you can.  That's one of the reasons I prefer to use sender-subject messages going up the tree.  Status update semantics naturally encourage messages without sequential dependencies.
   
   As AQ said, Caller serves as the central point to coordinate the activities of A, B, and C.  If determinacy between m1.4 and m2.2 is required, implement that system level logic in Caller.  Notice in the direct topology there is no single actor coordinating the behavior, and there is no way to ensure B receives the messages in any particular order.
2. If A does not expect B to receive m1 and m2 in the same order they were sent, then the indeterminacy you noted is the correct behavior.  If m2 is sent 30 seconds after m1, we would probably expect m1 to arrive at B before m2.  On the other hand, if C involves a 5 minute process prior to sending m1.3, we would expect m2 to arrive before m1.  We don't want to impose an order on B receiving m1 and m2 because they are independent and the system needs to be built such that it knows how to handle either order appropriately.

AQ and I disagree about the value of sender-subject messages, but we agree heirarchical messaging is an easier way to reason about the overall system behavior.  Other topologies may have benefits I don't fully understand yet, but until I do I will recommend new AOD developers stick with hierarchical messaging.