Abstract
Total Order (TO) broadcast is a widely used communication abstraction that has been deeply investigated during the last decade. As such, the amount of relevant works may leave practitioners wondering how to select the TO implementation that best fits the requirements of their applications. Different implementations are indeed available, each providing distinct safety guarantees and performance. These aspects must be considered together in order to build a correct and sufficiently performing application. To this end, this paper analyzes six TO implementations embedded in three freely-distributed group communication systems, namely Ensemble, Spread and JavaGroups. Implementations are first classified according to the enforced specifications, which is given using a framework for specification tailored to total order communications. Then, implementations are compared under the performance viewpoint in a simple yet meaningful deployment scenario. In our opinion, this structured information should assist practitioners (i) in deeply understanding the ways in which implementations may differ (specifications, performance) and (ii) in quickly relating a set of total order algorithms to their specifications, implementations and performance.
This work is partially supported by the european project EUPubli.com funded by the European Community and by the italian project MAIS funded by the Italian Ministry of Research.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Schneider, F.B.: Replication Management Using the State Machine Approach. In: Mullender, S. (ed.) Distributed Systems. ACM Press -Addison Wesley (1993)
Chockler, G., Keidar, I., Vitenberg, R.: Group Communications Specifications: a Comprehensive Study. ACM Computing Surveys 33, 427–469 (2001)
Powell, D.: Group Communication. Communications of the ACM 39, 50–97 (1996)
Baldoni, R., Cimmino, S., Marchetti, C.: Total order communications over asynchronous distributed systems: Specifications and implementations. Technical Report 06/04, Università di Roma “La sapienza” (2004), Available at http://www.dis.uniroma1.it/~midlab/publications.html
Friedman, R., van Renesse, R.: Packing Messages as a Tool for Boosting the Performance of Total Ordering Protocols. Technical Report TR95-1527, Department of Computer Science, Cornell University (1995) (Submitted for publication)
Dèfago, X.: Agreement-Related Problems: From Semi Passive Replication to Totally Ordered Broadcast. PhD thesis, École Polytechnique Fédérale de Lausanne, Switzerland, PhD thesis no. 2229 (2000)
Dèfago, X., Schiper, A., Urbán, P.: Total order broadcast and multicast algorithms: Taxonomy and survey. Technical Report IC/2003/56, École Polytechnique Fédérale de Lausanne, Switzerland (2003)
Hayden, M.: The Ensemble System. PhD thesis, Cornell University, Ithaca, NY, USA (1998)
Ban, B.: Design and implementation of a reliable group communication toolkit for java. Cornell University (1998)
Mena, S., Schiper, A., Wojciechowski, P.: A step towards a new generation of group communication systems. Technical Report IC/2003/01, École Polytechnique Fédérale de Lausanne, Switzerland (2003)
Birman, K., Joseph, T.: Exploiting Virtual Synchrony in Distributed Systems. In: Proceedings of the 11th ACM Symp. on Operating Systems Principles, pp. 123–138 (1987)
Chandra, T.D., Hadzilacos, V., Toueg, S.: he weakest failure detector for solving Consensus. Journal of ACM 43, 685–722 (1996)
Birman, K., van Renesse, R.: Reliable Distributed Computing with the ISIS toolkit. IEEE CS Press, Los Alamitos (1994)
Chandra, T., Hadzilacos, V., Toueg, S., Charron-Bost, B.: On the Impossibility of Group Membership. In: Proc. of the 15th ACM Symposium of Principles of Distributed Computing (1996)
Schiper, A.: Dynamic group communication. Technical Report IC/2003/27, École Polytechnique Fédérale de Lausanne, Switzerland (2003)
Hadzilacos, V., Toueg, S.: Fault-Tolerant Broadcast and Related Problems. In: Mullender, S. (ed.) Distributed Systems. Addison Wesley, Reading (1993)
Amir, Y., Moser, L., Melliar-Smith, P.M., Agarwal, D., Ciarfella, P.: The Totem single-ring ordering and membership protocol. ACM Transactions on Computer Systems 13, 93–132 (1995)
Amir, Y., Stanton, J.: The Spread Wide Area Group Communication System. Technical Report CNDS-98-4, Center for Networking and Distributed Systems, Computer Science Department, Johns Hopkins University, 3400 N. Charles Street Baltimore, MD 21218-2686 (1998)
Moser, L.E., Amir, Y., Melliar-Smith, P.M., Agarwal, D.A.: Extended Virtual Synchrony. In: Proceedings of the 14 International Conference on distributed Computing Systems (1994)
Cristian, F., de Beijer, R., Mishra, S.: A Performance Comparison of Asynchronous Atomic Broadcast Protocols. Distributed Systems Engineering Journal 1, 177–201 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baldoni, R., Cimmino, S., Marchetti, C. (2005). Total Order Communications: A Practical Analysis. In: Dal Cin, M., Kaâniche, M., Pataricza, A. (eds) Dependable Computing - EDCC 5. EDCC 2005. Lecture Notes in Computer Science, vol 3463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11408901_4
Download citation
DOI: https://doi.org/10.1007/11408901_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25723-3
Online ISBN: 978-3-540-32019-7
eBook Packages: Computer ScienceComputer Science (R0)