article

Total order broadcast and multicast algorithms: Taxonomy and survey

Authors:

Xavier Défago,

André Schiper,

Péter UrbánAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 36, Issue 4

Pages 372 - 421

https://doi.org/10.1145/1041680.1041682

Published: 01 December 2004 Publication History

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.

References

[1]

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.]]

Digital Library

[2]

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.]]

Digital Library

[3]

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.]]

Digital Library

[4]

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.]]

Digital Library

[5]

Aguilera, M. K., Chen, W., and Toueg, S. 2000. On quiescent reliable communication. SIAM J. Comput. 29, 6, 2040--2073.]]

Digital Library

[6]

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.]]

Digital Library

[7]

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.]]

Digital Library

[8]

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.]]

[9]

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.]]

Digital Library

[10]

Anceaume, E. 1993a. Algorithmique de fiabilisation de systémes répartis. Ph.D. thesis, Université de Paris-sud (Paris XI), Paris, France.]]

[11]

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.]]

[12]

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.]]

Digital Library

[13]

Anceaume, E. and Minet, P. 1992. Étude de protocoles de diffusion atomique. TR 1774, INRIA (Oct.) Rocquencourt, France.]]

[14]

Armstrong, S., Freier, A., and Marzullo, K. 1992. Multicast transport protocol. RFC 1301, IETF (Feb.)]]

Digital Library

[15]

Attiya, H. and Welch, J. L. 1994. Sequential consistency versus linearizability. ACM Trans. Comput. Syst. 12, 2 (May), 91--122.]]

Digital Library

[16]

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.]]

[17]

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.]]

Digital Library

[18]

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.]]

Digital Library

[19]

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.]]

Digital Library

[20]

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/.]]

Digital Library

[21]

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.]]

Digital Library

[22]

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.]]

Digital Library

[23]

Birman, K. and van Renesse, R. 1994. Reliable Distributed Computing with the Isis Toolkit (Los Alamitos, CA). IEEE Computer Society Press.]]

Digital Library

[24]

Birman, K. P. and Joseph, T. A. 1987. Reliable communication in the presence of failures. ACM Trans. Comput. Syst. 5, 1 (Feb.), 47--76.]]

Digital Library

[25]

Birman, K. P., Schiper, A., and Stephenson, P. 1991. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst. 9, 3 (Aug.), 272-- 314.]]

Digital Library

[26]

Carr, R. 1985. The Tandem global update protocol. Tandem Syst. Rev. 1, 2 (June), 74--85.]]

[27]

Chandra, T. D., Hadzilacos, V., and Toueg, S. 1996. The weakest failure detector for solving consensus. J. ACM 43, 4 (July), 685--722.]]

Digital Library

[28]

Chandra, T. D. and Toueg, S. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2, 225--267.]]

Digital Library

[29]

Chang, J.-M. and Maxemchuk, N. F. 1984. Reliable broadcast protocols. ACM Trans. Comput. Syst. 2, 3 (Aug.), 251--273.]]

Digital Library

[30]

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.)]]

[31]

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.]]

Digital Library

[32]

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.]]

Digital Library

[33]

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.]]

Digital Library

[34]

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.]]

Digital Library

[35]

Chockler, G., Keidar, I., and Vitenberg, R. 2001. Group communication specifications: A comprehensive study. ACM Comput. Surv. 33, 4 (Dec.), 427--469.]]

Digital Library

[36]

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.]]

Digital Library

[37]

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.]]

Digital Library

[38]

Chor, B. and Dwork, C. 1989. Randomization in Byzantine Agreement. Adv. Comput. Res. 5, 443--497.]]

[39]

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.]]

[40]

Cristian, F. 1990. Synchronous atomic broadcast for redundant broadcast channels. Real-Time Syst. 2, 3 (Sept.), 195--212.]]

Digital Library

[41]

Cristian, F. 1991. Asynchronous atomic broadcast. IBM Technical Disclosure Bulletin 33, 9, 115--116.]]

[42]

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.]]

Digital Library

[43]

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.]]

[44]

Cristian, F. and Fetzer, C. 1999. The timed asynchronous distributed system model. IEEE Trans. Parall. Distrib. Syst. 10, 6 (June), 642--657.]]

Digital Library

[45]

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.]]

[46]

Cristian, F., Mishra, S., and Alvarez, G. 1997. High-performance asynchronous atomic broadcast. Distrib. Syst. Eng. J. 4, 2 (June), 109--128.]]

[47]

Dasser, M. 1992. TOMP: A total ordering multicast protocol. ACM Operat. Syst. Rev. 26, 1 (Jan.), 32--40.]]

Digital Library

[48]

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.]]

[49]

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.]]

[50]

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.]]

Digital Library

[51]

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.]]

[52]

Dolev, D., Dwork, C., and Stockmeyer, L. 1987. On the minimal synchrony needed for distributed consensus. J. ACM 34, 1 (Jan.), 77--97.]]

Digital Library

[53]

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.]]

[54]

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.]]

Digital Library

[55]

Dolev, D. and Malkhi, D. 1996. The Transis approach to high availability cluster communnication. Comm. ACM 39, 4 (April), 64--70.]]

Digital Library

[56]

Dwork, C., Lynch, N. A., and Stockmeyer, L. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (April), 288--323.]]

Digital Library

[57]

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.]]

Digital Library

[58]

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.]]

Digital Library

[59]

Fekete, A. 1993. Formal models of communication services: A case study. IEEE Comput. 26, 8 (Aug.), 37--47.]]

Digital Library

[60]

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.]]

Digital Library

[61]

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.]]

Digital Library

[62]

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.]]

Digital Library

[63]

Fetzer, C. 2003. Perfect failure detection in timed asynchronous systems. IEEE Trans. Comput. 52, 2 (Feb.), 99--112.]]

Digital Library

[64]

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.]]

Digital Library

[65]

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.]]

Digital Library

[66]

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.]]

Digital Library

[67]

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.]]

[68]

Garcia-Molina, H. and Spauster, A. 1991. Ordered and reliable multicast communication. ACM Trans. Comput. Syst. 9, 3 (Aug.), 242--271.]]

Digital Library

[69]

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.]]

Digital Library

[70]

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.]]

Digital Library

[71]

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.]]

Digital Library

[72]

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.]]

Digital Library

[73]

Guerraoui, R. and Schiper, A. 2001. Genuine atomic multicast in asynchronous distributed systems. Theor. Comput. Sci. 254, 297-- 316.]]

Digital Library

[74]

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.]]

[75]

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.)]]

Digital Library

[76]

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.]]

Digital Library

[77]

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.]]

Digital Library

[78]

Jia, X. 1995. A total ordering multicast protocol using propagation trees. IEEE Trans. Parall. Distrib. Syst. 6, 6 (June), 617--627.]]

Digital Library

[79]

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.]]

Digital Library

[80]

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.]]

[81]

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.]]

Digital Library

[82]

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.]]

Digital Library

[83]

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.]]

Digital Library

[84]

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.]]

[85]

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.]]

[86]

Lamport, L. 1978a. The implementation of reliable distributed multiprocess systems. Comput. Netw. 2, 95--114.]]

[87]

Lamport, L. 1978b. Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 7 (July), 558--565.]]

Digital Library

[88]

Lamport, L. 1984. Using time instead of time-outs in fault-tolerant systems. ACM Trans. Program. Lang. Syst. 6, 2, 256--280.]]

Digital Library

[89]

Lamport, L. 1986a. The mutual exclusion problem: Part I---a theory of interprocess communication. J. ACM 33, 2 (April), 313--326.]]

Digital Library

[90]

Lamport, L. 1986b. On interprocess communication. part I: Basic formalism. Distrib. Comput. 1, 2, 77--85.]]

[91]

Lamport, L., Shostak, R., and Pease, M. 1982. The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4, 3, 382--401.]]

Digital Library

[92]

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.]]

Digital Library

[93]

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.]]

Digital Library

[94]

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.]]

Digital Library

[95]

Lynch, N. A. 1996. Distributed Algorithms. Morgan Kaufmann, San Francisco, CA.]]

Digital Library

[96]

Lynch, N. A. and Tuttle, M. R. 1989. An introduction to input/output automata. CWI Quarterly 2, 3 (Sept.), 219--246.]]

[97]

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.]]

[98]

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.]]

[99]

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.]]

[100]

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.]]

Digital Library

[101]

Minet, P. and Anceaume, E. 1991a. ABP: An atomic broadcast protocol. TR 1473, INRIA (June). Rocquencourt, France.]]

[102]

Minet, P. and Anceaume, E. 1991b. Atomic broadcast in one phase. ACM Operat. Syst. Rev. 25, 2 (April), 87--90.]]

Digital Library

[103]

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.]]

[104]

Moser, L. E. and Melliar-Smith, P. M. 1999. Byzantine-resistant total ordering algorithms. Inf. Comput. 150, 1 (April), 75--111.]]

Digital Library

[105]

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.]]

Digital Library

[106]

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.]]

Digital Library

[107]

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.]]

Digital Library

[108]

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.]]

[109]

Neiger, G. and Toueg, S. 1990. Automatically increasing the fault-tolerance of distributed algorithms. J. Algorithms 11, 3, 374--419.]]

Digital Library

[110]

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.]]

[111]

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.]]

[112]

Pedone, F. 2001. Boosting system performance with optimistic distributed protocols. IEEE Comput. 34, 12 (Dec.), 80--86.]]

Digital Library

[113]

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.]]

Digital Library

[114]

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.]]

Digital Library

[115]

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.]]

Digital Library

[116]

Pedone, F. and Schiper, A. 2002. Handling message semantics with generic broadcast protocols. Distrib. Comput. 15, 2, 97--107.]]

Digital Library

[117]

Pedone, F. and Schiper, A. 2003. Optimistic atomic broadcast: A pragmatic viewpoint. Theor. Comput. Sci. 291, 79--101.]]

Digital Library

[118]

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.]]

Digital Library

[119]

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.]]

Digital Library

[120]

Poledna, S. 1994. Replica determinism in distributed real-time systems: A brief survey. Real-Time Syst. 6, 3 (May), 289--316.]]

Digital Library

[121]

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.]]

Digital Library

[122]

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.]]

[123]

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.]]

Digital Library

[124]

Reiter, M. K. 1996. Distributing trust with the Rampart toolkit. Comm. ACM 39, 4 (April), 71--74.]]

Digital Library

[125]

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.]]

Digital Library

[126]

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.]]

Digital Library

[127]

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.]]

Digital Library

[128]

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.]]

[129]

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.]]

[130]

Schiper, A. and Raynal, M. 1996. From group communication to transactions in distributed systems. Comm. ACM 39, 4 (April), 84--87.]]

Digital Library

[131]

Schneider, F. B. 1990. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22, 4 (Dec.), 299--319.]]

Digital Library

[132]

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.]]

Digital Library

[133]

Shrivastava, S. K. 1994. To CATOCS or not to CATOCS, that is the… ACM Operat. Syst. Rev. 28, 4 (Oct.), 11--14.]]

Digital Library

[134]

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.]]

Digital Library

[135]

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.]]

Digital Library

[136]

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.]]

[137]

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.]]

[138]

Veríssimo, P., Rodrigues, L., and Baptista, M. 1989. AMp: A highly parallel atomic multicast protocol. Comput. Comm. Rev. 19, 4 (Sept.), 83-- 93.]]

Digital Library

[139]

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.]]

Digital Library

[140]

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.]]

Digital Library

[141]

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.]]

Digital Library

[142]

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.]]

Digital Library

[143]

Zhou, P. and Hooman, J. 1995. Formal specification and compositional verification of an atomic broadcast protocol. Real-Time Syst. 9, 2 (Sept.), 119--145.]]

Digital Library

Cited By

Gomes Jr. EAlchieri EDotti FMendizabal O(2024)Reducing Persistence Overhead in Parallel State Machine Replication through Time-Phased Partitioned CheckpointJournal of Internet Services and Applications10.5753/jisa.2024.389115:1(194-211)Online publication date: 26-Jul-2024
https://doi.org/10.5753/jisa.2024.3891
Ramseyer GGoel AKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Fair Ordering via Streaming Social Choice TheoryProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662772(279-282)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662772
Capretto MCeresa MFndez Anta ARusso ASánchez C(2024)Improving Blockchain Scalability with the Setchain Data-TypeDistributed Ledger Technologies: Research and Practice10.1145/36269633:2(1-27)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3626963
Show More Cited By

Index Terms

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

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 36, Issue 4

December 2004

129 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/1041680

Issue’s Table of Contents

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2004

Published in CSUR Volume 36, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

364
Total Citations
View Citations
6,836
Total Downloads

Downloads (Last 12 months)185
Downloads (Last 6 weeks)12

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gomes Jr. EAlchieri EDotti FMendizabal O(2024)Reducing Persistence Overhead in Parallel State Machine Replication through Time-Phased Partitioned CheckpointJournal of Internet Services and Applications10.5753/jisa.2024.389115:1(194-211)Online publication date: 26-Jul-2024
https://doi.org/10.5753/jisa.2024.3891
Ramseyer GGoel AKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Fair Ordering via Streaming Social Choice TheoryProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662772(279-282)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662772
Capretto MCeresa MFndez Anta ARusso ASánchez C(2024)Improving Blockchain Scalability with the Setchain Data-TypeDistributed Ledger Technologies: Research and Practice10.1145/36269633:2(1-27)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3626963
Gramoli VLu ZTang QZarbafian P(2024)AOAB: Optimal and Fair Ordering of Financial Transactions2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00045(377-388)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN58291.2024.00045
Ruchel LTavares de Camargo ERodrigues LTurchetti RArantes LProcópio Duarte E(2024)Scalable atomic broadcastJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.104789184:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2023.104789
Yeow KIdris MGani AAhmedy IHakak S(2024)BRAPTOR: An efficient method for instant asset-transfer and generic application in blockchainComputers and Electrical Engineering10.1016/j.compeleceng.2024.109636120(109636)Online publication date: Dec-2024
https://doi.org/10.1016/j.compeleceng.2024.109636
Chaurasia BVerma AVerma P(2024)An in-depth and insightful exploration of failure detection in distributed systemsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110432247:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110432
Misra AKshemkalyani A(2024)Towards Stronger Blockchains: Security Against Front-Running AttacksNetworked Systems10.1007/978-3-031-67321-4_11(171-187)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-67321-4_11
Scharf JXavier LMendizabal O(2023)Joining Parallel and Partitioned State Machine Replication Models for Enhanced Shared Logging PerformanceProceedings of the 12th Latin-American Symposium on Dependable and Secure Computing10.1145/3615366.3615422(90-99)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3615366.3615422
Batista ECoelho PAlchieri EDotti FPedone F(2023)FlexCastProceedings of the 24th International Middleware Conference10.1145/3590140.3629122(288-300)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629122
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents