Knowledge base

The star topology places a single originator at the centre with direct links to every worker. It is the foundational DLT model, introduced by Cheng and Robertazzi (1988), and the basis of all closed-form results. Every transfer goes directly from the originator to a worker over the shared single port; there is no relaying, no intermediate node, and no multi-hop delay. This simplicity is what makes the simultaneous-finish linear system tractable in O(m) time.

In a star, the activation order matters only when startup costs Sᵢ are nonzero. With zero startup the optimal fractions are independent of order (all orderings of the same fractions give the same makespan). With nonzero startup, serving a slow-link worker first delays all subsequent fast-link workers. The optimal order is non-trivial and must be found by the exact solvers. The star model is also the natural entry point for the energy extension: the four power states (idle, startup, networking, running) map cleanly onto the single-transfer structure.

The Solver Studio is built on the star model. All topology-independent solvers (closed-form, best rate, MILP, FPTAS, energy MILP, Pareto sweep) operate on a star instance. Chain, tree and graph instances are converted to effective star parameters or solved by their own specialised methods.

In a linear chain, processors are connected in a line: node 1 is the originator, node 2 receives load from node 1 and forwards the remainder to node 3, and so on. Each intermediate node keeps a fraction of what it receives and relays the rest downstream. The last node in the chain receives whatever remains after all predecessors have taken their shares. There is no direct link between non-adjacent nodes.

The scheduling problem on a chain has a recursive structure. Node i can only begin receiving its chunk after node i−1 has finished sending its own chunk downstream. There is no overlap between consecutive relay transfers on the same link. This serialisation means the chain accumulates communication delays much faster than a star: the effective startup cost for the k-th node includes the cumulative transfer times of all k−1 preceding transfers, not just its own startup. As a result, chain topologies scale poorly with depth for large startup-to-bandwidth ratios.

Chain instances arise naturally in pipeline architectures, relay networks without a dedicated hub, and streaming data processing where each stage passes processed data to the next. The closed-form DLT solution for the chain follows the same simultaneous-finish principle as the star, but the finish-time recurrences are more complex because each node's start time depends on the entire prefix of transfers rather than only on the originator's schedule.

The tree topology generalises both the star (a tree of depth 1, every node a leaf) and the chain (a tree with branching factor 1). The originator is the root; each internal node receives a chunk from its parent, retains a fraction for local computation, and distributes the remainder among its children. Leaf nodes receive a fraction and compute, with no forwarding. The tree structure allows multiple subtrees to be active simultaneously, which is the primary advantage over the chain.

Distribution within the tree follows the single-port constraint at each node: a node can send to one child at a time. This means an internal node with k children must serve them sequentially, and its own computation cannot begin until it has received its own chunk from its parent. The scheduling problem therefore involves a two-level simultaneous-finish condition: all leaves under a given internal node should finish at the same time, and all subtrees rooted at children of the originator should finish at the global Cmax.

Tree topologies appear in hierarchical HPC cluster architectures (compute nodes grouped into racks, racks grouped into clusters), broadcast-based data distribution systems, and divide-and-conquer parallel frameworks. The DLT solution for trees uses a bottom-up computation of optimal fractions: leaf fractions are computed first from the subtree capacities, and internal node fractions are derived from the residuals. The same simultaneous-finish principle applies at every level of the hierarchy.

A graph topology is the most general case: an arbitrary network where workers may be connected by diverse links with different bandwidths and startup costs, and where multiple paths exist between the originator and a given worker. There is no assumed structure (no star, no chain, no tree); the solver must discover the best distribution structure from the network graph itself.

The key step is selecting a rooted spanning tree (an [arborescence](#term-arborescence)) from the graph along which load will be distributed. Every node in the network is reachable via the chosen arborescence, and once the tree is fixed, the scheduling problem reduces to the tree case above. The complication is that the optimal arborescence is not necessarily the minimum-weight spanning tree: DLT scheduling is sensitive to the depth and ordering of nodes, so a slightly longer total path can be preferable if it reduces the critical path through the bottleneck link.

The graph solver searches over candidate arborescences, evaluates the DLT objective for each, and returns the schedule with the smallest makespan. For small graphs this is tractable by enumeration; for large graphs, heuristic tree selection (shortest-path arborescences, capacity-weighted trees) is used as the search space becomes exponential in the number of edges. Graph topologies model real-world distributed systems where workers are connected through a general network fabric rather than a dedicated hub.