Understanding the Limitations ofCausally and Totally Ordered CommunicationDavid R. CheritonandDale SkeenComputer Science Dept.Stanford [email protected]. eduAbstractCausally and totally ordered communication support(CMOCS) has been proposed as important to provide aspart of the basic building blocks for constructing reliabledistributed systems. In this paper, we identify four majorlimitations to CATOCS, investigate the applicability ofC~OCS to several classes of distributed applications inlight of these limitations, and the potential impact of thesefacilities on communication scalability and robustness.From this investigation, we find limited merit and severalpotential problems in using CATCICS. The fundamental dif-ficulty with the CN.OCS is that it attempts to solve stateproblems at the communication level in violation of thewell-known “end-t&end” argument.1IntroductionCausally and totally ordered communication support(C~OCS) has been proposed as another important facilityfor constructing reliable distributed systems [2, 3, 13, 22,24]. Causally-ordered communication ensws that mes-sages are delivered in an order that is consistent with thepotential causal dependencies between messages, followingthe logical clock model of imposing an overall partial order-ing on events in a distributed system [16]. Totally orderedcommunication support goes a step further to ensw thatmessages are delivered in the same order to all participants.CfWOCS implementations to date also provide atomicity ofmessage delivery, ensuring that either all messages arereceived or none am, at least at processes that do not failduring the interYal of interest. CATOCS implementationsmay also provide failure notification that is causally (ortotally) orde~d with respect to the message traftic. Withthese facilities, CATOCS has been advocated as well-suitedThis research is supported in part by DARPA under ContractDABT-63-91-K-001.Permission to copy without fee all or part of this material ISgranted prowded that the copies are not made or distributed fordirect commercial advantage, the ACM copyright notice and thetitle of the publication and Its date appear, and notice IS giventhat copying is by permission of the Assoclatlon for ComputingMachinery. To copy otherwise, or to republish, requires a feeand/or speclflc permission.SIGOPS ‘93/12 /93/N. C., USAo 1993 ACM 0-89791 -632 -8/93 /0012 ...$l .50Teknekron Software Systems, Inc.Palo Alto, [email protected] solving several important distributed computing prob-lems, including, in particular, data replication.However, CATOCS can only be justified by identifyinga significant class of real applications for which its facilitiesare sui%cient and efficient, and whine requirements can notbe efficiently satisfied using alternative, general-purposemechanisms. In this paper, we investigate the applicabilityof CATOCS to several classes of distributed applicationswith particular focus on examples used in the CATOCS lit-erature. From this investigation, we find limited merit inusing CATOCS. The basic diftkulty with CNOCS can bebest explained in terms of the end-to-end argument [25].CATOCS is at the communication level, but consistencyrequkmenta are typically expressed in terms of the applica-tion’s state.The next section describes in greater detail what wemean by causally and totally ordered communication sup-port (CATOCS). Section 3 describes a number of significantlimitations and cost of these techniques in a variety of com-munication situations. Section 4 considers the applicabilityof causal and total ordering protocols to a number of classesof distributed applications, including examples from litera-ture illustrating the use of CNOCS protocols. We show thatthe limitations pmented in Section 3 can and do signifi-cantly restrict the benefits of using CATOCS in these appli-cation areas. Section 5 presents arguments why CMOCS onthe communications data transfer path has a significant scal-ing cost. We conclude that a state-level approach imple-mented using object-oriented technology provides a moreefficient, robust, scalable and easier to specialize solution tothe distributed systems problems we have considered.2 Causally and Totally OrderedCommunicationIna causally ordered message system, messagea aredelivered in the order messages are sent, as determined bythe happens-before relationship [16] but restricted to mes-sage sending and nxeiving eventsl. For convenience, weextend the happens-before relationship to include messages.1. Thisis a natural restriction, given that message events are theonly events that the message system knows about.44In the simplest case, message ml is said to happen-beforem2 if there exists a process P such that ml is sent by orreceived at P before P sends m2. Taking the transitive C1Osure of these simple cases yields the full happens-beforerelationship on messages. The term causally precedes is asynonym for happens-before, i.e., ml causally-precedes m2if ml happens-before m2.Figure 1 illustrates causal ordering using a commoncharting device known as an event diagram. Message send-ing and receiving events are arranged by column, one perprocess, with time advancing from top to bottom. The dia-gram shows that Process Q sends ml, which is laterreceived by Process P. Later, P sends m2, which is subse-quently received by Process R, etc. Message ml causallyprecedes both m2 andm4. Messages m3 and m4 are said tobe “concurrent” because neither causally precedes the other.Causal multicast2 delivers messages in accordancewith the happens-before relationship within a specifiedgroup of processes, known as aprocess group [13]. Specifi-cally, if two messages are mukicast to the same processgroup and the sending of one message happens befo~ thesending of another message, then the first message is deliv-ered before the second message at all processes in thegroup. Hence, causal multicast really means “happens-before-preserving.”Figure 1. A 3-process event diagram. Messages ml“causally precedes”m2 and rn4. Messages m3 andm4 are “concurrent” and, hence, causally unrelated.Proc.Proc.Proc.PQRTIllEIM....................m 1sent by Qml....................... . .mlreceived byP~llm2se~’~ypwm2.,..m2 received by R\H3+++2. In the literature, this is sometimes referred to as a “broadcast”protocol [13], and sometimes as a “multicast” protocol [4]. Weprefer the term multicast.Totally ordered multicast delivers all messages in thesame