  We present a totally asynchronous algorithm for convex optimization that is
based on a novel generalization of Nesterov's accelerated gradient method. This
algorithm is developed for fast convergence under "total asynchrony," i.e.,
allowing arbitrarily long delays between agents' computations and
communications without assuming any form of delay bound. These conditions may
arise, for example, due to jamming by adversaries. Our framework is
block-based, in the sense that each agent is only responsible for computing
updates to (and communicating the values of) a small subset of the
network-level decision variables. In our main result, we present bounds on the
algorithm's parameters that guarantee linear convergence to an optimizer. Then,
we quantify the relationship between (i) the total number of computations and
communications executed by the agents and (ii) the agents' collective distance
to an optimum. Numerical simulations show that this algorithm requires 28%
fewer iterations than the heavy ball algorithm and 61% fewer iterations than
gradient descent under total asynchrony.
