Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 1 of 52 PageID #: 1891
`
` 
`
` 
`
` 
`
` 
`
` 
`
`Exhibit F
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 2 of 52 PageID #: 1892
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`Peer-to-Peer Architectures for Massively Multiplayer Online Games:
`A Survey
`
`AMIR YAHYAVI and BETTINA KEMME, McGill University
`
`Scalability, fast response time, and low cost are of utmost importance in designing a successful massively
`multiplayer online game. The underlying architecture plays an important role in meeting these conditions.
`Peer-to-peer architectures, due to their distributed and collaborative nature, have low infrastructure costs
`and can achieve high scalability. They can also achieve fast response times by creating direct connections
`between players. However, these architectures face many challenges. Distributing a game among peers makes
`maintaining control over the game more complex. Peer-to-peer architectures also tend to be vulnerable to
`churn and cheating. Moreover, different genres of games have different requirements that should be met by
`the underlying architecture, rendering the task of designing a general-purpose architecture harder. Many
`peer-to-peer gaming solutions have been proposed that utilize a range of techniques while using somewhat
`different and confusing terminologies. This article presents a comprehensive overview of current peer-to-peer
`solutions for massively multiplayer games using a uniform terminology.
`Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems;
`K.8.0 [Personal Computing]: Games
`General Terms: Algorithms, Design, Human Factors
`Additional Key Words and Phrases: Peer-to-peer networking, massively multiplayer online games, interest
`management, network overlays, multicasting, replication, fault tolerance, consistency control, incentives,
`cheating, commercial applications
`ACM Reference Format:
`Yahyavi, A. and Kemme, B. 2013. Peer-to-peer architectures for massively multiplayer online games: A
`survey. ACM Comput. Surv. 46, 1, Article 9 (October 2013), 51 pages.
`DOI: http://dx.doi.org/10.1145/2522968.2522977
`
`1. INTRODUCTION
`Massively Multiplayer Online Games (MMOGs) are among popular online technologies
`that produce billions of dollars in revenues and introduce several new and interesting
`challenges. One of the main attractions of these games lies in the number of players
`that participate in the game. The more players that are in the game world, the more
`interactive, complex, and attractive the game environment will become. Successful
`games such as World of Warcraft with nearly 12 million subscriptions [Blizzard 2011]
`have to provide a truly scalable game world while maintaining responsiveness.
`To better understand MMOGs, we first need to give a definition. Video game is
`usually defined as an electronic game that is played by a controller and provides
`user interactions by generating visual feedback. A multiplayer game is a game played
`by several players. Players can be simply independent opponents or they can play in
`
`A. Yahyavi was funded by NSERC Strategic Grant STPGP/350626-2007.
`Authors’ addresses: A. Yahyavi (corresponding author) and B. Kemme, School of Computer Science, McGill
`University, Montreal, QC H3A 0G4, Canada; email: amir.yahyavi@cs.mcgill.ca.
`Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
`without fee provided that copies are not made or distributed for profit or commercial advantage and that
`copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for
`components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.
`To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this
`work in other works requires prior specific permission and/or a fee. Permissions may be requested from
`Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212)
`869-0481, or permissions@acm.org.
`c(cid:2) 2013 ACM 0360-0300/2013/10-ART9 $15.00
`DOI: http://dx.doi.org/10.1145/2522968.2522977
`
`9
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 3 of 52 PageID #: 1893
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`9:2
`
`A. Yahyavi and B. Kemme
`
`teams. They can play against each other or can play against the game, that is, opponents
`that are controlled using Artificial Intelligence (AI). An MMOG is a game capable of
`supporting hundreds or thousands of players and is mostly played using the Internet.
`Many games such as World of Warcraft [Blizzard 2011], EVE Online [EVE 2011],
`and Final Fantasy XI [FFXI 2011] have shown that MMOGs are a thriving business
`industry. For example, Star Wars: The Old Republic was able to achieve one million
`subscribers in three days after launch.1 Second Life [SecondLife 2011], launched in
`2003 by Linden Lab, is the most famous social virtual world with more than 16 million
`registered users. The emergence of social games (such as Farmville and Mafia Wars2)
`with millions of subscribers [Zynga 2011] as well as mobile games that are played on
`smartphones, and the popularity of handheld devices such as Sony PSP [2011] and
`Nintendo DS [Nintendo 2011], lay the foundation for potential integration of social
`and mobile environments into massively multiplayer games [Iosup et al. 2010; Varvello
`and Voelker 2010].
`MMOGs can produce huge network traffic and processing loads [Suznjevic and
`Matijasevic 2012; Chen et al. 2005b]. Thus, the main challenges in MMOGs are scala-
`bility, that is, providing support for thousands of players simultaneously, consistency,
`security, and fast response time, and usually all at the same time, otherwise customer
`satisfaction would be reduced. In the next sections we discuss these challenges and
`different solutions that have been proposed.
`Client-server systems, where game execution and game state dissemination are com-
`pletely controlled by the server, are currently the prevalent game architecture. How-
`ever, peer-to-peer architectures can be beneficial for gaming infrastructures in several
`ways. If client nodes communicate directly with each other or perform part of the
`game state computation, server requirements in terms of computational power and
`network bandwidth can be significantly reduced. Even if the game execution remains
`completely controlled by servers, peer-to-peer technology can be used to coordinate mul-
`tiple servers, such as maintaining distributed game state execution and management
`of server farms [Chen et al. 2005a] or federated servers [Iimura et al. 2004; Ahmed
`et al. 2009]. Cloud-based game streaming services based on content distribution net-
`works [OnLive 2011] can also benefit from these architectures [Chien et al. 2010]. They
`can provide 3D streaming services where, similar to audio or video media streaming,
`3D content is fragmented into pieces at a server, before it is transmitted, reconstructed,
`and displayed at the clients [Wu et al. 2009].
`Peer-to-peer architectures have received a great deal of research attention in the
`recent past as they distribute computational and network load among peers, can po-
`tentially achieve high scalability, low cost, and good performance as will be discussed
`further. While most of our discussions are focused on multiplayer games, in particular
`MMOGs, many of these architectures can also be applied to other distributed systems
`such as distributed simulation environments [Fujimoto 2000], virtual worlds such as
`Second Life [SecondLife 2011], and other networked virtual environments [Blau et al.
`1992; Kawahara et al. 2004; Keller and Simon 2003].
`The remainder of this article is structured as follows. In Section 2 we study common
`game design principles used in most multiplayer games, and in particular MMOGs. In
`Section 3 we study and compare different architectures proposed for MMOGs. Next,
`we present in detail issues related to structure (Section 4), update dissemination
`(Section 5), interest management (Section 6), replication and consistency (Section 7),
`fault tolerance, availability, and persistence (Section 8) in peer-to-peer-based MMOG
`solutions. Section 9 discusses cheating. We explain how games, in particular P2P
`
`1http://www.swtor.com/news/press-release/20111223.
`2Zynga: 232 Million Monthly Players http://secfilings.com/searchresultswide.aspx?link=1&filingid=8022980.
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 4 of 52 PageID #: 1894
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`Peer-to-Peer Architectures for Massively Multiplayer Online Games: A Survey
`
`9:3
`
`(a) Different components of a multiplayer game, adapted from Mammoth [Kienzle et al. 2009]
`Fig. 1.
`(adapted, c(cid:2)ACM 2009), a massively multiplayer game research framework, are presented. The components
`discussed in this article are highlighted; (b) different game objects and their interactions. Players can interact
`with each other, objects, and NPCs.
`
`architectures, are affected by cheating and discuss some of the security measures
`proposed for P2P-based games. In Section 10 we study different incentives for using
`P2P architectures by consumers and the industry. Furthermore, we discuss various
`applications and adoption models of P2P-based gaming architectures. Section 11
`concludes the article.
`
`2. DESIGN PRINCIPLES
`Before getting into peer-to-peer architectures we first explain general concepts involved
`in designing a multiplayer game whether using client-server architectures or P2P. An
`overview of different components of a sample multiplayer game framework is shown
`in Figure 1(a). Here, we discuss the general concepts and execution patterns used in
`most multiplayer online games.
`
`2.1. Object Types
`In modern video games, the game world is usually made up of four types of com-
`ponents [Knutsson et al. 2004]: (1) immutable objects, such as landscape or terrain
`information, are usually designed and created offline and never change during the
`game. These objects are typically installed at the client and are initialized at the start
`of the game. (2) characters or avatars in the game world are controlled by the player
`using an input device. The avatar has a position in the game world and is usually
`allowed three types of actions: player updates, player-object interaction, and player-
`player interaction. (3) mutable objects such as food, weapons, and tools can be modified.
`For instance, players can interact with and/or use them in their interaction with other
`players. (4) NonPlayer Characters (NPCs), also called bots, are characters or avatars
`that are not controlled by a player but are usually controlled using AI. In the rest of
`this article, unless otherwise stated, game objects refer to avatars, mutable objects, and
`NPCs in the game. Object types are shown in Figure 1(b).
`
`2.2. Player Interactions
`Player interactions are typically divided into three categories: player updates, player-
`object interactions, and player-player interactions [Knutsson et al. 2004; Bharambe
`et al. 2006]. Player updates are interactions with the game world that only affect
`the player himself. Position updates and graphical updates to the player’s avatar are
`examples of player updates. In a simple and unoptimized implementation, a large
`proportion of all player interactions can be position updates [Knutsson et al. 2004].
`Player-object interactions are the interactions between a player and mutable objects
`in the game world. For example, picking up a health pack (adding it to the inventory)
`or consuming it are examples of player-object interaction. Player-player interactions
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 5 of 52 PageID #: 1895
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`9:4
`
`A. Yahyavi and B. Kemme
`
`are interactions between a player and other players in the game world. For example,
`attacking another player could decrease the other player’s health and increase the
`experience points for the attacker. Player interactions with NPCs, based on the game
`design, can be considered either player-object or player-player interactions.
`The type of interaction is important when dealing with consistency issues that arise
`from concurrent and conflicting updates to the same object. Also, most security and
`cheat prevention techniques only apply to certain types of interactions.
`
`2.3. Object Replication
`When a player joins a game, she receives an instance of the game world (it can be a
`limited view of the game world) that is made up of various types of game objects. Most
`game engines follow a primary copy replication approach. For each object and character
`there exists an authoritative copy, called primary or master copy. All other copies are
`secondary copies (also called replicas). Each player has, stored on his computer, copies
`of game objects which are of interest to the player. Any update to the object has to be
`first performed on the primary copy. How primary and secondary copies are distributed
`(e.g., primary copies might always reside on the server or might also be held by clients)
`depends on the game architecture. If a player wants to perform an update on an object
`for which she does not have the primary copy, she has to send the update to the primary
`copy. The holder of the primary copy decides whether to accept the update or not, and
`then sends the updated object to everyone that has a secondary copy, where the changes
`are applied.
`The update dissemination mechanism is quite similar to publish-subscribe systems
`that have been widely studied [Castro et al. 2002b]. Every replica becomes a subscriber
`to the primary copy of the object and receives publications (updates) from the primary
`copy (the publisher).
`
`2.4. Game Types and Latency Tolerance
`We refer to the latency as the delay between execution of an update at the primary
`copy of an object and the replica receiving the object update. This latency is dependent
`on the architectural design and networking delays as will be discussed.
`Various types of multiplayer and massively multiplayer games exist. In Real-Time
`Strategy (RTS) and Role Playing Games (RPGs) [Sheldon et al. 2003] the focus is
`more on game strategy rather than responsiveness. The player tells the avatar to do
`a possibly complex and long-lasting action, for example, go to a destination, and the
`avatar performs the requested action. In First Person Shooter (FPS) games, however,
`the player does short-lived and less complex actions, that is, the player actually does
`what he wants the character to do (for example, guides the avatar towards the des-
`tination) and as a result, higher responsiveness is required (see Armitage [2003] for
`Quake III latency requirements). Higher latencies than the tolerance threshold of the
`game have an adverse effect on playability of the game and user satisfaction. Based
`on the game type and design, games typically can tolerate latencies between 100 to
`300 milliseconds (ranging from FPS games to RPGs) [Armitage 2003; Bharambe et al.
`2006; Pantel and Wolf 2002b], however, games with higher latency tolerance exist (see
`Suznjevic and Matijasevic [2012]). Latency tolerance requirements have a dramatic
`effect on the architecture design for games. An architecture would only be feasible if it
`meets game latency requirements.
`
`2.5. Bucket Synchronization and Frame Rate
`Bucket synchronization [Lety et al. 1998] (also called local lag [Mauve et al. 2004]) is a
`method used to deal with latency and is used in most multiplayer games. Since network
`latency for each client is different and it is common for a primary copy to receive various
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 6 of 52 PageID #: 1896
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`Peer-to-Peer Architectures for Massively Multiplayer Online Games: A Survey
`
`9:5
`
`update requests concurrently from different clients, most games deliberately lag behind
`in executing the events. This allows fairness despite latency variations and more control
`over update dissemination costs. This is in essence similar to Nagle’s algorithm in IP
`networking. Games implement a discrete event loop (may also be referred to as frame)
`in which all actions (events) that have been submitted since the last execution of the
`loop are received, buffered, and then executed. The updates are then sent at the end of
`the loop. In addition, most game objects, including NPCs, have a think function which
`is executed in every game loop and determines the actions of the object in this loop. The
`game loop is usually executed 10 to 20 times every second; this frequency is sometimes
`referred to as frame rate [Bharambe et al. 2008] (not to be confused with graphical
`frame rate). Low frame rates can degrade the game play experience or even render the
`game unplayable. Note that based on the game design the number of frames shown
`to the player, that is, the graphical frame rate, may be equal to or different from this
`frame rate.
`The lag should be chosen so that it allows enough time for the updates of different
`clients to be received. This helps ensure fairness for clients that might have worse
`connectivity, and controls the number of updates that have to be sent per second. At
`the same time, the lag has to be small enough not to be perceived by the players. In
`essence, a trade-off has to be found.
`In this article we focus on the impact of architectures on networking, processing
`delays, and the resulting frame rate. We do not consider other delays such as those
`caused by graphical processing.
`
`2.6. Bandwidth Requirements
`The bandwidth requirement of MMOGs can be calculated based on average message
`size, update rate, and number of recipients (active players). Games with millions of
`(active) subscribers (e.g., WoW) have high bandwidth requirements due to their dy-
`namic environment (e.g., Second Life), or high update rates (e.g., Quake) [Chen et al.
`2005b; Suznjevic and Matijasevic 2012]. In addition, in order to have an acceptable
`game play, games should also accommodate occasional bursts in the game traffic that
`can be many times the average requirements. Such bursts happen due to sudden en-
`vironment changes or battles. Moreover, even inside the same game different gaming
`activities, such as raiding versus trading in WoW, generate different traffic [Suznjevic
`et al. 2011] that can lead to different network requirements. Game servers typically
`deal with this by overprovisioning.
`
`2.7. Interest Management
`Interest Management (IM) [Benford and Fahl´en 1993; Morse 1996] is an important
`mechanism used in many games, typically for scalability reasons. The idea is that
`players of a multiplayer game have only limited movement and vision capabilities.
`That is, players can only move a small distance in the game world in a given time
`interval. The players also have limited sensing capabilities, meaning that players can
`only interact with objects and other players in their vicinity [Makbily et al. 1999]. As
`a result, data access in games shows spatial and temporal locality. Utilizing this fact,
`interest management limits the amount of game state any player can access. That is,
`the player only receives the game state relevant to it, based on his position and vision
`in the game world. Interest management is important for scalability, as clients only
`need replicas of objects that are interesting for them, therefore keeping update and
`network overhead low. However, it can also be important as part of game semantics
`or to address other challenges such as cheating. IM plays an important role in how
`replication and communication between players are managed as will be discussed in
`the next sections, but first, we explain how it is implemented.
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 7 of 52 PageID #: 1897
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`9:6
`
`A. Yahyavi and B. Kemme
`
`Fig. 2. Different game zoning mechanisms [Chen et al. 2005a] (adapted, c(cid:2)ACM 2005); [Boulanger et al.
`2006] (adapted, c(cid:2)ACM 2006).
`
`Space-based interest management is based on proximity and follows an aura-nimbus
`model [Benford and Fahl´en 1993]. Aura is the bounding area around the player’s avatar,
`while nimbus defines the area around the player that is visible to the player, that is,
`the player can perceive game objects located in this area. Nimbus is also often referred
`to as Area-of-Interest (AOI) [Knutsson et al. 2004; Schmieg et al. 2008], Domain of
`Interest [Morse 1996], Aura [Greenhalgh and Benford 2002], or awareness area [Keller
`and Simon 2003]. We mainly use the term AOI in this article. A player can typically only
`interact with objects and players in her AOI, and therefore, only needs to have copies
`of these objects. As a result, the necessary computational and network requirements
`are substantially reduced compared to maintaining copies of all objects.
`Zoning. The most common mechanism for interest management is zoning where the
`game world is partitioned into smaller sections, called zones or regions, as depicted
`in Figure 2. Zoning approaches differ in the shape of their zones and how the AOI is
`mapped onto zones. In the simplest approach, the entire AOI resides in the same zone
`in which the player is located. In some systems, the player can simply interact with all
`objects in his zone, that is, his AOI is the entire zone [Berglund and Cheriton 1985; Lety
`et al. 1998]. A player’s AOI changes only if he moves from one zone to another. In other
`approaches, the AOI is a subarea of the entire zone. Often, it is a fixed-radius circle
`(or sphere) around the player. When the player moves, his AOI moves accordingly.
`Therefore interest management has to determine for each game object in the zone
`whether it falls in the current AOI of the player. Figure 2(a) shows an example of this
`subarea approach.
`More advanced interest management schemes allow the AOI to cover more than one
`zone. This is important for continuous worlds. Players at the borders of a zone should
`be able to see and interact with objects that are just across the zone boundary in a
`neighboring zone. Figures 2(b), (c), and (d) show examples where the AOI can cover
`several zones.
`In regard to zone shapes, the game world can simply be split statically into grid
`cells as shown in Figure 2(b). Since this is a straightforward approach, many solutions
`use it [Chen et al. 2005a; Iimura et al. 2004; Cecin et al. 2004]. Hexagonal zoning
`(Figure 2(c)) has also been widely used for game architectures [Yu and Vuong 2005;
`Macedonia et al. 1995; Jaramillo et al. 2003] as well as other systems such as cellular
`networks. Hexagons have uniform orientation and uniform adjacency, meaning that
`players will always move to an adjacent zone. In addition, since most AOI mechanisms
`consider a circle, hexagons provide a good approximation.
`Using triangulation, as shown in Figure 2(d), allows for taking obstacles in the game
`world into account. This can help in reducing the AOI, and thus the number of objects
`that have to be considered for interest management, leading to less object replicas to be
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 8 of 52 PageID #: 1898
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`Peer-to-Peer Architectures for Massively Multiplayer Online Games: A Survey
`
`9:7
`
`maintained by the players, and less update messages that need to be sent [Boulanger
`et al. 2006]. Techniques such as Delaunay triangulation have been widely studied.
`They can be used to triangulate the area inside or around the polygon-shaped obstacle,
`so that triangles follow the boundaries of obstacles [Boulanger et al. 2006; Buyukkaya
`and Abdallah 2008] as shown in the figure.
`Games can also be divided into mini worlds that have a free format and are con-
`nected to each other such as countries in the game world, with portals for moving
`between them [Chen et al. 2005a; Knutsson et al. 2004] as in Figure 2(a). This is par-
`ticularly useful when AOI always resides within a single zone. While mini worlds do
`not offer the concept of a continuous world, other approaches do. The zoning is only
`virtual, done merely for the purpose of interest management, and is not visible to the
`players.
`Determining the right size for zones is challenging. Different games have very dif-
`ferent characteristics, and even inside a game, different parts may require different
`zoning mechanisms. Therefore, an optimal zoning mechanism for all cases does not
`exist. A very large zone can result in too many objects in a single zone, making interest
`management less efficient as any player might only be interested in a small set of
`these objects. On the other hand, too small a zone may be much smaller than the AOI
`of players, resulting again in complex interest management between multiple zones.
`This trade-off is addressed by dynamic interest management schemes.
`
`Limits of AOI and Dynamic Zoning. AOI filtering suffers specific user behaviors,
`such as flocking, which refers to the movement of many players to one area in the
`game world [Pittman and GauthierDickey 2007; Chen et al. 2005a]. This can adversely
`affect replication management (see Section 7). Game hotspots form since some areas
`become more interesting or more profitable to the players in terms of experience points,
`treasures, new quests, or invitations by other players. This results in a large number
`of players coming to the same area while other areas become less populated. Hotspots
`can change quickly as players move to new interesting areas as they emerge, making
`it often difficult to prepare for such changes in advance. Populations in real games
`often follow a power law distribution [Pittman and GauthierDickey 2007], and the
`increase in the number of players in the area can result in a quadratic increase in the
`network traffic generated due to the increase in the number of interactions between
`players [Bharambe et al. 2008]. Varvello et al. [2011] find that in Second Life the
`number of objects per region is roughly constant over a one month period and that the
`active population at any point of time is between 30,000 and 50,000 avatars, that is,
`about 0.3% of the registered avatars. About 30% of the regions are never visited in a
`six day period and less than 1% of the regions have large peak populations. Avatars
`tend to organize in small groups of 2 to 10 avatars. Large groups of avatars are very
`rare and are driven by the presence of events such as concerts and shows. As a result,
`game designers may have to use artificial means to discourage players from gathering
`in the same region. This can prevent certain types of interesting game play such as epic
`battles [Blizzard 2011]. A more comprehensive study of player movements in Massively
`Multiplayer Online Role Playing Games (MMORPG) and session patterns is provided
`in Varvello et al. [2011], Suznjevic et al. [2009], and Miller and Crowcroft [2010].
`Flocking can be partially addressed with dynamic zones. As more players move into a
`popular zone, the zone can be split. However, if zones become significantly smaller than
`the typical AOI, splitting does not really help anymore as inter-zone communications
`become the bottleneck. One possibility then is to shrink the AOI of the players. However,
`this might lower the game experience for the players. In addition, depending on the
`game design, AOI can be further broken down into different types [Morse 1996] but for
`the purpose of this article we use the general term AOI.
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-4 Filed 10/21/16 Page 9 of 52 PageID #: 1899
`
`CSUR4601-09
`
`ACM-TRANSACTION
`
`October 10, 2013
`
`21:43
`
`9:8
`
`A. Yahyavi and B. Kemme
`
`2.8. Consistency Control
`In a distributed architecture like a multiplayer game, concurrent and possibly con-
`flicting updates may be executed at different sites resulting in inconsistent states.
`Inconsistencies occur due to the execution of parallel and conflicting updates, and con-
`sistency mechanisms have to avoid or correct them. For example, if two players shoot
`a third player, nearly at the same time, all players should see the updates in the same
`order and only the first shot should be successful at all replicas.
`Generally, systems are built such that if all replicas execute all updates in the same
`order, then all sites will have the same state. However, if messages are received out of
`order, their execution can result in inconsistent state if the out-of-order messages are
`causally dependent. For example, if a player drinks a healing potion to increase his
`health points and then, and only based on the increased amount of health, is able to
`pick up a sword, these actions have to be performed in the same order at all replicas,
`otherwise inconsistencies might become visible. Other types of inconsistency are caused
`by loss of updates. Most games, in order to deal with latency issues, use the fast but
`unreliable UDP messaging protocol where message loss is possible. Solutions are to
`send some updates with reliable TCP, or to use commit protocols for critical actions, in
`particular if they change the state of several objects and atomicity is required [Mauve
`et al. 2004; Bharambe et al. 2008, 2006; Chandler and Finney 2005].
`
`Consistency Definitions. Many definitions for consistency exist and consistency con-
`trol has been studied in other distributed contexts (e.g., shared memory [Adve and
`Gharachorloo 1996] or distributed systems [ ¨Ozsu and Valduriez 2011]). A very strong
`form of consistency is achieved if every interaction is treated as a transaction that pro-
`vides the transactional properties such as isolation and atomicity. However, providing
`transactional properties is often costly and might not be feasible for all game actions.
`For instance, running a two-phase commit protocol to guarantee atomicity leads to large
`latencies which could reduce the interactivity of the game significantly. Eventual con-
`sistency [Terry et al. 1995] is a weaker form of consistency. It allows individual copies
`of an object to be temporarily inconsistent but eventually consistent, meaning that if
`update activity did cease for sufficiently long time all object copies would eventually
`have the same state. Generally, there exist well-known trade-offs between performance
`and consistency restrictions, which can also be applied to MMOGs. This fact has been
`well presented in Brewer’s “CAP conjecture” [Gilbert and Lynch 2002], indicating that
`a system can only achieve two out of three properties of consistency, availability, and
`handling network partitions. As interactivity is of essence to the success of most games,
`they often sacrifice consistency for other goals, and as a result, games usually provide
`inconsistency resolution instead of inconsistency prevention, enforcing not more than
`eventual consistency [Chandler and Finney 2005; Mauve et al. 2004].
`Different levels of consistency, implemented by various mechanisms, might be con-
`sidered for different object and interaction types as not all interactions are of the same
`importance [Zhang and Kemme 2011]. For example, many virtual game objects are con-
`sidered valuable and can be sold or traded for real money, making consistency control a
`critical requirement. In 2009, micro-transactions generated 250 million dollars in U.S.
`alone, with the most expensive item being 635 thousand dollars3, and are projected to
`hit 13.6 billion dollars by 2014 worldwide4. In contrast, player position updates have
`much lower consistency requirements, and eventual consistency will be sufficient.
`
`3Planet Calypso Player Sells Virtual Resort for $635,000 USD http://www.prnewswire.com/news-releases/
`planet-calypso-player-sells-virtual-resort-for-63500000-usd-107426428.html.
`4Magid Associates and PlaySpan Release 2nd Annual Survey on Virtual Goods Market Penetration and
`Growth in North America. https://developer.playspan.com/developer/pdf/PlaySpan Magid 5 27 10 Final.pdf.
`
`ACM Computing Surveys, Vol. 46, No. 1, Article 9, Publication date: October 2013.
`
`

`

`Case 1:16-cv-00455-RGA Document 32-