The problem of atomic cross-chain trading is one where (at least) two parties, Alice and Bob, own coins in separate cryptocurrencies (e.g. Bitcoin and Litecoin), and want to exchange them without having to trust a third party (centralized exchange).
A non-atomic trivial solution would have Alice send her Bitcoins to Bob, and then have Bob send Litecoins to Alice - but Bob has the option of going back on his end of the bargain and simply not following through with the protocol, ending up with both Bitcoins and Litecoins.
Here is one description of an algorithm that solves this problem, credit goes to TierNolan for this specific description (the algorithm was described in other terms by other people including Mike Hearn above).
A picks a random number x A creates TX1: "Pay w BTC to <B's public key> if (x for H(x) known and signed by B) or (signed by A & B)" A creates TX2: "Pay w BTC from TX1 to <A's public key>, locked 48 hours in the future, signed by A" A sends TX2 to B B signs TX2 and returns to A 1) A submits TX1 to the network B creates TX3: "Pay v alt-coins to <A-public-key> if (x for H(x) known and signed by A) or (signed by A & B)" B creates TX4: "Pay v alt-coins from TX3 to <B's public key>, locked 24 hours in the future, signed by B" B sends TX4 to A A signs TX4 and sends back to B 2) B submits TX3 to the network 3) A spends TX3 giving x 4) B spends TX1 using x This is atomic (with timeout). If the process is halted, it can be reversed no matter when it is stopped. Before 1: Nothing public has been broadcast, so nothing happens Between 1 & 2: A can use refund transaction after 72 hours to get his money back Between 2 & 3: B can get refund after 24 hours. A has 24 more hours to get his refund After 3: Transaction is completed by 2 - A must spend his new coin within 24 hours or B can claim the refund and keep his coins - B must spend his new coin within 72 hours or A can claim the refund and keep his coins For safety, both should complete the process with lots of time until the deadlines.