Descriptions may be stale. Consult the linked Lean sources.
Star Network
Oracle Model
We consider distributed computation on a star with hub and workers, indexed by . Inputs and outputs belong
to arbitrary sets and
. Worker returns for input , shared random seed , and completed-computation count
, after time . A message of transmitted bits takes , where . 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 . The network
parameters are Let be a measurable seed space
with probability law . The
computation maps are 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 at time with input becomes available at time When this evaluation is
delivered, the oracle returns the pair where 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 to node is accepted only on a directed
hub–worker link, that is, 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 with transmitted string , its delivery time is where is its bit length. When used through
the distributed execution interface, a payload of bits is extended by zero bits, so its communication time
is 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
is drawn and shared by all
workers throughout the computation. Worker uses on its th 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 .
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.