| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
Nondeterministic Control Flow

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;
}
tf::Executor
class to create an executor
Definition executor.hpp:62
tf::Executor::run_n
tf::Future< void > run_n(Taskflow &taskflow, size_t N)
runs a taskflow for N times
tf::FlowBuilder::emplace
Task emplace(C &&callable)
creates a static task
Definition flow_builder.hpp:1738
tf::Task
class to create a task handle over a taskflow node
Definition task.hpp:569
tf::Task::precede
Task & precede(Ts &&... tasks)
adds precedence links from this to other tasks
Definition task.hpp:1258
tf::Taskflow
class to create a taskflow object
Definition taskflow.hpp:64

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.