  We give optimally fast $O(\log p)$ time (per processor) algorithms for
computing round-optimal broadcast schedules for message-passing parallel
computing systems. This affirmatively answers difficult questions posed in a
SPAA 2022 BA and a CLUSTER 2022 paper. We observe that the computed schedules
and circulant communication graph can likewise be used for reduction,
all-broadcast and all-reduction as well, leading to new, round-optimal
algorithms for these problems. These observations affirmatively answer open
questions posed in a CLUSTER 2023 paper.
  The problem is to broadcast $n$ indivisible blocks of data from a given root
processor to all other processors in a (subgraph of a) fully connected network
of $p$ processors with fully bidirectional, one-ported communication
capabilities. In this model, $n-1+\lceil\log_2 p\rceil$ communication rounds
are required. Our new algorithms compute for each processor in the network
receive and send schedules each of size $\lceil\log_2 p\rceil$ that determine
uniquely in $O(1)$ time for each communication round the new block that the
processor will receive, and the already received block it has to send. Schedule
computations are done independently per processor without communication. The
broadcast communication subgraph is an easily computable, directed,
$\lceil\log_2 p\rceil$-regular circulant graph also used elsewhere. We show how
the schedule computations can be done in optimal time and space of $O(\log p)$,
improving significantly over previous results of $O(p\log^2 p)$ and $O(\log^3
p)$, respectively. The schedule computation and broadcast algorithms are simple
to implement, but correctness and complexity are not obvious. The schedules are
used for new implementations of the MPI (Message-Passing Interface) collectives
MPI_Bcast, MPI_Allgatherv, MPI_Reduce and MPI_Reduce_scatter. Preliminary
experimental results are given.
