← All setups

Star Network Oracle Model

Descriptions may be stale. Consult the linked Lean sources.

Star Network Oracle Model

We consider distributed computation on a star with hub 0 and n≥0 workers, indexed by i=1,…,n. Inputs and outputs belong to arbitrary sets X and Y. Worker i returns Ci(x,Z,k)∈Y for input x∈X, shared random seed Z∼P, and completed-computation count k≥0, after time ci≥0. A message of b transmitted bits takes ℓ+βb, where ℓ,β≥0. Computations and directed links each admit one pending request. This model specifies oracle access and elapsed-time costs; it does not specify an optimization objective or accuracy requirement.

The hub communicates directly with every worker. Computation is available only at the workers. Time takes values in R≥0. The network parameters are n∈Z≥0,(c1,…,cn)∈R≥0n,ℓ,β∈R≥0. Let S be a measurable seed space with probability law P. The computation maps are Ci:X×S×Z≥0⟶Y,i=1,…,n. The model does not distinguish algorithm inputs from hidden parameters.

Our assumptions:

Assumption 1 (Worker computation). Initially, each worker is idle and its completed-computation count is zero. An evaluation submitted to idle worker i at time t with input x becomes available at time t+ci. When this evaluation is delivered, the oracle returns the pair (x,Ci(x,Z,k)), where k is that worker’s count immediately before delivery. Delivery clears the pending evaluation and increments the count by one. An evaluation submitted while another evaluation is pending at the same worker is ignored. An abort request clears the pending evaluation without changing the count. The hub produces no computation replies.

Assumption 2 (Communication and concurrency). Messages are finite binary strings. A transmission from node u to node v is accepted only on a directed hub–worker link, that is, (u=0 and v≠0)or(u≠0 and v=0). Each directed link holds at most one pending message; another submission on that link is ignored until the pending message is delivered. Distinct directed links operate concurrently, including the two directions of a hub–worker connection. Worker computations can also proceed concurrently with one another and with communication.

For a message submitted at time t with transmitted string m, its delivery time is t+ℓ+β|m|, where |m| is its bit length. When used through the distributed execution interface, a payload of b bits is extended by 64 zero bits, so its communication time is ℓ+β(b+64). A delivered message identifies its source and contains the transmitted string. Among pending messages, delivery selects one with the earliest delivery time, provided that time has been reached, and then frees its directed link.

Assumption 3 (Shared randomness). A single seed Z∼P is drawn and shared by all workers throughout the computation. Worker i uses Ci(x,Z,k) on its kth completed evaluation, counting from zero. Consequently, replies may depend across workers and across successive evaluations through the same seed. Any algorithm randomness is independent of Z.

Resource budgets in this model measure elapsed time, accounting for computation delays, communication latency, and transmitted bits. No particular distributed method, output rule, optimization task, or numerical success criterion is specified by this network model.

Results

    Lean setup