Y. Amir
Abstract
Fault-tolerant distributed systems are becoming more important, but in existing systems, maintaining the consistency of replicated data is quite expensive. The Totem single-ring protocol supports consistent concurrent operations by placing a total order on broadcast messages. This total order is derived from the sequence number in a token that circulates around a logical ring imposed on a set of processors in a broadcast domain. The protocol handles reconfiguration of the system when processors fail and restart or when the network partitions and remerges. Extended virtual synchrony ensures that processors deliver messages and configuration changes to the application in a consistent, systemwide total order. An effective flow control mechanism enables the Totem single-ring protocol to achieve message-ordering rates significantly higher than the best prior total-ordering protocols.
- AMiR, Y, DOLEV, D., KRAMER, S., AND MALKI, D. 1992a. Membership algorithms in broadcast domains In Proceedings of the 6th Internattonal Workshop on Distributed Algorithms (Haifa, Israel). Spnnger-Verlag, Berlin, 292-312. Google Scholar
- AMm, Y, DOLEV, D., KRAIvlER, S., AND MALKI, D. 1992b. Transis: A commumcation subsystem for high avafiabfilty. In Proceedings of the IEEE 22nd Annual Internatmnal Svmposiiim on Fault-Tolerant Computing (Boston, Mass). IEEE, New York, 76-84Google Scholar
- A~nR, Y, MOSER, L E., MELLIAR-SMITH, P. M., AGARWAL, D. A., AND CIARFELLA, P. 1993 Fast message ordering and membership using a logical token-passing ring. In Proceedings of the IEEE 13th International Conference on Distributed Computing Systems (Pittsburgh, Pa) IEEE, New York, 551-560.Google Scholar
- A~nn, Y, MOSER, L. E, MELLIAR-SMITH, P. M., AGARWAL, D. A, A~'4O CIAnFELLA, P. 1994. The Totem single-ring ordering and membership protocol. Tech Rep. 94-19, Dept of Electrical and Computer Engnneermg, Umv. of California, Santa Barbara, Calif. Aug.Google Scholar
- BIRMAN K. P AND VAN RENESSE, R. 1994 Reliable Distributed Computing w~th the Isis Toolkit. IEEE Computer Somety Press, Los Alamltos, Calif Google Scholar
- BOXMA, O. J., LEVY J., AND WESTRATE, J.A. 1990. Optimization of polling systems. In Performance '90, Proceedings of the 14th IFIP WG 7.3 International Symposium on Computer Perforrnarice Modelhng, Measurement and Evaluation (Edinburg, U.K ). North-Holland, Amsterdam, 349 361. Google Scholar
- CHANG, J. M. AND Mg24EMCHUK, N F. 1984. Reliable broadcast protocols ACM Trans Comput Syst. 2, 3 (Aug.), 251 273. Google Scholar
- FISCHER, M. J., LYNCH, N. A., AND PATERSON, M S. 1985. Impossibility of distributed consensus with one faulty process J. ACM 32, 2 (Apr), 374-382 Google Scholar
- K~SHOEK, M F. ANn TANENnAU~, A. S. 1991. Group communicatmn m the Amoeba distnbuted operating system. In Proceedings of the IEEE lltb International Conference on Distributed Computing Systems (Arlington, Tax ). IEEE, New York, 882 891.Google Scholar
- LAMPORT, L 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July), 558-565. Google Scholar
- MELLIAR-SMITH, P. M., MOSER, L. E., AND AGARWAL, D.A. 1991. Ring-based ordering protocols. In Proceedings of the IEE International Conference on Information Engineering (Singapore) IEE, Stevenage, Harts, U.K, 882 891Google Scholar
- MELLIAn-SMITn, P. M., MOSE~, L. E., ANi~ A(n~AWALA, V. 1990. Broadcast protocols for d~stributed sytems. IEEE Trans. Parallel D*strib. Syst. 1, 1 (Jan.), 17-25. Google Scholar
- MISHRA, S., PETERSON, L. L., AND SCHLICHTING, R.D. 1991. A membership protocol based on partml order. In Procee&ngs of the 2rid IFIP WG 10.4 Internatzonal Working Conference on Dependable Computing for Cr~tzcal Appl~catmns (Tucson, Ariz.). Springer-Verlag, Wien, Austria, 309-331.Google Scholar
- MosE~, L. E ANn MELLIAR-SMITH, P.M. 1994. Probablhstm bounds on message delivery for the Totem single-rang protocol. In Proceedings of the IEEE 15th Real-T~me Systems Symposium (San Juan, Puerto Rico). IEEE, New York, 238-248.Google Scholar
- MOSEn, L. E., AMIn, Y., MnLLIAn-SMITn, P M., AND AOARWAL, D.A. 1994a. Extended virtual synchrony. In Proceedings of the IEEE 14th International Conference on Dzstrlbuted Computing Systems (Posnan, Poland). IEEE, New York, 56-65.Google Scholar
- MOSER, L. E., MELL~AR-SMn'H, P. M., AND AGRAWALA, V. 1994b. Processor membership in asynchronous distributed systems IEEE Trans Parallel Dlstrzb. Syst. 5, 5 (May), 459-473. Google Scholar
- PETERSON, L. L,, BUCHHOLZ, N. C., AND 8CHLICHTING, R.D. 1989. Preaerving and using context information in interprocess communication. ACM Trans Comput. Syst 7, 3 (Aug.), 217-246. Google Scholar
- RAJAGOPALAN, B. AND McKINLEY, P. K. 1989. A token-based protocol for reliable, ordered multicast communication In Proceedings of the IEEE 8th Symposium on Reliable Distributed Systems (Seattle, Wash ). IEEE, New York, 84-93.Google Scholar
- VAN RENESSE, R., HICKEY, T. M., AND BIRMAN, K. P 1994. Design and performance of Horus: A lightwmght group communications system Tech Rep. 94-1442, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y. Aug. Google Scholar
Index Terms
- The Totem single-ring ordering and membership protocol
Recommendations
The Totem multiple-ring ordering and topology maintenance protocol
The Totem multiple-ring protocol provides reliable totally ordered delivery of messages across multiple local-area networks interconnected by gateways. This consistent message order is maintained in the presence of network partitioning and remerging, ...
Leader-Determined Membership Protocol
HASE '11: Proceedings of the 2011 IEEE 13th International Symposium on High-Assurance Systems EngineeringMany fault-tolerant systems organize the replicas of an application process as a process group. The Leader-Determined Membership Protocol determines a new membership for the process group, when a member becomes faulty, a member leaves the group, or a ...
Reviews
Valentin Cristea
Totem is a single-ring protocol for high-performance, fault-tolerant distributed systems that must continue to operate despite network partitioning and re-merging and despite processor failure and restart. Totem provides totally ordered message delivery with good performance using a logical token-passing ring imposed on a broadcast domain. After an introductory section, the authors present related work and highlight the differences of the Totem protocol. Significant literature on the subject is analyzed. Section 3 is dedicated to the distributed system model used in the Totem protocol design. Several terms related to protocol functioning are defined. The objective of Totem is to provide the application with reliable message delivery and membership services. These services are described in section 4 of the paper. Section 5 is devoted to the total ordering protocol with the assumptions that the token is never lost; processor failures do not occur; and the network does not become partitioned. In section 6, the conditions are relaxed, and the protocol to handle token loss, processor failure and restart, and network partitioning and re-merging is presented. The protocol is described using a finite-state machine model. Data structures used, as well as pseudocode for the work performed by processors during different states of the model, are also given. Sections 7 and 8 present the recovery protocol that maintains extended virtual synchrony during recovery after a failure, and the flow control mechanism that avoids message loss due to buffer overflow. Section 9 addresses implementation and performance. Future work is mentioned at the end of the paper. The paper is well structured, but the presentation is not uniform, some aspects being described in great detail, while others are quickly summarized. The important works on the subject are included as references.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments