Nondeterministic Control Flow

Table of Contents

• Problem Formulation
• Implementation with Conditional Tasking
• Extension to Ternary Coins

We demonstrate how Taskflow models nondeterministic control flow using conditional tasking — a powerful pattern for stochastic search, probabilistic simulation, and optimization algorithms whose execution path is determined only at runtime.

Problem Formulation

Consider a fair binary coin. We toss it repeatedly until we observe five consecutive heads. The probability of obtaining five heads in a row is 1/25 = 1/32:

The expected number of tosses required to reach five consecutive heads is therefore 32. Our goal is to model this stochastic process as a Taskflow task graph and verify that the observed average over many trials matches the theoretical expectation.

Implementation with Conditional Tasking

We create five condition tasks, each returning a random binary value. A return value of 0 (heads) advances execution to the next coin-flip task; a return value of 1 (tails) sends execution back to the first coin-flip task to restart. This structure expresses nondeterministic control flow directly as a task graph — no explicit loop variables, mutexes, or synchronisation needed:

#include <taskflow/taskflow.hpp>
 
int main() {
 
  tf::Taskflow taskflow;
  tf::Executor executor;
 
  const size_t rounds = 10000;
  size_t tosses = 0;
  size_t total_tosses = 0;
 
  // reset the toss counter at the start of each trial
  tf::Task init = taskflow.emplace([&]() { tosses = 0; })
                          .name("init");
 
  // each condition task returns 0 (heads) or 1 (tails)
  tf::Task B = taskflow.emplace([&]() { ++tosses; return std::rand() % 2; })
                       .name("flip-coin-1");
  tf::Task C = taskflow.emplace([&]() { return std::rand() % 2; })
                       .name("flip-coin-2");
  tf::Task D = taskflow.emplace([&]() { return std::rand() % 2; })
                       .name("flip-coin-3");
  tf::Task E = taskflow.emplace([&]() { return std::rand() % 2; })
                       .name("flip-coin-4");
  tf::Task F = taskflow.emplace([&]() { return std::rand() % 2; })
                       .name("flip-coin-5");
 
  // accumulate the toss count when five consecutive heads are achieved
  tf::Task stop = taskflow.emplace([&]() { total_tosses += tosses; })
                          .name("stop");
 
  init.precede(B);
 
  // 0 (heads) → advance to next flip; 1 (tails) → restart from B
  B.precede(C, B);
  C.precede(D, B);
  D.precede(E, B);
  E.precede(F, B);
  F.precede(stop, B);
 
  // run 10,000 independent trials
  executor.run_n(taskflow, rounds).wait();
 
  double average_tosses = static_cast<double>(total_tosses) / rounds;
  assert(std::fabs(average_tosses - 32.0) < 1.0);
 
  std::cout << "average tosses to five consecutive heads: "
            << average_tosses << '\n';
 
  return 0;
}

After 10,000 trials, the observed average converges to approximately 32, matching the theoretical expectation. The corresponding task graph is shown below:

Although individual executions are non-deterministic, the task graph's control flow expands to a tree of tasks according to Taskflow's scheduling rule for conditional tasking (see Conditional Tasking). Each path from the root to stop represents one successful run of five consecutive heads, and no two live paths can race — the conditional edges ensure that only one execution path is active at any time.

Extension to Ternary Coins

The same pattern extends naturally to higher-arity conditions. With a ternary coin (three equally likely outcomes), two outcomes advance execution and one restarts. The expected number of tosses to observe five identical consecutive results is 35 = 243:

tf::Task B = taskflow.emplace([&]() { ++tosses; return std::rand() % 3; })
                     .name("flip-coin-1");
tf::Task C = taskflow.emplace([&]() { return std::rand() % 3; })
                     .name("flip-coin-2");
tf::Task D = taskflow.emplace([&]() { return std::rand() % 3; })
                     .name("flip-coin-3");
tf::Task E = taskflow.emplace([&]() { return std::rand() % 3; })
                     .name("flip-coin-4");
tf::Task F = taskflow.emplace([&]() { return std::rand() % 3; })
                     .name("flip-coin-5");
 
// outcomes 0 and 1 advance; outcome 2 restarts
B.precede(C, B, B);
C.precede(D, B, B);
D.precede(E, B, B);
E.precede(F, B, B);
F.precede(stop, B, B);
 
executor.run_n(taskflow, rounds).wait();
 
double average_tosses = static_cast<double>(total_tosses) / rounds;
assert(std::fabs(average_tosses - 243.0) < 1.0);

This pattern scales to probabilistic conditions of any arity, making conditional tasking a natural fit for Monte Carlo simulation, stochastic search, Markov chain sampling, and any algorithm whose control flow depends on outcomes known only at runtime.