Knowledge base

The standard DLT model places a single originator at the centre of a star topology. It holds a total load V to be distributed to m worker processors over a shared network port. All outbound transfers use that single port, so chunks are sent one at a time in a sequence chosen by the scheduler; the activation order is a first-class scheduling decision alongside the load fractions themselves.

Each worker i is characterised by four parameters. The startup latency Sᵢ is a fixed overhead paid once per transfer before any data can flow; it models protocol handshaking, buffer allocation, or OS context-switch costs and is independent of chunk size. The communication rate Cᵢ is the time per unit of load transmitted across the link (the inverse of bandwidth); the total transfer time for a chunk of size αᵢ is Sᵢ + Cᵢ·αᵢ. The computation rate Aᵢ is the time per unit of load processed on the worker (the inverse of its speed); the computation time for αᵢ is Aᵢ·αᵢ. The memory bound Bᵢ caps the chunk size per installment; if the optimal αᵢ exceeds Bᵢ, the load must be delivered in multiple rounds.

A schedule specifies a permutation of the workers and fractions α₁, …, αₘ summing to V. Worker i in position k of the permutation starts receiving data only after all k−1 preceding transfers have finished. It starts computing as soon as its chunk arrives. The simultaneous-finish condition is the key DLT insight: the optimal schedule (for startup-free stars) is the unique one in which every active worker finishes at the same instant Cmax. Setting all finish times equal and summing the fractions to V yields a linear system whose solution gives the optimal fractions in O(m) time. When startups Sᵢ are nonzero the system is still linear for a fixed activation order, but the optimal order must be found by search (branch-and-bound or MILP), since different orders produce different finish-time systems.

A lower bound LB derived from the instance brackets the optimal makespan from below. Common constructions include the total computation work V·min(Aᵢ) / m (ignoring communication), the single-bottleneck bound from the slowest link, or LP relaxations of the activation-order integer program. The optimality gap (Cmax − LB) / LB measures how far a heuristic solution is from the best achievable schedule. A gap of 0 certifies optimality. A gap of 3% means the heuristic is within 3% of any possible schedule, regardless of which exact method were run.