Trading across chains (e.g. Litecoin for Bitcoin) has actually already been solved. Take a look at CoinSwap; the algorithm works even if A->B and C->D are on different chains!

At this point it's just a matter of someone actually implementing the protocol.