  Modern distributed data management systems face a new challenge: how can
autonomous, mutually-distrusting parties cooperate safely and effectively?
Addressing this challenge brings up questions familiar from classical
distributed systems: how to combine multiple steps into a single atomic action,
how to recover from failures, and how to synchronize concurrent access to data.
Nevertheless, each of these issues requires rethinking when participants are
autonomous and potentially adversarial.
  We propose the notion of a *cross-chain deal*, a new way to structure complex
distributed computations that manage assets in an adversarial setting. Deals
are inspired by classical atomic transactions, but are necessarily different,
in important ways, to accommodate the decentralized and untrusting nature of
the exchange. We describe novel safety and liveness properties, along with two
alternative protocols for implementing cross-chain deals in a system of
independent blockchain ledgers. One protocol, based on synchronous
communication, is fully decentralized, while the other, based on
semi-synchronous communication, requires a globally shared ledger.
