Learning from Examples » Nondeterministic Control Flow

This page demonstrates how Taskflow models nondeterministic control flow using conditional tasking. Nondeterministic control flow is a fundamental abstraction in many optimization, search, and simulation algorithms that rely on randomness, probabilistic pruning, or stochastic convergence. We use a chain of coin-flipping tasks as a concrete example to illustrate how conditional tasks dynamically alter execution paths at runtime.

Problem Formulation

Consider a fair binary coin. We repeatedly toss the coin until we observe five consecutive heads. Apparently, the probability of obtaining five heads in a row is 1/32:

Equivalently, the expected number of tosses required to observe five consecutive heads is 32. Our goal is to model this stochastic process using Taskflow and verify that the observed execution behavior matches the theoretical expectation.

Implementation using Conditional Tasking

We use condition tasks to simulate the five coin tosses. We create five condition tasks each returning a random binary number. If the return is zero (head toss), the execution moves to the next condition task; or it (tail toss) goes back to the first condition task to restart the simulation. This structure naturally expresses nondeterministic control flow without explicit loops or synchronization:

#include <taskflow/taskflow.hpp>

int main() {

  tf::Taskflow taskflow;
  tf::Executor executor;
  
  size_t rounds = 10000;
  size_t tosses = 0; 
  size_t total_tosses = 0; 
  double average_tosses = 0.0; 
  
  tf::Task A = taskflow.emplace([&](){ tosses = 0; })
                       .name("init"); 
  
  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");
  
  // reach the target; record the number of tosses 
  tf::Task G = taskflow.emplace([&](){ total_tosses += tosses; })
                       .name("stop");
  
  A.precede(B);
  
  // five probabilistic conditions
  B.precede(C, B);
  C.precede(D, B);
  D.precede(E, B);
  E.precede(F, B);
  F.precede(G, B);
  
  // repeat the flip-coin simulation by rounds times
  executor.run_n(taskflow, rounds).wait();
  
  // calculate the expected number of tosses
  average_tosses = total_tosses / (double)rounds;
  
  assert(std::fabs(average_tosses-32.0)<1.0);
  
  return 0;
}

Running the taskflow by a fair number of times, the average tosses we have is close to 32. The corresponding taskflow diagram is shown below:

Although the execution of this taskflow is non-deterministic, its control flow can expand to a tree of tasks based on our scheduling rule for conditional tasking (see Conditional Tasking). Each path from the root to a leaf represents a result of five heads, and none of them can overlap at the same time (no task race). You must follow the same rule when creating a probabilistic framework using conditional tasking.

Ternary Coins

We can extend the binary coin example to a ternary case. Each condition task has one successor going back to the beginning and two successors moving to the next task. The expected number of tosses to reach five identical results is 3*3*3*3*3 = 243.

tf::Task A = taskflow.emplace( [&](){ tosses = 0; } )
                     .name("init"); 

// start over the flip again
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");

// reach the target; record the number of tosses 
tf::Task G = taskflow.emplace([&](){ total_tosses += tosses; })
                     .name("stop");

A.precede(B);

// five probabilistic conditions
B.precede(C, B, B);
C.precede(D, B, B);
D.precede(E, B, B);
E.precede(F, B, B);
F.precede(G, B, B);

// repeat the flip-coin simulation by rounds times
executor.run_n(taskflow, rounds).wait();

// calculate the expected number of tosses
average_tosses = total_tosses / (double)rounds;

assert(std::fabs(average_tosses-243.0)<1.0);

This pattern extends naturally to probabilistic conditions of any degree, making conditional tasking a powerful tool for expressing nondeterministic control flow in stochastic algorithms.