4 ms·

How does one do simulation without synchrony and some kind of global clock? Actors and message passing aren't sufficient; at the very least one needs causal or

How does one do simulation without synchrony and some kind of global clock? Actors and message passing aren't sufficient; at the very least one needs causal ordering, and even that won't be enough, I suspect.

tinco 4y ago
Why would you need a clock for causal ordering? You don't need every actor to respond to a change at the same time.
- sriram_malhar 4y ago
  Consider: A sends a message to "x = 2" to B and C. B receives this message and sends "x = 3" to C. Now, C receives two messages one from A and one from B. It could receive them in any order. However, there is no way for it to tell whether there is a causal order or not. With a clock embedded in the messages, one can state that "x=2" happened before "x=3". (or more strictly, "x=3" def did not happen before "x=2"). Extending this, if C and D receive copies of the above messages from A and B, we want C and D to both process them in the same (deterministic) order.
  - tinco 4y ago
    Besides that it's a very synthetic example that I don't think makes sense in the context of a city simulation, I think that it's also a bad design. You shouldn't have multiple authorities on the value of x, C shouldn't rely on both A and B to get a value for x. In the context of a city simulator, every road segment could be an actor, as well as every simulated vehicle. Two vehicles might try to enter a road segment at the same time, so they both send a message :enter(entity_1) to :road_segment_1. Then the :road_segment_1 actor decides what to do with those messages. Structuring it this way allows you to massively distribute these kinds of simulations, which is exactly why citybound attempted an actor-based approach. There's a load of overhead, and there's still issues with buffers and backpressure, but in theory you could infinitely scale a simulation this way.
    - sriram_malhar 4y ago
      It isn't a synthetic example at all. We want two receivers of the same set of messages from the same set of senders to process them in the same order. Determinism is of utmost importance. In your example, the vehicles' messages have no causal relationship; they are concurrent. Order does not matter. However, for the sake of determinism in a simulation, the above constraint is necessary even for concurrent messages.
      - tinco 4y ago
        Why is determinism of the utmost importance? That's an arbitrary constraint you put on the system that doesn't even exist in the real world.
        sriram_malhar 4y ago
        For me, determinism is a fundamental property to be aimed for, to build testable and repeatable systems, whether they are simulation engines or real-world systems. For example, one of the projects I have worked on is one of the largest trading engines in the world, with high concurrency. To make it testable and fault-tolerant, all incoming messages are timestamped and handled in time-serial order. The same timestamp helps with idempotence. When testing the engine core and downstream systems, a previous day's test data can be input in timestamp order (instead of concurrently), so that we know the behaviour of the system in the face of a fix. Dataflow systems (which is most software) should be idempotent and deterministic. If random() is called, then fixing the seed should make it deterministic.
        tinco 4y ago
        The only reason your system needs to be deterministic is because your company is afraid. If it wasn't afraid and instead just interested in making an accurate model of reality, it wouldn't be interested in determinism. Basing the behavior of your simulator on yesterdays data is a neat trick, but it has no relationship to the actual world. Not in a million years would the exact same market behavior of yesterday happen again. Instead of building it deterministic, you could simply run your system a hundred times, and maybe purposefully mess with the timings to make execution more non-deterministic. And instead of a precise number "yesterday we would have made X amount of money with our trading engine", you would come up with a distribution that is much more predictive of the future "with market circumstances similar to yesterday we would have made between X and Y amount of money with our trading engine". Anyway, I don't work on trading systems so I probably shouldn't tell you how to do your job. This is just how I see simulation systems.
atoav 4y ago
Causal ordering is what emerges when messages can only arrive after they have been sent right? How would a message arrive before it has been sent?
- sriram_malhar 4y ago
  It won't, true, but that's not the point. The question is what order does a receiver process messages received from multiple senders. Please see the response to the other poster in this mini-thread.
frankling_ 4y ago
This is the problem dealt with by the field of parallel and distributed simulation [1]. The two basic approaches are to either block the receiver until you can guarantee that a received message will not be displaced by one with earlier timestamp (conservative algorithms) or to speculatively handle messages and roll back if an earlier message ends up arriving (optimistic algorithms). If the simulation is stepwise, life is little bit easier compared to arbitrarily timestamped messages, but even then the questions of a "correct" ordering and the handling of conflicts must be dealt with. It's a pretty rich field, partially due to the often-unpredictable runtime behavior of simulation models and the challenge of balancing the generality of the algorithms with their efficiency for particular problem domains (such as the agent-based simulations discussed here). [1] https://doi.org/10.1109/WSC.2015.7408152 https://doi.org/10.1109/WSC.2015.7408152

tinco 4y ago

Why would you need a clock for causal ordering? You don't need every actor to respond to a change at the same time.

sriram_malhar 4y ago
Consider: A sends a message to "x = 2" to B and C. B receives this message and sends "x = 3" to C. Now, C receives two messages one from A and one from B. It could receive them in any order. However, there is no way for it to tell whether there is a causal order or not. With a clock embedded in the messages, one can state that "x=2" happened before "x=3". (or more strictly, "x=3" def did not happen before "x=2"). Extending this, if C and D receive copies of the above messages from A and B, we want C and D to both process them in the same (deterministic) order.
- tinco 4y ago
  Besides that it's a very synthetic example that I don't think makes sense in the context of a city simulation, I think that it's also a bad design. You shouldn't have multiple authorities on the value of x, C shouldn't rely on both A and B to get a value for x. In the context of a city simulator, every road segment could be an actor, as well as every simulated vehicle. Two vehicles might try to enter a road segment at the same time, so they both send a message :enter(entity_1) to :road_segment_1. Then the :road_segment_1 actor decides what to do with those messages. Structuring it this way allows you to massively distribute these kinds of simulations, which is exactly why citybound attempted an actor-based approach. There's a load of overhead, and there's still issues with buffers and backpressure, but in theory you could infinitely scale a simulation this way.
  - sriram_malhar 4y ago
    It isn't a synthetic example at all. We want two receivers of the same set of messages from the same set of senders to process them in the same order. Determinism is of utmost importance. In your example, the vehicles' messages have no causal relationship; they are concurrent. Order does not matter. However, for the sake of determinism in a simulation, the above constraint is necessary even for concurrent messages.
    - tinco 4y ago
      Why is determinism of the utmost importance? That's an arbitrary constraint you put on the system that doesn't even exist in the real world.
      - sriram_malhar 4y ago
        For me, determinism is a fundamental property to be aimed for, to build testable and repeatable systems, whether they are simulation engines or real-world systems. For example, one of the projects I have worked on is one of the largest trading engines in the world, with high concurrency. To make it testable and fault-tolerant, all incoming messages are timestamped and handled in time-serial order. The same timestamp helps with idempotence. When testing the engine core and downstream systems, a previous day's test data can be input in timestamp order (instead of concurrently), so that we know the behaviour of the system in the face of a fix. Dataflow systems (which is most software) should be idempotent and deterministic. If random() is called, then fixing the seed should make it deterministic.
        tinco 4y ago
        The only reason your system needs to be deterministic is because your company is afraid. If it wasn't afraid and instead just interested in making an accurate model of reality, it wouldn't be interested in determinism. Basing the behavior of your simulator on yesterdays data is a neat trick, but it has no relationship to the actual world. Not in a million years would the exact same market behavior of yesterday happen again. Instead of building it deterministic, you could simply run your system a hundred times, and maybe purposefully mess with the timings to make execution more non-deterministic. And instead of a precise number "yesterday we would have made X amount of money with our trading engine", you would come up with a distribution that is much more predictive of the future "with market circumstances similar to yesterday we would have made between X and Y amount of money with our trading engine". Anyway, I don't work on trading systems so I probably shouldn't tell you how to do your job. This is just how I see simulation systems.

atoav 4y ago

Causal ordering is what emerges when messages can only arrive after they have been sent right? How would a message arrive before it has been sent?

sriram_malhar 4y ago
It won't, true, but that's not the point. The question is what order does a receiver process messages received from multiple senders. Please see the response to the other poster in this mini-thread.

frankling_ 4y ago

This is the problem dealt with by the field of parallel and distributed simulation [1]. The two basic approaches are to either block the receiver until you can guarantee that a received message will not be displaced by one with earlier timestamp (conservative algorithms) or to speculatively handle messages and roll back if an earlier message ends up arriving (optimistic algorithms). If the simulation is stepwise, life is little bit easier compared to arbitrarily timestamped messages, but even then the questions of a "correct" ordering and the handling of conflicts must be dealt with. It's a pretty rich field, partially due to the often-unpredictable runtime behavior of simulation models and the challenge of balancing the generality of the algorithms with their efficiency for particular problem domains (such as the agent-based simulations discussed here). [1] https://doi.org/10.1109/WSC.2015.7408152 https://doi.org/10.1109/WSC.2015.7408152