Due to the extensive use of computers and networks in critical systems, survivability is no longer a luxury but an essential requirement. We consider survivability assurance for critical applications where the system may incur accidental failures as well as intentional attacks. A successful attack can penetrate and compromise a part of the system and, consequently, make the system behave like incurring a malicious failure. We model successful attacks as Byzantine failures and use the replication scheme to uniformly cope with failures and attacks. Instead of using conventional replication protocols that generally have a high overhead, we develop a novel coordination protocol, namely, Adaptive NMR (ANMR) algorithm, to provide efficient coordination among replicated sites. Also, a special data partitioning technique is used with ANMR to assure confidentiality of the system even if it is partially compromised. Due to the adaptive nature, our ANMR algorithm reduces the communication overhead incurred in conventional NMR schemes. When there is no failure, the system operates at a very good performance. When failures occur, the system adapts to the NMR scheme gracefully.