Determinism

Search…
Determinism
Random number generation
Simulate uses srand and srandom to seed rand and random. Each worker is seeded by the manager deterministically during spawn. This allows each worker to have different sequences when requesting new random numbers.
Simulate's random number utility functions can be found in the aether/common/random.hh header file. A new random number can be requested as follows (the seed parameter should not be supplied).
uint64_t aether::random::generate_random_u64(unsigned seed = 0);    // numbers between 0 and 18446744073709551615
uint32_t aether::random::generate_random_u32(unsigned seed = 0);    // numbers between 0 and 4294967295
float aether::random::generate_random_f32(unsigned seed = 0);       // floating point numbers between 0 and 1
double aether::random::generate_random_f64(unsigned seed = 0);      // double precision floating point numbers between 0 and 1
rand and random should not be seeded non-deterministically if deterministic behaviour is required. Instead, a pseudo-deterministic C++ random number generator can be used by seeding it with Simulate's random number utility functions. This will provide deterministic random number generation.
Cell split and merge
As mentioned in the Introduction to this section, cells split and merge based on the estimate_load function.
Users must generate a deterministic value from the estimate_load function to have deterministic split and merge. For instance using time since epoch or simulation start would generate a non-deterministic output whereas using tick count would generate a deterministic output.
Non-deterministic split and merge would cause cells random number generator to be seeded non-deterministically.
Blob store
Asynchronous use of the blob store may introduce non-deterministic behaviour. For example, two separate workers download an asset asynchronously and complete the downloads at tick 1 and tick 3. This asset is then used to alter the behaviour of entities on each worker. The simulation's behaviour is now non-deterministic.
To have deterministic behaviour:
blob store can be called synchronously, blocking the simulation until the download is complete.
A mechanism can be put in place so that all workers start processing the asset at the same tick.
Entity Ordering
Entities are moved between cells, and ghost entities updated if necessary, by Simulate in a process called 'handover'. This obviously requires communication between Simulate workers, and so the order in which entities are received and inserted is non-deterministic (due to real-world effects such as network latency etc.). Additionally, existing entities within the entity store may be re-ordered as an implementation detail of the underlying storage mechanism during the insertion and removal process - Simulate cannot guarantee consistent ordering of entities in the entity store following handover.
There are various approaches that can be used to improve determinism in the presence of non-deterministic entity ordering:
The most heavyweight is to re-order entities according to some unique identifier guaranteed to remain identical across runs. Code that is sensitive to entity ordering will now always see entities in the same order. Entity IDs are suitable for this provided that they are generated in a deterministic way and are unique.
If calculations are performed which involve aggregating across entities, it may be possible to produce determinism by ensuring that the operators involved are insensitive to ordering. In practice, this may include modifying calculations to avoid using floating-point arithmetic. Although operations such as addition and multiplication are theoretically associative and commutative, this is untrue for floating-point numbers but true for other representations such as integers and fixed-point numbers.
PhysX
PhysX offers limited determinism, producing the same result for the same binary, hardware, scene and time-step. For reproducibility, PhysX also requires that actors are inserted into the scene in an identical order.
Simulate will always advance the simulation with a fixed time-step irrespective of wall-clock time. However, Simulate's PhysX support is integrated with handover, meaning that Simulate cannot guarantee actor insertion order. For this reason, any Simulate simulation using PhysX to advance the simulation is not guaranteed to be reproducible.
Deterministic Identifiers
Simulate does not require entities to have an explicit identifier, and therefore does not provide a mechanism for generating them. Identifiers are required if using entity-targeted messaging (which includes the field-of-view feature), and are required to be a 64-bit integer that is unique across the simulation.
As mentioned above in the section regarding Entity Ordering during handover, if there are operations that rely on the ordering of entities to preserve determinism then identifiers should be generated in a deterministic manner.
For most purposes, a reasonable strategy is to generate a pseudorandom 64-bit integer per cell using a good pseudorandom generator. The chance of collision is exceeding low even for the typical scale of Simulate simulations - it is expected that over 600 million IDs would need to be generated for a 1% chance of collision. See above for notes on generating pseudorandom numbers deterministically.
C's rand() function and Simulate's generate_random_* family are implemented as simple Linear Congruential Generators and are not suitable for this purpose. Aether's random number generators can be used to initialize ("seed") a higher-quality engine.
The following example code shows how to set up C++11's 64-bit Mersenne Twister to generate IDs with an appropriate statistical distribution.
    // Create a seed for the high-quality random number generator
    // with a deterministic value from Aether
    uint64_t seed = aether::random::generate_random_u64();
​
    // Create a 64-bit Mersenne Twister generator, seeded with the earlier value
    // This will deterministically produce high-quality pseudorandom numbers
    std::mt19937_64 generator(seed);
​
    // Define a distribution over the entire 64-bit integer range
    std::uniform_int_distribution<uint64_t> distribution();
​
    // Generate an ID
    uint64_t id = dist(generator);
Worked Example
Next - Developing Simulations
Blob Store
Last modified 2mo ago
Copy link
Outline
Random number generation
Deterministic Identifiers