Xavier Défago
Skip Abstract Section
Abstract
Total order broadcast and multicast (also called atomic broadcast/multicast) present an important problem in distributed systems, especially with respect to fault-tolerance. In short, the primitive ensures that messages sent to a set of processes are, in turn, delivered by all those processes in the same total order.
- Abdelzaher, T., Shaikh, A., Jahanian, F., and Shin, K. 1996. RTCAST: Lightweight multicast for real-time process groups. In IEEE Real-Time Technology and Applications Symposium (RTAS'96). (Boston, MA). IEEE Computer Society Press. 250--259.]] Google Scholar
Digital Library
- Agarwal, D. A., Moser, L. E., Melliar-Smith, P. M., and Budhia, R. K. 1998. The Totem multiple-ring ordering and topology maintenance protocol. ACM Trans. Comput. Syst. 16, 2 (May), 93--132.]] Google ScholarDigital Library
- Agrawal, D., Alonso, G., El Abbadi, A., and Stanoi, I. 1997. Exploiting atomic broadcast in replicated databases (extended abstract). In Proceedings of EuroPar'97 (Passau, Germany). Lecture Notes in Computer Science, vol. 1300. Springer-Verlag. 496--503.]] Google ScholarDigital Library
- Aguilera, M. K., Chen, W., and Toueg, S. 1999. Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks. Theor. Comput. Sci. 220, 1 (June), 3--30.]] Google ScholarDigital Library
- Aguilera, M. K., Chen, W., and Toueg, S. 2000. On quiescent reliable communication. SIAM J. Comput. 29, 6, 2040--2073.]] Google ScholarDigital Library
- Aguilera, M. K., Delporte-Gallet, C., Fauconnier, H., and Toueg, S. 2000. Thrifty generic broadcast. In Proceedings of 14th International Symposium on Distributed Computing (DISC'00) (Toledo, Spain). M. Herlihy, Ed. Lecture Notes in Computer Science, vol. 1914. Springer-Verlag. 268--282.]] Google ScholarDigital Library
- Aguilera, M. K. and Strom, R. E. 2000. Efficient atomic broadcast using deterministic merge. In Proceedings of 19th ACM Symposium on Principles of Distributed Computing (PODC-19) (Portland, OR). ACM Press. 209--218.]] Google ScholarDigital Library
- Amir, Y., Dolev, D., Kramer, S., and Malki, D. 1992. Transis: A communication sub-system for high availability. In Proceedings of 22nd International Symposium on Fault-Tolerant Computing (FTCS-22) (Boston, MA). IEEE Computer Society Press. 76--84.]]Google Scholar
- Amir, Y., Moser, L. E., Melliar-Smith, P. M., Agarwal, D. A., and Ciarfella, P. 1995. The Totem single-ring ordering and membership protocol. ACM Trans. Comput. Syst. 13, 4 (Nov.), 311--342.]] Google ScholarDigital Library
- Anceaume, E. 1993a. Algorithmique de fiabilisation de systémes répartis. Ph.D. thesis, Université de Paris-sud (Paris XI), Paris, France.]]Google Scholar
- Anceaume, E. 1993b. A comparison of fault-tolerant atomic broadcast protocols. In Proceedings of 4th IEEE Computer Society Workshop on Future Trends in Distributed Computing Systems (FTDCS-4) (Lisbon, Portugal). IEEE Computer Society Press. 166--172.]]Google ScholarCross Ref
- Anceaume, E. 1997. A lightweight solution to uniform atomic broadcast for asynchronous systems. In Proceedings of 27th International Symposium on Fault-Tolerant Computing (FTCS-27) (Seattle, WA). IEEE Computer Society Press. 292--301.]] Google ScholarDigital Library
- Anceaume, E. and Minet, P. 1992. Étude de protocoles de diffusion atomique. TR 1774, INRIA (Oct.) Rocquencourt, France.]]Google Scholar
- Armstrong, S., Freier, A., and Marzullo, K. 1992. Multicast transport protocol. RFC 1301, IETF (Feb.)]] Google ScholarDigital Library
- Attiya, H. and Welch, J. L. 1994. Sequential consistency versus linearizability. ACM Trans. Comput. Syst. 12, 2 (May), 91--122.]] Google ScholarDigital Library
- Bar-Joseph, Z., Keidar, I., Anker, T., and Lynch, N. 2000. QoS preserving totally ordered multicast. In Proceedings of 4th International Conference on Principles of Distributed Systems (OPODIS). Studia Informatica, Paris, France, 143--162.]]Google Scholar
- Bar-Joseph, Z., Keidar, I., and Lynch, N. 2002. Early-delivery dynamic atomic broadcast. In Proceedings of 16th International Symposium on Distributed Computing (DISC'02) (Toulouse, France). D. Malkhi, Ed. Lecture Notes in Computer Science, vol. 2508. Springer-Verlag. 1--16.]] Google ScholarDigital Library
- Ben-Or, M. 1983. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of 2nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC-2) (Montreal Quebec, Canada). ACM Press. 27--30.]] Google ScholarDigital Library
- Berman, P. and Bharali, A. A. 1993. Quick atomic broadcast (extended abstract). In Proceedings of 7th International Workshop on Distributed Algorithms (WDAG'93) (Lausanne, Switzerland). A. Schiper Ed. Lecture Notes in Computer Science, vol. 725. Springer-Verlag. 189--203.]] Google ScholarDigital Library
- Bernstein, P. A., Hadzilacos, V., and Goodman, N. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Boston, MA. http://research.microsoft.com/pubs/ccontrol/.]] Google ScholarDigital Library
- Bhatti, N. T., Hiltunen, M. A., Schlichting, R. D., and Chiu, W. 1998. Coyote: A system for constructing fine-grain configurable communication services. ACM Trans. Comput. Syst. 16, 4 (Nov.), 321--366.]] Google ScholarDigital Library
- Birman, K. 1994. A response to Cheriton and Skeen's criticism of causal and totally ordered communication. ACM Operat. Syst. Rev. 28, 1 (Jan.), 11--21.]] Google ScholarDigital Library
- Birman, K. and van Renesse, R. 1994. Reliable Distributed Computing with the Isis Toolkit (Los Alamitos, CA). IEEE Computer Society Press.]] Google ScholarDigital Library
- Birman, K. P. and Joseph, T. A. 1987. Reliable communication in the presence of failures. ACM Trans. Comput. Syst. 5, 1 (Feb.), 47--76.]] Google ScholarDigital Library
- Birman, K. P., Schiper, A., and Stephenson, P. 1991. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst. 9, 3 (Aug.), 272-- 314.]] Google ScholarDigital Library
- Carr, R. 1985. The Tandem global update protocol. Tandem Syst. Rev. 1, 2 (June), 74--85.]]Google Scholar
- Chandra, T. D., Hadzilacos, V., and Toueg, S. 1996. The weakest failure detector for solving consensus. J. ACM 43, 4 (July), 685--722.]] Google ScholarDigital Library
- Chandra, T. D. and Toueg, S. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2, 225--267.]] Google ScholarDigital Library
- Chang, J.-M. and Maxemchuk, N. F. 1984. Reliable broadcast protocols. ACM Trans. Comput. Syst. 2, 3 (Aug.), 251--273.]] Google ScholarDigital Library
- Charron-Bost, B., Pedone, F., and Défago, X. 1999. Private communications. (Showed an example illustrating the fact that even the combination of strong agreement, strong total order, and strong integrity does not prevent a faulty process from reaching an inconsistent state.)]]Google Scholar
- Charron-Bost, B., Toueg, S., and Basu, A. 2000. Revisiting safety and liveness in the context of failures. In Concurrency Theory, 11th International Conference (CONCUR 2000) (University Park, PA). Lecture Notes in Computer Science, vol. 1877. Springer-Verlag. 552--565.]] Google ScholarDigital Library
- Chen, X., Moser, L. E., and Melliar-Smith, P. M. 1996. Reservation-based totally ordered multicasting. In Proceedings of 16th IEEE International Conference on Distributed Computing Systems (ICDCS-16) (Hong Kong). IEEE Computer Society Press. 511--519.]] Google ScholarDigital Library
- Cheriton, D. R. and Skeen, D. 1993. Understanding the limitations of causally and totally ordered communication. In Proceedings of 14th ACM Symposium on Operating Systems Principles (SoSP-14) (Ashville, NC). ACM Press. 44--57.]] Google ScholarDigital Library
- Chiu, G.-M. and Hsiao, C.-M. 1998. A note on total ordering multicast using propagation trees. IEEE Trans. Parall. Distrib. Syst. 9, 2 (Feb.), 217--223.]] Google ScholarDigital Library
- Chockler, G., Keidar, I., and Vitenberg, R. 2001. Group communication specifications: A comprehensive study. ACM Comput. Surv. 33, 4 (Dec.), 427--469.]] Google ScholarDigital Library
- Chockler, G. V., Huleihel, N., and Dolev, D. 1998. An adaptive total ordered multicast protocol that tolerates partitions. In Proceedings of 17th ACM Symposium on Principles of Distributed Computing (PODC-17) (Puerto Vallarta, Mexico). ACM Press. 237--246.]] Google ScholarDigital Library
- Chockler, G. V., Malkhi, D., and Reiter, M. K. 2001. Backoff protocols for distributed mutual exclusion and ordering. In Proceedings of 21st IEEE International Conference on Distributed Computing Systems (ICDCS-21) (Phoenix, AZ). IEEE Computer Society Press. 11--20.]] Google ScholarDigital Library
- Chor, B. and Dwork, C. 1989. Randomization in Byzantine Agreement. Adv. Comput. Res. 5, 443--497.]]Google Scholar
- Córdova, J. and Lee, Y.-H. 1996. Multicast trees to provide message ordering in mesh networks. Comput. Syst. Sci. Eng. 11, 1 (Jan.), 3--13.]]Google Scholar
- Cristian, F. 1990. Synchronous atomic broadcast for redundant broadcast channels. Real-Time Syst. 2, 3 (Sept.), 195--212.]] Google ScholarDigital Library
- Cristian, F. 1991. Asynchronous atomic broadcast. IBM Technical Disclosure Bulletin 33, 9, 115--116.]]Google Scholar
- Cristian, F., Aghili, H., Strong, R., and Dolev, D. 1995. Atomic broadcast: From simple message diffusion to Byzantine agreement. Inf. Comput. 18, 1, 158--179.]] Google ScholarDigital Library
- Cristian, F., de Beijer, R., and Mishra, S. 1994. A performance comparison of asynchronous atomic broadcast protocols. Distrib. Syst. Eng. J. 1, 4 (June), 177--201.]]Google Scholar
- Cristian, F. and Fetzer, C. 1999. The timed asynchronous distributed system model. IEEE Trans. Parall. Distrib. Syst. 10, 6 (June), 642--657.]] Google ScholarDigital Library
- Cristian, F. and Mishra, S. 1995. The pinwheel asynchronous atomic broadcast protocols. In Proceedings of 2nd International Symposium on Autonomous Decentralized Systems (Phoenix, AZ). IEEE Computer Society Press. 215-- 221.]]Google Scholar
- Cristian, F., Mishra, S., and Alvarez, G. 1997. High-performance asynchronous atomic broadcast. Distrib. Syst. Eng. J. 4, 2 (June), 109--128.]]Google ScholarCross Ref
- Dasser, M. 1992. TOMP: A total ordering multicast protocol. ACM Operat. Syst. Rev. 26, 1 (Jan.), 32--40.]] Google ScholarDigital Library
- Défago, X. 2000. Agreement-related problems: From semi-passive replication to totally ordered broadcast. Ph.D. thesis, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland. Number 2229.]]Google Scholar
- Défago, X., Schiper, A., and Urbán, P. 2003. Comparative performance analysis of ordering strategies in atomic broadcast algorithms. IEICE Trans. Inf. Syst. E86--D, 12 (Dec.), 2698--2709.]]Google Scholar
- Delporte-Gallet, C. and Fauconnier, H. 1999. Real-time fault-tolerant atomic broadcast. In Proceedings of 18th IEEE International Symposium on Reliable Distributed Systems (SRDS'99) (Lausanne, Switzerland). IEEE Computer Society Press. 48--55.]] Google ScholarDigital Library
- Delporte-Gallet, C. and Fauconnier, H. 2000. Fault-tolerant genuine Atomic Broadcast to multiple groups. In Proceedings of 4th International Conference on Principles of Distributed Systems (OPODIS). Studia Informatica, Paris, France, 143--162.]]Google Scholar
- Dolev, D., Dwork, C., and Stockmeyer, L. 1987. On the minimal synchrony needed for distributed consensus. J. ACM 34, 1 (Jan.), 77--97.]] Google ScholarDigital Library
- Dolev, D., Kramer, S., and Malki, D. 1993. Early delivery totally ordered multicast in asynchronous environments. In Proceedings of 23rd International Symposium on Fault-Tolerant Computing (FTCS-23) (Toulouse, France). IEEE Computer Society Press. 544--553.]]Google Scholar
- Dolev, D. and Malkhi, D. 1994. The design of the Transis system. In Theory and Practice in Distributed Systems, K. Birman, F. Mattern, and A. Schiper, Eds. Lecture Notes in Computer Science, vol. 938. Springer-Verlag, 83--98.]] Google ScholarDigital Library
- Dolev, D. and Malkhi, D. 1996. The Transis approach to high availability cluster communnication. Comm. ACM 39, 4 (April), 64--70.]] Google ScholarDigital Library
- Dwork, C., Lynch, N. A., and Stockmeyer, L. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (April), 288--323.]] Google ScholarDigital Library
- Ekwall, R., Schiper, A., and Urbán, P. 2004. Token-based atomic broadcast using unreliable failure detectors. In Proceedings of 23nd IEEE International Symposium on Reliable Distributed Systems (SRDS'04) (Florianópolis, Brazil). IEEE Computer Society Press. 52--65.]] Google ScholarDigital Library
- Ezhilchelvan, P. D., Macêdo, R. A., and Shrivastava, S. K. 1995. Newtop: A fault-tolerant group communication protocol. In Proceedings of 15th IEEE International Conference on Distributed Computing Systems (ICDCS-15) (Vancouver, Canada). IEEE Computer Society Press. 296--306.]] Google ScholarDigital Library
- Fekete, A. 1993. Formal models of communication services: A case study. IEEE Comput. 26, 8 (Aug.), 37--47.]] Google ScholarDigital Library
- Fekete, A., Lynch, N., and Shvartsman, A. 2001. Specifying and using a partitionable group communication service. ACM Trans. Comput. Syst. 19, 2 (May), 171--216.]] Google ScholarDigital Library
- Felber, P. and Pedone, F. 2002. Probabilistic atomic broadcast. In Proceedings of 21st IEEE International Symposium on Reliable Distributed Systems (SRDS'02) (Osaka, Japan). IEEE Computer Society Press. 170--179.]] Google ScholarDigital Library
- Felber, P. and Schiper, A. 2001. Optimistic active replication. In Proceedings of 21st IEEE International Conference on Distributed Computing Systems (ICDCS-21) (Phoenix, AZ). IEEE Computer Society Press. 333--341.]] Google ScholarDigital Library
- Fetzer, C. 2003. Perfect failure detection in timed asynchronous systems. IEEE Trans. Comput. 52, 2 (Feb.), 99--112.]] Google ScholarDigital Library
- Fischer, M. J., Lynch, N. A., and Paterson, M. S. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April), 374--382.]] Google ScholarDigital Library
- Friedman, R. and van Renesse, R. 1997. Packing messages as a tool for boosting the performance of total ordering protocols. In Proceedings of 6th IEEE Symposium on High Performance Distributed Computing (Portland, OR). IEEE Computer Society Press. 233--242.]] Google ScholarDigital Library
- Fritzke, U., Ingels, P., Mostéfaoui, A., and Raynal, M. 2001. Consensus-based fault-tolerant total order multicast. IEEE Trans. Parall. Distrib. Syst. 12, 2 (Feb.), 147--156.]] Google ScholarDigital Library
- Garcia-Molina, H. and Spauster, A. 1989. Message ordering in a multicast environment. In Proceedings of 9th IEEE International Conference on Distributed Computing Systems (ICDCS-9) (Newport Beach, CA). IEEE Computer Society Press. 354--361.]]Google Scholar
- Garcia-Molina, H. and Spauster, A. 1991. Ordered and reliable multicast communication. ACM Trans. Comput. Syst. 9, 3 (Aug.), 242--271.]] Google ScholarDigital Library
- Gopal, A. and Toueg, S. 1989. Reliable broadcast in synchronous and asynchronous environment. In Proceedings of 3rd International Workshop on Distributed Algorithms (WDAG'89) (Nice, France). Lecture Notes in Computer Science, vol. 392. Springer-Verlag. 111--123.]] Google ScholarDigital Library
- Gopal, A. and Toueg, S. 1991. Inconsistency and contamination. In Proceedings of 10th ACM Symposium on Principles of Distributed Computing (PODC-10). ACM Press. 257--272.]] Google ScholarDigital Library
- Guerraoui, R. 1995. Revisiting the relationship between non-blocking atomic commitment and consensus. In Proceedings of 9th International Workshop on Distributed Algorithms (WDAG'95) (Le Mont-St-Michel, France). Lecture Notes in Computer Science, vol. 972. Springer-Verlag. 87--100.]] Google ScholarDigital Library
- Guerraoui, R. and Schiper, A. 1997. Genuine atomic multicast. In Proceedings of 11th International Workshop on Distributed Algorithms (WDAG'97) (Saarbrücken, Germany). Lecture Notes in Computer Science, vol. 1320. Springer-Verlag. 141--154.]] Google ScholarDigital Library
- Guerraoui, R. and Schiper, A. 2001. Genuine atomic multicast in asynchronous distributed systems. Theor. Comput. Sci. 254, 297-- 316.]] Google ScholarDigital Library
- Guy, R. G., Popek, G. J., and Page Jr., T. W. 1993. Consistency algorithms for optimistic replication. In Proceedings of 1st IEEE International Conference on Network Protocols (ICNP'93) (San Francisco, CA). IEEE Computer Society Press.]]Google ScholarCross Ref
- Hadzilacos, V. and Toueg, S. 1994. A modular approach to fault-tolerant broadcasts and related problems. TR 94-1425, Dept. of Computer Science, Cornell University, Ithaca, NY (May.)]] Google ScholarDigital Library
- Hiltunen, M. A., Schlichting, R. D., Han, X., Cardozo, M. M., and Das, R. 1999. Real-time dependable channels: Customizing QoS attributes for distributed systems. IEEE Trans. Parall. Distrib. Syst. 10, 6 (June), 600--612.]] Google ScholarDigital Library
- Jalote, P. 1998. Efficient ordered broadcasting in reliable CSMA/CD networks. In Proceedings of 18th IEEE International Conference on Distributed Computing Systems (ICDCS-18) (Amsterdam, The Netherlands). IEEE Computer Society Press. 112--119.]] Google ScholarDigital Library
- Jia, X. 1995. A total ordering multicast protocol using propagation trees. IEEE Trans. Parall. Distrib. Syst. 6, 6 (June), 617--627.]] Google ScholarDigital Library
- Kaashoek, M. F. and Tanenbaum, A. S. 1996. An evaluation of the Amoeba group communication system. In Proceedings of 16th IEEE International Conference on Distributed Computing Systems (ICDCS-16) (Hong Kong). IEEE Computer Society Press. 436--447.]] Google ScholarDigital Library
- Keidar, I. and Dolev, D. 2000. Totally ordered broadcast in the face of network partitions. In Dependable Network Computing, D. R. Avresky, Ed. Kluwer Academic Pub., Chapter 3, 51-- 75.]]Google Scholar
- Kemme, B. and Alonso, G. 2000. Don't be lazy, be consistent: Postgres-r, a new way to implement database replication. In Proceedings of 26th International Conference on Very Large Data Bases (VLDB 2000) (Cairo, Egypt). Morgan Kaufmann. 134--143.]] Google ScholarDigital Library
- Kemme, B., Pedone, F., Alonso, G., and Schiper, A. 1999. Processing transactions over optimistic atomic broadcast protocols. In Proceedings of 19th IEEE International Conference on Distributed Computing Systems (ICDCS-19) (Austin, TX). IEEE Computer Society Press. 424--431.]] Google ScholarDigital Library
- Kemme, B., Pedone, F., Alonso, G., Schiper, A., and Wiesmann, M. 2003. Using optimistic atomic broadcast in transaction processing systems. IEEE Trans. Know. Data Eng. 15, 4 (July), 1018--1032.]] Google ScholarDigital Library
- Kim, J. and Kim, C. 1997. A total ordering protocol using a dynamic token-passing scheme. Distrib. Syst. Eng. J. 4, 2 (June), 87--95.]]Google Scholar
- Kopetz, H., Grünsteidl, G., and Reisinger, J. 1991. Fault-tolerant membership service in a synchronous distributed real-time system. In Proceedings of 2nd IFIP International Working Conf. on Dependable Computing for Critical Applications (DCCA-1) (Tucson, AZ). A. Avižienis and J.-C. Laprie, Eds. Springer-Verlag. 411-- 429.]]Google Scholar
- Lamport, L. 1978a. The implementation of reliable distributed multiprocess systems. Comput. Netw. 2, 95--114.]]Google Scholar
- Lamport, L. 1978b. Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 7 (July), 558--565.]] Google ScholarDigital Library
- Lamport, L. 1984. Using time instead of time-outs in fault-tolerant systems. ACM Trans. Program. Lang. Syst. 6, 2, 256--280.]] Google ScholarDigital Library
- Lamport, L. 1986a. The mutual exclusion problem: Part I---a theory of interprocess communication. J. ACM 33, 2 (April), 313--326.]] Google ScholarDigital Library
- Lamport, L. 1986b. On interprocess communication. part I: Basic formalism. Distrib. Comput. 1, 2, 77--85.]]Google ScholarCross Ref
- Lamport, L., Shostak, R., and Pease, M. 1982. The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4, 3, 382--401.]] Google ScholarDigital Library
- Le Lann, G. and Bres, G. 1991. Reliable atomic broadcast in distributed systems with omission faults. ACM Operat. Syst. Rev. SIGOPS 25, 2 (April), 80--86.]] Google ScholarDigital Library
- Liu, X., van Renesse, R., Bickford, M., Kreitz, C., and Constable, R. 2001. Protocol switching: Exploiting meta-properties. In Proceedings of 21st IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW'01), Intl. Workshop on Applied Reliable Group Communication (WARGC 2001) (Mesa, AZ). IEEE Computer Society Press. 37--42.]] Google ScholarDigital Library
- Luan, S.-W. and Gligor, V. D. 1990. A fault-tolerant protocol for atomic broadcast. IEEE Trans. Parall. Distrib. Syst. 1, 3 (July), 271--285.]] Google ScholarDigital Library
- Lynch, N. A. 1996. Distributed Algorithms. Morgan Kaufmann, San Francisco, CA.]] Google ScholarDigital Library
- Lynch, N. A. and Tuttle, M. R. 1989. An introduction to input/output automata. CWI Quarterly 2, 3 (Sept.), 219--246.]]Google Scholar
- Malhis, L. M., Sanders, W. H., and Schlichting, R. D. 1996. Numerical performability evaluation of a group multicast protocol. Distrib. Syst. Eng. J. 3, 1 (March), 39--52.]]Google Scholar
- Malloth, C. P. 1996. Conception and implementation of a toolkit for building fault-tolerant distributed applications in large scale networks. Ph.D. thesis, École Polytechnique Fédérale de Lausanne, Switzerland. Number 1557.]]Google Scholar
- Malloth, C. P., Felber, P., Schiper, A., and Wilhelm, U. 1995. Phoenix: A toolkit for building fault-tolerant distributed applications in large scale. In Workshop on Parallel and Distributed Platforms in Industrial Products; 7th IEEE Symposium on Parallel and Distributed Processing. San Antonio, TX.]]Google Scholar
- Mayer, E. 1992. An evaluation framework for multicast ordering protocols. In Proceedings of ACM International Conference on Applications, Technologies, Architecture, and Protocols (SIGCOMM) (Baltimore, Maryland). ACM Press. 177--187.]] Google ScholarDigital Library
- Minet, P. and Anceaume, E. 1991a. ABP: An atomic broadcast protocol. TR 1473, INRIA (June). Rocquencourt, France.]]Google Scholar
- Minet, P. and Anceaume, E. 1991b. Atomic broadcast in one phase. ACM Operat. Syst. Rev. 25, 2 (April), 87--90.]] Google ScholarDigital Library
- Mishra, S., Peterson, L. L., and Schlichting, R. D. 1993. Consul: a communication substrate for fault-tolerant distributed programs. Distrib. Syst. Eng. J. 1, 1, 87--103.]]Google ScholarCross Ref
- Moser, L. E. and Melliar-Smith, P. M. 1999. Byzantine-resistant total ordering algorithms. Inf. Comput. 150, 1 (April), 75--111.]] Google ScholarDigital Library
- Moser, L. E., Melliar-Smith, P. M., Agrawal, D. A., Budhia, R. K., and Lingley-Papadopoulos, C. A. 1996. Totem: A fault-tolerant multicast group communication system. Comm. ACM 39, 4 (April), 54--63.]] Google ScholarDigital Library
- Moser, L. E., Melliar-Smith, P. M., and Agrawala, V. 1993. Asynchronous fault-tolerant total ordering algorithms. SIAM J. Comput. 22, 4 (Aug.), 727--750.]] Google ScholarDigital Library
- Mostéfaoui, A. and Raynal, M. 2000. Low cost consensus-based atomic broadcast. In Proceedings of 7th IEEE Pacific Rim Symposium on Dependable Computing (PRDC'00) (Los Angeles, CA). IEEE Computer Society Press. 45--52.]] Google ScholarDigital Library
- Navaratnam, S., Chanson, S. T., and Neufeld, G. W. 1988. Reliable group communication in distributed systems. In Proceedings of 8th IEEE International Conference on Distributed Computing Systems (ICDCS-8) (San Jose, CA). IEEE Computer Society Press. 439--446.]]Google Scholar
- Neiger, G. and Toueg, S. 1990. Automatically increasing the fault-tolerance of distributed algorithms. J. Algorithms 11, 3, 374--419.]] Google ScholarDigital Library
- Nestmann, U., Fuzzati, R., and Merro, M. 2003. Modeling consensus in a process calculus. In (CONCUR 2003) Concurrency Theory, 14th International Conference (Marseille, France). R. M. Amadio and D. Lugiez, Eds. Lecture Notes in Computer Science, vol. 2761. Springer-Verlag. 393--407.]]Google Scholar
- Ng, T. P. 1991. Ordered broadcasts for large applications. In Proceedings of 10th IEEE International Symposium on Reliable Distributed Systems (SRDS'91) (Pisa, Italy). IEEE Computer Society Press. 188--197.]]Google ScholarCross Ref
- Pedone, F. 2001. Boosting system performance with optimistic distributed protocols. IEEE Comput. 34, 12 (Dec.), 80--86.]] Google ScholarDigital Library
- Pedone, F., Guerraoui, R., and Schiper, A. 1998. Exploiting atomic broadcast in replicated databases. In Proceedings of EuroPar (EuroPar'98) (Southampton, UK). Lecture Notes in Computer Science, vol. 1470. Springer-Verlag. 513--520.]] Google ScholarDigital Library
- Pedone, F. and Schiper, A. 1998. Optimistic atomic broadcast. In Proceedings of 12th International Symposium on Distributed Computing (DISC'98) (Andros, Greece). Lecture Notes in Computer Science, vol. 1499. Springer-Verlag. 318--332.]] Google ScholarDigital Library
- Pedone, F. and Schiper, A. 1999. Generic broadcast. In Proceedings of 13th International Symposium on Distributed Computing (DISC'99) (Bratislava, Slovak Republic). Lecture Notes in Computer Science, vol. 1693. Springer-Verlag. 94--108.]] Google ScholarDigital Library
- Pedone, F. and Schiper, A. 2002. Handling message semantics with generic broadcast protocols. Distrib. Comput. 15, 2, 97--107.]] Google ScholarDigital Library
- Pedone, F. and Schiper, A. 2003. Optimistic atomic broadcast: A pragmatic viewpoint. Theor. Comput. Sci. 291, 79--101.]] Google ScholarDigital Library
- Pedone, F., Schiper, A., Urbán, P., and Cavin, D. 2002. Solving agreement problems with weak ordering oracles. In Proceedings of 4th European Dependable Computing Conference (EDCC-4) (Toulouse, France). Lecture Notes in Computer Science, vol. 2485. Springer-Verlag. 44-- 61.]] Google ScholarDigital Library
- Peterson, L. L., Buchholz, N. C., and Schlichting, R. D. 1989. Preserving and using context information in interprocess communication. ACM Trans. Comput. Syst. 7, 3, 217--246.]] Google ScholarDigital Library
- Poledna, S. 1994. Replica determinism in distributed real-time systems: A brief survey. Real-Time Syst. 6, 3 (May), 289--316.]] Google ScholarDigital Library
- Rabin, M. 1983. Randomized Byzantine generals. In Proceedings of 24th Annual ACM Symposium on Foundations of Computer Science (FOCS) (Tucson, AZ). ACM Press. 403--409.]]Google ScholarDigital Library
- Rajagopalan, B. and McKinley, P. 1989. A token-based protocol for reliable, ordered multicast communication. In Proceedings of 8th IEEE International Symposium on Reliable Distributed Systems (SRDS'89) (Seattle, WA). IEEE Computer Society Press. 84--93.]]Google ScholarCross Ref
- Reiter, M. K. 1994. Secure agreement protocols: Reliable and atomic group multicast in Rampart. In Proceedings of 2nd ACM Conf. on Computer and Communications Security (CCS-2) (Fairfax, VA). ACM Press. 68--80.]] Google ScholarDigital Library
- Reiter, M. K. 1996. Distributing trust with the Rampart toolkit. Comm. ACM 39, 4 (April), 71--74.]] Google ScholarDigital Library
- Rodrigues, L., Fonseca, H., and Veríssimo, P. 1996. Totally ordered multicast in large-scale systems. In Proceedings of 16th IEEE International Conference on Distributed Computing Systems (ICDCS-16) (Hong Kong). IEEE Computer Society Press. 503--510.]] Google ScholarDigital Library
- Rodrigues, L., Guerraoui, R., and Schiper, A. 1998. Scalable atomic multicast. In Proceedings of 7th IEEE International Conference on Computer Communications and Networks (Lafayette, LA). IEEE Computer Society Press. 840-- 847.]] Google ScholarDigital Library
- Rodrigues, L. T. and Raynal, M. 2000. Atomic broadcast in asynchronous crash-recovery distributed systems. In Proceedings of 20th IEEE International Conference on Distributed Computing Systems (ICDCS-20) (Taipei, Taiwan). IEEE Computer Society Press. 288-- 295.]] Google ScholarDigital Library
- Rodrigues, L. T. and Veríssimo, P. 1992. xAMP: a multi-primitive group communications service. In Proceedings of 11th IEEE International Symposium on Reliable Distributed Systems (SRDS'92) (Houston, TX). IEEE Computer Society Press. 112--121.]]Google Scholar
- Rodrigues, L. T., Veríssimo, P., and Casimiro, A. 1993. Using atomic broadcast to implement a posteriori agreement for clock synchronization. In Proceedings of 12th IEEE International Symposium on Reliable Distributed Systems (SRDS'93) (Princeton, NJ). IEEE Computer Society Press. 115--124.]]Google Scholar
- Schiper, A. and Raynal, M. 1996. From group communication to transactions in distributed systems. Comm. ACM 39, 4 (April), 84--87.]] Google ScholarDigital Library
- Schneider, F. B. 1990. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22, 4 (Dec.), 299--319.]] Google ScholarDigital Library
- Shieh, S.-P. and Ho, F.-S. 1997. A comment on "a total ordering multicast protocol using propagation trees''. IEEE Trans. Parall. Distrib. Syst. 8, 10 (Oct.), 1084.]] Google ScholarDigital Library
- Shrivastava, S. K. 1994. To CATOCS or not to CATOCS, that is the… ACM Operat. Syst. Rev. 28, 4 (Oct.), 11--14.]] Google ScholarDigital Library
- Sousa, A., Pereira, J., Moura, F., and Oliveira, R. 2002. Optimistic total order in wide area networks. In Proceedings of 21st IEEE International Symposium on Reliable Distributed Systems (SRDS'02) (Osaka, Japan). IEEE Computer Society Press. 190--199.]] Google ScholarDigital Library
- Toinard, C., Florin, G., and Carrez, C. 1999. A formal method to prove ordering properties of multicast algorithms. ACM Operat. Syst. Rev. 33, 4 (Oct.), 75--89.]] Google ScholarDigital Library
- Urbán, P., Défago, X., and Schiper, A. 2000. Contention-aware metrics for distributed algorithms: Comparison of atomic broadcast algorithms. In Proceedings of 9th IEEE International Conference on Computer Communications and Networks (IC3N'00) (Las Vegas, NV). IEEE Computer Society Press. 582--589.]]Google Scholar
- Urbán, P., Shnayderman, I., and Schiper, A. 2003. Comparison of failure detectors and group membership: Performance study of two atomic broadcast algorithms. In Proceedings of IEEE International Conference on Dependable Systems and Networks (DSN'03) (San Francisco, CA). IEEE Computer Society Press. 645--654.]]Google Scholar
- Veríssimo, P., Rodrigues, L., and Baptista, M. 1989. AMp: A highly parallel atomic multicast protocol. Comput. Comm. Rev. 19, 4 (Sept.), 83-- 93.]] Google ScholarDigital Library
- Vicente, P. and Rodrigues, L. 2002. An indulgent uniform total order algorithm with optimistic delivery. In Proceedings of 21st IEEE International Symposium on Reliable Distributed Systems (SRDS'02) (Osaka, Japan). IEEE Computer Society Press. 92--101.]] Google ScholarDigital Library
- Whetten, B., Montgomery, T., and Kaplan, S. 1994. A high performance totally ordered multicast protocol. In Theory and Practice in Distributed Systems (Dagstuhl Castle, Germany). K. P. Birman, F. Mattern, and A. Schiper, Eds. Lecture Notes in Computer Science, vol. 938. Springer-Verlag. 33--57.]] Google ScholarDigital Library
- Wiesmann, M., Pedone, F., Schiper, A., Kemme, B., and Alonso, G. 2000. Understanding replication in databases and distributed systems. In Proceedings of 20th IEEE International Conference on Distributed Computing Systems (ICDCS-20) (Taipei, Taiwan). IEEE Computer Society Press. 264--274.]] Google ScholarDigital Library
- Wilhelm, U. and Schiper, A. 1995. A hierarchy of totally ordered multicasts. In Proceedings of 14th IEEE International Symposium on Reliable Distributed Systems (SRDS'95) (Bad Neuenahr, Germany). IEEE Computer Society Press. 106--115.]] Google ScholarDigital Library
- Zhou, P. and Hooman, J. 1995. Formal specification and compositional verification of an atomic broadcast protocol. Real-Time Syst. 9, 2 (Sept.), 119--145.]] Google ScholarDigital Library
Index Terms
- Total order broadcast and multicast algorithms: Taxonomy and survey
Recommendations
A classification of total order specifications and its application to fixed sequencer-based implementations
During the last two decades the design and development of total order (TO) communications has been one of the main research topics in dependable distributed computing. The huge amount of research work has produced several TO specifications and a wide ...
Handling message semantics with Generic Broadcast protocols
Message ordering is a fundamental abstraction in distributed systems. However, ordering guarantees are usually purely "syntactic," that is, message "semantics" is not taken into consideration despite the fact that in several cases semantic information ...
Total Order Multicast to Multiple Groups
ICDCS '97: Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97)We present a fault-tolerant algorithm that ensures total order delivery of messages sent to multiple groups of processes. Our algorithm is a multiple group ``genuine'' multicast algorithm in the sense that (1) any process can send a message to any set ...
Comments