We address the problem of message-parsimonious asynchronous atomic broadcast when a subset t out of n parties may exhibit Byzantine behavior. Message parsimony involves using only the optimal O(n) message exchanges per atomically delivered payload in the normal case. Message parsimony is desirable for Internet-like deployment environments in which message loss rates are non-negligible. Protocol PABC, the only previously-known message-parsimonious solution, suffered from two limitations vis-à-vis the solutions with O(n2) message complexity: more communication steps and the use of digital signatures. We present a protocol termed AMP that for the first time provides signature-free message parsimony while at the same time reducing the number of communication steps to the minimum necessary. In contrast to many previous atomic broadcast solutions, our protocol satisfies both safety and liveness in the asynchronous model. © 2007 IEEE.