Information flow based event distribution middleware

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

Information Flow Based Event Distribution Middleware

Guruduth Banavar1, Marc Kaplan1, Kelly Shaw2, Robert E. Strom1, Daniel C. Sturman1, and Wei Tao3

1

IBM T. J. Watson Research Center

Hawthorne, NY

{banavar, kaplan, strom, sturman}

2

Dept. of Computer ScienceStanford Universitykashaw@cs.stanford.edu

3

Dept. of Computer Science

University of Utahtao@cs.utah.edu

@

Abstract

Event distribution middleware supports the integration ofdistributed applications by accepting events frominformation producers and disseminating applicableevents to interested consumers. In this paper we present aflexible new model, the Information Flow Graph (IFG), forspecifying the flow of information in such a system. Weillustrate the use of the IFG for: (1) content-basedpublish/subscribe; (2) stateless event transformations thatconsolidate events from diverse sources; and (3) statefulevent interpretation functions for deriving trends,summaries, and alarms from published events and fordefining equivalent event sequences. We introduce twotechniques for efficient implementation of such systems: (1) a flow graph rewriting optimization which allowsstateless IFGs to be converted to a form which can exploitefficient multicast technology developed for content-basedpublish/subscribe systems; and (2) an algorithm forconverting a sequence of events to the shortest equivalentsequence of events with respect to an event interpretationfunction.

1Introduction

Event distribution middleware is growing inimportance with the need to glue together heterogeneous,distributed, and dynamically changing components oflarge information systems. The middleware performs thefunction of collecting messages from producers, filteringand transforming them as necessary, and routing them tothe appropriate consumers. This approach is currentlybeing applied in domains such as finance, processautomation, and transportation. The Gryphon project atIBM Research is advancing the technology of eventdistribution middleware and extending its range ofapplication.

Using subject-based publish/subscribe systems as astarting point, Gryphon has introduced the followingextensions:

1.Content-based publish/subscribe. Rather thantreating events as uninterpreted data with a single“subject” field, we associate schemas with eventstreams, and express subscriptions as predicates overall fields in the event.

2.Stateless event transformations. To supportscenarios where events from multiple publishers aresimilar but not identical, Gryphon supportstransformations on events. These operations arestateless in the sense that they do not depend uponprior events.

3.Event stream interpretations. To supportsubscribers who are interested not only in publishedevents but also in events such as summaries, trends,and alarms, derived from a sequence of relatedevents, the Gryphon model supports several“stateful” operations as well (operations whoseresults depend on the event history). State can alsobe used to express the “meaning” of an eventstream, and by implication, the equivalence of twoevent streams.

In this paper, we describe Gryphon’s approach to eventdistribution middleware based on the concept ofinformation flow graphs (IFGs). We show that IFGs notonly are a flexible and powerful model for expressingevent flows, but also can be efficiently implemented on adistributed network of event brokers.

Section 2 defines the IFG model. The motivations forcontent-based subscription, and efficient and scalablealgorithms developed by the Gryphon project for matchingevents to subscriptions and delivering them are omittedhere, since they are discussed in detail in [1] and [3].Section 3 introduces motivating examples of stateless andstateful event transformations. Section 4 discusses theimplementation problems of the IFG approach, and thenpresents an overview of two implementation techniques wehave developed to address these problems. Section 5discusses related work, the current status of this work, andconcludes.

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

2The Information Flow Graph

In Gryphon, an event system is modeled as aninformation flow graph. Figure 1 illustrates such an IFGfor a collection of stock services. An IFG contains thefollowing components:

OInformation spaces. They are either event histories(circles, e.g. states (squares, e.g. .Event histories are lists of events. They growmonotonically over time as events are added. Statescapture selected information about event streams, andare typically not monotonic. The type of aninformation space is defined by an informationschema. In this paper, we assume that each event is atyped tuple. For instance, the informationspace is a sequence of events having the schema[issue: string, price: integer, capital: integer]. The information space is a state represented as a keyedrelation associating the name of a stock issue with itsmaximum price and current price. Certain eventhistories, represented as unfilled circles, are sourcesor sinks; these represent the information providersand consumers.

ODataflows. These are directed arcs (arrows)connecting nodes in the graph. The graph is requiredto be acyclic. Sources must have only out-arcs andsinks in-arcs. State nodes must have only a singlein-arc. The arcs determine how the contents of theinformation spaces change as events enter thesystem.

There are four types of dataflows, indicated by thelabels on the arcs:

OSelect. This arc connects two event histories havingthe same schema. Associated with each select arc isa predicate on the attributes of the event typeassociated with the information space. An example

of a predicate is the expression (issue=”IBM” &price<120). All events in the information space at thesource of the arc which satisfy the predicate aredelivered to the information space at the destinationof the arc.

OTransform. This arc connects any two event historieswhich may have different event schemas ES and ED.Associated with each transform arc is a rule formapping an event of type ES into an event of type ED.For example, the transform arc connecting the spacerule

[issue:i, price:p, capital:c] 9 [name: NAS(i), price:p, volume:c/p]

which maps the issue to a name using the functionNAS, and derives volume as capital divided by price.Whenever a new event arrives at the space at thesource of the arc, it is transformed using the rule anddelivered to the space at the destination of the arc.OCollapse. This arc connects an event history to astate. Associated with each collapse arc is a rule forcollapsing a sequence of events to a state. The rulemaps a new event and a current state into a newstate. For example the following rule defines thecollapse arc from the space to the space[n, p, v], «n: p > maxP, curP¬ s 9 «n: p, p¬ s

[n, p, v], «n: p > maxP, curP¬ s9 «n: maxP, p¬ s

This rule contains two patterns: in each, the tuple inthe state is found whose key matches the name field nof the event [n, p, v]. If the price p in the event isgreater than the current max price maxP, the firstpattern is triggered, and the state is updated byreplacing maxP and curP with p. Otherwise, thesecond pattern is triggered, and only curP is replaced.Given an initial state (in this example, a maximumand current price of zero for all stocks), the state at

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

is updated each time a new event is added to.

OExpand. This is the inverse of Collapse. This arclinks a state to an information space. Associatedwith each arc is a collapse rule. When the state at thesource of the arc changes, the destination space isupdated so that the sequence of events it containscollapses to the new state. Notice that unlike theother dataflows, expand is non-deterministic. For agiven state, there may be many possible eventsequences which map to the state, or there may benone. The non-determinism is further constrained bythe need for information spaces to be observablymonotonic: that is, an expansion may not“undeliver” an event already delivered to a consumer.We restrict the language to avoid the case in whichthere is no possible event sequence, but we exploitthe non-determinism to give flexibility to theimplementation to deliver one of a set of equivalentevent sequences.

In addition to the above four operations, there are twooperations implicit in the graph. Fan-in to an event historyproduces a merge of the events --- there isnon-determinism here too, as multiple interleavings arepossible. Fan-out from an event history replicates theevents.

3Motivating Examples of IFGs

Consider regions 1 and 2 of the stock event systemshown in Figure 1. Each of the regions has aninformation space, a collection of producers, and acollection of consumers with content-based selections onthe events of the information spaces and .These regions are examples of “pure content-basedpub/sub” systems. The consumers with content-basedselections correspond to subscribers.

Region 3 represents a service attempting to integratethe two spaces and have different conventions for issue names; therefore it isdesirable to map the local issue names to a common namevia some conversion table. Furthermore, one exchangedelivers trades using price and volume, the other usingprice and total capital (price times volume). It is thereforenecessary to map these into either one of the two formatsor a common format. The result is a new informationinformation spaces, but in a common format, enabled bythe use of stateless event transforms. Subscribers to thenew service can deal with this new space and need noteven be aware of the existence of the original suppliers.

Region 4 represents a collection of subscribers to who are interested in particular stock events,but whose requirements on guaranteed delivery areweaker. It should be pointed out that an event history,such as total order depends upon non-deterministic factors, such asthe order in which events from the previous section guarantee that all subscribers to receive the events in the same order.Guaranteeing this total order adds to the cost of thedelivery protocol.

However, the subscribers to region 4 have a weakerrequirement: they are interested only in tracking themaximum price and current price of each stock issue.They cannot ignore ordering entirely (otherwise theymight swap today’s price of IBM with yesterday’s price),but they can ignore the order between today’s IBM priceand today’s HP price. And under appropriate conditions,messages may be dropped altogether. These subscribersexpress this requirement by defining an eventinterpretation — a mapping of the event sequence into astate which captures precisely the information relevant tothese consumers, namely the current and maximum priceof each issue.

The collapse arc converts the event sequence from into a state representing this eventinterpretation. The expand arc converts the state back intoan event sequence. The associated rule on this arc is theidentical rule from the collapse arc. Therefore, the eventsin interpretation is the same as the interpretation of theevents in collapse and expand as a null operation and deliverexactly the same events to and to However, the non-determinism of expand permits cheapersolutions, in which some events can be dropped orpermuted. One instance where this flexibility is importantoccurs when the subscriber disconnects from the networkwithout terminating the subscription and later reconnects.Rather than bombarding the subscriber with all the eventswhich would have been delivered during the disconnectperiod, the system instead delivers a much shorterequivalent system that preserves the specifiedinterpretation: the current and maximum price of eachstock. In the next section, we show an algorithm forcomputing the minimal event sequence after a disconnectand reconnect.

Once the collapse operation has been introduced, it ispossible to use it not only for equivalent event sequences,but also for deriving new types of events from the state. Inregion 5, we show a collapse operation introduced tocompute a state which tracks for each stock

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

issue, the average price and the magnitude of the largestrecent price drop. From that state, we can introduce anexpand operation to produce a new event space named. Consumers wishing to be alerted to “alarms”such as a drop exceeding 20 can then subscribe to thisderived event space.

4Implementation Techniques

IFGs are logical descriptions of the flow of events in asystem. Ultimately, this description must be realized on aphysical network of message brokers. The problem ofmapping an arbitrary logical IFG to a physical brokernetwork is nontrivial. If done naively, the performance ofefficient content-based routing systems (such as the one in[3]) cannot be exploited at all.

In this section, we present solutions to twoimplementation problems.

The first problem is the consolidation of transformoperations at the periphery and select operations at theinterior, so that we can use existing techniques forefficient content-based subscription as the basis for animplementation of an IFG with both selects andtransforms.

The second problem is how to implement expand byproducing the shortest event sequence corresponding to agiven change in state.

together and moved closer to the subscribers. (Becausetransforms may destroy information, they cannot, ingeneral be pushed ahead of selects.) This will allow us touse the content-based routing protocols described in [3] toimplement the select operations within the broker network,then perform the transform operation at the periphery ofthe broker network. Furthermore, we may be able tooptimize away transform operations on events that wouldbe eliminated by later select operations.

Rewriting the IFG can be done by an automated systemso that, while users specify information flows as a series ofselects and transforms that closely matches the way theythink about the flow and processing of events, the systemcan optimize the processing of information flows.

The rules for rewriting graphs are described below.Selects can be pushed ahead of transforms.

For any dataflow in which a transform TA is followedby select SA, there is an equivalent dataflow of the formSB followed by TB. To see how, observe that the predicateof SA must be a function of constants and the functionoutputs of TA. We can construct a predicate for SB that

4.1 Reordering Selects and Transforms

Our approach to efficient realization of IFGs is toreduce an arbitrary IFG to one that can be efficientlyimplemented on a content-based routing system. Thebasic idea is to rewrite the IFG so that all the selectoperations are lumped together and moved closer topublishers, and all the transform operations are lumped

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

will choose the same messages as SA, by simplysubstituting the appropriate functions of TA for theattributes in the predicate of SA.

For example (in all of the examples in this section, thesemicolon is used to mean “followed by” in an informationflow):

TA: [x1, x2] => [y1=f1(x1,x2,c1), y2=f2(x1,x2,c2)];SA: (p(y1,y2,d))

can be rewritten as:

SB: (p(f1(x1,x2,c1), f2(x1,x2,c2),d));

TB: [x1,x2] => [y1=f1(x1,x2,c1), y2=f2(x1,x2,c2)]

where x1,x2,y1,y2 are attribute names, and c1,c2,d areconstants.

Selects and Transforms can be combined.

Observe that a sequence of selects is just a conjunctionof predicates. Thus, selects SA: (p(...)) followed by SB: (q(...))can be rewritten as SC: (p(...) & q(...)).

Similarly, we can perform variable substitutions from afirst transform into a second. For example:

[x,y] => [y1:=f1(x1,x2,c1), y2:=f2(x1,x2,c2)];[y1,y2] => [z1:=g1(y1,y2,d1), z2:=g2(y1,y2,d2)]

can be rewritten as

[x,y]=> [z1:=g1(f1(x1,x2,c1),f2(x1,x2,c2),d1),z2:= g2(f1(x1,x2,c1),f2(x1,x2,c2),d2)]

By applying the above rewriting rules, any sequence ofselects and transforms can be reduced to a single selectfollowed by a single transform. For example, starting withthe sequence [T T S T S T], we push selects ahead oftransforms to get [S S T T T], and combine selects andtransforms to get [S T].

Once a dataflow has been reduced so that all pathsfrom publishers to subscribers may be represented by a[Select;Transform] pair, the single select can be furtheroptimized. A straightforward application of the rewritingrules may cause many common subexpressions to appearwithin the combined predicate. A smart implementationcan discover those, just like any good compiler, and avoidrecomputation of sub-functions. Likewise, the final, singletransform will likely contain many commonsubexpressions and many of those will have already beencomputed for the select. A smart implementation cancache them and/or tag each selected message with them asauxiliary attributes.

Externalizing I/S nodes as terminal nodes.

As we combine and rearrange the select and transformoperations specified by an IFG, we may eliminate orchange the meaning of the non-terminal I/S nodes.However, the users who specify IFGs may wish to use anon-terminal or internal I/S node as a publication and/orsubscription point. (e.g., the node labeled Figure 1.) To avoid losing such I/S nodes due torewriting an IFG:

1.For each internal node that may be used as a

publication point we add an explicit terminal nodewith an identity arc that connects to the internalnode.

2.For each internal node that may be used as a

subscription point we add an explicit terminal nodewith an identity arc from the internal node to theterminal node.

Thus, all publication and subscription points arerepresented by the terminal nodes of the IFG. All arcs andinternal nodes can be subjected to rewriting rules andoptimizations.

Rewriting the entire IFG.

Consider an IFG, G1, with all interesting publicationand subscription points externalized. We can construct anequivalent IFG, G2, as follows. For each publication andsubscription point in G1, add a like-named publication orsubscription point to G2. For each possible pair (p,s) ofpublication and subscription points in G1, if there is a pathfrom p to s in G1 consisting of arcs labeled withtransforms and/or select operations:

p =>(ts1; ts2; ...; tsk) =>s

then add a single arc from p to s in G2 that is labeled withthe (select;transform) pair of operations that is equivalentto (ts1; ts2; ...; tsk), as given by the above rewrite rules.Example

Consider the IFG for stock services shown in Figure2a. It is similar to Figure 1, integrating two independentstock markets and into the combinedinformation space . In this example, themessages from both sources must first undergo a lookupconversion (T1 and T2). A capital field is then added toeach message which is the product of the number of sharesin the trade and the price per share (T3). The newvalue-added information space from by using a select operation (S1), whichselects those trades involving over a million dollars.

As shown in Figure 2b, we split each externally visibleI/S into two: one for publishers and another forsubscribers, e.g., is split into andtransform, all the advertised content is still available todynamically joining publishers and subscribers.

Next, we identify all paths in the graph of Figure 2b toarrive at Figure 2c. For each path that has more than oneselect or transform, we then apply the rewrite rules so that1) selects are moved before transforms and 2) a series ofselects or a series of transforms are combined into a single

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

instance of each. In this example, we simplify three suchpaths:

1. to : T1; T3; S, which reduces to:

S1: (price*vol >= 1000000);

T4: [issue, price, vol] => [com=NYS(issue), cap=price*vol]

2. to reduces to:

S1: (price*vol >= 1000000);

T5: [issue, price, vol] => [com=NAS(issue), cap=price*vol]

3.: T3; S. This reduces to:

S1: (price*vol >= 1000000);

T6: [com, price, vol] => [com, cap=price*vol]

With this, each path from a publisher to a subscriber isof the form select followed by transform, as shown inFigure 3.

The selects can now be implemented by an efficientcontent-based routing system, and the transformsperformed before delivering to subscribers. Going onestep further, we can combine the individually derivedpaths back into a single I/S, which may be implemented asa content-based publish/subscribe system. These paths canthen be split by adding an additional select based onmessage source, then tagging the transforms with a source. Before an event is delivered to a subscriber, it istransformed based on the I/S to which the clientsubscribed and the source of the message. Taggedtransforms can be stored in a table for lookup andexecution before the system delivers a message to a client.New subscriptions coming into any of the subscriptionpoints () have their contentfilters modified based on the filter arcs out of the root intothese spaces using a simple application of the rewriterules.

4.2 Expanding State to Event Streams

Suppose a mobile client subscribes to the IBM eventsfrom the information space equivalent to the events in using the state[n, p], «n: p > maxP, curP¬ s 9 «n: p, p¬ s

[n, p], «n: p > maxP, curP¬ s9 «n: maxP, p¬ s

(These are the identical rules discussed in theillustration of collapse in Section 2, except that we areignoring the volume field v of events.)

Say that a number of events have been delivered todisconnects. Suppose that at this point, the state in«IBM: 160, 140¬. While the client is disconnected,a long series of events is published, arriving at a new state«IBM: 200, 120¬. The mobile client then reconnects to thesystem. If the system is able to exploit the knowledge of

the client’s interpretation of event sequences, it should beable to deliver just the two events [IBM, 200] and [IBM, 120]rather than the much longer sequence of published events.The following table shows the original events, thegenerated state, and the compressed set of deliveredevents.

disconnect:

reconnect:

Given a state space S, a start state s0 and a goal state gin S, and a collapse rule, the expansion problem is definedas the generation of the most economical sequence ofevents which, starting from s0, yields g. The expansionproblem can be converted into a shortest path graph searchproblem. We represent the states in S as vertices in agraph, and define each possible event transition as anedge. We then label these edges with a cost. For thepurpose of this paper, we will assume each event has unitcost 1. Figure 4 shows a fragment of the state transitiondiagram for the above example (but for just IBM events --thus, issue name has been left out of both events and

states).

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

To solve the shortest path problem, we use the knownA* algorithm [4]. This algorithm requires an estimatorfunction h, where h(s) is a lower estimate of the shortestpath from an arbitrary state s to state s0. Workingbackwards from the goal state g toward s0, we keep a set ofcandidate paths. We sort these paths based upon theactual length from of the path from g to s plus theestimated length h(s) from s to s0. Beginning with thenode n at the end of the best candidate path, of length f(n),we locate that neighbor n’ of n that minimizes (f(n) + 1) +h(n’). We extend the candidate path in the direction to n’.(We ignore other neighbors unless and until all candidatesof at least this distance have been explored.)

The problem is to find suitable estimator functionsh(s). One can obtain an estimator h(s) for a particulargraph by constructing an exact solution for an extendedgraph with a strict superset of edges. We have developed astrategy for finding h for an important subclass ofsummarization functions — those which can be convertedto the replacement form described below — by solving ahierarchy of problems.

Let us assume that the incremental formulation of thesummarization function can be represented by a table suchas the following:

Each row of the table corresponds to a particularcollection of events meeting a particular condition, andhaving parameters, e.g. a, b, and c. Each column of thetable corresponds to a component of the state. Each blankentry in the table indicates that the event in thecorresponding row leaves the corresponding component ofthe state unchanged; each non-blank entry indicates thatthe event in the corresponding row replaces thecorresponding component of the state. Not everysummarization function can be put in this form; howevermany can, such as the stock example illustrated above. If a summarization function is in replacement form,and it contains no rows such as the second in the exampleabove, in which two or more columns are constrained to bereplaced by the same value, then it is in unconstrainedform. If a summarization function is in unconstrainedform, and each row changes k columns, and for any kcolumns there is a row which changes those columns, thenit is in uniform unconstrained form. The exact solution toa problem in uniform unconstrained form requires anumber of events equal to ceil(m/k), where m is thenumber of state components in which the start and goalstates differ. Any problem in unconstrained form but not

uniform unconstrained form can be solved by extending itto uniform unconstrained form, and using the exactsolution to the extended problem as an estimator for theoriginal problem, and then applying A*. Similarly, anyproblem in constrained form can be extended tounconstrained form by assuming that all steps except thefirst (for which the constraints are known) may follow newrules in which additional parameters have been added asnecessary to eliminate constraints.

The extension from constrained to unconstrained form,or from unconstrained to uniform unconstrained form isequivalent to adding edges to the state graph. The optimalsolution to the extended problem therefore serves as anestimator for the original problem.

For example, the stock price example can be put intothe form of a constrained problem as follows:

This problem can be solved by using the correspondingunconstrained problem as an estimator:

In this case, the estimation function is straightforward:the estimated distance from start to goal equals the numberof issues for which the current state differs in cur price ormax price from the goal state.

In this example (see Figure 4), finding a path from s0 =«160, 140¬ to state g = «200, 120¬, the search isstraightforward. Starting at goal state «200, 120¬, we findthat only the second row of the above matrix leads to apredecessor state, which has the form «200, *¬. For anyvalue of the second state except 200, the first row isblocked and therefore the estimated distance from the startstate is 2. For the state «200, 200¬ the estimated distance is1. We therefore choose state «200, 200¬ as the bestcandidate to continue the search. In fact, this state satisfiesthe conditions for firing row one of the matrix to reach apredecessor«*, *¬, so we can insert the start state «160, 140¬.

5Discussion

5.1 Related Work

Many concepts in Gryphon have been synthesized froma large base of results in group communication, databases,

Event distribution middleware supports the integration of distributed applications by accepting events from information producers and disseminating applicable events to interested consumers. In this paper we present a flexible new model, the Information Fl

programming languages, and software engineering. Asmentioned in Section 1, existing publish/subscribetechnologies were our starting points.

The basic idea of representing system behavior interms of the flow of data from inputs through functionalmodules to output, is used extensively in software design,see for example [7]. It is also common practice to allowsoftware designers to depict the structure of a system usinga high-level visual representation similar to data flowdiagrams. The tool then converts the high-levelrepresentation into lower-level executable code.

Ideas for graph rewriting and analysis of data flowgraphs have their origins in very early work inprogramming languages and code optimization incompilers [2].

Some systems commercially available today (e.g.,NEON, [11]) claim to support arbitrary filtering andtransforming operations. However, there is scant literatureon the exact technical nature of these operations. It is notclear that these systems support a systematic approach tospecifying the flow of events. Furthermore, there is noevidence that these systems support efficient routing ofevents by optimizing IFGs and mapping them todistributed broker networks.

5.2 Current Status and Future Work

We have developed a Gryphon system prototype thatsupports content-based publish/subscribe via efficientmatching and multi-broker networks. We have alsodeveloped initial prototypes of tools for supportingstateless and stateful information flows. One tool supportsthe visual specification of information flow graphs andapplies the rules of Section 3 to rewrite the graph.Another tool supports a restricted language to specify themeaning of event sequences, using which the toolgenerates equivalent, but shorter event sequences.

Several directions of work are ongoing and appearpromising. Besides extending our graph rewritingtechniques to encompass a more expressive language, weare working on ways to efficiently map optimized IFGsonto physical broker networks of various configurations.We are also incorporating protocols for reliable andordered delivery within this framework of eventdistribution middleware.

We believe that stateful operations within IFGs are thenext major step in the functionality of event distributionmiddleware. We are currently exploring the breadth ofapplicability of derived events and equivalent eventsequences. Finally, we are beginning to deploy this newgeneration of event distribution middleware in real-worldapplication integration scenarios.

6Bibliography

[1]Marcos Aguilera, Rob Strom, Daniel Sturman, Mark Astley,

Tushar Chandra. 1999. Proceedings of ACM Symposium onPrinciples of Distributed Computing, 1999, Atlanta, GA. [2]Aho, A., Sethi, R., and Ullman, J. 1985. Compilers,

Principles, Techniques, and Tools. Addison-Wesleypublishing, Reading, MA.

[3]Banavar, G., Chandra, T., Mukherjee, B., Nagarajarao, J.,

Strom, R., Sturman, D. 1999. “An Efficient MulticastProtocol for Content-based Publish-Subscribe Systems”,Proceedings of IEEE International Conference onDistributed Computing Systems ‘99, Austin, TX.

[4]Barr, A., and Feigenbaum, Edward A. 1986. The

Handbook of Artificial Intelligence. Volume 1.Addison-Wesley Publishing, Reading, MA.

[5]K. P. Birman. “The process group approach to reliable

distributed computing,” pages 36-53, Communications ofthe ACM, Vol. 36, No. 12, Dec. 1993.

[6]Antonio Carzaniga, Architectures for an Event Notification

Service Scalable to Wide-area Networks''. Ph.D. Thesis.Politecnico di Milano. December, 1998. Available fromhttp://www.cs.colorado.edu/~carzanig/papers/

[7]Ghezzi, C., Jazayeri, M., and Mandrioli, D. 1991.

Fundamentals of Software Engineering. Prentice-Hall,Englewood Cliffs, NJ.

[8]John Gough and Glenn Smith. “Efficient Recognition of

Events in a Distributed System,” Proceedings of ACSC-18,Adelaide, Australia, 1995.

[9]Shivakant Mishra, Larry L. Peterson, and Richard D.

Schlichting. Consul: A Communication Substrate forFault-Tolerant Distributed Programs, Dept. of computerscience, The University of Arizona, TR 91-32, Nov. 1991.[10]Object Management Group. CORBA services: Common

Object Service Specification. Technical report, ObjectManagement Group, July 1998.

[11]New Era of Networks (NEON). .[12]Brian Oki, Manfred Pfluegl, Alex Siegel, Dale Skeen. “The

Information Bus - An Architecture for ExtensibleDistributed Systems,” pages 58-68, Operating SystemsReview, Vol. 27, No. 5, Dec. 1993.

[13]David Powell (Guest editor). “Group Communication”,

pages 50-97, Communications of the ACM, Vol. 39, No. 4,April 1996.

[14]Bill Segall and David Arnold. “Elvin has left the building:

A publish/subscribe notification service with quenching,”Proceedings of AUUG97, Brisbane, Austrailia, September,1997.

[15]Dale Skeen. Vitria's Publish-Subscribe Architecture:

Publish-Subscribe Overview, /

本文来源：https://www.bwwdw.com/article/562j.html