In this paper, we show that distributed systems are vul- nerable to routing attacks and propose an architecture to obviate this vulnerability. A somewhat surprising finding is that even a small-scale routing attack can completely dis- rupt the operation of a state-machine replication service. The architecture that we propose is based on the following simple ideas: (1) Circumvent the adversary if possible and (2) if it is not possible, relax the application semantics.