4 ms·

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

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.
        sriram_malhar 4y ago

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.
      - sriram_malhar 4y ago