  In this paper, we consider the convergence of a very general
asynchronous-parallel algorithm called ARock, that takes many well-known
asynchronous algorithms as special cases (gradient descent, proximal gradient,
Douglas Rachford, ADMM, etc.). In asynchronous-parallel algorithms, the
computing nodes simply use the most recent information that they have access
to, instead of waiting for a full update from all nodes in the system. This
means that nodes do not have to waste time waiting for information, which can
be a major bottleneck, especially in distributed systems. When the system has
$p$ nodes, asynchronous algorithms may complete $\Theta(\ln(p))$ more
iterations than synchronous algorithms in a given time period ("more iterations
per second").
  Although asynchronous algorithms may compute more iterations per second,
there is error associated with using outdated information. How many more
iterations in total are needed to compensate for this error is still an open
question. The main results of this paper aim to answer this question. We prove,
loosely, that as the size of the problem becomes large, the number of
additional iterations that asynchronous algorithms need becomes negligible
compared to the total number ("same quality" of the iterations). Taking these
facts together, our results provide solid evidence of the potential of
asynchronous algorithms to vastly speed up certain distributed computations.
