Randomness

Open
#20 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Stale
Tech stack
ocaml
Domain
distributed-systems, testing-qa

Research direction

Start by tracing DSCheck's run and replay setup, then inspect how OCaml's PRNG is initialized during repeated exploration. Use the lockfree pull request #65 as reproduction context; done means consecutive reruns use consistent randomness and no longer crash or miss interleavings because a thread becomes disabled.

Written by the indexing model from the issue text.

Description

Many lock-free implementations use some randomness as an easy way to load balance without coordination. This may be a source of nondeterminism and DSCheck does not like it. For example, say we have a test that begins with two threads wanting to put two elements into random slots in an array.

Run:

  1. Thread A draws slot 3 and puts item there
  2. Thread B draws slot 3 and fails
  3. Thread B retries; draws slot 5 and puts item there
    ..
    ..
    more steps

If DSCheck finds some races after step 3, it will keep rerunning the sequence 1-3 to explore events of interest that occur further down the sequence. But on the consecutive runs, thread B may succeed on the first try, yielding a different state. In the positive case, B will become disabled before its schedule and DSCheck crashes explicitly. In the more scary one, we may give a positive result without actually having explored all the interesting interleavings.

It's an easy mistake to make and a pretty difficult one to find. Perhaps, DSCheck should choose some random seed, and then reinitialize OCaml's prng to this value at the beginning of every run?

cc @lyrm, who's observed this issue in pratice, with dscheck crashing uncontrollably on https://github.com/ocaml-multicore/lockfree/pull/65

Dominant language
OCaml
Stars
47
Forks
8
No merged PRs in 30d

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from ocaml-multicore/dscheck

All issues in ocaml-multicore/dscheck

Similar issues

More Distributed Systems issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.