  We present a parallelized primal-dual algorithm for solving constrained
convex optimization problems. The algorithm is "block-based," in that vectors
of primal and dual variables are partitioned into blocks, each of which is
updated only by a single processor. We consider four possible forms of
asynchrony: in updates to primal variables, updates to dual variables,
communications of primal variables, and communications of dual variables. We
explicitly construct a family of counterexamples to rule out permitting
asynchronous communication of dual variables, though the other forms of
asynchrony are permitted, all without requiring bounds on delays. A first-order
update law is developed and shown to be robust to asynchrony. We then derive
convergence rates to a Lagrangian saddle point in terms of the operations
agents execute, without specifying any timing or pattern with which they must
be executed. These convergence rates contain a synchronous algorithm as a
special case and are used to quantify an "asynchrony penalty." Numerical
results illustrate these developments.
