  The ability to distribute high-quality entanglement between remote parties is
a necessary primitive for many quantum communication applications. A large
range of schemes for realizing the long-distance delivery of remote
entanglement has been proposed, both for bipartite and multipartite
entanglement. For assessing the viability of these schemes, knowledge of the
time at which entanglement is delivered is crucial. Specifically, if the
communication task requires multiple remote-entangled quantum states and these
states are generated at different times by the scheme, the earlier states will
need to wait and thus their quality will decrease while being stored in an
(imperfect) memory. For the remote-entanglement delivery schemes which are
closest to experimental reach, this time assessment is challenging, as they
consist of nondeterministic components such as probabilistic entanglement
swaps. For many such protocols even the average time at which entanglement can
be distributed is not known exactly, in particular when they consist of
feedback loops and forced restarts. In this work, we provide improved
analytical bounds on the average and on the quantiles of the completion time of
entanglement distribution protocols in the case that all network components
have success probabilities lower bounded by a constant. A canonical example of
such a protocol is a nested quantum repeater scheme which consists of heralded
entanglement generation and entanglement swaps. For this scheme specifically,
our results imply that a common approximation to the mean entanglement
distribution time, the 3-over-2 formula, is in essence an upper bound to the
real time. Our results rely on a novel connection with reliability theory.
