The Many Faces of Publish/Subscribe

1 .The Many Faces of Publish/Subscribe PATRICK TH. EUGSTER Swiss Federal Institute of Technology, Lausanne PASCAL A. FELBER Institut Eur´ecom RACHID GUERRAOUI Swiss Federal Institute of Technology, Lausanne AND ANNE-MARIE KERMARREC Microsoft Research Well adapted to the loosely coupled nature of distributed interaction in large-scale applications, the publish/subscribe communication paradigm has recently received increasing attention. With systems based on the publish/subscribe interaction scheme, subscribers register their interest in an event, or a pattern of events, and are subsequently asynchronously notified of events generated by publishers. Many variants of the paradigm have recently been proposed, each variant being specifically adapted to some given application or network model. This paper factors out the common denominator underlying these variants: full decoupling of the communicating entities in time, space, and synchronization. We use these three decoupling dimensions to better identify commonalities and divergences with traditional interaction paradigms. The many variations on the theme of publish/subscribe are classified and synthesized. In particular, their respective benefits and shortcomings are discussed both in terms of interfaces and implementations. Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems—Distributed applications; D.1.3 [Programming Techniques]: Concurrent Programming—Distributed programming General Terms: Design Additional Key Words and Phrases: Distribution, interaction, publish/subscribe 1. INTRODUCTION entities—potentially distributed all over The Internet has considerably changed the world—whose location and behavior the scale of distributed systems. Dis- may greatly vary throughout the life- tributed systems now involve thousands of time of the system. These constraints Authors’ addresses: P. Th. Eugster and R. Guerraoui, Swiss Federal Institute of Technology, 1015 Lausanne, Switzerland; email: {patrick.eugster, rachid.guerraoui}@epfl.ch; P. A. Felber, Institut Eur´ecom, 2229 routes des Crˆetes, 06904 Sophia Antipolis, France; email: pascal.felber@eurecom.fr; A.-M. Kermarrec, Microsoft Research Ltd., 7 J. J. Thomson Ave., Cambridge CB3 0FB, U.K.; email: annemk@microsoft.com. Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee. c 2003 ACM 0360-0300/03/0600-0114 $5.00 ACM Computing Surveys, Vol. 35, No. 2, June 2003, pp. 114–131. 

2 .The Many Faces of Publish/Subscribe 115 Fig. 1. A simple object-based publish/subscribe system. visualize the demand for more flexi- The aim of this paper is threefold. ble communication models and systems, First we point out the common denomi- reflecting the dynamic and decoupled nators of publish/subscribe schemes: time, nature of the applications. Individual space, and synchronization decoupling of point-to-point and synchronous commu- subscribers and publishers. These decou- nications lead to rigid and static appli- pling dimensions are illustrated by com- cations, and make the development of paring the publish/subscribe paradigm dynamic large-scale applications cumber- with “traditional” interaction schemes. some. To reduce the burden of application Second, we compare the many variants of designers, the glue between the different publish/subscribe schemes: namely, topic- entities in such large-scale settings should based, content-based, and type-based. rather be provided by a dedicated middle- Third, we discuss variations and trade- ware infrastructure, based on an adequate offs in the design and implementation of communication scheme. publish/subscribe-based systems through The publish/subscribe interaction sch- specific examples. eme is receiving increasing attention and is claimed to provide the loosely coupled 2. THE BASIC INTERACTION SCHEME form of interaction required in such large scale settings. Subscribers have the abil- The publish/subscribe interaction para- ity to express their interest in an event, or digm provides subscribers with the ability a pattern of events, and are subsequently to express their interest in an event or a notified of any event, generated by a pub- pattern of events, in order to be notified lisher, which matches their registered in- subsequently of any event, generated by terest. An event is asynchronously prop- a publisher, that matches their registered agated to all subscribers that registered interest. In other terms, producers publish interest in that given event. The strength information on a software bus (an event of this event-based interaction style manager) and consumers subscribe to the lies in the full decoupling in time, space, information they want to receive from and synchronization between publishers that bus. This information is typically and subscribers. Many industrial sys- denoted by the term event and the act of tems and research prototypes support this delivering it by the term notification. style of interaction, and there are several The basic system model for publish/ prominent research efforts on novel forms subscribe interaction (Figure 1) relies on of publish/subscribe interaction schemes. an event notification service providing However, because of the multiplicity of storage and management for subscrip- these systems and prototypes, it is diffi- tions and efficient delivery of events. Such cult to capture their commonalities and an event service represents a neutral me- draw sharp lines between their main diator between publishers, acting as pro- variations. ducers of events, and subscribers, acting ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

3 .116 Eugster et al. Fig. 2. Space, time, and synchronization decoupling with the publish/subscribe paradigm. as consumers of events. Subscribers reg- The publishers publish events through ister their interest in events by typically an event service and the subscribers calling a subscribe() operation on the get these events indirectly through the event service, without knowing the effec- event service. The publishers do not usu- tive sources of these events. This sub- ally hold references to the subscribers, scription information remains stored in neither do they know how many of these the event service and is not forwarded subscribers are participating in the in- to publishers. The symmetric operation teraction. Similarly, subscribers do not unsubscribe() terminates a subscription. usually hold references to the publish- To generate an event, a publisher typ- ers, neither do they know how many of ically calls a publish() operation. The these publishers are participating in the event service propagates the event to all interaction. relevant subscribers; it can thus be viewed —Time decoupling: The interacting par- as a proxy for the subscribers. Note that ties do not need to be actively parti- every subscriber will be notified of every cipating in the interaction at the same event conforming to its interest (obviously, time. In particular, the publisher might failures might prevent subscribers from publish some events while the sub- receiving some events). Publishers also of- scriber is disconnected, and conver- ten have the ability to advertise the na- sely, the subscriber might get notified ture of their future events through an about the occurrence of some event advertise() operation. The provided in- while the original publisher of the event formation can be useful for (1) the event is disconnected. service to adjust itself to the expected flows of events, and (2) the subscribers to —Synchronization decoupling: Publishers learn when a new type of information be- are not blocked while producing events, comes available. and subscribers can get asynchronously The decoupling that the event service notified (through a callback) of the occur- provides between publishers and sub- rence of an event while performing some scribers can be decomposed along the fol- concurrent activity. The production and lowing three dimensions (Figure 2): consumption of events do not happen in the main flow of control of the publish- —Space decoupling: The interacting par- ers and subscribers, and do not therefore ties do not need to know each other. happen in a synchronous manner. ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

4 .The Many Faces of Publish/Subscribe 117 Decoupling the production and con- sumption of information increases scala- bility by removing all explicit dependen- cies between the interacting participants. In fact, removing these dependencies strongly reduces coordination and thus synchronization between the different en- Fig. 3. Message passing interaction: the producer tities, and makes the resulting commu- sends messages asynchronously through a commu- nication infrastructure well adapted to nication channel (previously set up for that purpose). distributed environments that are asyn- The consumer receives messages by listening syn- chronously on that channel. chronous by nature, such as mobile en- vironments [Huang and Garcia-Molina 2001]. Complementary classifications of the in- ing is nowadays rarely used directly for teraction models of distributed informa- developing distributed applications, since tion systems have been proposed in the physical addressing and data marshaling, literature. Franklin and Zdonik [1997] and sometimes even flow control (e.g., re- classified dissemination-based systems transmission), become visible to the ap- according to their data delivery mecha- plication layer. Message passing is asyn- nisms: push versus pull, aperiodic ver- chronous for the producer, while message sus periodic, and unicast versus 1-to-N. consumption is generally synchronous. Push-based information systems have The producer and the consumer are cou- been studied extensively [Hauswirth and pled both in time and space (cf. Figure 3): Jazayeri 1999; Hauswirth 1999]. Simi- they must both be active at the same time lar characterizations are used in software and the recipient of a message is known to engineering [Sullivan and Notkin 1990; the sender. Garlan and Notkin 1991] and coordination models [Papadopoulos and Arbab 1998]. 3.2. RPC 3. THE COUSINS: ALTERNATIVE One of the most widely used forms of dis- COMMUNICATION PARADIGMS tributed interaction is the remote invoca- tion, an extension of the notion of “oper- Message passing, remote invocations, no- ation invocation” to a distributed context. tifications, shared spaces, and message This type of interaction was first proposed queuing do all constitute alternative in the form of a remote procedure call communication paradigms to the pub- (RPC) [Birrell and Nelson 1983; Tay and lish/subscribe scheme. They stand at dif- Ananda 1990] for procedural languages, ferent abstraction levels and are not easy and has been straightforwardly applied to compare. Nevertheless, we overview to object-oriented contexts in the form of below their commonalities with pub- remote method invocations, for example, lish/subscribe systems and emphasize in Java RMI [Sun 2000], CORBA [OMG their inability to fully decouple communi- 2002a], Microsoft DCOM [Horstmann and cation between participants. Kirtland 1997; Chung et al. 1998]. 3.1. Message Passing By making remote interactions appear the same way as local interactions, the Message passing can be viewed as the an- RPC model and its derivatives make dis- cestor of distributed interactions. Message tributed programming very easy. This ex- passing represents a low-level form of dis- plains their tremendous popularity in dis- tributed communication, in which partic- tributed computing. Distribution cannot, ipants communicate by simply sending however, be made completely transparent and receiving messages. Although com- to the application, because it gives rise plex interaction schemes are still built to further types of potential failures (e.g., on top of such primitives, message pass- communication failures) that have to be ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

5 .118 Eugster et al. Fig. 4. RPC and derivatives: the producer per- Fig. 6. Decoupling synchronization with future re- forms a synchronous call, which is processed asyn- mote invocation: the producer is not blocked and can chronously by the consumer. access the reply later when it becomes available. dealt with explicitly. As shown in Figure 4, of a remote invocation is a handle through RPC differs from publish/subscribe in which the actual return values will be ac- terms of coupling: the synchronous na- cessed when needed. With this approach, ture of RPC introduces a strong time, known as future or future type message synchronization (on the consumer side1 ), passing [Yonezawa et al. 1987; Ananda and also space coupling (since an invoking et al. 1992] or wait-by-necessity [Caromel object holds a remote reference to each of 1993], the invoking thread can continue its invokees). processing and request the return value Several attempts have been made to re- later, thanks to the handle (Figure 6). move synchronization coupling in remote and avoid blocking the caller thread while waiting for the reply of a remote invo- 3.3. Notifications cation. A first variant consists in provid- ing a special flavor of asynchronous in- In order to achieve synchronization decou- vocation for remote methods that have pling, a synchronous remote invocation is no return values, as shown in Figure 5. sometimes split into two asynchronous in- For instance, CORBA [OMG 2002a] pro- vocations: the first one sent by the client vides a special one-way modifier that can to the server—accompanied by the invo- be used to specify such methods. This ap- cation arguments and a callback refer- proach leads to invocations with weak re- ence to the client—and the second one liability guarantees because the sender sent by the server to the client to return does not receive success or failure noti- the reply. This scheme can be easily ex- fications (this type of interaction is often tended to return several replies by hav- called fire-and-forget). The second, less re- ing the server make several callbacks to strictive variant supports return values, the client. Such notification-based interac- but does not make them directly available tion is widely used to ensure consistency to the calling thread. Instead, the result of Web caches [Wessels 1995]: upon down- load of Web contents, Web proxies receive a promise to be notified if any change occurs at the Web server. This implements a lim- ited form of publish/subscribe interaction in which Web proxies act as subscribers and the Web server as the publisher. This type of interaction—where sub- scribers register their interest directly Fig. 5. Decoupling synchronization with asyn- chronous remote invocation: the producer does not with publishers, which manage subscrip- expect a reply. tions and send events—corresponds to the so-called observer design pattern [Gamma 1 The distinction between consumer and producer et al. 1995] (Figure 7). It is gener- roles is not straightforward in RPC. We assume here ally implemented using asynchronous in- that an RPC that yields a reply attributes a consumer role to the invoker, while the invokee acts as pro- vocations in order to enforce synchro- ducer. As we will point out, the roles are inverted with nization decoupling. Although publishers asynchronous invocations (which yield no reply). notify subscribers asynchronously, they ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

6 .The Many Faces of Publish/Subscribe 119 all such consumers). Unlike the pub- lish/subscribe paradigm, the DSM model does not provide synchronization decou- pling because consumers pull new tuples from the space in a synchronous style (Figure 8). This limits the scalability of the Fig. 7. Notifications: producers and consumers model due to the required synchronization communicate using asynchronous invocations flow- between the participants. To compensate ing in both directions. the lack of synchronization decoupling, some modern tuple space systems like both remain coupled in time and in space. JavaSpaces [Sun 2002], TSpaces [Lehman Furthermore the communication manage- et al. 1999], and WCL [Rowstron 1998] ment is left to the publisher and can be- extend the Linda tuple space model with come burdensome as the system grows in asynchronous notifications. size. A similar communication abstraction, called rendezvous, has been introduced 3.4. Shared Spaces in the Internet Indirection Infrastructure (I3) [Stoica et al. 2002]. Instead of explic- The distributed shared memory (DSM) itly sending a packet to a destination, each paradigm [Li and Hudak 1989; Tam packet is associated with an identifier; this et al. 1990] provides hosts in a dis- identifier is then used by the receiver to ob- tributed system with the view of a com- tain delivery of the packet. This level of in- mon shared space across disjoint ad- direction decouples the act of sending from dress spaces, in which synchronization the act of receiving. and communication between participants take place through operations on shared data. The notion of tuple space was origi- 3.5. Message Queuing nally integrated at the language level in Message queuing [Blakeley et al. 1995] is Linda [Gelernter 1985], and provides a a more recent alternative for distributed simple and powerful abstraction for ac- interaction. In fact, the term message cessing shared memory. A tuple space is queuing is often used to refer to a family composed of a collection of ordered tu- of products (e.g., IBM Corporation [1995]; ples, equally accessible to all hosts of a Houston [1998]; DEC [1994]; Oracle distributed system. Communication be- [2002]) rather than to a specific interac- tween hosts takes place through the inser- tion scheme. Message queuing and tion/removal of tuples into/from the tuple publish/subscribe are tightly inter- space. Three main operations can be per- twined: message queuing systems usually formed: out() to export a tuple into a tuple integrate some form of publish/subscribe- space, in() to import (and remove) a tuple like interaction. Such message-centric from the tuple space, and read() to read (without removing) a tuple from the tuple space. The interaction model provides time and space decoupling, in that tuple pro- ducers and consumers remain anonymous with respect to each other. The creator of a tuple needs no knowledge about the future use of that tuple or its destination. An in- based interaction implements one-of-n se- mantics (only one consumer reads a given tuple) whereas read-based interaction can Fig. 8. Shared space: producers insert data asyn- be used to implement one-to-n message chronously into the shared space, while consumers delivery (a given tuple can be read by read data synchronously. ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

7 .120 Eugster et al. Fig. 9. Message queuing: messages are stored in Fig. 10. The publish/subscribe interaction para- a FIFO queue. Producers append messages asyn- digm decouples consumers and producers in terms chronously at the end of the queue, while consumers of space, time, and synchronization. dequeue them synchronously at the front of the queue. communication (Figure 10) by their lim- ited support for time, space and synchro- approaches are often referred to as nization decoupling. Table 1 summarizes message-oriented middleware (MOM) the decoupling properties of the aforemen- [Banavar et al. 1999b]. tioned communication models. At the interaction level, message queues recall much of tuple spaces: queues can be seen as global spaces, which are fed with 4. THE SIBLINGS: PUBLISH/SUBSCRIBE messages from producers. From a func- VARIATIONS tional point of view, message queuing sys- Subscribers are usually interested in par- tems additionally provide transactional, ticular events or event patterns, and not timing, and ordering guarantees not nec- in all events. The different ways of spec- essarily considered by tuple spaces. ifying the events of interest have led to In message queuing systems, messages several subscription schemes. In this sec- are concurrently pulled by consumers with tion we compare the two most widely used one-of-n semantics similar to those offered schemes, namely topic-based and content- by tuple spaces through the in() operation based publish/subscribe, as well the re- (Figure 9). These interaction model is of- cently proposed type-based subscription ten also referred to as point-to-point (PTP) scheme. queuing. Which element is retrieved by a 4.1. Topic-Based Publish/Subscribe consumer is not defined by the element’s structure, but by the order in which the el- The earliest publish/subscribe scheme was ements are stored in the queue (generally based on the notion of topics or subjects, first-in first-out (FIFO) or priority-based and has been implemented by many in- order). dustrial strength solutions (e.g., Altherr Similarly to tuple spaces, producers and et al. [1999]; Talarian Corporation [1999]; consumers are decoupled in both time and Skeen [1998]; TIBCO [1999]). It extends space. As consumers synchronously pull the notion of channels, used to bundle com- messages, message queues do not provide municating peers, with methods to charac- synchronization decoupling. Some mes- terize and classify event content. Partic- sage queuing systems offer limited sup- ipants can publish events and subscribe port for asynchronous message delivery, to individual topics, which are identified but these asynchronous mechanisms do by keywords. Topics are strongly simi- not scale well to large populations of con- lar to the notion of groups, as defined sumers because of the additional inter- in the context of group communication actions needed to maintain transactional, [Powell 1996] and often used for repli- timing, and ordering guarantees. cation [Birman 1993]. This similarity is not surprising, since some of the first 3.6. Summary systems to offer publish/subscribe inter- action were based on the Isis [Birman Traditional interaction paradigms es- et al. 1990] group communication toolkit sentially differ from publish/subscribe and the subscription scheme was thus ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

8 .The Many Faces of Publish/Subscribe 121 Table 1. Decoupling Abilities of Interaction Paradigms Space Time Synchronization Abstraction decoupling decoupling decoupling Message passing No No Producer-side RPC/RMI No No Producer-side Asynchronous RPC/RMI No No Yes Future RPC/RMI No No Yes Notifications (observer pattern) No No Yes Tuple spaces Yes Yes Producer-side Message queuing (Pull) Yes Yes Producer-side Publish/subscribe Yes Yes Yes inherently based on groups. Consequently, all the subtopics of that node. Topic names subscribing to a topic T can be viewed are generally represented with a URL- as becoming a member of a group T , and like notation and introduce a hierarchy publishing an event on topic T trans- very similar to the USENET news. Most lates accordingly into broadcasting that systems allow topic names to contain event among the members of T . Although wildcards, first introduced in TIBCO groups and topics are similar abstractions, Rendezvous [TIBCO 1999], which offer the they are generally associated with differ- possibility to subscribe and publish to sev- ent application domains: groups are used eral topics whose names match a given set for maintaining strong consistency be- of keywords, like an entire subtree or a tween the replicas of a critical component specific level in the hierarchy. in a local area network (LAN), whereas Consider the example of stock quotes topics are used to model large-scale dis- disseminated to a large number of inter- tributed interactions. ested brokers. In a first step, we are inter- In practice, topic-based publish/ ested in buying stocks, advertised by stock subscribe systems introduce a program- quote events. Such events consist of five ming abstraction which maps individual attributes: a global identifier, the name topics to distinct communication chan- of the company, the price, the amount of nels. They present interfaces similar to stocks, and the identifier of the selling those of the event service discussed in trader. Figure 11 shows how to subscribe Section 2, and the topic name is usually to all stock quotes, and Figure 12 gives specified as an initialization argument. an overview of the resulting distributed Every topic is viewed as an event service interaction. of its own, identified by a unique name, with an interface offering publish() and 4.2. Content-Based Publish/Subscribe subscribe() operations. The topic abstraction is easy to under- Despite improvements like hierarchical stand, and enforces platform interoper- addressing facilities and wildcards, the ability by relying only on strings as keys topic-based publish/subscribe variant rep- to divide the event space. Additions to the resents a static scheme which offers only topic-based scheme have been proposed by limited expressiveness. The content-based various systems. The most useful improve- (or property-based [Rosenblum and Wolf ment is the use of hierarchies to orches- 1997]) publish/subscribe variant improves trate topics. While group-based systems on topics by introducing a subscription offer flat addressing, where groups repre- scheme based on the actual content of sent disconnected event spaces, nearly all the considered events. In other terms, modern topic-based engines offer a form events are not classified according to some of hierarchical addressing, which permits predefined external criterion (e.g., topic programmers to organize topics accord- name), but according to the properties ing to containment relationships. A sub- of the events themselves. Such proper- scription made to some node in the hier- ties can be internal attributes of data archy implicitly involves subscriptions to structures carrying events, as in Gryphon ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

9 .122 Eugster et al. Fig. 11. Sample code for topic-based publish/subscribe. [Banavar et al. 1999a], Siena [Carzaniga resenting a subscription pattern. There et al. 2000], Elvin [Segall et al. 2000], and are several means of representing such Jedi [Cugola et al. 2001], or meta-data patterns: associated to events, as in the Java Mes- sage Service [Hapner et al. 2002]. —String: Subscription patterns are most Consumers subscribe to selective events frequently expressed using strings. by specifying filters using a subscription Filters must conform to a subscrip- language. The filters define constraints, tion grammar, such as SQL [Hapner usually in the form of name-value pairs et al. 2002; Oracle 2002; Lewis 1999], of properties and basic comparison op- OMG’s Default Filter Constraint Lan- erators (=, <, ≤, >, ≥), which identify guage [OMG 2002b], XPath [Altinel valid events. Constraints can be logically and Franklin 2000; Chan et al. 2002a; combined (and, or, etc.) to form complex Diao et al. 2002], or some propri- subscription patterns. Some systems, like etary language [Banavar et al. 1999a; the Cambridge Event Architecture (CEA) Carzaniga et al. 2001; Segall and Arnold [Bacon et al. 2000], also provide for event 1997]. Strings are then parsed by the correlation: participants can subscribe to engine. logical combinations of elementary events —Template object: Inspired by tuple-based and are only notified upon occurrence of matching, JavaSpaces [Freeman et al. the composite events. Subscription pat- 1999] adopts an approach based on tem- terns are used to identify the events plate objects. When subscribing, a par- of interest for a given subscriber and ticipant provides an object t, which indi- propagate events accordingly. For sub- cates that the participant is interested scribing, a variant of the subscribe() in every event that conforms to the type operation is provided by the event ser- of t and whose attributes all match the vice, with an additional argument rep- corresponding attributes of t, except for the ones carrying a wildcard (null). —Executable code: Subscribers provide a predicate object able to filter events at runtime. The implementation of that object is usually left to the applica- tion developer. An alternative approach, based on a library of filter objects imple- mented using reflection, was described in Eugster and Guerraoui [2001]. Exe- cutable code is not widely used in prac- tice because the resulting filters are ex- Fig. 12. Topic-based publish/subscribe interactions. tremely hard to optimize. ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

10 .The Many Faces of Publish/Subscribe 123 Fig. 13. Sample code for content-based publish/ subscribe. Figures 13 and 14 illustrate the use of string-based filters. The example out- lines how a content-based scheme enforces Fig. 15. Sample code for type-based publish/ a finer granularity than a static scheme subscribe. based on topics. To achieve the same functionality with topics, the subscriber notion of event kind is directly matched would either have to filter out irrelevant with that of event type. This enables a events, or topics would need to be split closer integration of the language and the into several subtopics—one for each com- middleware. Moreover, type safety can be pany (and recursively several subtopics ensured at compile-time by parameteriz- for different price “categories”). The first ing the resulting abstraction interface by approach leads to an inefficient use of the type of the corresponding events (with- bandwidth, while the second approach re- out any type cast in the resulting code). sults in a high number of topics and an In contrast, the aforementioned template- increased risk of redundant events. based approach of JavaSpaces [Freeman et al. 1999] considers the type of events as a dynamic property, and the result- 4.3. Type-Based Publish/Subscribe ing JavaSpace API forces the application Topics usually regroup events that present to perform explicit type casts. Similarly, commonalities not only in content, but the TAO CORBA Event Service [Harrison also in structure. This observation has led et al. 1997] does not view the type of an to the idea of replacing the name-based event object as an implicit attribute. topic classification model by a scheme The example in Figure 15 illustrates that filters events according to their type type-based subscription. Stock events can [Eugster et al. 2001]. In other terms, the be split into two distinct types: stock quotes (for sale) and stock requests, as shown in Figure 16. Brokers use stock requests to express their interest in buying stock. In contrast to quotes, requests have a range of possible prices. Subtyping can be used to subscribe to both stock quotes and requests. It is important to notice that type- based publish/subscribe can lead to a nat- ural description of content-based filtering through public members of the considered event type, while ensuring the encapsu- Fig. 14. Content-based publish/subscribe interac- lation of these events. This is achieved in tions. our example of Figure 15 by declaring only ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

11 .124 Eugster et al. Fig. 16. Type-based publish/subscribe interactions. private data members and enforcing their from different approaches, in terms of flex- access through public methods. ibility, reliability, scalability, and perfor- mance. Additional details on specific im- 4.4. Summary plementation issues of publish/subscribe systems can be found in Rosenblum and There exist several variants for design- Wolf [1997]; Banavar et al. [1999a]; and ing publish/subscribe systems, which offer Tai and Rouvellou [2000]. different degrees of expressiveness and, as we shall see in Section 5, different performance overhead. Topic-based pub- 5.1. Events lish/subscribe is rather static and prim- Events are found in two forms: messages itive, but can be implemented very effi- or invocations. In the first case, events are ciently. On the other hand, content-based delivered to a subscriber through a single publish/subscribe is highly expressive, but generic operation (e.g., notify()), while in requires sophisticated protocols that have the second case events trigger the execu- higher runtime overhead. Because of this tion of specific operations of the subscriber. additional overhead, one should generally prefer a static scheme whenever a pri- mary property ranges over a limited set 5.1.1. Messages. At the lowest level, of possible discrete values, for example, any data that goes on the network is a stock quotes/requests. As outlined in message. In most systems, event notifica- Eugster and Guerraoui [2001], additional tions take the form of messages, which are expressiveness can be achieved by apply- explicitly created by the application. Mes- ing content-based filters in the context of sages are generally made of a header that statically configured topics, in particular contains message-specific information in a types, to express constraints on properties generic format, and payload data that con- that are not within discrete ranges (e.g., tains user-specific information. Typical stock prices). header fields include message identifier, issuer, priority, or expiration time, which 5. THE INCARNATIONS: IMPLEMENTATION can be interpreted by the system or purely ISSUES serve as information for the consumers. Some systems (e.g., IBM MQSeries [Lewis This section discusses some implementa- 1999] and Oracle Advanced Queuing tion issues underlying publish/subscribe [Oracle 2002]) do not make any assump- schemes, and how these issues are ad- tion on the type of the payload data and dressed in current systems and proto- treat it as an opaque array of bytes. Some types. We focus on three major aspects of other systems (e.g., JMS [Hapner et al. publish/subscribe middleware: the events, 2002], CORBA Notification Service [OMG the media, and qualities of service, in the 2002b]) provide a set of message types, context of the classification introduced in such as text or XML messages. Finally, the previous sections. Furthermore, we some systems provide self-describing mes- discuss the different tradeoffs that result sages. TIBCO Rendezvous [TIBCO 1999], ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

12 .The Many Faces of Publish/Subscribe 125 for instance, defines a message format middleware medium. Media can be classi- that does not have header information, fied according to characteristics like their but allows the programmer to create his architecture or the guarantees they pro- or her own message structure based on a vide for the data, such as persistence or set of basic types that can be structured reliability. hierarchically. The type of messages can be queried later at runtime. Distributed 5.2.1. Architectures. The role of pub- Asynchronous Collections (DAC) [Eugster lish/subscribe systems is to permit the ex- et al. 2000] and Java Message Service change of events between producers and (JMS) [Hapner et al. 2002] even support consumers in an asynchronous manner. object messages, where the event can be Asynchrony can be implemented by hav- any serializable Java object. In most cases, ing producers send messages to a spe- messages are viewed as records with sev- cific entity that stores them, and forwards eral fields. them to consumers on demand. We call this approach a centralized architecture 5.1.2. Invocations. At a higher level, because of the central entity that stores we generally differentiate between invo- and forwards messages. This approach cations and messages. An invocation is is adopted by queuing systems like the directed to a specific type of object, and IBM MQSeries [Lewis 1999] and Oracle has well-defined semantics. The system Advanced Queuing [Oracle 2002], each ensures that all consumers have a match- of which is built on top of a centralized ing interface for processing the invocation. database. Applications based on such sys- The interface acts as a binding contract tems have strong requirements in terms between the invoker and the invokees. of reliability, data consistency, or trans- Systems which offer invocation-style actional support, but do not need a high interaction along with different seman- data throughput. Examples of such appli- tics and various addressing schemes are cations are electronic commerce or bank- usually termed messaging systems. They ing applications. incorporate additional logic on top of a Asynchrony can also be implemented publish/subscribe or message queuing sys- by using smart communication primitives tem to transform low-level messages into that implement store and forward mech- invocations to methods of the subscribers, anisms both in the producer’s and con- which must all be of the same type. While sumer’s processes, so that communication certain systems take into account return appears asynchronous and anonymous to values of invocations, the typed pub- the application without the need for an in- lish/subscribe models of COM+ [Sessions termediary entity. We call this approach a 1997] or the CORBA Event Service [OMG distributed architecture because there is 2001] typically only consider one-way no central entity in the system. TIBCO invocations. Producers invoke operations Rendezvous [TIBCO 1999] uses a decen- on some intermediary object (e.g., event tralized approach in which no process acts channel) that exhibits the same interface as a bottleneck or a single point of fail- as the actual consumers and forwards ure. Such architectures are well suited events to all registered consumers. COM+ for fast and efficient delivery of tran- furthermore provides a form of content- sient data, which is required for applica- based filtering, by offering the possibility tions like stock exchange or multimedia to specify values for invocation argu- broadcasting. ments in order to restrict the potential An intermediate approach, adopted for invocations. instance by Gryphon [Banavar et al. 1999a], Siena [Carzaniga et al. 2000], 5.2. The Media and Jedi [Cugola et al. 2001], consists in implementing the event notification ser- The transmission of data between pro- vice as a distributed network of servers. ducers and consumers is the task of the In contrast to completely decentralized ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

13 .126 Eugster et al. systems, this approach discharges the par- 2002; Banerjee et al. 2002; Ratnasamy ticipating processes by using dedicated et al. 2001; Zhuang et al. 2001] are com- servers to execute the complex proto- monly employed. cols required for persistence, reliability, or Efficient multicast of events in content- high-availability, as well as for content- based publish/subscribe systems remains based filtering and routing. There are dif- an issue. Gryphon and Siena both use al- ferent topologies for these servers. Jedi’s gorithms [Aguilera et al. 1999; Carzaniga event dispatchers are organized in a hi- et al. 2001] that deliver events to a logi- erarchical structure, where clients can cal network of servers in such a way that connect to any node. Subscriptions are an event is propagated only to the servers propagated upward the tree of servers. that manage subscribers interested by Such hierarchical topologies tend, how- that event. The performance of such ever, to heavily load the root servers, dissemination-based systems is strongly and the failure of a server might dis- affected by the cost of event filtering on connect the entire subtree. In Gryphon, each of the servers, which directly depends a graph summarizing the common inter- on the number of subscriptions in the sys- ests of subscribers is superimposed with tem. Highly efficient and scalable algo- the message broker graph, to avoid re- rithms have been recently proposed for fil- dundant matches. Siena uses subscription tering data in publish/subscribe systems and advertisement forwarding to set the [Altinel and Franklin 2000; Pereira et al. paths for notifications. Event servers keep 2000; Fabret et al. 2001; Campailla et al. track of useful information to efficiently 2001; Chan et al. 2002a; Diao et al. 2002]. match events with subscriptions. Sev- The problem of aggregating subscriptions eral server topologies have been consid- to increase the filtering speed at each ered, each with respective advantages and server, at the price of a small loss in pre- shortcomings. cision, has been studied in Chan et al. [2002a]. Irrespective of the filtering tech- 5.2.2. Dissemination. The actual trans- niques, the selective event routing in- mission of data can happen in various herent to content-based publish/subscribe ways. In particular, data can be sent using makes the exploitation of network-level point-to-point communication primitives, multicast primitives difficult. or using hardware multicast facilities like IP multicast [Deering n.d.]. The choice of 5.3. Qualities of Service the communication mechanism depends on factors such as the target environment The guarantees provided by the medium and the architecture of the system. for every message vary strongly between Centralized approaches like certain the different systems. Among the most message queuing systems are likely to use common qualities of service considered point-to-point communication primitives in publish/subscribe, we have persistence, between producers/consumers and the transactional guarantees, and priorities. centralized broker. As already mentioned, these systems focus more on strong guar- 5.3.1. Persistence. In RPC-like systems, antees than on high throughput and scal- a method invocation is by definition a tran- ability. Topic-based publish/subscribe sys- sient event. The lifetime of a remote invo- tems can straightforwardly benefit from cation is short and, if the invokee does not the vast amount of studies on group com- get a reply after a given period of time, it munication [Powell 1996] and the re- may reissue the request. The situation is sulting protocols to disseminate events different in publish/subscribe or queuing to subscribers. To ensure high through- systems. Messages may be sent without put, Internet protocol (IP) multicast or generating replies, and they may be pro- a wide range of reliable multicast proto- cessed hours after having been sent. The cols [Floyd et al. 1997; Holbrook et al. communicating parties do not control how 1995; Lin and Paul 1996; Castro et al. messages are transmitted and when they ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

14 .The Many Faces of Publish/Subscribe 127 are processed. Thus, the messaging sys- listening to the same topics may process tem must provide guarantees not only in messages in different orders because they terms of reliability, but also in terms of process messages at different speeds, even durability of the information. It is not suf- though communication channels are first ficient to know that a message has reached in, first out (FIFO). Priorities should be the messaging system that sits between considered as a best-effort quality of ser- the producers and consumers; we must vice (unlike persistence). get the guarantee that the message will Most publish/subscribe messaging sys- not be lost upon failure of that messaging tems (centralized or distributed) provide system. priorities, although the number of prior- Persistence is generally present in pub- ities and the way they are applied dif- lish/subscribe systems that have a central- fer. IBM MQSeries [Lewis 1999], Oracle ized architecture and store messages until Advanced Queuing [Oracle 2002], TIBCO consumers are able to process them. Queu- Rendezvous [TIBCO 1999], and the JMS ing systems like the IBM MQSeries [Lewis specification [Hapner et al. 2002] all sup- 1999] and Oracle Advanced Queuing port priorities. [Oracle 2002] offer persistence using an underlying database. Distributed pub- 5.3.3. Transactions. Transactions are lish/subscribe systems do not generally generally used to group multiple opera- offer persistence since messages are di- tions in atomic blocks that are either rectly sent by the producer to all sub- completely executed or not executed at all. scribers. Unless the producer keeps a copy In messaging systems, transactions are of each message, a faulty subscriber may used to group messages into atomic units: not be able to get missed messages when either a complete sequence of messages recovering. TIBCO Rendezvous [TIBCO is sent (received), or none of them is. For 1999] offers a mixed approach, in which instance, a producer that publishes sev- a process may listen to specific subjects, eral semantically related messages may store messages on persistent storage, and not want consumers to see a partial (in- resend missed messages to recovering sub- consistent) sequence of messages if it fails scribers. The Cambridge Event Architec- during emission. Similarly, a mission- ture [Bacon et al. 2000] provides a po- critical application may want to consume tentially distributed event repository for one or several messages, process them, event storage and efficient retrieval (with and only then commit the transaction. If searching facilities for simple and compos- the consumer fails before committing, all ite events) that enables the replaying of messages are still available for reprocess- stored sequences of events. ing after recovery. Due to their tight integration with databases, IBM MQSeries [Lewis 1999] 5.3.2. Priorities. Like persistence, mes- and Oracle Advanced Queuing [Oracle sage prioritization is a quality of service of- 2002] provide a wide range of transac- fered by some messaging systems. Indeed, tional mechanisms. JMS [Hapner et al. it may be desirable to sort the messages 2002] and TIBCO Rendezvous [TIBCO waiting to be processed by a consumer 1999] also provide transaction support in order of priority. For instance, a real- for grouping messages in the context of a time event may require immediate reac- single session. JavaSpaces [Freeman et al. tion (e.g., failure notification) and should 1999] provides lightweight transactional be processed before other messages. mechanisms to guarantee atomicity of Priorities affect messages that are in event production and consumption. An transit, that is, not being processed. Run- event published in a JavaSpace in the time execution priorities are handled by context of a transaction is not visible the application scheduler and are not outside the transaction until it is com- managed by the messaging system. In par- mitted. Similarly, a consumed event is ticular, this implies that two subscribers not removed from a JavaSpace until the ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

15 .128 Eugster et al. enclosing transaction commits. Several ployment of scalable and loosely cou- events can be produced and consumed in pled systems. To survey and compare the context of the same transaction. distributed event-based abstractions, we have introduced a classification based 5.3.4. Reliability. Reliability is an impor- on three dimensions: the decoupling in tant feature of distributed information time, space, and synchronization between systems. It is often necessary to have producers and consumers of information. strong guarantees about the reliable de- Decoupling is a desirable property be- livery of information to one or several cause it enforces scalability at the ab- distributed entities. Because of the loose straction level, by allowing participants synchronization between producers and to operate independently of one another. consumers of information, implementing At the implementation level, however, reliable event propagation (“guaranteed scalability remains a sensitive issue, be- delivery”) is challenging. cause publish/subscribe interaction can Centralized publish/subscribe systems be built on top of various communica- generally use reliable point-to-point chan- tion substrates and can easily be ham- nels to communicate with publishers and pered by an inappropriate architecture, subscribers, and keep copies of events in particular when publish/subscribe sys- on stable storage. Events are therefore tems are built on top of infrastructures reliably delivered to all subscribers, al- that were not designed with scalability in though a failure of the centralized event mind. broker may delay delivery. Scalability also often conflicts with Systems based on an overlay network other desirable properties. For instance, of distributed event brokers often use reli- highly expressive and selective subscrip- able protocols to propagate events to all or tions require complex and expensive fil- a subset of the brokers. Protocols based on tering and routing algorithms, and thus group communication [Powell 1996] and limit scalability. Similarly, strong relia- reliable application-layer multicast [Floyd bility guarantees involve important over- et al. 1997; Holbrook et al. 1995; Lin and heads, because events must be logged, Paul 1996; Castro et al. 2002; Banerjee and missed events must be detected and et al. 2002; Ratnasamy et al. 2001; Zhuang retransmitted. Even protocols developed et al. 2001] are good candidates as they especially for wide-area networks, such are resilient to the failure of some of the as the sender-reliable Reliable Multicast brokers. Individual publishers and sub- Transport Protocol (RMTP) [Lin and Paul scribers generally communicate with the 1996], do not scale well to large numbers nearer broker using point-to-point com- of subscribers because of the considerable munication channels. amount of traffic resulting from message Finally, systems that let publishers and acknowledgments. subscriber communicate directly with Recently, probabilistic protocols have each other, such as TIBCO Rendezvous received increasing attention since they [TIBCO 1999], also use lightweight reli- match the decoupled and peer-based na- able multicast protocols. As events are ture of publish/subscribe systems. Instead generally not kept in the system for of providing deterministic (guaranteed) re- failed or disconnected (time-decoupled) liability, probabilistic multicast protocols subscribers, guaranteed delivery must be ensure that a given event will reach all implemented by deploying dedicated pro- subscribers with a very high and quantifi- cesses that store events and replay them able probability [Birman et al. 1999]. In- to requesting subscribers. tegration of such probabilistic protocols in content-based publish/subscribe systems remains a challenging issue. 6. CONCLUDING REMARKS While programming abstractions for Publish/subscribe is a distributed inter- publish/subscribe are plentiful, designing action paradigm well adapted to the de- appropriate algorithms for deploying such ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

16 .The Many Faces of Publish/Subscribe 129 systems on a large scale is still an open BIRRELL, A. D. AND NELSON, B. J. 1983. Implement- issue, and tradeoffs must be dealt with to ing remote procedure calls. In Proceedings of the ACM Symposium on Operating System Prin- cope with scalability, expressiveness and ciples (Bretton Woods, NH). ACM Press, New quality of service. Significant research ef- York, NY, 3. forts remain to be invested, in particular BLAKELEY, B., HARRIS, H., AND LEWIS, J. 1995. Mes- as tribute to the unpredictability of the saging and Queuing Using the MQI. McGraw- Internet. Hill, New York, NY. CAMPAILLA, A., CHAKI, S., CLARKE, E., JHA, S., AND VEITH, H. 2001. Efficient filtering in publish- REFERENCES subscribe systems using binary decision. In Pro- ceedings of the International Conference on Soft- AGUILERA, M. K., STROM, R. E., STURMAN, D. C., ASTLEY, ware Engineering. 443–452. M., AND CHANDRA, T. D. 1999. Matching events CAROMEL, D. 1993. Towards a method of object- in a content-based subscription system. In Pro- oriented concurrent programming. Commun. ceedings of the Eighteenth ACM Symposium ACM 36, 90–102. on Principles of Distributed Computing (PODC CARZANIGA, A., ROSENBLUM, D., AND WOLF, A. 2000. ’99, Atlanta, GA). ACM Press, New York, NY, Achieving scalability and expressiveness in an 53–61. Internet-scale event notification service. In Pro- ALTHERR, M., ERZBERGER, M., AND MAFFEIS, S. 1999. ceedings of the Nineteenth ACM Symposium on iBus—a software bus middleware for the Java Principles of Distributed Computing (PODC ’00). platform. In Proceedings of the International ACM Press, New York, NY. Workshop on Reliable Middleware Systems. CARZANIGA, A., ROSENBLUM, D., AND WOLF, A. 2001. 43–53. Design and evaluation of a wide-area event noti- ALTINEL, M. AND FRANKLIN, M. 2000. Efficient Fil- fication service. ACM Trans. Comput. Syst. 19, 3 tering of XML documents for selective dissemi- (Aug.), 332–383. nation of information. In Proceedings of the 26th CASTRO, M., DRUSCHEL, P., KERMARREC, A.-M., AND International Conference on Very Large Data ROWSTRON, A. 2002. SCRIBE: A large-scale Bases (VLDB ’00). 53–64. and decentralized application-level multicast in- ANANDA, A., TAY, B., AND KOCH, K. 1992. A survey frastructure. IEEE J. Sel. Areas Commun. 20, 8 of asynchronous remote procedure calls. ACM (Oct.), 1489–1499. Operat. Syst. Rev. 26, 2 (July), 92–109. CHAN, C.-Y., FAN, W., FELBER, P., GAROFALAKIS, M., AND BACON, J., MOODY, K., BATES, J., R. HAYTON, MA, C., RASTOGI, R. 2002a. Tree pattern aggregation MCNEIL, A., SEIDEL, O., AND SPITERI, M. 2000. for scalable XML data dissemination. In Pro- Generic support for distributed applications. ceedings of the 28th International Conference on IEEE Comput. 33, 3 (Mar.), 68–76. Very Large Data Bases (VLDB ’02, Hong Kong, BANAVAR, G., CHANDRA, T., MUKHERJEE, B., China). NAGARAJARAO, J., STROM, R., AND STURMAN, D. CHAN, C.-Y., FELBER, P., GAROFALAKIS, M., AND RASTOGI, 1999a. An efficient multicast protocol for R. 2002b. Efficient filtering of XML docu- content-based publish-subscribe systems. In ments with XPath expressions. In Proceedings of Proceedings of the 19th International Conference the 18th International Conference on Data Engi- on Distributed Computing Systems (ICDCS’99). neering (ICDE ’02, San Jose, CA). BANAVAR, G., CHANDRA, T., STROM, R., AND STURMAN, D. CHUNG, P., HUANG, Y., YAJNIK, S., LIANG, D., SHIH, J., 1999b. A case for message oriented middle- WANG, C.-Y., AND WANG, Y. 1998. DCOM and ware. In Proceedings of the 13th International CORBA side by side, step by step, and layer by Symposium on Distributed Computing (DISC layer. C++ Rep. 10, 1 (Jan.), 18–29. 99). 1–18. CUGOLA, G., NITTO, E. D., AND FUGETTA, A. 2001. The BANERJEE, S., BHATTACHARJEE, B., AND KOMMAREDDY, C. Jedi event-based infrastructure and its appli- 2002. Scalable application layer multicast. In cation to the development of the opss wfms. Proceedings of ACM SIGCOMM. ACM Press, IEEE Trans. Softw. Eng. 27, 9 (Sept.), 827– New York, NY. 850. BIRMAN, K. 1993. The process group approach DEC. 1994. DECMessageQ: Introduction to Mes- to reliable distributed computing. Commun. sage Queuing. Digital Equipment Corporation; ACM 36, 12 (Dec.), 36–53. now part of Hewlett Packard, Palo Alto, CA. BIRMAN, K., COOPER, R., JOSEPH, T., MARZULLO, K., DEERING, S. N. D. Host extension for ip multicast. MAKPANGOU, M., KANE, K., SCHMUCK, F., AND WOOD, IETF RFC 1112. Internet Engineering Task M. 1990. The Isis System Manual. Dept. of Force (Web site: www.ietf.org). Computer Science, Cornell University, Ithaca, DIAO, Y., FISCHER, P., FRANKLIN, M., AND TO, R. 2002. NY. YFilter: Efficient and scalable filtering of XML BIRMAN, K., HAYDEN, M., O. OZKASAP, XIAO, Z., BUDIU, documents. In Proceedings of the 18th Interna- M., AND MINSKY, Y. 1999. Bimodal multicast. tional Conference on Data Engineering (ICDE ACM Trans. Comput. Syst. 17, 2 (May), 41–88. ’02, San Jose, CA). ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

17 .130 Eugster et al. EUGSTER, P. AND GUERRAOUI, R. 2001. Content- HAUSWIRTH, M. AND JAZAYERI, M. 1999. A compo- based publish/subscribe with structural reflec- nent and communication model for push sys- tion. In Proceedings of the 6th Usenix Con- tems. In Proceedings of Software Engineering— ference on Object-Oriented Technologies and ESEC/FSE’99. 20–28. Systems (COOTS’01). HOLBROOK, H., SINGHAL, S., AND CHERITON, D. 1995. EUGSTER, P., GUERRAOUI, R., AND DAMM, C. 2001. Log-based receiver-reliable multicast for dis- On objects and events. In Proceedings of the tributed interactive simulation. In Proceedings OOPSLA ’01 Conference on Object Oriented of ACM SIGCOMM’95. Programming Systems Languages and Applica- HORSTMANN, M. AND KIRTLAND, M. 1997. DCOM ar- tions. ACM Press, New York, NY, 254–269. chitecture. Available online at www.microsoft. EUGSTER, P., GUERRAOUI, R., AND SVENTEK, J. 2000. com/com/tech/DCOM.asp. Distributed Asynchronous Collections: Abstrac- HOUSTON, P. 1998. Building distributed applica- tions for publish/subscribe interaction. In Pro- tions with message queuing middleware White ceedings of the 14th European Conference on paper. Available online at http://msdn.microsoft. Object-Oriented Programming (ECOOP’2000). com/library/en-us/dnmqqc/html/bldappmq.asp. FABRET, F., JACOBSEN, H., LLIRBAT, F., PEREIRA, J., HUANG, Y. AND GARCIA-MOLINA, H. 2001. Pub- ROSS, K., AND SHASHA, D. 2001. Filtering algo- lish/subscribe in a mobile enviroment. In Pro- rithms and implementations for very fast pub- ceedings of MobiDE. 27–34. lish/subscribe systems. In Proceedings of ACM IBM CORPORATION. 1995. MQSeries: An introduc- SIGMOD (Santa Barbara, CA). 115–126. tion to messaging and queuing. Tech. Rep. FLOYD, S., JACOBSON, V., LIU, C., MCCANNE, S., AND GC33-0805-01. IBM Corporation, Yorktown ZHANG, L. 1997. A reliable multicast frame- Heights, NY. work for light-weight sessions and application LEHMAN, T., LAUGHRY, S. M., AND WYCKOFF, P. 1999. level framing. IEEE/ACM Trans. Netw. 5, 6, Tspaces: The next wave. In Proceedings of the 784–803. Hawaii International Conference on System Sci- FRANKLIN, M. AND ZDONIK, S. 1997. A framework for ences (HICSS-32). scalable dissemination-based systems. In Pro- LEWIS, R. 1999. Advanced Messaging Applications ceedings of the 12th ACM Conference on Object- with MSMQ and MQSeries. QUE. Oriented Programming Systems, Languages and Applications (OOPSLA’97). ACM Press, New LI, K. AND HUDAK, P. 1989. Memory coherence in York, NY, 94–105. shared memory systems. ACM Trans. Comput. Syst. 7, 4 (Nov.), 321–359. FREEMAN, E., HUPFER, S., AND ARNOLD, K. 1999. JavaSpaces Principles, Patterns, and Practice. LIN, J. AND PAUL, S. 1996. A reliable multicast Addison-Wesley, Reading, MA. transport protocol. In Proceedings of the IEEE INFOCOM’96. IEEE Computer Society Press, GAMMA, E., HELM, R., JOHNSON, R., AND VLISSIDES, J. Los Alamitos, CA, 1414–1424. 1995. Design Patterns, Elements of Reusable Object-Oriented Software. Addison-Wesley, OMG. 2001. CORBA Event Service Specification. Reading, MA. Object Management Group, Needham, MA. GARLAN, D. AND NOTKIN, D. 1991. Formalizing de- OMG. 2002a. The Common Object Request sign spaces: Implicit invocation mechanisms. Broker: Core Specification. Object Management In VDM ’91: Formal Software Development Group, Needham, MA. Methods. Lecture Notes in Computer Science, OMG. 2002b. CORBA Notification Service Speci- vol. 551. Springer-Verlag, Berlin, Germany, fication. Object Management Group, Needham, 31–44. MA. GELERNTER, D. 1985. Generative communication Oracle 2002. Oracle9i Application Developer’s in Linda. ACM Trans. Program. Lang. Syst. 7, Guide—Advanced Queuing. Oracle, Redwood 80–112. Shores, CA. HAPNER, M., BURRIDGE, R., SHARMA, R., FIALLI, J., AND PAPADOPOULOS, G. AND ARBAB, F. 1998. Coordination STOUT, K. 2002. Java Message Service. Sun models and languages. In The Engineering of Microsystems Inc., Santa Clara, CA. Large Systems. Advances in Computers, vol. 46. HARRISON, T., LEVINE, D., AND SCHMIDT, D. 1997. The Academic Press, New York, NY. design and performance of a real-time CORBA PEREIRA, J., FABRET, F., LLIRBAT, F., AND SHASHA, event service. In Proceedings of the 12th ACM S. 2000. Efficient matching for Web-based Conference on Object-Oriented Programming publish/subscribe systems. In Proceedings of Systems, Languages and Applications (OOP- CoopIS. SLA ’97). ACM Press, New York, NY, 184– POWELL, D. 1996. Group communication. Com- 200. mun. ACM 39, 4 (Apr.), 50–97. HAUSWIRTH, M. 1999. Internet-scale push systems RATNASAMY, S., HANDLEY, M., KARP, R., AND SHENKER, for information distribution—architecture, com- S. 2001. Application-level multicast using ponents, and communication. Ph.D. disserta- content-addressable networks. In Proceedings of tion. Technical University of Vienna, Vienna, the Third International Workshop on Networked Austria. Group Communication. ACM Computing Surveys, Vol. 35, No. 2, June 2003. 

18 .The Many Faces of Publish/Subscribe 131 ROSENBLUM, D. AND WOLF, A. 1997. A design frame- TAI, S. AND ROUVELLOU, I. 2000. Strategies for work for Internet-scale event observation and integrating messaging and distributed object notification. In Proceedings of the 6th European transactions. In Proceedings of the IFIP/ACM Software Engineering Conference/ACM SIG- International Conference on Distributed Sys- SOFT 5th Symposium on the Foundations of tems Platforms and Open Distributed Process- Software Engineering. ACM Press, New York, ing (Middleware ’00). ACM Press, New York, NY, NY, 344–360. 308–330. ROWSTRON, A. 1998. Wcl: A co-ordination language TALARIAN CORPORATION. 1999. Everything you need for geographically distributed agents. World to know about middleware: Mission-critical Wide Web 1, 3, 167–179. interprocess communication. White paper. SEGALL, B. AND ARNOLD, D. 1997. Elvin has left Talarian Corporation, Los Altos, CA (now part the building: A publish/subscribe notification of TIBCO, Palo Alto, CA). Available online at service with quenching. In Proceedings of the http://www.talarian. com/. Australian UNIX and Open Systems User TAM, M., SMITH, J., AND FARBER, D. 1990. A Group Conference (AUUG’97). Available online taxonomy-based comparison of several dis- at http://www.dtsc.edu.au/. tributed shared memory systems. ACM Operat. SEGALL, B., ARNOLD, D., BOOT, J., HENDERSON, M., AND Syst. Rev. 24, 3 (July), 40–67. PHELPS, T. 2000. Content based routing with TAY, B. H. AND ANANDA, A. L. 1990. A survey Elvin4. In AUUG2K (Canberra, Australia). of remote procedure calls. ACM Operat. Syst. SESSIONS, R. 1997. COM and DCOM: Microsoft’s Rev. 24, 3 (July), 68–79. Vision for Distributed Objects. John Wiley & TIBCO. 1999. TIB/Rendezvous. White paper. Sons, New York, NY. TIBCO, Palo Alto, CA. SKEEN, D. 1998. Vitria’s Publish-Subscribe WESSELS, D. 1995. Intelligent caching for world- Architecture: Publish-Subscribe Overview. wide-web objects. In Proceedings of INET’95 http://www.vitria.com. (Honolulu, HI). STOICA, I., ADKINS, D., ZHUANG, S., SHENKER, S., AND YONEZAWA, A., SHIBAYAMA, E., TAKADA, T., AND HONDA, SURANA, S. 2002. Internet indirection infras- Y. 1987. Modeling and programming in an tructure. In Proceedings of ACM SIGCOMM. object-oriented concurrent language ABCL/1. ACM Press, New York, NY. In Object-Oriented Concurrent Programming, SULLIVAN, K. AND NOTKIN, D. 1990. Reconciling en- A. Yonezawa, J.-P. Briot, and E. Shiboyama, vironment integration and component inde- Eds. MIT Press, Cambridge, MA, Chap. 4, pendence. In Proceedings of the Fourth ACM pp. 55–89. SIGSOFT Symposium on Software Develop- ZHUANG, S., ZHAO, B., JOSEPH, A., KATZ, R., AND ment environments. ACM Press, New York, NY, KUBIATOWICZ, J. 2001. Bayeux: An architec- 22–33. ture for scalable and fault-tolerant wide-area SUN. 2000. Java Remote Method Invocation Spec- data dissemination. In Proceedings of the ification. Sun Microsystems, Santa Clara, CA. Eleventh International Workshop on Network SUN. 2002. JavaSpaces Service Specification. Sun and Operating System Support for Digital Audio Microsystems, Santa Clara, CA. and Video (NOSSDAV ’01). Received January 2001; revised December 2002; accepted March 2003 ACM Computing Surveys, Vol. 35, No. 2, June 2003.