Knowledge base

A divisible load is work that can be partitioned into arbitrarily-sized, independent pieces with no precedence between them: any fraction can be sent to any processor without coordination. The assumption holds for a wide class of real workloads — pixel-parallel image and video processing, batch record transformations over databases, Monte-Carlo sampling runs, independent parameter sweeps, and distributed tensor computations. What distinguishes a divisible load from a general parallel task is precisely this continuous partitioning freedom: the scheduler is not assigning discrete jobs but choosing a real-valued fraction for each worker.

The master-worker architecture distributes the load over a network under the single-port constraint: the originator (master) sends data to one worker at a time, serialising all outbound transfers through its single network port. A worker begins computing only after its chunk has arrived in full, but different workers compute concurrently once served. The result is a pipelined structure: communication to later workers overlaps with computation by earlier ones, delivering parallel speedup even though the transfers themselves are sequential.

The central scheduling question is who computes how much, and in what order, to minimise the makespan (the instant the last worker finishes). The answer is not simply “give more to faster processors”: sending a slow worker first delays all subsequent transfers; sending a fast worker first risks the slow worker becoming the tail. The optimal solution resolves this tension through the simultaneous-finish condition: all workers complete at exactly the same instant, so no processor sits idle while another is still running. This condition collapses what would be a combinatorial optimisation into a linear system, yielding optimal fractions in O(m) time for startup-free stars.

Divisible Load Theory (DLT) was established by Cheng and Robertazzi (1988) and developed extensively through the 1990s and 2000s. It supplies closed-form solutions for homogeneous networks, LP-based exact methods for heterogeneous ones, FPTAS schemes for resource-constrained cases, online rules for dynamic workloads, and a growing body of energy-aware methods. This portal exposes the core of that theory as a C++ library accessible through a JSON API and the Solver Studio, with all results reproducible from the reference bibliography.