Distributed transactions generally use 2 phase-commit (2PC). If message loss happens, the 2PC algorithm will block, i.e. the transaction can neither be committed nor aborted. When the network gets reliable again, the algorithm will finish. So strong consistency isn't really affected by this problem.

A special case would be if the network is broken only in one direction. In that case, the same command may be sent multiple times, but even this is not a problem, since the 2PC commands are idempotent (e.g. receiving the Commit-message multiple times won't hurt, since the receiving node knows that it has already committed the transaction).

You can guarantee consistency; but what you must then lose is the ability to make progress in all situations ('liveness').

A trivial commit protocol that is consistent but not live simply sends no messages. All updates that succeed are consistent, but no updates succeed.

An eventually consistent protocol is often correct for stronger consistency guarantees, but instead sacrifices consistency in the case of network problems rather than liveness.

(sidebar: this is really what the CAP theorem is driving at. You must choose between consistency and liveness if the network can lose messages).

There is also the Paxos algorithm:

http://en.wikipedia.org/wiki/Paxos_algorithm

(Bigtable uses 'Chubby' - google's implementation of Paxos)