The paper presents a primary-backup protocol to manage replicated in-memory database systems (IMDBs). The protocol exploits two features of IMDBs: coarse-grain concurrency control and deferred disk writes. Primary crashes are quickly detected by backups and a new primary is elected whenever the current one is suspected to have failed. False failure suspicions are tolerated and never lead to incorrect behavior. The protocol uses a consensus-like algorithm tailor-made for our replication environment. Under normal circumstances (i.e., no failures or false suspicions), transactions can be committed after two communication steps, as seen by the applications. Performance experiments have shown that the protocol has very low overhead and scales linearly with the number of replicas. © 2006 IEEE.2006 204211Agrawal, D., Alonso, G., Abbadi, A.E., Stanoi, I., Exploiting atomic broadcast in replicated databases (1997) Proceedings of EuroPar (EuroPar'97), , Passau Germany, SeptAmir, Y., Tutu, C., From total order to database replication (2002) International Conference on Distributed Computing Systems (ICDCS), , JulyBernstein, P., Hadzilacos, V., Goodman, N., (1987) Concurrency Control and Recovery in Database Systems, , Addison-WesleyBlott, S., Korth, H.F., An almost-serial protocol for transaction execution in main-memory database systems (2002) Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), pp. 706-717Camargos, L., Pedone, F., Schmidt, R., A primary-backup protocol for main-memory database replication Technical Report LABOS-REPORT-2006-01, EPFL, 2006Chandra, T.D., Toueg, S., Unreliable failure detectors for reliable distributed systems (1996) Journal of the ACM, 43 (2), pp. 225-267. , MarChockler, G., Malkhi, D., Active disk paxos with infinitely many processes (2005) Distributed Computing, 18 (1), pp. 73-84Dutta, P., Frølund, F., Guerraoui, R., Pochon, B., An efficient universal construction for message-passing systems (2002) LNCS, pp. 133-147. , Proceedings of the 16th International Symposium on Distributed Computing DISC'02, Springer-Verlag, OctoberFelber, P., Schiper, A., Optimistic active replication (2001) Proceedings of 21st International Conference on Distributed Computing SystemsThe FirstSQL/J in-memory database system, , http://www.firstsql.com, FirstSQL IncGarcia-Molina, H., Salem, K., Main memory database systems: An overview (1992) IEEE Transactions on Knowledge and Data Engineering, 4 (6), pp. 509-516Gray, J., Lamport, L., Consensus on transaction commit Technical Report MSR-TR-2003-96, Microsoft, 2003Gray, J.N., Heiland, P., O'Neil, P., Shasha, D., The dangers of replication and a solution (1996) Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, , Montreal Canada, JuneHolliday, J., Agrawal, D., Abbadi, A.E., The performance of database replication with group multicast (1999) Proceedings of International Symposium on Fault Tolerant Computing (FTCS29), pp. 158-165. , IEEE Computer SocietyKemme, B., Alonso, G., Don't be lazy, be consistent: Postgres-r, a new way to implement database replication (2000) Proceedings of 26th International Conference on Very Large Data Bases, , SeptKemme, B., Alonso, G., A new approach ro developing and implementing eager database replication protocols (2000) ACM Transactions on Database Systems (TODS), 25 (3). , SeptemberLamport, L., The part-time parliament (1998) ACM Transactions on Computer Systems, 16 (2), pp. 133-169. , MayLamport, L., (2004), Lower bounds on consensus algorithms. Private communicationLamport, L., Massa, M., Cheap paxos (2004) Proceedings of the International Conference on Dependable Systems and Networks (DSN'2004), , JulyPapathanasiou, A.E., Markatos, E.P., Lightweight transactions on networks of workstations (1998) Proceedings of the the 18th International Conference on Distributed Computing Systems (ICDCS'98), pp. 544-552. , Washington, DC, USAPatino-Martínez, M., Jiménez-Peris, R., Kemme, B., Alonso, G., Scalable replication in database clusters (2000) Disctributed Computing (DISC)Pedone, F., Frølund, S., Pronto: A fast failover protocol for off-the-shelf commercial databases (2000) Proceedings of 19th IEEE Symposium on Reliable Distributed Systems (SRDS'2000), , Nürnberg, GermanyPedone, F., Guerraoui, R., Schiper, A., Transaction reordering in replicated databases (1997) Proceedings of the 16th IEEE Symposium on Reliable Distributed Systems, , Durham USA, OctPedone, F., Schiper, A., Urban, P., Cavin, D., Solving agreement problems with weak ordering oracles (2002) 4th European Dependable Computing Conference (EDCC-4), , Toulouse, France, OctPfister, G.F., (1998) In search of clusters, , Prentice HallRabin, M., Randomized byzantine generals (1983) Proceedings of 24 th Annual ACM Symposium on Foundations of Computer ScienceRodrigues, L., Miranda, H., Almeida, R., Martins, J., Vicente, P., Strong replication in the GLOBDATA middleware (2002) Workshop on Dependable Middleware-Based SystemsSavarese, D.F., Sterling, T., Beowulf (1999) High Performance Cluster Computing, 1, pp. 625-645. , Architectures and Systems, Prentice Hall PTRZhou, Y., Chen, P., Li, K., Fast cluster failover using virtual memory-mapped communication. Technical Report TR591-99, Princeton University (1999), Jan