1

I read about how FoundationDB does its network testing/simulation here: http://www.slideshare.net/FoundationDB/deterministic-simulation-testing

I would like to implement something very similar, but cannot figure out how they actually did implement it. How would one go about writing, for example, a C++ class that does what they do. Is it possible to do the kind of simulation they do without doing any code generation (as they presumeably do)?

Also: How can a simulation be repeated, if it contains random events?? Each time the simulation would require to choose a new random value and thus be not the same run as the one before. Maybe I am missing something here...hope somebody can shed a bit of light on the matter.

pnuts
  • 58,317
  • 11
  • 87
  • 139
kitomer
  • 33
  • 1
  • 7

2 Answers2

3

You can find a little bit more detail in the talk that went along with those slides here: https://www.youtube.com/watch?v=4fFDFbi3toc

As for the determinism question, you're right that a simulation cannot be repeated exactly unless all possible sources of randomness and other non-determinism are carefully controlled. To that end:

(1) Generate all random numbers from a PRNG that you seed with a known value.

(2) Avoid any sort of branching or conditionals based on facts about the world which you don't control (e.g. the time of day, the load on the machine, etc.), or if you can't help that, then pseudo-randomly simulate those things too.

(3) Ensure that whatever mechanism you pick for concurrency has a mode in which it can guarantee a deterministic execution order.

Since it's easy to mess all those things up, you'll also want to have a way of checking whether determinism has been violated.

All of this is covered in greater detail in the talk that I linked above.

willwilson
  • 422
  • 3
  • 8
0

In the sims I've built the biggest issue with repeatability ends up being proper seed management (as per the previous answer). You want your simulations to give different results only when you supply a different seed to your random number generators than before.

After that the biggest issue I've seen seems tends to be making sure you don't iterate over collections with nondeterministic ordering. For instance, in Java, you'd use a LinkedHashMap instead of a HashMap.

E Clark
  • 23
  • 4
  • A HashMap is not randomized. And even if it was, you could probably control the seed. So the iteration order may not be specified, but if you use the same HashMap implementation with the same inputs you will always get the same results back. – Thilo May 03 '18 at 09:29
  • Nondeterministic isn't the same thing as random. In Java, the hashCode() method is used to determine iteration order for HashMaps, but the contract for the hashCode() method does not require the same value to be used each time the program is run. In fact, the default implementation for hashCode() usually depends on the in-memory location of an object. Because of this, a good general rule is to not rely on bucket membership when iterating a hash map if you want repeatable results. – E Clark May 03 '18 at 13:38
  • Okay, if you use a HashMap with "non-value" objects as keys, then this will indeed be a problem. I'd group this under the "Avoid any sort of branching or conditionals based on facts about the world which you don't control" item raised in the other answer. However, any "normal" object you'd use for hash keys (such as String or Integer) with a hashCode that is stable in its "value" will not have this problem. Then the behaviour is completely deterministic. https://stackoverflow.com/questions/9440380/using-an-instance-of-an-object-as-a-key-in-hashmap-and-then-access-it-with-exa – Thilo May 04 '18 at 03:51