Elisa Bertino (Ed.)
`
`ECOOP2000 —
`Object-Oriented
`Programming
`
`14th European Conference
`Sophia Antipolis and Cannes, France, June 12-16, 2000
`Proceedings
`
`
`
`);) Springer
`
`Zynga Ex. 1022, p. 1
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 1
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Series Editors
`
`Gerhard Goos, Karlsruhe University, Germany
`Juris Hartmanis, Cornell University, NY, USA
`Jan van Leeuwen, Utrecht University, The Netherlands
`
`Volume Editor
`
`Elisa Bertino
`Universita’ di Milano
`Dipartimento di Scienze dell’ Informazione
`Via Comelico 39/49, 20135 Milano,Italy
`E-mail: bertino @dsi.unimi.it
`
`Cataloging-in-Publication Data applied for
`
`Die Deutsche Bibliothek - CIP-Einheitsaufnahme
`
`Object oriented programming : 14th European conference ; proceedings/
`ECOOP2000, Sophia Antipolis and Cannes,France, June 12 - 16, 2000.
`Elisa Bertino (ed.). - Berlin ; Heidelberg ; New York ; Barcelona;
`Hong Kong; London; Milan ; Paris ; Singapore ; Tokyo : Springer, 2000
`(Lecture notes in computerscience ; Vol. 1850)
`ISBN 3-540-67660-0
`
`.. WenctLibrary
`Uns
`in_-M i
`ity ¢
`nive
`
`niversity oj
`onsin-Madison
`venue
`
`Wi 53706-1688
`
`Tata.
`
`CR Subject Classification (1991): D.1-3, H.2, F.3, C.2, K.4, J.1
`
`ISSN 0302-9743
`ISBN 3-540-67660-0 Springer-Verlag Berlin Heidelberg New York
`
`This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
`concerned,specifically the rights of translation, reprinting, re-useofillustrations, recitation, broadcasting,
`reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
`orparts thereof is permitted only underthe provisions of the German Copyright Law of September9, 1965,
`in its current version, and permission for use must alwaysbe obtained from Springer-Verlag. Violations are
`liable for prosecution under the German Copyright Law.
`
`Springer-Verlag is a companyin the BertelsmannSpringerpublishing group.
`© Springer-Verlag Berlin Heidelberg 2000
`Printed in Germany
`
`Typesetting: Camera-ready by author, data conversion by PTP-Berlin, Stefan Sossna
`Printed on acid-free paper
`SPIN 10722117
`06/3142
`543210
`
`Zynga Ex. 1022, p. 2
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 2
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Zynga Ex. 1022, p. 3
`Zynga v. IGT
`IPR2022-00368
`
`
`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`

`

`Distributed Asynchronous Collections
`
`253
`
`the demand for more flexible communication models,reflecting the dynamic na-
`ture of the applications. The publish/subscribe interaction style has proven its
`ability to fill this gap [22]. Indeed the decoupling of parties in time as well as
`space is a key to scalability.
`
`topic-based or subject-based pu-
`Publish/Subscribe Interaction. The classical
`blish/subscribe involves a static classification of the messages by introducing
`group-like notions [26], and is incorporated by most industrial strength soluti-
`ons, e.g., [7,32]. Publish/subscribe is frequently based on a push model, where
`producers feed a software bus with information and the information is pushed
`towards consumers from there. Other approaches to “messaging” furthermore
`integrate pull-style mechanisms [24], i.e., consumers actively poll for new infor-
`mation. The term queueing is frequently applied when referring to such pull-style
`interaction. Queueing usually expresses one-for-all semantics, which meansthat
`one single consumer will consume an information. In contrast, with push-style
`interaction, an information is generally pushed to all consumers (one-for-each).
`Asnoticedin [28], some applications need only one interaction style while others
`require both. Instead of bringing all these variants to a common denominator,
`much emphasis is usually put on their differences.
`
`Object-Oriented Publish/Subscribe: Does it Make Sense? It is often claimed that
`“objects” cannot really support the requirements of a publish/subscribe midd-
`leware [18]. That argumentation is also commonly used by the promotersof so-
`called “messaging systems”, which claim that objects do communicate through
`synchronous method invocations which force the interacting parties to be both
`coupled in time and in space.
`.
`This paper makes a case against this argument by making an attempt to
`unify the diverging flavors of publish/subscribe. The argument against a fu-
`sion of object-orientation and the publish/subscribe communication style indeed
`might apply to the current commercial practices in distributed object-oriented
`computing, which are mainly based on derivatives of the remote procedure call
`(DCOM [25], Java RMI [31], CORBA [23]).? As we will convey in this paper,
`decoupling publishers and subscribers can be made very practical in an object-
`oriented setting, and the integration of object-oriented principles and messaging
`can go further than simply wrapping a messaging system with an object-oriented
`API.
`
`Publish/Subscribe Abstractions. To capture the various interaction styles of
`publish/subscribe, we propose an abstraction called Distributed Asynchronous
`Collection (DAC). A DACdiffers from a conventionalcollection by its distribu-
`ted nature and the way objects interact with it: besides representing a collection
`
`1 Time decoupling: the interacting parties do not need to be up at the same time.
`Space decoupling: the interacting parties do not need to know each other.
`2 Mucheffort is currently made to integrate messaging into existing middlewaresolu-
`tions, as shown by [12,24].
`
`Zynga Ex. 1022, p. 4
`Zyngav. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 4
`Zynga v. IGT
`IPR2022-00368
`
`

`

`254
`
`P.T. Eugster, R. Guerraoui, and J. Sventek
`
`of objects (set, bag, queue, etc.), a DAC can be viewed as a publish/subscribe
`engine of its own. In fact, when querying a DAC for objects, the client expresses
`its interest in such objects. In other words, the invocation of an operation on a
`DACexpresses the notion of future notifications and can be viewed as a sub-
`scription. According to the terminology adopted in the observer design pattern
`[9], the DACis the subject anditsclient is the observer. This abstraction allows
`to unify different publish/subscribe styles in a single framework, which can be
`seen as an extension of a conventional collection framework. Wewill showin this
`paper how this approach allowed us to mix push and pull models, one-for-all
`and one-for-each semantics, along with different QoS.
`In short, within all publish/subscribe interaction styles noneis clearly better
`than the others for all application purposes. In this paper we present simple
`abstractions for publish/subscribe interaction, called Distributed Asynchronous
`Collections. On the one hand, DACsallow to capture the different styles without
`blurring their respective advantages. On the other hand, DACs unite these styles
`inside a single framework.
`
`Roadmap. The remainderof this paper is organized as follows. Section 2 recalls
`the various interaction styles in distributed computing and motivates the need
`for a subscription-like way of communicating. Section 3 gives an overview of the
`DACabstraction. Section 4 gives the basic DAC API, whereas Section 5 presents
`some preliminary class implementations. In Section 6 we show a simple example
`of programming with DACs. Section 7 discusses some performanceissues of our
`implementation, and Section 8 contrasts our efforts with related work. Finally
`Section 9 summarizes our work and concludes the paper.
`
`2 Publish/Subscribe: Commonalities and Variations
`
`Before describing our DAC abstraction, we first overview the basics of pu-
`blish/subscribe interaction styles. In a first step, the publish/subscribe com-
`munication style is compared with more traditional interaction schemes. In a
`second phase,the different existing approaches to publish/subscribe are elucida-
`ted more precisely. We point out the fact that each of the different interaction
`styles has proven certain advantages over others, which motivates the usefulness
`of unifying them inside a framework.
`
`2.1 Publish/Subscribe in Perspective
`
`The publish/subscribe paradigm is a loose communication scheme for modeling
`the interaction between applications in distributed systems. Unlike the classic
`request/reply model or shared memory communication, publish/subscribe pro-
`vides time decoupling (i.e., the interacting parties do not need to be up at the
`same time) of message producers and consumers. Figure 1 shows a comparison
`of the most common communication schemes: message passing (asynchronous
`Zynga Ex. 1022, p. 5
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 5
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Distributed Asynchronous Collections
`
`255
`
`send) may also offer an asynchronous interaction scheme, but lacks space de-
`coupling(i.e., the interacting parties need to know each other), just like the re-
`quest/reply communication style. Indeed with message passing, the information
`producer must have a meansoflocating the information consumer to which the
`information will be sent, whereas with the request/reply interaction model the
`message consumerrequiresa reference to the information producerin orderto is-
`sue a request to it. Publish/subscribe combines time as well as space decoupling,
`since the information providers and consumers remain anonymousto each other.
`This outlines the general applicability of this communication model and makes
`it appealing.? Like communication based on shared memory, publish/subscribe
`moreover allows to address several destinations (arity of n). Basically the pu-
`blish/subscribe terminology defines tworoles:
`
`— Subscriber: A party which is interested in certain information (events, mes-
`sages) subscribes to that information,signalling that it wishes to receive all
`pieces of information (event notifications, messages) manifesting the speci-
`fied characteristics. Leasing is a special form of subscribing, in which the
`duration of the subscription is limited by a time-out.
`— Publisher: A party that produces information (events, messages) becomes a
`publisher.
`
`In most applications however, participating entities incorporate both publis-
`hers and subscribers, which allows a very flexible interaction. This is one of
`the main differences to pure push-based systems [13], where participants are eit-
`her producers or consumers and producers are supposed to beseveral orders of
`magnitude higher in number than consumers.
`
`Time
`
`Space
`
`
`
`
`
`
`
`
`Request/Reply
`
`Asnynchronous Send
`
`
`Shared Memory
`
`
`Publish/Subscribe
`
`
`Arity
`
`
`
`
`
`
`Fig. 1. Different Communication Models
`
`2.2 Topics
`
`The classic publish/subscribe interaction model is based on the notion of topics
`or subjects, which basically resemble groups [26]. Subscribing to a topic T can
`be viewed as becoming memberof a group T. The topic abstraction however
`
`3 It is possible to build closer coupled communication models on top of loose ones and
`vice versa, as proposed by [34] for instance. The resulting performance in the second
`case howeveris generally poor.
`
`Zynga Ex. 1022, p. 6
`Zyngav. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 6
`Zynga v. IGT
`IPR2022-00368
`
`

`

`256
`
`P.T. Eugster, R. Guerraoui, and J. Sventek
`
`differs from the group abstraction by its more dynamic nature. While groups
`are usually disjoint sets of members (e.g., group communication for replication
`[3]), topics typically overlap, i.e., a participant subscribes to more than just one
`topic. In orderto classify the topics more easily, it is of great use to furthermore
`introduce a hierarchy of topics [32]. In this model, a topic can be a derived or
`more specialized topic of another one,and is therefore called subtopic. The use
`of wildcards offers a more convenient way of expressing cross-topic requests.
`Figure 2 shows an example of topic-based subscribing. Subscriber Shas an-
`nouncedits interest in both topics x andy. It is notified of events corresponding
`to both topics (messages m, and m,). Subscriber S2 has only subscribed to topic
`x, and therefore only receives messages related to that topic (message m;).
`
`
`
`
`
`
`y Publish
`v Subscribe
`4 Deliver
`P Publisher
`
`S$; Subscriber
`
`Fig. 2. Topic-Based Subscribing
`
`2.3. Push and Pull Mixing
`
`In the publish/subscribe model, the action of subscribing describes a sort of
`registration procedure for an interested party. However, interests in events can
`also be expressed through a moredirect interaction. In general, we distinguish
`the following ways for an interested party to interact:
`
`— In a passive way,it can subscribe to a choice of notifications. By callbacksit
`will be notified of the occurrence of events. This kind of interaction consti-
`tutes the push model, since the information is pushed from the information
`bus to the subscriber. This is the classic publish/subscribe approach, since
`it enforces applications which are only loosely coupled in time.
`— Moreactively, a consumercan poll for new notifications. This task may waste
`resources and is not well adapted to asynchronous systems. In fact, polling
`based solutions tend to be very expensive and scale poorly: polling too often
`can beinefficient and polling too slowly may result in delayed responses to
`critical situations [29]. This style is often called queueing, and in the context
`of this paper this is the type of interaction we will refer to as pull model.
`
`Zynga Ex. 1022, p. 7
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 7
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Distributed Asynchronous Collections
`
`257
`
`— Another yet more synchronouspull-type interaction is given by blocking pull-
`style interaction. In this scenario, a consumer which tries to pull information
`is blocked until a new notification is available. Just like the request/reply
`model however, this variant introduces time coupling,andis therefore rarely
`used in common messaging systems.
`
`Although in general push-style interaction seems more appropriate, certain
`applications may not be interested in receiving information as soon as possible,
`but only at precise moments. In those situations, the pull model might be of
`interest.
`
`2.4 Delivery Semantics and Reliability Issues
`
`In distributed systems, and in particular when considering communication mo-
`dels and protocols, precise specification of the semantics ofa delivery is a crucial
`issue. Delivery guaranteesare often limited by the behavior of deeper communi-
`cation layers, down to the properties of the network itself, limiting the choice of
`feasible semantics. On the other hand, different applications also may demand
`for different semantics. While sometimes a high throughput is preeminent and
`a low reliability degree is tolerable, some applications prioritize reliability to
`throughput. For this reason most common messaging systems provide different
`qualities of service, in order to meet the demandsofa variety of application pur-
`poses [1,32].4 The delivery semantics for notifications offered by existing systems
`can be roughly divided into two groups.
`
`— Unreliable delivery. Protocols for unreliable delivery give few guarantees.
`These semantics are often used for applications where the throughputis of
`primary importance, but the loss of certain messages is not fatal for the
`application.
`— Reliable delivery. Reliable delivery means that a message will be delivered to
`every subscriber despite certain failures. Usually the failure or the absence
`of the subscriber itself is not considered,i.e., if the subscriber has failed,
`the message might not be delivered to it and thereliability property is not
`considered violated. When using persistent storage to buffer such messages
`until the subscriber is back on line, a stronger guarantee is given. This is
`often referred to as certified delivery [32].
`
`3 Distributed Asynchronous Collections: Overview
`
`This section gives an overview of our approach to publish/subscribe, by first
`introducing Distributed Asynchronous Collections as key abstractions. We show
`the relationship between those abstractions and the publish/subscribe communi-
`cation model. In a second step, we picture more in detail how these abstractions
`allow to build several different publish/subscribe variants inside a unified frame-
`work. This section however should be understood as a general introduction to
`
`4 [32] adopts the notion ofdelivery service.
`
`Zynga Ex. 1022, p. 8
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 8
`Zynga v. IGT
`IPR2022-00368
`
`

`

`258
`
`P.T. Eugster, R. Guerraoui, and J. Sventek
`
`our abstractions for publish/subscribe. The following sections will give a more
`concrete view of DACs.
`
`3.1 DACs as Object Containers
`
`Just like any collection, a DAC is an abstraction of a container object that re-
`presents a group of objects. It can be seen as a meansto store, retrieve and
`manipulate objects that form a natural group, like a mail folder or a file direc-
`tory. Unlike a conventional collection, a DAC is a distributed collection whose
`operations might be invoked from various nodesof a network. DACsdiffer funda-
`mentally from the distributed collections described in [21] for instance, by being
`asynchronousandessentially distributed, i.e., DACs can be seen as omnipresent
`entities.> Participating processes act with a DAC througha local proxy, which
`is viewed as a local collection and hides the distribution of the DAC. DACsare
`not centralized on a single host, in order to guarantee their availability despite
`certain failures.
`A collection framework is a unified architecture for representing and acces-
`sing collections, allowing them to be manipulated independently of their repre-
`sentation. For example, both Smalltalk [14] and Java [16] contain rich collection
`frameworks that reduce the programmingeffort by providing useful data structu-
`res and algorithms together with high-performance implementations. Collection
`frameworkscan for instance also be found for C++ (e.g., Silicon Graphics’ STL
`[30]) as additional libraries. Figure 3 shows the inheritance graph of the Java
`collection framework.
`
`3.2 The Asynchronous Flavor of DACs
`
`Ournotion of Distributed Asynchronous Collection represents more than just a
`distributed collection. In fact, a synchronous invocation of a distant object can
`involve a considerable latency, hardly comparable with that of a local one. In
`contrast, asynchronousinteraction is enforced with ourcollections. By calling
`an operation of a DAC, one expresses an interest in future notifications. When
`querying a DACfor objects of a certain kind for instance, the party interacting
`with the DAC expresses its interest in such objects. Therefore, when such an ob-
`ject is eventually “pushed” into the DAC, the interested party is asynchronously
`notified.
`Thereis a strong resemblance with the notion of future [4] (future type mes-
`sage passing [35]), that describes a communication model in which a client que-
`ries an asynchronous object for information by issuing a request to it. Instead
`of blocking however, the client can pursue its processing. As soon as the reply
`has been computed, the object acting as server notifies the client. Latter one
`may query the result (lazy synchronization or wait-by-necessity [5]), or ignore
`it. Figure 4 compares the two paradigms. When programming with DACs, the
`° The distributed collections presented in [21] are centralized collections that can be
`remotely accessed through RMI.
`
`Zynga Ex. 1022, p. 9
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 9
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Distributed Asynchronous Collections
`
`259
`
`Collection
`
`aa
`
`
`
`ch implements A extends
`
`Abstract Cl.
`
`Fig. 3. Collections in Java (Excerpt)
`
`subscriber can be viewed as the client. The DAC incarnates a server role in
`this scenario, since the publishers, which are theeffective information suppliers,
`remain anonymous.
`Bycalling an operation on the DAC, thecaller requests certain information.
`The main difference with futures lies in the numberof times that information is
`supplied to the client. Within the notion of future, only a single reply is passed to
`the client,® whereas with DACs, every time an information which is interesting
`for the registered party is created, it will be sent to it.
`
`3.3. Publish/Subscribe with DACs
`
`Expressing onesinterest in receiving information of a certain kind can be viewed
`as subscribing to information of that kind. By viewing event notifications as
`objects, a DAC can beseen as an entity representing related event notifications.
`Clearly, if a collection is a set of somehow related objects, a DAC can beseen as
`a set of related “events”. When considering the classical topic-based approach
`to publish/subscribe, a DAC can bepictured as an extension of a conventional
`collection but also as a representation for a topic. It is always possible to insert
`a new element into a DAC. In the sense of publish/subscribe, inserting an object
`e ABCL/1 represents an exception, in the sense that several replies may be returned
`[35].
`
`Zynga Ex. 1022, p. 10
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 10
`Zynga v. IGT
`IPR2022-00368
`
`

`

`260
`
`P.T. Eugster, R. Guerraoui, and J. Sventek
`
`Publish/Subscribe with DACs
`
`Invocation
`
`1
`
`n__
`
`Notifications
`
`Subscriber
`
`DAC
`
`g Thread
`
`| | | |
`
`|
`|
`
`|
`
`| | |
`
`AsynchronousInvocation
`
`Invocation
`
`1
`
`;
`
`Panne
`
`Client
`
`Asynchr. Object
`
`Fig. 4. DACsvs. Future
`
`into a DAC also meansto publish that object for the topic represented by the
`DAC. Every DAC can thus be viewed as a publish/subscribe engine of its own.
`Figure 5 showsthe traditional topic-based publish/subscribe scheme. The topic
`is represented by an attribute of the message, and the application has to deal
`with it explicitly. Since a DAC is boundto a topic, the topic is given implicitly,
`and appears only in the protocol message which is hidden from the application,
`as shown in Figure 6. It encapsulates the application message.
`Existing publish/subscribe frameworks introduce specialized message types,
`e.g., [12]. Our approach frees the application programmer from the burden of
`marshalling and unmarshalling data into and from dedicated messages. In our
`context, a message can be basically of any kind of object. In Java, this is ex-
`pressed by allowing any object of class java.lang.Object to be passed as a
`message.”
`
`Message m|public class Message {
`public String topic;
`
`public String content;
`
`
`
`
`
`
`
`
`—_|topic of m is “/Chat/Insomnia”
`Criteria
`|String topic = "/Chat/Insomnia"
`Argument
`
`
`Evaluation |m.topic.equals("/Chat/Insomnia")
`
`
`
`
`Fig. 5. “Traditional” Topic-Based Publish/Subscribe
`
`to be conveyable, a Java object should furthermore implement
`7 In order
`java.io.Serializable interface [15], which contains no methods.
`
`the
`
`Zynga Ex. 1022, p. 11
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 11
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Distributed Asynchronous Collections
`
`261
`
`
`|public class Message {
`Protocol
`Message p|public String getTopic() Aisiee}
`public Object getMsg() {...}
`
`Message m|public class ChatMsg {...}
`
`Criteria
`—_|topic of m is “/Chat/Insomnia”
`Argument
`|String topic = "/Chat/Insomnia"
`Evaluation |p. getTopic() .equals("/Chat/Insomnia")
`Deliver
`m = p.getMsg()
`
`
`Fig. 6. Topic-Based Publish/Subscribe with DACs
`
`4 DAC Interfaces
`
`The previous section introduced DACsas general abstractions for publish/sub-
`scribe. This section presents the main interfaces of our DACrealization in Java.
`In the context of this paper, we will limit ourselves to describing the functionali-
`ties which are commonto all DAC subinterfaces, in order to show their similarity
`to operations on conventional centralized collections.
`
`4.1 Topic-Based Subscribing with DACs
`
`In our system, each topic is represented by a DAC, and is denoted by a name,
`like “Chat”. A DAC constructor thus requires an argument which denotes the
`nameof the topic it will represent (see Section 6 for an example). Topics can
`have specializations, or subtopics, and connecting to a topic requires the name
`in a URL-type format. Typically, “/Chat/Insomnia” is a reference to the topic
`called “Insomnia” which is a subtopic of “Chat”. The root of the hierarchy is
`represented by an abstract topic (denoted by “/”). Top-level topics, which are
`no specializations of already existing ones, are subtopics of the abstract root
`topic only. Subscribing to a topic can trigger subscriptions for the subtopics as
`well, as illustrated in Figure 8. Subscriber S; subscribes to topic “Chat” and
`claims its interest in all subtopics. Hence S, does not only receive message m2
`but also message m, published for topic “/Chat/Insomnia”. In contrast, S2 only
`subscribes to “/Chat/Insomnia” and thus does not receive message m2, which
`belongs to the supertopic. With the push model adopted in DACs, subscribing
`entities must register a callback object. That callback object must implement a
`specific interface, namely the Notifiableinterface, shown in Figure 7. Through
`acall to the contains() method, the DACnotifies the subscriber that it contains
`a new notification. The second argument enables the use of the same callback
`object for several topics.
`
`Zynga Ex. 1022, p. 12
`Zyngav. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 12
`Zynga v. IGT
`IPR2022-00368
`
`

`

`P.T. Eugster, R. Guerraoui, and J. Sventek
`ineeEEEEEEESSENSE
`
`262
`
`public interface Notifiable {
`
`public void contains(Object msg, String topicName) ;
`}
`
`Fig. 7. Interface Notifiable
`
`S| Subscriber
`
`¥ -Publish
`v Subscribe
`4 Deliver
`P Publisher
`
`Fig. 8. Topic-Based Publish/Subscribe with DACs
`
`4.2 DAC Methods
`
`Figure 9 summarizes the main methods of the base DAC interface. More sophi-
`sticated interfaces like the DASet all derive from this interface, but are omitted
`for the sake of brevity. We roughly distinguish synchronous and asynchronous
`methods.
`
`Synchronous Methods. Since a DAC is in the first place a collection, the DAC
`interface inherits from the standard java.util.Collection interface. The in-
`herited methods are not denatured but adapted, and we denote them as syn-
`chronous.
`
`get(). Similarly to a centralized collection, calling this method allows to
`retrieve objects. The synchronization it introduces is however very weak,
`since it returns null in the absence of unconsumed information, as explained
`in Section 2. Which element will be returned depends on the nature of the
`collection (see Section 5 for more details). This implements the pull model.
`contains(). A DACisfirst ofall a representationofa collection of elements.
`This method allows to query thecollection for the presence of an object. Note
`that an object that is contained in a DAC belongsto the topic represented
`by that DAC.
`add(). This methodallows to add an object to the collection. The correspon-
`ding meaning for a DACis straightforward: it allows to publish a message
`for the topic represented by that collection. An asynchronousvariant of this
`method could consist in advertising the eventual production of notifications.
`Zynga Ex. 1022, p. 13
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 13
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Distributed Asynchronous Collections
`
`263
`
`This could furthermore be combined with the registration of a callback ob-
`ject, that the DAC would poll in order to obtain new event notifications. In
`the terminology adopted in [24], this is called a pullsupplier.
`
`Asynchronous Methods. We have added several asynchronous methods to ex-
`press the decoupled nature of publish/subscribe interaction specific to DACs. In
`these methods, asynchrony is expressed by an additional argument, denoting a
`callback object which implements the Notifiable interface. Not all operations
`known from conventional collections find an analogous meaning in an asynchro-
`nous distributed context, and our ongoing research in that domain might cause
`minor modifications to this interface.
`
`— contains(Notifiable n). Theeffect, for instance, of invoking this method
`is not to check if the collection already contains an object revealing certain
`characteristics, but is to manifest an interest in any such object, that should
`be eventually pushed into the collection. The interested party advertises its
`interest by providing a reference to an object implementing the Notifiable
`interface (Figure 7), through whichit will be notified of events.
`— containsAll (Notifiable n). This method offers the same signature than
`the previous method. Thedifference is that a subscription is generated for
`all subtopics of the topic represented by this DAC. This reflects the situation
`given in Figure 8.
`— remove(Notifiable n). Likewise, by calling one of these methods, a sub-
`scriber does not trigger the removal of an object already contained in the
`collection, but expresses its interest in being notified whenever an object
`matchingits criteria is inserted in the collection, after which the object will
`be removed immediately. This expresses that a message is delivered to one
`single subscriber only. This is frequently called one-for-all or one-of-n [32]
`in contrast to one-for-each,® implemented by the asynchronous contains ()
`methods, where a messageis sent to all.
`— removeAll (Notifiable n). This methodis similar to the previous one, ex-
`cept that a subscription is generatedfor all subtopics of the topic represented
`by this DAC.
`— clear(Notifiable n). The conventional argument-less clear() method al-
`lows to erase all elements from the collection, whereas this asynchronous
`variant expresses the action of unsubscribing.
`
`5 DAC Classes
`
`The previous section focused on the interfaces, through which an application can
`use DACsin orderto benefit from the strength of our publish/subscribe abstrac-
`tions. As depicted earlier, our framework consists of a variety of DACs spanning
`® By using the formalism of [27], one could say that every Nth occurrence of an event
`is notified to a subscriber, with N being the total numberof subscribers, and no
`event being delivered to more than one subscriber.
`
`Zynga Ex. 1022, p. 14
`Zyngav. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 14
`Zynga v. IGT
`IPR2022-00368
`
`

`

`264
`
`P.T. Eugster, R. Guerraoui, and J. Sventek
`
`
`public interface DAC
`extends java.util.Collection
`
`public Object get();
`public boolean contains(Object message) ;
`public boolean add(Object message) ;
`
`public boolean contains (Notifiable N);
`public boolean containsAll (Notifiable N);
`
`public boolean remove(Notifiable N);
`public boolean removeAll (Notifiable N);
`
`public void clear(Notifiable N);
`
`
`
`Fig. 9. Interface DAC (Excerpt)
`
`different semantics and guarantees, since different applications have different
`requirements. These semantics can be seenas different QoS. While certain pro-
`perties of DACsreflect in their interfaces, certain semantics do not appearin the
`API. These parameters influence the classes implementing those interfaces, and
`thus lead to a variety of classes implementing the sameinterface. This section
`presents the different properties of the classes constituting our framework.
`
`5.1 Delivery Semantics
`Whena producer publishes a message, it does not directly interact with sub-
`scribers. To whom exactly the message will be delivered does not show in the
`DACsinterface. Parts of the semantics do not cometo light in the interfaces.
`The underlying multicast protocols mightlead to different classes implementing
`the sameinterface. The DASet (Distributed AsynchronousSet) interface, for in-
`stance, is implemented by multiple classes. The first one does not offer more
`than plain unreliable delivery (DAWeakSet), whereas others guarantee reliability
`(e.g., DAStrongSet). By distinguishing between unreliable and reliable DACs our
`framework hierarchy is roughly split into two subtrees, as shown in Figure 10.
`
`5.2 Duplicates
`Just like it is possible to have duplicate elements in centralized collections,it is
`possible in Distributed Asynchronous Collections that a same message is deli-
`vered more than once. In fact, the twoare closely related in our context. If a DAC
`does not accept duplicates, it should not deliver any duplicates to subscribers.
`Zynga Ex. 1022, p. 15
`Zynga v. IGT
`IPR2022-00368
`
`Zynga Ex. 1022, p. 15
`Zynga v. IGT
`IPR2022-00368
`
`

`

`Distributed Asynchronous Collections
`
`265
`
`The simple DAWeakBagclass for instance does not prevent a notification to
`be delivered more than once, whereas the DAWeakSet class gives stronger gua-
`rantees by eliminating duplicate elements. This property is orthogonal to other
`characteristics of our DACs. For that reason, our framework contains a variant
`with and without duplicates for every other property, as shown in Figure 10.
`When allowing duplicates and combining with unreliable delivery for instance,
`the outcomeis best-effort semantics. In return, with reliable delivery, at-least-
`once semantics can be guaranteed.
`
`At-most-once
` At-least-once
`
`Exactly-once
`
`Implicit
`
`Best-effort
`
`Explicit
`
`At-least-once Epos
`FIFO
`FIFO
`
`At-least-once
`Total Order
`
`Exactly-once
`Total Order
`
`Fig. 10. DAC Framework
`
`5.3 Storage vs. Delivery Order
`
`Collect