# Virtual Net: A Decentralized Architecture for Interaction in Mobile Virtual Worlds

Authors: Bingqing Shen; Jingzhi Guo
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

With the development of mobile technology, mobile virtual worlds have attracted massive users. To improve scalability, a peer-to-peer virtual world provides the solution to accommodate more users without increasing hardware investment. In mobile settings, however, existing P2P solutions are not applicable due to the unreliability of mobile devices and the instability of mobile networks. To address the issue, a novel infrastructure model, called Virtual Net, is proposed to provide fault-tolerance in managing user content and object state. In this paper, the key problem, namely, object state update, is resolved to maintain state consistency and high interaction responsiveness. This work is important in implementing a scalable mobile virtual world.


---

## Body

## 1. Introduction

Virtual worlds, including multiplayer online games and virtual social worlds, allow users to inhabit in virtual environments, create their own content, and interact with each other. Mobile virtual worlds allow users to access the simulated environments through mobile devices, achieving the possibility to play anywhere. Mobile virtual worlds have gained large attraction from the development of mobile devices. They have become an important market and revenue source for the game industry and attracted a large number of users. For example, Fortnite has earned $1,996,917 gross daily revenue [1] and reported 3.4 million concurrent players [2] in 2018. The success and expansion of mobile virtual worlds raise new challenges in infrastructure development; one of them is the scalability problem. In virtual worlds, interaction is implemented by sending events to servers for processing and receiving updates from the servers for rendering and state synchronization. With the increase of concurrent online users, more computing load is imposed on game infrastructures. Servers have to process and respond to more client requests within a short period for high responsiveness. Also, network bandwidth consumption is increased to pack multiple game states in an update. For scaling, more computing resources have to be invested. Otherwise, user experience will be affected.Peer-to-peer (P2P) virtual worlds, firstly introduced in [3], explore the possibility of running a virtual world without a central server. In P2P virtual worlds, user devices run both the client program and server program for event handling and state update. Thus, computing resources naturally scale along with the change of user population. Mobile applications, however, have different characteristics with respect to their desktop counterparts. One outstanding issue is client failure. Compared to desktop PCs, mobile devices are more prone to failure, due to, for example, battery depletion or application conflict. Moreover, the access to mobile networks, such are MANETs and VANETs, is also unstable. Client unreliability may cause content loss or state inconsistency, if user content and object state are not properly saved or backed up before failure. Yet, existing P2P virtual worlds do not concern the peer device unreliability problem [4]. Thus, they cannot be directly applied in mobile settings.In this paper, a Virtual Net model is proposed to address the client unreliability problem for mobile P2P virtual worlds. The model utilizes the cloud-fog structure, but totally decentralized. To avoid content loss, the cloud layer stores user contents for content persistency. The fog layer caches object states for client recovery and maintains state consistency. The separation of content storage and state caching can improve responsiveness, since operations direct on P2P storage have more communication overhead [5]. Based on the P2P content storage, a content addressing scheme is devised, which can facilitate content integrity check.To avoid reinventing the wheel, this paper mainly focuses on the state update problem to maintain object state consistency. At the fog layer, object states are replicated on several nodes for fault-tolerance. Thus, all replicas must maintain the same state in event handling so that interaction can be performed within a consistent shared environment. Yet, the requirement of high responsiveness in virtual world interaction makes the problem difficult. To attack the difficulty, an opportunistic approach, called fast event delivery, is proposed. Based on the approach, a virtual world interaction model is then designed. In short, the main contributions of the paper are listed as follows.(1)
A new P2P cloud-fog structure, called Virtual Net model, is proposed to resolve the client unreliability problem, which can provide fault-tolerance in playing a mobile virtual world.(2)
A fast event delivery approach is proposed to maintain both replica state consistency and high responsiveness in the process of handling user events.(3)
A new virtual world interaction model is designed to achieve game state consistency and high responsiveness when interacting with different neighbors.The remainder of the paper is organized as follows. The related works are introduced in Section2. The overall Virtual Net model is described in Section 3. Section 4 studies the state update problem in detail. Based on the solution of the problem, the virtual world interaction model is provided in Section 5 with neighbor change management. The correctness of the solution is proved in Section 6. Sections 7 and 8 evaluate the performance through theoretical analysis and experiments. Section 9 concludes the paper.


## 2. Related Work

Mobile P2P virtual worlds combine the characteristics of mobile virtual world and P2P virtual world problems. Due to the lack of study in this field, the related work in P2P virtual worlds and cloud-fog mobile applications is surveyed to shape the distinct characteristics of the combined problem.


### 2.1. P2P Virtual Worlds

P2P MMORPGs and P2P virtual environments have been amply surveyed in [4, 6]. Previous works mainly focus on inter-player consistency management, including peer connectivity, interest management, event dissemination, and cheat prevention. Peer connectivity [7] studies the connection of all user devices within an overlay network such that any peer can be reached from another peer. Interest management [8] restricts the range of message receipt to reduce communication overhead in state update. Event dissemination [9] reduces the number of communication channels on event senders to avoid overwhelming them in hotspot areas. Cheat prevention [10] is needed to achieve fairness without the arbitration from a central server. In these works, a desktop environment is assumed such that a client is always reliable in storage and connection. In contrast, the Virtual Net targets the mobile environments in which both devices and connections are unreliable, which is the new problem and orthogonal to the above studies. Thus, a complete implementation of Virtual Net can employ existing P2P solutions in inter-player consistency management, such as peer connectivity and interest management, to avoid reinventing the wheel.Early work on P2P state persistency is related to the content storage in this work. State persistency studies the reliable storage and efficient retrieval of user state [11]. Each time a state is updated, it has to be persisted in the overlay network, and the state has to be queried from the overlay network when the client is recovered from a failure. Same as the above argument, the work in [11] only assumes a reliable client, which is not applicable in a mobile setting. The Virtual Net model not only solves the unreliable client problem, but also reduces storage and retrieval overhead through content caching. Moreover, content integrity check is included in Virtual Net, which is not mentioned in previous works.


### 2.2. Fog Computing

Firstly introduced in [12], cloud gaming moves the game engine functions to the cloud to simplify development, distribution, access, and update [13]. However, the measurement study [14] shows that the current cloud gaming infrastructure is unable to meet the latency requirement for end-users distant from data centers. To improve latency, fog computing [15] has been introduced to move the time-critical functions to the locations near clients. Fog computing has been widely discussed in both Internet of Things (IoT) [16] and mobile computing [17] to offload server burden [18], enable location awareness, and provide real-time interaction. Among its many applications, mobile gaming [19] and mobile reality [20] are two important examples. Similar to the cloud-fog structure, the Virtual Net solution also employs the cloud layer for content storage and the fog layer for latency improvement. But differently, Virtual Net explores a totally decentralized solution, with no central control at the cloud layer.


## 2.1. P2P Virtual Worlds

P2P MMORPGs and P2P virtual environments have been amply surveyed in [4, 6]. Previous works mainly focus on inter-player consistency management, including peer connectivity, interest management, event dissemination, and cheat prevention. Peer connectivity [7] studies the connection of all user devices within an overlay network such that any peer can be reached from another peer. Interest management [8] restricts the range of message receipt to reduce communication overhead in state update. Event dissemination [9] reduces the number of communication channels on event senders to avoid overwhelming them in hotspot areas. Cheat prevention [10] is needed to achieve fairness without the arbitration from a central server. In these works, a desktop environment is assumed such that a client is always reliable in storage and connection. In contrast, the Virtual Net targets the mobile environments in which both devices and connections are unreliable, which is the new problem and orthogonal to the above studies. Thus, a complete implementation of Virtual Net can employ existing P2P solutions in inter-player consistency management, such as peer connectivity and interest management, to avoid reinventing the wheel.Early work on P2P state persistency is related to the content storage in this work. State persistency studies the reliable storage and efficient retrieval of user state [11]. Each time a state is updated, it has to be persisted in the overlay network, and the state has to be queried from the overlay network when the client is recovered from a failure. Same as the above argument, the work in [11] only assumes a reliable client, which is not applicable in a mobile setting. The Virtual Net model not only solves the unreliable client problem, but also reduces storage and retrieval overhead through content caching. Moreover, content integrity check is included in Virtual Net, which is not mentioned in previous works.


## 2.2. Fog Computing

Firstly introduced in [12], cloud gaming moves the game engine functions to the cloud to simplify development, distribution, access, and update [13]. However, the measurement study [14] shows that the current cloud gaming infrastructure is unable to meet the latency requirement for end-users distant from data centers. To improve latency, fog computing [15] has been introduced to move the time-critical functions to the locations near clients. Fog computing has been widely discussed in both Internet of Things (IoT) [16] and mobile computing [17] to offload server burden [18], enable location awareness, and provide real-time interaction. Among its many applications, mobile gaming [19] and mobile reality [20] are two important examples. Similar to the cloud-fog structure, the Virtual Net solution also employs the cloud layer for content storage and the fog layer for latency improvement. But differently, Virtual Net explores a totally decentralized solution, with no central control at the cloud layer.


## 3. Virtual Net Model

The proposed Virtual Net structure is based on the commonly used three-layer structure shown in Figure1. Similar to some existing cloud-fog structures, it is divided into three layers: the cloud layer (L1), the fog layer (L2), and the client layer (L3). The cloud layer provides persistency service, which stores the files of user content and the state of virtual objects (avatars, accessories, achievements, etc.). The fog layer caches object states in play and provides state recovery for clients in case of short-term failure. It also periodically checks object states and saves them to the cloud layer for state persistency, which is asynchronous to event handling. When a user leaves a game, the cached state of user object will be saved to the cloud layer. The client layer provides user interfaces for receiving user operations and displaying updated states for user interaction. Virtual worlds are latency-sensitive applications. Yet, on one hand, clients require fast state update in user interaction [21]. On the other hand, the complexity of peer-to-peer routing slows down the process of content storage and retrieval [22]. Thus, the fog layer is padded between L1 and L3 to improve responsiveness in fault-tolerance.Figure 1
Virtual Net overall model.The three-layer architecture is resilient. First, L1 and L2 can be individually scaled without affecting each other, since they are built for different purposes. The cloud layer focuses on the long-term storage of user content, which is only accessed at user login, logout, and periodic state checkpoint by the fog nodes. On the other hand, the fog layer maintains the latest state of user content and provides state recovery from intermittent client failure. Except for state initialization and checkpoint, L1 and L2 do not need to interact with each other. Besides, the model provides some extent of isolation of failure. The failure of one layer can be recovered by another layer, since each layer has a separate copy of content.Different from the existing cloud-fog computing paradigm, computing resources in the cloud and fog layer are P2P nodes, like BitTorrent or eDonkey. Specifically, users contribute part of the computing resources from their devices which can be smartphones, laptops, desktop PCs, or even servers. A device is divided into one or several virtual nodes [23] for fine-grained load balancing. All virtual nodes are managed by a node pool. For different computing purposes, there are two types of virtual nodes: storage nodes and cache nodes. The storage nodes construct the cloud layer and the cache nodes construct the fog layer. Thus, Virtual Net is a decentralized computing paradigm. A client could be on the same device of a virtual node, like BitTorrent, or on a separate lightweight device.


### 3.1. P2P Cloud Layer

Object files are stored on the cloud layer through P2P file storage. Based on the file storage system, a content addressing scheme is devised, which can not only provide flexibility in content identification and addressing but also provide integrity in object management.


#### 3.1.1. File Storage

The TotalRecall [5] storage architecture is applied to manage the storage nodes for file storage. The details of the design and performance can be found in [5]. Here, only the overall mechanism is introduced. In TotalRecall, each node is assigned a unique hash code as the node ID. Also, each file has a file ID which is the hash checksum of the file. When a new file is created, the file is associated with a storage node, called the master node whose ID is closest to the file ID. Other nodes hosting the data of the file are called host nodes. Master nodes manage the location of host nodes and the version control for the associated files. Each storage node can be the master node for some files and the host node for other files. Thus, the entire storage node network forms a distributed hash table (DHT) for file lookup. To request a file, its master node is found first with the file ID. Then, based on the reply from the master node, the host nodes are located and the file can be retrieved (or reconstructed).


#### 3.1.2. Content Addressing

To retrieve the objects from the cloud layer, object content needs to be identified and addressed. A hierarchical content addressing scheme is devised, which can facilitate content integrity check. The devised content addressing scheme has four hierarchies: inventory, objects, components, and files, as illustrated in Figure2.Figure 2
Illustration of the content addressing scheme hierarchy.Inventory-level: each user has an inventory file, identified by the inventory ID which is the hash code of the user ID. An inventory contains all the object descriptions, consistently managing content identification and modification. Thus, to retrieve the object contents, the inventory file needs to be retrieved first.Object-level: an object is identified by the object hash code and composed of one or multiple components.Component-level: each component is identified by the component hash code. Object components are the categories of object resource files, which are classified into animation, sound, texture, script, etc.File-level: the actual files of objects are addressed by file IDs in object descriptions. Through files ID, the actual file can be retrieved either from the local cache or from the DHT of the cloud storage.Based on the structure of the content addressing scheme, a Merkle tree [24] (Figure 2) can be hierarchically constructed with the file hash code, component hash code, object hash code, and inventory hash code. With the Merkle tree, the integrity of user content can be recursively checked and the number of hash comparisons can be largely reduced [25]. Typically, a client caches more than 500,000 files of user-created contents [26]. Thus, an exhaustive search of updated files will be inefficient. We conduct an experiment with 200 objects and more than 5,000 files. Compared with the file-level and object-level content integrity check [26], Figure 3 shows that the proposed four-level content integrity verification has fewer hash comparisons, especially with respect to a small number of file changes.Figure 3
Number of hash comparisons with random file changes in content integrity check.


### 3.2. P2P Fog Layer

The fog layer is added between the cloud layer and the client layer to mask the latency of content storage and meanwhile provide fault-tolerance. From the user perspective, each user is allocated some cache nodes, when he/she is playing in a virtual world. These cache nodes provide the user some computing resources, forming a logical computing unit. We call it mesh computer, as illustrated in Figure4. When a user logs to the system, his/her client firstly initializes the mesh computer by requesting for some cache nodes from the node pool. The cache nodes then retrieve the content from the cloud layer. The client also retrieves the saved content from the cloud layer for content rendering and state synchronization. When the mesh computer receives a quit instruction from the client or the client is experiencing a long-term failure, the mesh computer will release the cache nodes to the node pool. Optimal resource allocation and cost minimization have been studied in [23], which is out of the scope of this paper.Figure 4
Mesh computer.Due to the unreliability characteristic of P2P nodes, they are subject to (either temporarily or permanently) failure. Thus, for reliability purpose, a mesh computer maintains multiple cache nodes which are the replicas of the same user content, called a replica group. Content will be transferred from failed nodes to live nodes. Replica group management has been studied in our previous work [27]. This paper focuses on replica state management in the following sections.


## 3.1. P2P Cloud Layer

Object files are stored on the cloud layer through P2P file storage. Based on the file storage system, a content addressing scheme is devised, which can not only provide flexibility in content identification and addressing but also provide integrity in object management.


### 3.1.1. File Storage

The TotalRecall [5] storage architecture is applied to manage the storage nodes for file storage. The details of the design and performance can be found in [5]. Here, only the overall mechanism is introduced. In TotalRecall, each node is assigned a unique hash code as the node ID. Also, each file has a file ID which is the hash checksum of the file. When a new file is created, the file is associated with a storage node, called the master node whose ID is closest to the file ID. Other nodes hosting the data of the file are called host nodes. Master nodes manage the location of host nodes and the version control for the associated files. Each storage node can be the master node for some files and the host node for other files. Thus, the entire storage node network forms a distributed hash table (DHT) for file lookup. To request a file, its master node is found first with the file ID. Then, based on the reply from the master node, the host nodes are located and the file can be retrieved (or reconstructed).


### 3.1.2. Content Addressing

To retrieve the objects from the cloud layer, object content needs to be identified and addressed. A hierarchical content addressing scheme is devised, which can facilitate content integrity check. The devised content addressing scheme has four hierarchies: inventory, objects, components, and files, as illustrated in Figure2.Figure 2
Illustration of the content addressing scheme hierarchy.Inventory-level: each user has an inventory file, identified by the inventory ID which is the hash code of the user ID. An inventory contains all the object descriptions, consistently managing content identification and modification. Thus, to retrieve the object contents, the inventory file needs to be retrieved first.Object-level: an object is identified by the object hash code and composed of one or multiple components.Component-level: each component is identified by the component hash code. Object components are the categories of object resource files, which are classified into animation, sound, texture, script, etc.File-level: the actual files of objects are addressed by file IDs in object descriptions. Through files ID, the actual file can be retrieved either from the local cache or from the DHT of the cloud storage.Based on the structure of the content addressing scheme, a Merkle tree [24] (Figure 2) can be hierarchically constructed with the file hash code, component hash code, object hash code, and inventory hash code. With the Merkle tree, the integrity of user content can be recursively checked and the number of hash comparisons can be largely reduced [25]. Typically, a client caches more than 500,000 files of user-created contents [26]. Thus, an exhaustive search of updated files will be inefficient. We conduct an experiment with 200 objects and more than 5,000 files. Compared with the file-level and object-level content integrity check [26], Figure 3 shows that the proposed four-level content integrity verification has fewer hash comparisons, especially with respect to a small number of file changes.Figure 3
Number of hash comparisons with random file changes in content integrity check.


## 3.1.1. File Storage

The TotalRecall [5] storage architecture is applied to manage the storage nodes for file storage. The details of the design and performance can be found in [5]. Here, only the overall mechanism is introduced. In TotalRecall, each node is assigned a unique hash code as the node ID. Also, each file has a file ID which is the hash checksum of the file. When a new file is created, the file is associated with a storage node, called the master node whose ID is closest to the file ID. Other nodes hosting the data of the file are called host nodes. Master nodes manage the location of host nodes and the version control for the associated files. Each storage node can be the master node for some files and the host node for other files. Thus, the entire storage node network forms a distributed hash table (DHT) for file lookup. To request a file, its master node is found first with the file ID. Then, based on the reply from the master node, the host nodes are located and the file can be retrieved (or reconstructed).


## 3.1.2. Content Addressing

To retrieve the objects from the cloud layer, object content needs to be identified and addressed. A hierarchical content addressing scheme is devised, which can facilitate content integrity check. The devised content addressing scheme has four hierarchies: inventory, objects, components, and files, as illustrated in Figure2.Figure 2
Illustration of the content addressing scheme hierarchy.Inventory-level: each user has an inventory file, identified by the inventory ID which is the hash code of the user ID. An inventory contains all the object descriptions, consistently managing content identification and modification. Thus, to retrieve the object contents, the inventory file needs to be retrieved first.Object-level: an object is identified by the object hash code and composed of one or multiple components.Component-level: each component is identified by the component hash code. Object components are the categories of object resource files, which are classified into animation, sound, texture, script, etc.File-level: the actual files of objects are addressed by file IDs in object descriptions. Through files ID, the actual file can be retrieved either from the local cache or from the DHT of the cloud storage.Based on the structure of the content addressing scheme, a Merkle tree [24] (Figure 2) can be hierarchically constructed with the file hash code, component hash code, object hash code, and inventory hash code. With the Merkle tree, the integrity of user content can be recursively checked and the number of hash comparisons can be largely reduced [25]. Typically, a client caches more than 500,000 files of user-created contents [26]. Thus, an exhaustive search of updated files will be inefficient. We conduct an experiment with 200 objects and more than 5,000 files. Compared with the file-level and object-level content integrity check [26], Figure 3 shows that the proposed four-level content integrity verification has fewer hash comparisons, especially with respect to a small number of file changes.Figure 3
Number of hash comparisons with random file changes in content integrity check.


## 3.2. P2P Fog Layer

The fog layer is added between the cloud layer and the client layer to mask the latency of content storage and meanwhile provide fault-tolerance. From the user perspective, each user is allocated some cache nodes, when he/she is playing in a virtual world. These cache nodes provide the user some computing resources, forming a logical computing unit. We call it mesh computer, as illustrated in Figure4. When a user logs to the system, his/her client firstly initializes the mesh computer by requesting for some cache nodes from the node pool. The cache nodes then retrieve the content from the cloud layer. The client also retrieves the saved content from the cloud layer for content rendering and state synchronization. When the mesh computer receives a quit instruction from the client or the client is experiencing a long-term failure, the mesh computer will release the cache nodes to the node pool. Optimal resource allocation and cost minimization have been studied in [23], which is out of the scope of this paper.Figure 4
Mesh computer.Due to the unreliability characteristic of P2P nodes, they are subject to (either temporarily or permanently) failure. Thus, for reliability purpose, a mesh computer maintains multiple cache nodes which are the replicas of the same user content, called a replica group. Content will be transferred from failed nodes to live nodes. Replica group management has been studied in our previous work [27]. This paper focuses on replica state management in the following sections.


## 4. Object State Update

At the fog layer, it is important that all replicas of the same group maintain the same state of user objects so that any failure of a replica will not invalidate a user’s current state. The problem becomes challenging, since replicas could receive different sets of concurrent events from different senders and events could be received in different orders. The state machine replication (SMR) [28] approach is adopted to manage object state. SMR is a fault-tolerance model replicating a deterministic finite state machine on a set of distributed nodes, each of which has the same input, output, and state transfer. In an asynchronous cycle, firstly, clients send requests to all the nodes. On receiving the requests, a consensus protocol is triggered to determine the sequence of requests. Then, all nodes process the requests in the decided sequence so that they can reach the same new state. To reduce communication overhead, one replica is elected as the leader, coordinating membership reconfiguration and request ordering.In virtual worlds, however, the consensus process adds a large delay in user interaction, because a requested event must be agreed on by all replicas after at least two communication rounds (i.e., four communication steps) [29] to reach an agreement, before it can be handled and replied to clients. The interaction delay issue in event handling is addressed based on the following observations. Due to users’ limited perception range and motion speed, the number of event senders within a small period is fixed. Thus, the number of concurrent event senders within the period can be known a priori. Based on this observation, we propose a fast event delivery approach.


### 4.1. Fast Event Delivery

Fast event delivery allows a replica to directly deliver a received event through a cycle-event mapping, if it can ensure that the same event will eventually be delivered by all replicas. Specifically, the timeline is divided into infinite cycles of length ∆t. From cyclec0, an event senders periodically broadcasts an event to the replicas in each cycle. Each event is identified by the sender ID and the sequence number. The sequence number of the first event at cyclec0 is 0. If there is no operation,s just broadcasts a no-op event. At the receiving end,c0 is also known by all replicas. Each replica delivers an event with sequence numberc - c0 froms for cyclec, which is called the event of cyclec. Events for cyclec from different senders will be ordered by sender ID. If a replica does not receive the event for cyclec froms, it will start an instance of consensus for the cycle. In the consensus, if a replica has received the event for cyclec, that event will be decided by the leader and delivered by all replicas. Otherwise, they will decide and deliver an empty event for cyclec. Events will be delivered to a queueQd first and then sent to the application from the queue for handling in sequence.The relation of cycle (ci), sender ID, event sequence number, delivery queue (Qd), and delivery sequence (λ) are illustrated in Figure 5. Specifically, inQd, the subscript of evente denotes the event sequence number which is equal to the event sending cycle. Thus, for the same cycle, the events inQd are sorted by the sender ID and mapped to the local index numbers inQd (i.e., the second member in the tuples ofQd).λ represents the global index of events delivered to the application, which will be introduced in Section 4.1.4.Figure 5
Relation of cycle (Ci), sender ID (Si), event sequence number, delivery queue (Qd), and delivery sequence (λ).Figure6 illustrates the fast event delivery process with one senders and three replicasr1,r2, andr3 in the replica groupg.s broadcasted four events,e1,e2,e3, ande4, at cyclesc1,c2,c3, andc4 tog. All replicas receivede1 at cyclec2 ande4 atc5. Only replicar1 receivede2 atc3. No replica receivede3 atc4, butr1 andr2 receivede3 atc5.r1,r2, andr3 delivere1 forc1. They then collectively decidee2 forc3 and an empty event forc4 through consensus. The first problem is how to decidec5 ande3. According to the cycle-event mapping principle (i.e., one-cycle-one-event), the replicas should only delivere4 forc5 and discarde3, leading to event loss. Before discussing the late events handling problem in detail, the settings and assumptions of the system will be introduced first.Figure 6
Illustration of fast event delivery.


#### 4.1.1. Settings and Assumptions

For fault-tolerance, a replica group contains at leastn replicas. The minimal group sizen is determined by the content availability requirement [27] and the replica failure rate. To reduce replication overhead, each group also has an extra numbere of nodes for lazy repair [5]. Oncee + 1 replicas fail, new replicas will be added to recover the group size ton + e.In each replica group, there is one non-replica node monitoring the state of all replicas, called Rendezvous [30]. A Rendezvous uses timeout to determine the state of replicas and then broadcasts their states to all replicas. Monitoring replica state is implemented by exchanging heartbeat messages between a replica and a Rendezvous. If the Rendezvous does not receive one heartbeat message within a cycle, the replica is treated as failed and removed from the group. New replicas are also added by the Rendezvous, once the group size is smaller thann. Rendezvouses are reliable nodes, or called super-peers [19], since the existence of a group is determined by the Rendezvous. Once a Rendezvous fails, a new Rendezvous must be assigned to the replica group, which then rebuilds the replica group and recovers the object states from the cloud storage. By exchanging heartbeat messages, each replica learns the current membership of the groupg, denoted byG, which contains all live replicas of groupg. When the Rendezvous tells a replica that a member has failed or a new member is added, the replica will remove the member fromG or add the member intoG.The system is assumed to be live. The SMR model contains three types of group-wide activities: leader election, group reconfiguration, and consensus. The liveness assumption ensures that when an activity is needed, it will eventually succeed after a finite number of failures.Each replica group maintains a set of event senders. It is assumed that each event sender has an ID which is globally unique and sender IDs are comparable. Moreover, a replica group will append the join timestamp to sender IDs to distinguish a sender in two different joins of a sender set.Lets be the ID of an event sender,c be a cycle number of a replica groupg, andri be theith replica in groupg. Some important relations of event, event sender, event sequence number, and cycle number are defined in Table 1. Other notations used throughout the subsequent sections are listed in Table 1. Besides, event names are capitalized.Table 1
Notations.
Notations Descriptions Relations of event, event sequence number, sender, and cycle number  Seq(s, c) The sequence number of the event sent for cyclec from sender s  Seq(e) The sequence number of evente  e(s, j) The event of sequence numberj sent from s  Deliver(e, c) Returntrue if event e is deliverable at cycle c. Otherwise, return false  DeliverCycle(e) Return the cycle in which evente is delivered. If e has not been delivered, return ⊥.  Receive(e, c) Returntrue if e has been received at cycle c. Otherwise, return false.  ReceiveCycle(e) Return the cycle in which evente is received. If e has not been received, return ⊥.  Event of cycle The event sent by a sender for a cycle is called the event of the cycle. Given the first event sent from senders at cycle c0. The event of cycle c satisfies Seq(e) = Seq(s, c) = (c - c0).  Cycle open / close If a replicari has delivered the events for cycle c and moved to the next cycle c + 1, then c is closed and c + 1 is still open to ri.  Other notations  r i Replicai  r L Group leader  G The set of group members  S The set of event senders  U Set of update recipients  g Replica groupg  s Senders∈S  Index(s) The index ofs in S sorted by sender ID  Sender(e) The sender of evente  c Cycle numberc  ∆t Cycle length  t start,s The start time of the first cycle fors  t send,s(n) The time to send thenth event from s  t recv,s(n) The time to receive thenth event sent from s  t now Current time  E / E(c) The set of decided events / decided events ofc  Q d Delivery queue, containing the sorted events to be delivered to the application in sequence  (c,γ, e) The evente delivered for cycle c with local index γ in Qd  (λ, e) The delivery sequenceλ of event e in Qd, one-to-one mapped onto (c,γ, e) for the given e.  Ω(s, c) The set of expected events which can be delivered toQd (called deliverable events) from s at cycle c  Π(s, c) The set of actual received events froms at cycle c


#### 4.1.2. Late Event Handling

An event is late if the event of cyclec is received afterc on all replicas. Formally, a late evente satisfiesSeq(e) =Seq(s, c) ∧ReceiveCycle(e)> c onri ∈ G andSeq(e) =Seq(s, c) ∧ (ReceiveCycle(e)> c∨ReceiveCycle(e) = ⊥) onrj ∈ G ∖ {ri}. For example,e3 in Figure 6 is a late event.To ensure the agreement of cycle event delivery on all replicas, a late event can be simply discarded, since any event can be re-sent by a client with a new sequence number if the client does not receive the reply for the event for a period. However, if a sender’s clock is temporarily out-of-sync with the replicas’ clock or a large sending delay is experienced, a large number of events could be discarded and need to be re-send, as shown in Figure7.Figure 7
An extreme scenario of late event discard.To address the late event handling problem, a dynamic cycle event delivery approach is proposed, which includes two conditions for late event delivery. The purpose of the approach is to minimize the number of event discards, and meanwhile each replica can decide the delivery of late events with only local information. Below are the conditions of late event delivery. In short, only late and out-of-order events will be discarded.(1)
At cyclec, all events from senders with sequence number less thanc will be deliverable. Formally, ∀e(s, j1),e(s, j2), …,e(s, jn), (1)Receivees,j1,c∧⋯Receivees,jn,c∧DeliverCyclees,j1=⋯=DeliverCyclees,jn=⊥∧seqs,j1<seqs,c∧⋯seqs,jn<seqs,c→Deliveres,j1,c∧⋯∧Deliveres,jn,c.(2)
At cyclec, an event will be nondeliverable, if one of its subsequent events has been delivered beforec. Such event is a late and out-of-order event. Formally, ∀e(s, j),(2)Receivees,j,c∧∃es,k∧k>j∧DeliverCyclees,j=⊥∧DeliverCyclees,k<c→¬Deliveres,j,c.To implement the dynamic cycle event delivery approach, the lowest deliverable sequence number from any sender needs to be determined first for all cycles. Specifically, at cyclec, letMinSeq(s, c) be the lowest sequence number of all undelivered events from senders andMinSeq(s, c) ≤seq(s, c). Also, letMaxSeq(s, c) be the sequence number of the last delivered nonempty event in cyclec froms. Then,MinSeq(s, c) =MaxSeq(s, c−1) +1, whereMaxSeq(i, c−1) is determined by the event delivery for cyclec - 1. Define the set of expected deliverable events froms at cyclec byΩ(s, c) = [MinSeq(s, c),Seq(s, c)] and the set of actual received eventsΠ(s, c). The actual deliverable events froms at cyclec can be filtered by Ω(s,c)∩Π(s,c), which excludes the late and out-of-order events.


#### 4.1.3. Total-Order Event Delivery

Total-order event delivery is the key mechanism in object state update to ensure that all replicas in the same group can reach the same state along the same path of state transfer, if no more event is received. By applying the dynamic cycle event delivery approach, the event delivery for one cycle is described in Algorithm1, whereE(c) stores the events from the consensus for cyclec and γ is the event delivery index in cycle c. γ is calculated by γ=Seq(e)+∑k=1Index(Sender(e))-1Seq(k,c)+1. (c,γ) and the calculation of γ ensure that the events inQd are sorted first by cycle number, then by sender index, and lastly by event sequence number, which can sort all events in the same order on all replicas.Algorithm 1:Event delivery.
1. For cyclec, 2. IfE(c) ≠ ∅, then 3.Qd←Qd∪{(c,γ,e(s,j))∣(c,e(s,j))∈E(c)} 4.  c← c + 1 5. Else, 6.  For∀s ∈ S, 7.   IfΠ(s, c) = Ω(s, c), then 8.Qt← Qt∪ {(c,γ,e(s,j))∣j∈Ω(s,c)} 9.   Else, 10.Qt← ∅ 11.    Consensus for (c, ⋃i=0S-1Ωs,c) 12.    End the loop 13.  IfQt≠∅, then 14.Qd← Qd∪ Qt 15.   c← c + 1In a run for cyclec, each replica firstly checks whether there are any events decided for the cycle from any consensus instance. If they exist, these events will be directly moved toQd for event handling by the application. Otherwise, Algorithm 1 checks the conditionΠ(s, c) =Ω(s, c) for each senders to ensure whether all expected deliverable events have been received. If there is an expected deliverable event not received in this cycle, then the replica will trigger a consensus instance to determine the event delivery for cyclec. Note that the cycle numberc will only be increased if the events of the cycle have been delivered.The proposed consensus algorithm is described in Algorithm2 and illustrated in Figure 8. The consensus request is composed of the cycle numberc and the sequence number of all the expected deliverable events inc from all senders. By receiving the consensus request, each replica proposes the actual deliverable events to the leader. If a replica does not receive an expected event, it will propose ⊥ for the event. On receiving all proposals, the leader then decides the event for each sender and each expected sequence number. If at least one replica proposes a non-⊥ and nonempty evente(s, j) forj ∈ Ω(s, c), thene(s, j) will be decided for sequence numberj froms. Otherwise, an empty event will be decided for the slot. After the events of all slots have been decided, the leader will broadcast the decision to all replicas, and they will move the decided events toE(c) for event delivery after receiving the decision. It is assumed that reliable point-to-point and multicast communication channels [29] are applied in the consensus protocol.Algorithm 2:Consensus.
1. Given (c, ⋃i=0S-1Ωs,c), 2.ri proposes: {(s,j,e(s,j))∣s∈s∧j∈Ω(s,c)∩Π(s,c)} 3. 4.rL decides: 5.   For eachs∈s and j∈Ω(s, c), 6.   // Proposals: the set of proposed events forc from all replicas; 7.     If∄e(s, j) ≠ ⊥ ∧ e(s, j) ∈ Proposals, then 8.e(s, j) ←Empty 9.D(c)←D(c)∪{(c,e(s,j))} 10. 11.rn applies the decision: E(c) ←D(c)Figure 8
Illustration of the consensus protocol.The complete algorithms of total-order event delivery, including event collection, event delivery, and consensus, can be found in AppendixA.


#### 4.1.4. Garbage Collection

To avoid buffer overflow, events which have been delivered to the application need to be removed fromQd to avoidQd from unlimited growth or even overflow. Due to asynchronous event handling, however, a replicari cannot safely remove a delivered event only with local information, because another replicarj later may request the removed event for a given cycle ifrj does not receive it. Thus, determining the removable events is a challenging problem.Learned from Algorithm1, since all events inQd can be uniquely identified by (c,γ), there exists a relation that maps each (c,γ) to a unique integer numberλ∈ [0,∞), called delivery sequence. Thus, events inQd can also be identified by (λ, e) and each (c,γ, e) and (λ, e) has a one-to-one mapping for the samee. LetQd be a sequenceeiei+1... ej...ek mapped toλiλi+1…λj…λk. It can be observed that the events which can be safely pruned satisfy the following characteristics.(1)
Ifej can be pruned fromQd, then all events beforeej can all be pruned fromQd.(2)
LetL = eiei+1...ej be the subsequence ofQd. IfL can be pruned fromQd on one replica, thenL can be pruned fromQd of all the replicas in groupg.(3)
Ifej can be pruned fromQd, thenλj≤λc, whereλc is the sequence of the last event handled by the application, returned by the functionLastApplied(Qd).(4)
Trailing rounds with empty events cannot be removed fromQd, since the events of these rounds may be used in consensus for deciding the value of late events.( 1 ) and (2) imply that there is a common latest applied eventecle such that all the events delivered beforeecle (includingecle) have been applied on all the replicas, whereas the events afterecle are undecidable. The delivery sequence ofecle is denoted byλcle. (3) implies thatλcle cannot exceedλc. (4) restricts the range of garbage collection. Thus, all the events beforeλcle, which are not empty trailing events, can be safely removed fromQd.Based on the above observation, a gossip protocol is devised to learnλcle by exchangingλc of all replicas for safely estimating the earliest removable event, which is described in Algorithm 3. In the protocol, each replica periodically sends itsλc to other replicas. A replica also caches the receivedλc. Based on the latest receivedλc from all replicas,λcle can be determined by the minimalλc. Then,λcle is adjusted to exclude the trailing empty events (Lines 12-16). Lastly, all the events beforeλcle are removed fromQd. In Algorithm 3,Λ caches the receivedλc’s from all replicas inG. For aλc fromri, ifλc is greater than the cached value ofri inΛ, the newλc can safely replace the existing one sinceλc from the same replica are monotonically nondecreasing.Algorithm 3:Garbage collection protocol.
1. On replicari: 2. Upon Timer TIMEOUT 3.λc ←LastApplied(Qd) 4.  Broadcastλc to all r∈G 5.  Reset Timer 6. 7. On replicarj: 8. Uponλc from ri∧λc>Λ(ri) 9.Λ←Λ∪{(ri,λc)} 10.  If|Λ|≥|G|, then 11.λcle←min⁡{λc∣(ri,λc)∈Λ} 12.   If (λcle,ecle) = Qd.last // last event in Qd 13.    Mapλcle to (c,γ) 14.    While∃(c,γ,e)∈Qd∧e=Empty 15.λcle←λcle-  |{(c,γ,e)∣(c,γ,e)∈Qd}| 16.c← c - 1 17.Qd← Qd ∖ {(λ,e)|λ≤λlce}


#### 4.1.5. Time Synchronization

In the fast event delivery approach, another key component is the synchronization of the start and end time of a cycle on event senders and recipients (all the replicas in group g) to minimize the chance of handling late events through consensus. Specifically, let ∆tn be the amount of network latency. Assume that the upper bound and lower bound of∆tn, denoted by∆TnL and∆TnH, can be estimated such that most∆tn falls within the range [∆TnL, ∆TnH]. Then, cycle length∆t can be determined by∆t = (∆TnH– ∆TnL).Lettstart,s be the start time of the first cycle for event senders designated by the replicas. Also, lettsend,s(n) be the send time of thenth event froms to the replicas.s firstly calculatestsend,s(1) bytsend,s(1)≤ tstart,s– ∆TnL. Then, in thenth cycle, it calculates the sending time of thenth event bytsend,s(n) =tsend,s(1) + (n – 1)·∆t. At the receiving end, all replicas are timed to receive thenth event froms attrecv,s(n)= tsend,s(n)+ ∆t = tstart,s+ n·∆t. To timely collect received events, event collection and event delivery can be run by different threads with different buffers (see Appendix A for details).A time server, such as a NTP server [31], can be deployed to the system for synchronizing the clock of event senders and recipients, which can improve the performance of the system.


### 4.2. Leader Election and Group Reconfiguration

Once the leader fails, a new leader is elected through leader election. Since both group reconfiguration and event handling rely on group leader, leader election has the highest priority in the three routines. It interrupts any ongoing group reconfiguration or event delivery process. The leader election criterion is replica age, which increases by one after each group reconfiguration. Based on the assumption that node failure rate increase with time, the new leader is the youngest replica in the group.Group reconfiguration adds new members for fault-tolerance. A group reconfiguration will be triggered once the group size is lower thann and recover group size ton + e. Group reconfiguration has higher priority than event delivery, so that new members can be quickly added to a group. After group reconfiguration, the leader will also notify all senders of the new configuration.In both leader election and group reconfiguration, the leader will decide the current states, namely,Qd,E, andG, and synchronize them to all replicas so that all replicas will load the same state after a leader election or a group reconfiguration, which is called state synchrony. For new replicas, the application state, the sequence of the last applied eventλc, the time of the first cyclet0, the start timetstart,s for each senders, and the sender setS are also synchronized from the leader for initialization. The detailed algorithms of leader election and group reconfiguration are in Appendix B.


## 4.1. Fast Event Delivery

Fast event delivery allows a replica to directly deliver a received event through a cycle-event mapping, if it can ensure that the same event will eventually be delivered by all replicas. Specifically, the timeline is divided into infinite cycles of length ∆t. From cyclec0, an event senders periodically broadcasts an event to the replicas in each cycle. Each event is identified by the sender ID and the sequence number. The sequence number of the first event at cyclec0 is 0. If there is no operation,s just broadcasts a no-op event. At the receiving end,c0 is also known by all replicas. Each replica delivers an event with sequence numberc - c0 froms for cyclec, which is called the event of cyclec. Events for cyclec from different senders will be ordered by sender ID. If a replica does not receive the event for cyclec froms, it will start an instance of consensus for the cycle. In the consensus, if a replica has received the event for cyclec, that event will be decided by the leader and delivered by all replicas. Otherwise, they will decide and deliver an empty event for cyclec. Events will be delivered to a queueQd first and then sent to the application from the queue for handling in sequence.The relation of cycle (ci), sender ID, event sequence number, delivery queue (Qd), and delivery sequence (λ) are illustrated in Figure 5. Specifically, inQd, the subscript of evente denotes the event sequence number which is equal to the event sending cycle. Thus, for the same cycle, the events inQd are sorted by the sender ID and mapped to the local index numbers inQd (i.e., the second member in the tuples ofQd).λ represents the global index of events delivered to the application, which will be introduced in Section 4.1.4.Figure 5
Relation of cycle (Ci), sender ID (Si), event sequence number, delivery queue (Qd), and delivery sequence (λ).Figure6 illustrates the fast event delivery process with one senders and three replicasr1,r2, andr3 in the replica groupg.s broadcasted four events,e1,e2,e3, ande4, at cyclesc1,c2,c3, andc4 tog. All replicas receivede1 at cyclec2 ande4 atc5. Only replicar1 receivede2 atc3. No replica receivede3 atc4, butr1 andr2 receivede3 atc5.r1,r2, andr3 delivere1 forc1. They then collectively decidee2 forc3 and an empty event forc4 through consensus. The first problem is how to decidec5 ande3. According to the cycle-event mapping principle (i.e., one-cycle-one-event), the replicas should only delivere4 forc5 and discarde3, leading to event loss. Before discussing the late events handling problem in detail, the settings and assumptions of the system will be introduced first.Figure 6
Illustration of fast event delivery.


### 4.1.1. Settings and Assumptions

For fault-tolerance, a replica group contains at leastn replicas. The minimal group sizen is determined by the content availability requirement [27] and the replica failure rate. To reduce replication overhead, each group also has an extra numbere of nodes for lazy repair [5]. Oncee + 1 replicas fail, new replicas will be added to recover the group size ton + e.In each replica group, there is one non-replica node monitoring the state of all replicas, called Rendezvous [30]. A Rendezvous uses timeout to determine the state of replicas and then broadcasts their states to all replicas. Monitoring replica state is implemented by exchanging heartbeat messages between a replica and a Rendezvous. If the Rendezvous does not receive one heartbeat message within a cycle, the replica is treated as failed and removed from the group. New replicas are also added by the Rendezvous, once the group size is smaller thann. Rendezvouses are reliable nodes, or called super-peers [19], since the existence of a group is determined by the Rendezvous. Once a Rendezvous fails, a new Rendezvous must be assigned to the replica group, which then rebuilds the replica group and recovers the object states from the cloud storage. By exchanging heartbeat messages, each replica learns the current membership of the groupg, denoted byG, which contains all live replicas of groupg. When the Rendezvous tells a replica that a member has failed or a new member is added, the replica will remove the member fromG or add the member intoG.The system is assumed to be live. The SMR model contains three types of group-wide activities: leader election, group reconfiguration, and consensus. The liveness assumption ensures that when an activity is needed, it will eventually succeed after a finite number of failures.Each replica group maintains a set of event senders. It is assumed that each event sender has an ID which is globally unique and sender IDs are comparable. Moreover, a replica group will append the join timestamp to sender IDs to distinguish a sender in two different joins of a sender set.Lets be the ID of an event sender,c be a cycle number of a replica groupg, andri be theith replica in groupg. Some important relations of event, event sender, event sequence number, and cycle number are defined in Table 1. Other notations used throughout the subsequent sections are listed in Table 1. Besides, event names are capitalized.Table 1
Notations.
Notations Descriptions Relations of event, event sequence number, sender, and cycle number  Seq(s, c) The sequence number of the event sent for cyclec from sender s  Seq(e) The sequence number of evente  e(s, j) The event of sequence numberj sent from s  Deliver(e, c) Returntrue if event e is deliverable at cycle c. Otherwise, return false  DeliverCycle(e) Return the cycle in which evente is delivered. If e has not been delivered, return ⊥.  Receive(e, c) Returntrue if e has been received at cycle c. Otherwise, return false.  ReceiveCycle(e) Return the cycle in which evente is received. If e has not been received, return ⊥.  Event of cycle The event sent by a sender for a cycle is called the event of the cycle. Given the first event sent from senders at cycle c0. The event of cycle c satisfies Seq(e) = Seq(s, c) = (c - c0).  Cycle open / close If a replicari has delivered the events for cycle c and moved to the next cycle c + 1, then c is closed and c + 1 is still open to ri.  Other notations  r i Replicai  r L Group leader  G The set of group members  S The set of event senders  U Set of update recipients  g Replica groupg  s Senders∈S  Index(s) The index ofs in S sorted by sender ID  Sender(e) The sender of evente  c Cycle numberc  ∆t Cycle length  t start,s The start time of the first cycle fors  t send,s(n) The time to send thenth event from s  t recv,s(n) The time to receive thenth event sent from s  t now Current time  E / E(c) The set of decided events / decided events ofc  Q d Delivery queue, containing the sorted events to be delivered to the application in sequence  (c,γ, e) The evente delivered for cycle c with local index γ in Qd  (λ, e) The delivery sequenceλ of event e in Qd, one-to-one mapped onto (c,γ, e) for the given e.  Ω(s, c) The set of expected events which can be delivered toQd (called deliverable events) from s at cycle c  Π(s, c) The set of actual received events froms at cycle c


### 4.1.2. Late Event Handling

An event is late if the event of cyclec is received afterc on all replicas. Formally, a late evente satisfiesSeq(e) =Seq(s, c) ∧ReceiveCycle(e)> c onri ∈ G andSeq(e) =Seq(s, c) ∧ (ReceiveCycle(e)> c∨ReceiveCycle(e) = ⊥) onrj ∈ G ∖ {ri}. For example,e3 in Figure 6 is a late event.To ensure the agreement of cycle event delivery on all replicas, a late event can be simply discarded, since any event can be re-sent by a client with a new sequence number if the client does not receive the reply for the event for a period. However, if a sender’s clock is temporarily out-of-sync with the replicas’ clock or a large sending delay is experienced, a large number of events could be discarded and need to be re-send, as shown in Figure7.Figure 7
An extreme scenario of late event discard.To address the late event handling problem, a dynamic cycle event delivery approach is proposed, which includes two conditions for late event delivery. The purpose of the approach is to minimize the number of event discards, and meanwhile each replica can decide the delivery of late events with only local information. Below are the conditions of late event delivery. In short, only late and out-of-order events will be discarded.(1)
At cyclec, all events from senders with sequence number less thanc will be deliverable. Formally, ∀e(s, j1),e(s, j2), …,e(s, jn), (1)Receivees,j1,c∧⋯Receivees,jn,c∧DeliverCyclees,j1=⋯=DeliverCyclees,jn=⊥∧seqs,j1<seqs,c∧⋯seqs,jn<seqs,c→Deliveres,j1,c∧⋯∧Deliveres,jn,c.(2)
At cyclec, an event will be nondeliverable, if one of its subsequent events has been delivered beforec. Such event is a late and out-of-order event. Formally, ∀e(s, j),(2)Receivees,j,c∧∃es,k∧k>j∧DeliverCyclees,j=⊥∧DeliverCyclees,k<c→¬Deliveres,j,c.To implement the dynamic cycle event delivery approach, the lowest deliverable sequence number from any sender needs to be determined first for all cycles. Specifically, at cyclec, letMinSeq(s, c) be the lowest sequence number of all undelivered events from senders andMinSeq(s, c) ≤seq(s, c). Also, letMaxSeq(s, c) be the sequence number of the last delivered nonempty event in cyclec froms. Then,MinSeq(s, c) =MaxSeq(s, c−1) +1, whereMaxSeq(i, c−1) is determined by the event delivery for cyclec - 1. Define the set of expected deliverable events froms at cyclec byΩ(s, c) = [MinSeq(s, c),Seq(s, c)] and the set of actual received eventsΠ(s, c). The actual deliverable events froms at cyclec can be filtered by Ω(s,c)∩Π(s,c), which excludes the late and out-of-order events.


### 4.1.3. Total-Order Event Delivery

Total-order event delivery is the key mechanism in object state update to ensure that all replicas in the same group can reach the same state along the same path of state transfer, if no more event is received. By applying the dynamic cycle event delivery approach, the event delivery for one cycle is described in Algorithm1, whereE(c) stores the events from the consensus for cyclec and γ is the event delivery index in cycle c. γ is calculated by γ=Seq(e)+∑k=1Index(Sender(e))-1Seq(k,c)+1. (c,γ) and the calculation of γ ensure that the events inQd are sorted first by cycle number, then by sender index, and lastly by event sequence number, which can sort all events in the same order on all replicas.Algorithm 1:Event delivery.
1. For cyclec, 2. IfE(c) ≠ ∅, then 3.Qd←Qd∪{(c,γ,e(s,j))∣(c,e(s,j))∈E(c)} 4.  c← c + 1 5. Else, 6.  For∀s ∈ S, 7.   IfΠ(s, c) = Ω(s, c), then 8.Qt← Qt∪ {(c,γ,e(s,j))∣j∈Ω(s,c)} 9.   Else, 10.Qt← ∅ 11.    Consensus for (c, ⋃i=0S-1Ωs,c) 12.    End the loop 13.  IfQt≠∅, then 14.Qd← Qd∪ Qt 15.   c← c + 1In a run for cyclec, each replica firstly checks whether there are any events decided for the cycle from any consensus instance. If they exist, these events will be directly moved toQd for event handling by the application. Otherwise, Algorithm 1 checks the conditionΠ(s, c) =Ω(s, c) for each senders to ensure whether all expected deliverable events have been received. If there is an expected deliverable event not received in this cycle, then the replica will trigger a consensus instance to determine the event delivery for cyclec. Note that the cycle numberc will only be increased if the events of the cycle have been delivered.The proposed consensus algorithm is described in Algorithm2 and illustrated in Figure 8. The consensus request is composed of the cycle numberc and the sequence number of all the expected deliverable events inc from all senders. By receiving the consensus request, each replica proposes the actual deliverable events to the leader. If a replica does not receive an expected event, it will propose ⊥ for the event. On receiving all proposals, the leader then decides the event for each sender and each expected sequence number. If at least one replica proposes a non-⊥ and nonempty evente(s, j) forj ∈ Ω(s, c), thene(s, j) will be decided for sequence numberj froms. Otherwise, an empty event will be decided for the slot. After the events of all slots have been decided, the leader will broadcast the decision to all replicas, and they will move the decided events toE(c) for event delivery after receiving the decision. It is assumed that reliable point-to-point and multicast communication channels [29] are applied in the consensus protocol.Algorithm 2:Consensus.
1. Given (c, ⋃i=0S-1Ωs,c), 2.ri proposes: {(s,j,e(s,j))∣s∈s∧j∈Ω(s,c)∩Π(s,c)} 3. 4.rL decides: 5.   For eachs∈s and j∈Ω(s, c), 6.   // Proposals: the set of proposed events forc from all replicas; 7.     If∄e(s, j) ≠ ⊥ ∧ e(s, j) ∈ Proposals, then 8.e(s, j) ←Empty 9.D(c)←D(c)∪{(c,e(s,j))} 10. 11.rn applies the decision: E(c) ←D(c)Figure 8
Illustration of the consensus protocol.The complete algorithms of total-order event delivery, including event collection, event delivery, and consensus, can be found in AppendixA.


### 4.1.4. Garbage Collection

To avoid buffer overflow, events which have been delivered to the application need to be removed fromQd to avoidQd from unlimited growth or even overflow. Due to asynchronous event handling, however, a replicari cannot safely remove a delivered event only with local information, because another replicarj later may request the removed event for a given cycle ifrj does not receive it. Thus, determining the removable events is a challenging problem.Learned from Algorithm1, since all events inQd can be uniquely identified by (c,γ), there exists a relation that maps each (c,γ) to a unique integer numberλ∈ [0,∞), called delivery sequence. Thus, events inQd can also be identified by (λ, e) and each (c,γ, e) and (λ, e) has a one-to-one mapping for the samee. LetQd be a sequenceeiei+1... ej...ek mapped toλiλi+1…λj…λk. It can be observed that the events which can be safely pruned satisfy the following characteristics.(1)
Ifej can be pruned fromQd, then all events beforeej can all be pruned fromQd.(2)
LetL = eiei+1...ej be the subsequence ofQd. IfL can be pruned fromQd on one replica, thenL can be pruned fromQd of all the replicas in groupg.(3)
Ifej can be pruned fromQd, thenλj≤λc, whereλc is the sequence of the last event handled by the application, returned by the functionLastApplied(Qd).(4)
Trailing rounds with empty events cannot be removed fromQd, since the events of these rounds may be used in consensus for deciding the value of late events.( 1 ) and (2) imply that there is a common latest applied eventecle such that all the events delivered beforeecle (includingecle) have been applied on all the replicas, whereas the events afterecle are undecidable. The delivery sequence ofecle is denoted byλcle. (3) implies thatλcle cannot exceedλc. (4) restricts the range of garbage collection. Thus, all the events beforeλcle, which are not empty trailing events, can be safely removed fromQd.Based on the above observation, a gossip protocol is devised to learnλcle by exchangingλc of all replicas for safely estimating the earliest removable event, which is described in Algorithm 3. In the protocol, each replica periodically sends itsλc to other replicas. A replica also caches the receivedλc. Based on the latest receivedλc from all replicas,λcle can be determined by the minimalλc. Then,λcle is adjusted to exclude the trailing empty events (Lines 12-16). Lastly, all the events beforeλcle are removed fromQd. In Algorithm 3,Λ caches the receivedλc’s from all replicas inG. For aλc fromri, ifλc is greater than the cached value ofri inΛ, the newλc can safely replace the existing one sinceλc from the same replica are monotonically nondecreasing.Algorithm 3:Garbage collection protocol.
1. On replicari: 2. Upon Timer TIMEOUT 3.λc ←LastApplied(Qd) 4.  Broadcastλc to all r∈G 5.  Reset Timer 6. 7. On replicarj: 8. Uponλc from ri∧λc>Λ(ri) 9.Λ←Λ∪{(ri,λc)} 10.  If|Λ|≥|G|, then 11.λcle←min⁡{λc∣(ri,λc)∈Λ} 12.   If (λcle,ecle) = Qd.last // last event in Qd 13.    Mapλcle to (c,γ) 14.    While∃(c,γ,e)∈Qd∧e=Empty 15.λcle←λcle-  |{(c,γ,e)∣(c,γ,e)∈Qd}| 16.c← c - 1 17.Qd← Qd ∖ {(λ,e)|λ≤λlce}


### 4.1.5. Time Synchronization

In the fast event delivery approach, another key component is the synchronization of the start and end time of a cycle on event senders and recipients (all the replicas in group g) to minimize the chance of handling late events through consensus. Specifically, let ∆tn be the amount of network latency. Assume that the upper bound and lower bound of∆tn, denoted by∆TnL and∆TnH, can be estimated such that most∆tn falls within the range [∆TnL, ∆TnH]. Then, cycle length∆t can be determined by∆t = (∆TnH– ∆TnL).Lettstart,s be the start time of the first cycle for event senders designated by the replicas. Also, lettsend,s(n) be the send time of thenth event froms to the replicas.s firstly calculatestsend,s(1) bytsend,s(1)≤ tstart,s– ∆TnL. Then, in thenth cycle, it calculates the sending time of thenth event bytsend,s(n) =tsend,s(1) + (n – 1)·∆t. At the receiving end, all replicas are timed to receive thenth event froms attrecv,s(n)= tsend,s(n)+ ∆t = tstart,s+ n·∆t. To timely collect received events, event collection and event delivery can be run by different threads with different buffers (see Appendix A for details).A time server, such as a NTP server [31], can be deployed to the system for synchronizing the clock of event senders and recipients, which can improve the performance of the system.


## 4.1.1. Settings and Assumptions

For fault-tolerance, a replica group contains at leastn replicas. The minimal group sizen is determined by the content availability requirement [27] and the replica failure rate. To reduce replication overhead, each group also has an extra numbere of nodes for lazy repair [5]. Oncee + 1 replicas fail, new replicas will be added to recover the group size ton + e.In each replica group, there is one non-replica node monitoring the state of all replicas, called Rendezvous [30]. A Rendezvous uses timeout to determine the state of replicas and then broadcasts their states to all replicas. Monitoring replica state is implemented by exchanging heartbeat messages between a replica and a Rendezvous. If the Rendezvous does not receive one heartbeat message within a cycle, the replica is treated as failed and removed from the group. New replicas are also added by the Rendezvous, once the group size is smaller thann. Rendezvouses are reliable nodes, or called super-peers [19], since the existence of a group is determined by the Rendezvous. Once a Rendezvous fails, a new Rendezvous must be assigned to the replica group, which then rebuilds the replica group and recovers the object states from the cloud storage. By exchanging heartbeat messages, each replica learns the current membership of the groupg, denoted byG, which contains all live replicas of groupg. When the Rendezvous tells a replica that a member has failed or a new member is added, the replica will remove the member fromG or add the member intoG.The system is assumed to be live. The SMR model contains three types of group-wide activities: leader election, group reconfiguration, and consensus. The liveness assumption ensures that when an activity is needed, it will eventually succeed after a finite number of failures.Each replica group maintains a set of event senders. It is assumed that each event sender has an ID which is globally unique and sender IDs are comparable. Moreover, a replica group will append the join timestamp to sender IDs to distinguish a sender in two different joins of a sender set.Lets be the ID of an event sender,c be a cycle number of a replica groupg, andri be theith replica in groupg. Some important relations of event, event sender, event sequence number, and cycle number are defined in Table 1. Other notations used throughout the subsequent sections are listed in Table 1. Besides, event names are capitalized.Table 1
Notations.
Notations Descriptions Relations of event, event sequence number, sender, and cycle number  Seq(s, c) The sequence number of the event sent for cyclec from sender s  Seq(e) The sequence number of evente  e(s, j) The event of sequence numberj sent from s  Deliver(e, c) Returntrue if event e is deliverable at cycle c. Otherwise, return false  DeliverCycle(e) Return the cycle in which evente is delivered. If e has not been delivered, return ⊥.  Receive(e, c) Returntrue if e has been received at cycle c. Otherwise, return false.  ReceiveCycle(e) Return the cycle in which evente is received. If e has not been received, return ⊥.  Event of cycle The event sent by a sender for a cycle is called the event of the cycle. Given the first event sent from senders at cycle c0. The event of cycle c satisfies Seq(e) = Seq(s, c) = (c - c0).  Cycle open / close If a replicari has delivered the events for cycle c and moved to the next cycle c + 1, then c is closed and c + 1 is still open to ri.  Other notations  r i Replicai  r L Group leader  G The set of group members  S The set of event senders  U Set of update recipients  g Replica groupg  s Senders∈S  Index(s) The index ofs in S sorted by sender ID  Sender(e) The sender of evente  c Cycle numberc  ∆t Cycle length  t start,s The start time of the first cycle fors  t send,s(n) The time to send thenth event from s  t recv,s(n) The time to receive thenth event sent from s  t now Current time  E / E(c) The set of decided events / decided events ofc  Q d Delivery queue, containing the sorted events to be delivered to the application in sequence  (c,γ, e) The evente delivered for cycle c with local index γ in Qd  (λ, e) The delivery sequenceλ of event e in Qd, one-to-one mapped onto (c,γ, e) for the given e.  Ω(s, c) The set of expected events which can be delivered toQd (called deliverable events) from s at cycle c  Π(s, c) The set of actual received events froms at cycle c


## 4.1.2. Late Event Handling

An event is late if the event of cyclec is received afterc on all replicas. Formally, a late evente satisfiesSeq(e) =Seq(s, c) ∧ReceiveCycle(e)> c onri ∈ G andSeq(e) =Seq(s, c) ∧ (ReceiveCycle(e)> c∨ReceiveCycle(e) = ⊥) onrj ∈ G ∖ {ri}. For example,e3 in Figure 6 is a late event.To ensure the agreement of cycle event delivery on all replicas, a late event can be simply discarded, since any event can be re-sent by a client with a new sequence number if the client does not receive the reply for the event for a period. However, if a sender’s clock is temporarily out-of-sync with the replicas’ clock or a large sending delay is experienced, a large number of events could be discarded and need to be re-send, as shown in Figure7.Figure 7
An extreme scenario of late event discard.To address the late event handling problem, a dynamic cycle event delivery approach is proposed, which includes two conditions for late event delivery. The purpose of the approach is to minimize the number of event discards, and meanwhile each replica can decide the delivery of late events with only local information. Below are the conditions of late event delivery. In short, only late and out-of-order events will be discarded.(1)
At cyclec, all events from senders with sequence number less thanc will be deliverable. Formally, ∀e(s, j1),e(s, j2), …,e(s, jn), (1)Receivees,j1,c∧⋯Receivees,jn,c∧DeliverCyclees,j1=⋯=DeliverCyclees,jn=⊥∧seqs,j1<seqs,c∧⋯seqs,jn<seqs,c→Deliveres,j1,c∧⋯∧Deliveres,jn,c.(2)
At cyclec, an event will be nondeliverable, if one of its subsequent events has been delivered beforec. Such event is a late and out-of-order event. Formally, ∀e(s, j),(2)Receivees,j,c∧∃es,k∧k>j∧DeliverCyclees,j=⊥∧DeliverCyclees,k<c→¬Deliveres,j,c.To implement the dynamic cycle event delivery approach, the lowest deliverable sequence number from any sender needs to be determined first for all cycles. Specifically, at cyclec, letMinSeq(s, c) be the lowest sequence number of all undelivered events from senders andMinSeq(s, c) ≤seq(s, c). Also, letMaxSeq(s, c) be the sequence number of the last delivered nonempty event in cyclec froms. Then,MinSeq(s, c) =MaxSeq(s, c−1) +1, whereMaxSeq(i, c−1) is determined by the event delivery for cyclec - 1. Define the set of expected deliverable events froms at cyclec byΩ(s, c) = [MinSeq(s, c),Seq(s, c)] and the set of actual received eventsΠ(s, c). The actual deliverable events froms at cyclec can be filtered by Ω(s,c)∩Π(s,c), which excludes the late and out-of-order events.


## 4.1.3. Total-Order Event Delivery

Total-order event delivery is the key mechanism in object state update to ensure that all replicas in the same group can reach the same state along the same path of state transfer, if no more event is received. By applying the dynamic cycle event delivery approach, the event delivery for one cycle is described in Algorithm1, whereE(c) stores the events from the consensus for cyclec and γ is the event delivery index in cycle c. γ is calculated by γ=Seq(e)+∑k=1Index(Sender(e))-1Seq(k,c)+1. (c,γ) and the calculation of γ ensure that the events inQd are sorted first by cycle number, then by sender index, and lastly by event sequence number, which can sort all events in the same order on all replicas.Algorithm 1:Event delivery.
1. For cyclec, 2. IfE(c) ≠ ∅, then 3.Qd←Qd∪{(c,γ,e(s,j))∣(c,e(s,j))∈E(c)} 4.  c← c + 1 5. Else, 6.  For∀s ∈ S, 7.   IfΠ(s, c) = Ω(s, c), then 8.Qt← Qt∪ {(c,γ,e(s,j))∣j∈Ω(s,c)} 9.   Else, 10.Qt← ∅ 11.    Consensus for (c, ⋃i=0S-1Ωs,c) 12.    End the loop 13.  IfQt≠∅, then 14.Qd← Qd∪ Qt 15.   c← c + 1In a run for cyclec, each replica firstly checks whether there are any events decided for the cycle from any consensus instance. If they exist, these events will be directly moved toQd for event handling by the application. Otherwise, Algorithm 1 checks the conditionΠ(s, c) =Ω(s, c) for each senders to ensure whether all expected deliverable events have been received. If there is an expected deliverable event not received in this cycle, then the replica will trigger a consensus instance to determine the event delivery for cyclec. Note that the cycle numberc will only be increased if the events of the cycle have been delivered.The proposed consensus algorithm is described in Algorithm2 and illustrated in Figure 8. The consensus request is composed of the cycle numberc and the sequence number of all the expected deliverable events inc from all senders. By receiving the consensus request, each replica proposes the actual deliverable events to the leader. If a replica does not receive an expected event, it will propose ⊥ for the event. On receiving all proposals, the leader then decides the event for each sender and each expected sequence number. If at least one replica proposes a non-⊥ and nonempty evente(s, j) forj ∈ Ω(s, c), thene(s, j) will be decided for sequence numberj froms. Otherwise, an empty event will be decided for the slot. After the events of all slots have been decided, the leader will broadcast the decision to all replicas, and they will move the decided events toE(c) for event delivery after receiving the decision. It is assumed that reliable point-to-point and multicast communication channels [29] are applied in the consensus protocol.Algorithm 2:Consensus.
1. Given (c, ⋃i=0S-1Ωs,c), 2.ri proposes: {(s,j,e(s,j))∣s∈s∧j∈Ω(s,c)∩Π(s,c)} 3. 4.rL decides: 5.   For eachs∈s and j∈Ω(s, c), 6.   // Proposals: the set of proposed events forc from all replicas; 7.     If∄e(s, j) ≠ ⊥ ∧ e(s, j) ∈ Proposals, then 8.e(s, j) ←Empty 9.D(c)←D(c)∪{(c,e(s,j))} 10. 11.rn applies the decision: E(c) ←D(c)Figure 8
Illustration of the consensus protocol.The complete algorithms of total-order event delivery, including event collection, event delivery, and consensus, can be found in AppendixA.


## 4.1.4. Garbage Collection

To avoid buffer overflow, events which have been delivered to the application need to be removed fromQd to avoidQd from unlimited growth or even overflow. Due to asynchronous event handling, however, a replicari cannot safely remove a delivered event only with local information, because another replicarj later may request the removed event for a given cycle ifrj does not receive it. Thus, determining the removable events is a challenging problem.Learned from Algorithm1, since all events inQd can be uniquely identified by (c,γ), there exists a relation that maps each (c,γ) to a unique integer numberλ∈ [0,∞), called delivery sequence. Thus, events inQd can also be identified by (λ, e) and each (c,γ, e) and (λ, e) has a one-to-one mapping for the samee. LetQd be a sequenceeiei+1... ej...ek mapped toλiλi+1…λj…λk. It can be observed that the events which can be safely pruned satisfy the following characteristics.(1)
Ifej can be pruned fromQd, then all events beforeej can all be pruned fromQd.(2)
LetL = eiei+1...ej be the subsequence ofQd. IfL can be pruned fromQd on one replica, thenL can be pruned fromQd of all the replicas in groupg.(3)
Ifej can be pruned fromQd, thenλj≤λc, whereλc is the sequence of the last event handled by the application, returned by the functionLastApplied(Qd).(4)
Trailing rounds with empty events cannot be removed fromQd, since the events of these rounds may be used in consensus for deciding the value of late events.( 1 ) and (2) imply that there is a common latest applied eventecle such that all the events delivered beforeecle (includingecle) have been applied on all the replicas, whereas the events afterecle are undecidable. The delivery sequence ofecle is denoted byλcle. (3) implies thatλcle cannot exceedλc. (4) restricts the range of garbage collection. Thus, all the events beforeλcle, which are not empty trailing events, can be safely removed fromQd.Based on the above observation, a gossip protocol is devised to learnλcle by exchangingλc of all replicas for safely estimating the earliest removable event, which is described in Algorithm 3. In the protocol, each replica periodically sends itsλc to other replicas. A replica also caches the receivedλc. Based on the latest receivedλc from all replicas,λcle can be determined by the minimalλc. Then,λcle is adjusted to exclude the trailing empty events (Lines 12-16). Lastly, all the events beforeλcle are removed fromQd. In Algorithm 3,Λ caches the receivedλc’s from all replicas inG. For aλc fromri, ifλc is greater than the cached value ofri inΛ, the newλc can safely replace the existing one sinceλc from the same replica are monotonically nondecreasing.Algorithm 3:Garbage collection protocol.
1. On replicari: 2. Upon Timer TIMEOUT 3.λc ←LastApplied(Qd) 4.  Broadcastλc to all r∈G 5.  Reset Timer 6. 7. On replicarj: 8. Uponλc from ri∧λc>Λ(ri) 9.Λ←Λ∪{(ri,λc)} 10.  If|Λ|≥|G|, then 11.λcle←min⁡{λc∣(ri,λc)∈Λ} 12.   If (λcle,ecle) = Qd.last // last event in Qd 13.    Mapλcle to (c,γ) 14.    While∃(c,γ,e)∈Qd∧e=Empty 15.λcle←λcle-  |{(c,γ,e)∣(c,γ,e)∈Qd}| 16.c← c - 1 17.Qd← Qd ∖ {(λ,e)|λ≤λlce}


## 4.1.5. Time Synchronization

In the fast event delivery approach, another key component is the synchronization of the start and end time of a cycle on event senders and recipients (all the replicas in group g) to minimize the chance of handling late events through consensus. Specifically, let ∆tn be the amount of network latency. Assume that the upper bound and lower bound of∆tn, denoted by∆TnL and∆TnH, can be estimated such that most∆tn falls within the range [∆TnL, ∆TnH]. Then, cycle length∆t can be determined by∆t = (∆TnH– ∆TnL).Lettstart,s be the start time of the first cycle for event senders designated by the replicas. Also, lettsend,s(n) be the send time of thenth event froms to the replicas.s firstly calculatestsend,s(1) bytsend,s(1)≤ tstart,s– ∆TnL. Then, in thenth cycle, it calculates the sending time of thenth event bytsend,s(n) =tsend,s(1) + (n – 1)·∆t. At the receiving end, all replicas are timed to receive thenth event froms attrecv,s(n)= tsend,s(n)+ ∆t = tstart,s+ n·∆t. To timely collect received events, event collection and event delivery can be run by different threads with different buffers (see Appendix A for details).A time server, such as a NTP server [31], can be deployed to the system for synchronizing the clock of event senders and recipients, which can improve the performance of the system.


## 4.2. Leader Election and Group Reconfiguration

Once the leader fails, a new leader is elected through leader election. Since both group reconfiguration and event handling rely on group leader, leader election has the highest priority in the three routines. It interrupts any ongoing group reconfiguration or event delivery process. The leader election criterion is replica age, which increases by one after each group reconfiguration. Based on the assumption that node failure rate increase with time, the new leader is the youngest replica in the group.Group reconfiguration adds new members for fault-tolerance. A group reconfiguration will be triggered once the group size is lower thann and recover group size ton + e. Group reconfiguration has higher priority than event delivery, so that new members can be quickly added to a group. After group reconfiguration, the leader will also notify all senders of the new configuration.In both leader election and group reconfiguration, the leader will decide the current states, namely,Qd,E, andG, and synchronize them to all replicas so that all replicas will load the same state after a leader election or a group reconfiguration, which is called state synchrony. For new replicas, the application state, the sequence of the last applied eventλc, the time of the first cyclet0, the start timetstart,s for each senders, and the sender setS are also synchronized from the leader for initialization. The detailed algorithms of leader election and group reconfiguration are in Appendix B.


## 5. Virtual World Interaction

Virtual world interaction describes how users manipulate the state of virtual objects and perceive the state change in a shared simulated environment. Following the definition, a virtual world interaction includes two steps. First, a user modifies the state of an object through operations. Second, the new object state is synchronized to other interested users. This section extends the proposed event delivery approach for supporting interactions in Virtual Net.


### 5.1. Flow of Events and Updates

An object is replicated on multiple hosts (i.e., clients and mesh computers) if multiple users operate the same object. To facilitate object state consistency management in interaction, the copies of objects are classified into authoritative copies and nonauthoritative copies. Each object can only have one authoritative copy but multiple nonauthoritative copies. An authoritative copy is maintained by one mesh computer, e.g., the object owner’s. The nonauthoritative copies are maintained by the clients and the mesh computer of other interested users for fault-tolerance. Interest management has been intensively studied in [8] and thus is not discussed in this paper. It is only assumed that a user’s interest scope is determined by his/her perception range in a virtual world, as illustrated in Figure 10.By distinguishing authoritative copies from nonauthoritative copies, object state management is simplified to managing the state of an authoritative copy and synchronizing the updated state from the authoritative copy to nonauthoritative copies. For managing the authoritative copy, since the data is replicated to multiple nodes in a mesh computer, the fast event delivery approach is applied for maintaining the same state among these replicas.From the perspective of an authoritative copy, an interaction includes receiving the event from one client, handling the event after it is delivered to the application, and multicasting the updated state to all interested hosts. Figure9 illustrates the flow of events and updated states. The events of an object are only sent from the clients to the mesh computer which maintains the authoritative copy of the object, while updated states are broadcast by the mesh computers to all the nonauthoritative copies. To support interaction, each mesh computer maintains two sets: the event sender setS and the update recipient setU.Figure 9
The flow of events and updated states in virtual world interaction.Figure 10
Neighbor change: (a) neighbor join; (b) neighbor leave.
(a) (b)


### 5.2. Neighbors

To reduce overhead, each user only communicates with a limited number of peer users, called the neighbors. Due to user mobility, a user’s neighbor may be frequently changed. A neighbor join happens when another user enters the perception range of a user. Likewise, a neighbor leave happens when a neighbor moves out of a user’s perception range. For neighbour change, the key problem is to determine the same cycle of neighbor change on all replicas for their agreement on the cycle events. The join/leave cycle can be simply synchronized through consensus. However, high neighbor dynamics will increase the number consensus, resulting in high communication overhead and high interaction latency.To apply the fast event delivery approach in neighbour change, the connectivity maintenance approaches of mutual notification [6] are employed. Specifically, two types of neighbour are introduced:(1)
Perception neighbor set (Np): the set of users and their virtual objects appearing in the perception range of a user.(2)
Connectivity neighbor set (Nc): the set of users logically connected to the user.Assume each user maintains a set of connectivity neighborsNc. How to achieve it in a P2P virtual world can be found in [6]. A user (calledUser i) periodically exchanges its perception neighbor setNp with the connectivity neighbors. Once a connectivity neighbor finds that another user should/should not be inNp, it will notifyUser i. To facilitate description, some abstract functions are introduced:(i)
Multicast(e, y, g): evente with sequence numbery is sent to all replicas of groupg.(ii)
Handle(e): evente, which has been delivered toQd, is handled by the application.(iii)
Time(t): set the timer tot, which will trigger a timeout event att.(iv)
EVENT← c: assign contentc to event EVENT.


### 5.3. Neighbor Join

SupposeUser j is one of the connectivity neighbors ofUser i.User j discovers that another userUser k is in the perception range but not in theNp ofUser i; it will notifyUser i for adding the new neighbor with the following procedure. To distinguish clients from mesh computers, letpi be the client ofUser i andri be the replica of groupgi (i.e., the mesh computer ofUser i), the same forpj andpk.Step 1.
p j Multicast(ADD_NEIGHBOR ← (pk,Gk),y,gi).Step 2.
r i Handle(ADD_NEIGHBOR) for cyclec, ∀ri ∈ Gi.(a)
ri modifiesS← S∪  {pk},U← U∪  {pk,Gk}.(b)
ri calculateststart,k =trecv,j(y) +n·∆t andtrecv,k(1) =tstart,k + ∆t.(c)
ri calculates cycleck = ⌈(trecv,k(1) –tnow) / ∆t⌉ +c.(d)
ri Time(ck) for receiving the first event frompk.(e)
ri sends (HANDSHAKE ← (tstart,k,Gi)) topk.Step 3.
p k addsGi to the recipient list.Step 4.
pk Calculatetsend,k(1) ← tstart,k  − ∆TnL.Step 5.
pk Time(tsend,k(1)).Step 6.
pk Multicast(e, 0,gi) attsend,k(1).Step 7.
p k Time(tstart,k+ ∆t) for the next event.Step 8.
r i receives EVENT atck.Step 9.
r i delivers EVENT forck.The neighbor join process is illustrated in Figure10(a). First, the connectivity neighborpj sends the ADD_NEIGHBOR event to all replicas ingi for adding new neighborpk. Then, each replicari modifies the event sender and the update set recipient set, calculates the first event start time for event sending and receiving, and notifies the new neighborpk. The clientpk is timed to send the first event attrecv,j(y)+ n·∆t−∆TnL (wheren, ∆t, and∆TnL are preconfigured). Meanwhile, the replicas ofgi are waiting for the event of the first cycleck attrecv,k. Since the start timetstart,k and the first event sequence numberj0= 0 are known to both communication ends, they can individually calculate the time of subsequent event sending and receiving. At last, clientpi learns the new neighbor through the update fromgi and renders it toUser i.


### 5.4. Neighbor Leave

The procedure of neighbor leave is similar to but simpler than the neighbor join procedure. SupposeUser j is one of the connectivity neighbors ofUser i. Whenci discovers that another userUser k is out of the perception range but still inNp ofUser i, it will notifyUser i with the following procedure.Step 1.
p j Multicast(RM_NEIGHBOR ← (k), y, gi).Step 2.
r i Handle(RM_NEIGHBOR) for cyclec, ∀ri ∈ Gi.(a)
ri modifies S ← S ∖ {pk}, U ← U ∖ {pk,Gk} for cycle c + 1.The neighbor leave process is illustrated in Figure10(b). The connectivity neighborpj sends the RM_NEIGHBOR event to all replicas ingi for removing the neighborpk, which can then removepk andGk in both the event sender set and the event recipient set for cyclec + 1. Through the update fromgi, then clientpi learns the leave of neighborpk and removespk from display.


## 5.1. Flow of Events and Updates

An object is replicated on multiple hosts (i.e., clients and mesh computers) if multiple users operate the same object. To facilitate object state consistency management in interaction, the copies of objects are classified into authoritative copies and nonauthoritative copies. Each object can only have one authoritative copy but multiple nonauthoritative copies. An authoritative copy is maintained by one mesh computer, e.g., the object owner’s. The nonauthoritative copies are maintained by the clients and the mesh computer of other interested users for fault-tolerance. Interest management has been intensively studied in [8] and thus is not discussed in this paper. It is only assumed that a user’s interest scope is determined by his/her perception range in a virtual world, as illustrated in Figure 10.By distinguishing authoritative copies from nonauthoritative copies, object state management is simplified to managing the state of an authoritative copy and synchronizing the updated state from the authoritative copy to nonauthoritative copies. For managing the authoritative copy, since the data is replicated to multiple nodes in a mesh computer, the fast event delivery approach is applied for maintaining the same state among these replicas.From the perspective of an authoritative copy, an interaction includes receiving the event from one client, handling the event after it is delivered to the application, and multicasting the updated state to all interested hosts. Figure9 illustrates the flow of events and updated states. The events of an object are only sent from the clients to the mesh computer which maintains the authoritative copy of the object, while updated states are broadcast by the mesh computers to all the nonauthoritative copies. To support interaction, each mesh computer maintains two sets: the event sender setS and the update recipient setU.Figure 9
The flow of events and updated states in virtual world interaction.Figure 10
Neighbor change: (a) neighbor join; (b) neighbor leave.
(a) (b)


## 5.2. Neighbors

To reduce overhead, each user only communicates with a limited number of peer users, called the neighbors. Due to user mobility, a user’s neighbor may be frequently changed. A neighbor join happens when another user enters the perception range of a user. Likewise, a neighbor leave happens when a neighbor moves out of a user’s perception range. For neighbour change, the key problem is to determine the same cycle of neighbor change on all replicas for their agreement on the cycle events. The join/leave cycle can be simply synchronized through consensus. However, high neighbor dynamics will increase the number consensus, resulting in high communication overhead and high interaction latency.To apply the fast event delivery approach in neighbour change, the connectivity maintenance approaches of mutual notification [6] are employed. Specifically, two types of neighbour are introduced:(1)
Perception neighbor set (Np): the set of users and their virtual objects appearing in the perception range of a user.(2)
Connectivity neighbor set (Nc): the set of users logically connected to the user.Assume each user maintains a set of connectivity neighborsNc. How to achieve it in a P2P virtual world can be found in [6]. A user (calledUser i) periodically exchanges its perception neighbor setNp with the connectivity neighbors. Once a connectivity neighbor finds that another user should/should not be inNp, it will notifyUser i. To facilitate description, some abstract functions are introduced:(i)
Multicast(e, y, g): evente with sequence numbery is sent to all replicas of groupg.(ii)
Handle(e): evente, which has been delivered toQd, is handled by the application.(iii)
Time(t): set the timer tot, which will trigger a timeout event att.(iv)
EVENT← c: assign contentc to event EVENT.


## 5.3. Neighbor Join

SupposeUser j is one of the connectivity neighbors ofUser i.User j discovers that another userUser k is in the perception range but not in theNp ofUser i; it will notifyUser i for adding the new neighbor with the following procedure. To distinguish clients from mesh computers, letpi be the client ofUser i andri be the replica of groupgi (i.e., the mesh computer ofUser i), the same forpj andpk.Step 1.
p j Multicast(ADD_NEIGHBOR ← (pk,Gk),y,gi).Step 2.
r i Handle(ADD_NEIGHBOR) for cyclec, ∀ri ∈ Gi.(a)
ri modifiesS← S∪  {pk},U← U∪  {pk,Gk}.(b)
ri calculateststart,k =trecv,j(y) +n·∆t andtrecv,k(1) =tstart,k + ∆t.(c)
ri calculates cycleck = ⌈(trecv,k(1) –tnow) / ∆t⌉ +c.(d)
ri Time(ck) for receiving the first event frompk.(e)
ri sends (HANDSHAKE ← (tstart,k,Gi)) topk.Step 3.
p k addsGi to the recipient list.Step 4.
pk Calculatetsend,k(1) ← tstart,k  − ∆TnL.Step 5.
pk Time(tsend,k(1)).Step 6.
pk Multicast(e, 0,gi) attsend,k(1).Step 7.
p k Time(tstart,k+ ∆t) for the next event.Step 8.
r i receives EVENT atck.Step 9.
r i delivers EVENT forck.The neighbor join process is illustrated in Figure10(a). First, the connectivity neighborpj sends the ADD_NEIGHBOR event to all replicas ingi for adding new neighborpk. Then, each replicari modifies the event sender and the update set recipient set, calculates the first event start time for event sending and receiving, and notifies the new neighborpk. The clientpk is timed to send the first event attrecv,j(y)+ n·∆t−∆TnL (wheren, ∆t, and∆TnL are preconfigured). Meanwhile, the replicas ofgi are waiting for the event of the first cycleck attrecv,k. Since the start timetstart,k and the first event sequence numberj0= 0 are known to both communication ends, they can individually calculate the time of subsequent event sending and receiving. At last, clientpi learns the new neighbor through the update fromgi and renders it toUser i.


## 5.4. Neighbor Leave

The procedure of neighbor leave is similar to but simpler than the neighbor join procedure. SupposeUser j is one of the connectivity neighbors ofUser i. Whenci discovers that another userUser k is out of the perception range but still inNp ofUser i, it will notifyUser i with the following procedure.Step 1.
p j Multicast(RM_NEIGHBOR ← (k), y, gi).Step 2.
r i Handle(RM_NEIGHBOR) for cyclec, ∀ri ∈ Gi.(a)
ri modifies S ← S ∖ {pk}, U ← U ∖ {pk,Gk} for cycle c + 1.The neighbor leave process is illustrated in Figure10(b). The connectivity neighborpj sends the RM_NEIGHBOR event to all replicas ingi for removing the neighborpk, which can then removepk andGk in both the event sender set and the event recipient set for cyclec + 1. Through the update fromgi, then clientpi learns the leave of neighborpk and removespk from display.


## 6. Theoretical Verification

The correctness of the state update design is determined by the state of all replicas in a group, as well as the clients. Firstly, the correctness of leader election and group reconfiguration are verified, since they support the other propositions. The proof of all lemmas and theorems can be found in AppendixC.Lemma 1 (leader election synchrony).
All the live replicas inG maintain the sameQd,E, andG after leader election.Lemma 2 (group reconfiguration synchrony).
All the live replicas inG maintain the sameQd,E, andG after a group reconfiguration.Next, without loss of generality, the correctness of the consensus protocol is verified for an arbitrary cyclec. The validity property and the integrity property [29] are not verified here, since they are not related to the main result and easy to be verified. Interested users can prove them. Here, only the agreement property is verified.Lemma 3 (consensus agreement).
If a live replicari ∈ G delivers an evente toE(c) from a consensus instance for cyclec, thene is eventually delivered toE(c) by all the live replicas.With the above lemmas, the main result can be obtained. But before it, an important property of the late event handling approach needs to be verified first.Lemma 4 (Ω(s, c) agreement).
All the live replicas inG expect delivering the same set of eventsΩ(s, c) for senders∈ Sand cyclec.Now, the main result of theoretical verification can be presented with the following theorem and corollary.Theorem 5 (total-order event delivery).
If a live replicari ∈ G delivers two different events e1 and e2 intoQd withλ1 andλ2, thene1 ande2 will eventually be delivered intoQd on all the live replicas withλ1 andλ2 being two non-negative integer numbers andλ1≠λ2.Corollary 6 (replica synchronization).
All the live replicas inG maintain the same state of their virtual objects.Another important result is the correctness of garbage collection, which is verified in Theorem7.Theorem 7 (garbage collection safety).
If evente is removed fromQd onri ∈ G, thene has been handled by the application on all the live replicas inG.Based on Theorem5, the correctness of the neighbor change procedures is shown with the following corollaries.Corollary 8 (total-order event delivery with sender join).
All the live replicas inG deliver the same first evente0 from a neighbors with the same delivery sequenceλ0.Corollary 9 (total-order event delivery with sender leave).
All the live replicas inG deliver the same last event e∞ from a neighbors with the same delivery sequence λ∞.


## 7. Performance Analysis and Comparison

The performance of the proposed fast event delivery approach is studied in terms of synchronization delay and update loss rate. Three alternative approaches are introduced and compared with the proposed approach: the primary-backup approach, the reliable primary-backup approach, and the consensus-based total-order approach.In the primary-backup approach [11], one replica is the primary replica and the rest are the backup replicas. The primary receives and handles all events and then broadcasts updates to recipients. Meanwhile, the primary replica sends the received events to backups for fault-tolerance. In a reliable primary-backup, the primary broadcasts the update only after the events have been reliably synchronized to all backups. Note that the unreliable primary-backup approach does not ensure state consistency in case of primary failure. The consensus-based total-order approach [29] is similar to the proposed design, except that all events are delivered through consensus. Specifically, in each cycle, all replicas propose the received events within the cycle; the leader decides the events delivery order for the cycle.Synchronization delay describes the time consumed in synchronizing the events over all live replicas. The primary-backup approach does not have a synchronization delay. In the reliable primary-backup approach, only 2 communication steps are involved in event synchronization: the primary broadcasts the events to all backups and collects the response from the backups. The consensus-based total-order approach needs one more communication step, as shown in Figure8. In the proposed approach, synchronization delay is factored by the probabilitypsync of triggering the consensus protocol.Update loss rate describes the probability that a client does not receive the corresponding update after it sends an event to a mesh computer, due to event loss or update loss. In the primary-backup approach, update loss will occur as long as the channel between an event sender/update recipient and the primary replica is failed. In the consensus-based approach and the proposed approach, update loss occurs only when no replica receives the event or all replicas fail to send the update to a recipient. Moreover, assume that late and out-of-order events are discarded in all the approaches.The performance comparison of different approaches is shown in Table2, in whichdc denotes the delay in collecting a message from all replicas,dm denotes the reliable multicast delay, andploss denotes the probability of message loss on a link.Table 2
Performance analysis and comparison results.
Synchronization Delay Update Loss Rate Primary-backup 0 ploss+1-plossploss  Reliable Primary-backup d c + d m ploss+1-plossploss  Consensus-based d c + 2d m plossn+(1-plossn)plossn  Fast Event Delivery (dc+ 2dm)psync plossn+(1-plossn)plossnThe comparison result shows that ifpsync is small, i.e., transmission latency and clock offset are low, then the synchronization delay of the proposed approach is small and may even be close to that of the unreliable primary-backup approach. Thus the proposed approach can opportunistically provide higher responsiveness than the consensus-based total-order approach and the reliable primary-backup approach.For update loss rate,plossn+(1-plossn)plossn<ploss+1-plossploss forn ≥ 2, which can be proved as follows.First, letn = 2. Then, (3)ploss2+1-ploss2ploss2-ploss+1-plossploss=-plossploss+2ploss-12<0.Thus, plossn+(1-plossn)plossn< ploss+1-plossploss for n = 2.Second, letfx=plossx+(1-plossx)plossx, x ∈ R. Then, (4)∂∂xplossx+1-plossxplossx=plossxln⁡ploss+1-plossxplossxln⁡1-ploss+1-plossxplossxln⁡ploss<0.Thus, plossn+(1-plossn)plossn monotonically decreases along with n.Therefore,plossn+(1-plossn)plossn<ploss+1-plossploss forn ≥ 2. This shows that the consensus-based total-order approach and the proposed approach have lower update loss rate than the primary-back approaches.


## 8. Experiments and Results

### 8.1. Simulation Setup

The proposed model is evaluated by simulating distributed computing. Experiments are run in OMNeT++ to simulate message transmission in a network and event-based programming (simulation code at https://github.com/sunniel/VirtualNetEventHandling). The simulation is run by sending events from 10 clients to a replica group, representing 10 neighbors. The replica group size is configured to 5. Cycle length is set to 200ms. In experiments, each client sends more than 9000 events to the replica group, which can simulate a half-hour game session with 200ms user operation interarrival time, applicable to most game genres [32]. After events are sorted and handled, updates will be transmitted to clients for collecting the statistic result. New replicas are generated by the Rendezvous; if the group size is lower than the availability threshold new replicas will be generated by the Rendezvous.The network traffic model includes packet latency and packet loss. The packet loss rate is varied to simulate different rate of message loss rateploss. The packet delay is calculated by one-trip communication delay and network jitter. To facilitate simulation, network traffic is generated by a generating function from the analytical result of real data. Reference [33] suggests that the one-way delay between two hosts H1 and H2 can be modelled bydelay(H1, H2) =Dmin+ jitter, whereDmin is the minimum single-trip delay.jitter is the network jitter caused by network congestion. In the experiments,Dmin is configured to 50ms andjitter is modelled by an exponential distribution and varied to simulate the variation of network latency.To simulate replica failure, replica dynamics is characterized by session length which measures the length of time that a peer is continuously connected to a given P2P network, from its arrival to its departure [34]. Session length of P2P applications can be depicted by different stochastic models. Reference [34] shows that Weibull distribution or log-normal distribution fits the observation best. In this study, replica session length is modelled by a Weibull distribution with the mean value of half hour.


### 8.2. Experiment Results for Overall Performance

To verify the overall performance of event handling, three alternative event delivery approaches are implemented, including primary-backup, consensus-based total-order, and fast event delivery, for comparing their performances. Reliable primary-backup is not included in the comparison, since its performance is in-between the unreliable primary-backup approach and the consensus-based approach.First, responsiveness is evaluated by comparing the interaction latencies in different approaches. Interaction latency includes both the round-trip end-to-end delay between an event sender and a group of replicas and the synchronization delay. The mean value of network jitter is fixed to 50ms, and the standard deviation is changed from 50ms to 250ms to simulate the scenario that events occasionally come late and out-of-order. The experiment result in Figure11 shows that the fast event delivery approach provides much lower latency than the consensus-based total-order approach. Especially when the network latency is small, the responsiveness of the proposed approach is close to the primary-backup model. This is because the rate of triggering the consensus protocol decreases, when most events arrive before the end of cycles.Figure 11
Interaction latency comparison in different models.Second, end-to-end update delivery rate is evaluated by varying the message drop rate to simulate the change ofploss from 0.3 to 0.7. In an asynchronous network, message loss cannot be distinguished from long message delay. Thus, update delivery timeout is used to cover both situations, which is configured to 5 seconds. The mean value of network jitter is fixed to 50ms to eliminate the interference of late events.Figure12 shows the update delivery rate of the three different approaches. Specifically, the update delivery rate of the primary-backup approach is much lower than the other two approaches. Moreover, it drops quickly from around 0.7 to below 0.3 with the increase ofploss, showing the rapid increase of update loss rate. In contrast, the update delivery rate of the consensus-based total-order approach and the proposed approach (overlapped) can remain high. Beforeploss is lower than 0.5, the update delivery rate of these two approaches is close to 1. Whenploss is lower than 0.5, the drop of the update delivery rate of them becomes evident. This is because, with the increase of message drop rate, more messages are received by none of the replicas.Figure 12
Update delivery rate with different message drop rate.In the same experiment, interaction latency is also studied with the change message drop rate. Figure13 shows that, with the increase of message drop, a replica has a higher chance to miss the cycle events, such thatΠ(s, c) ≠Ω(s, c) and more consensus instances are triggered by replicas for event synchronization. This means that increasing message drop has a similar effect of increasing network jitter on the fast event delivery approach in interaction latency.Figure 13
Interaction latency with different message drop rate.


### 8.3. Experiment Results for Individual Improvements

#### 8.3.1. Performance of Late Event Handling

The experiment result in this section verifies the late event handling approach. The proposed approach is compared with the simple discard approach which simply discards any late events. In the experiment, the timing of event sending is modified with clock error which is modelled with a normal distribution (μ = 0). The standard deviation of the clock error is changed from 0 to 400ms to increase the rate of late event. Moreover, network jitter is fixed to 50ms and the message drop rateploss is fixed to 0 to eliminate their interference to the result.Figure14 shows that the proposed approach has a much higher update delivery rate than the simple discard approach. Especially when the clock error is higher than 300ms, simply discarding late events results in that almost no message is delivered, since most events will come late. On the other hand, through the proposed approach, the update delivery rate can be maintained as high as close to 1. But the update delivery rate is lower than 1, because a few late events do not meet the deliverability condition.Figure 14
Update delivery rate with different late event handling approaches.


#### 8.3.2. Performance of Garbage Collection

Garbage collection is tested to verify its effectiveness. The main purpose of the experiment is to show that the proposed mechanism can effectively limit the length ofQd from overgrowth. Thus, the experiment is conducted with two different settings: one with garbage collection and the other without garbage collection. The increase of the delivery queue length (Qd) is observed and compared for the two settings. Network jitter is fixed to 50ms and the message drop rateploss is configured to 0 to remove the interference of event loss in both settings, so that the length ofQd is only determined by the number of events and garbage collection. In the second setting, the length of the garbage collection cycle is fixed to 5 seconds. The experiment result is shown in Figure 15. In the case that garbage collection is not applied, the length ofQd quickly increases from several thousand events to tens of thousands of events within 500 seconds. On the other hand, if garbage collection is applied, the change ofQd is restrained within 300 hundred events. The comparison result shows that the proposed garbage collection protocol can effectively preventQd from unlimited growth or even overflow.Figure 15
Delivery queue (Qd) length along with simulation time with and without garbage collection (GC).Moreover, the cycle length of the gossip protocol is changed to show the control of the protocol onQd length. The experiment result is shown in Figure 16. When the cycle length of the gossip protocol increases from 1 second to 10 seconds, the length ofQd changes from around 50 events to around 500 events. This experiment result shows that the length ofQd is approximately linear to the cycle length of the gossip protocol. It implies that the length ofQd can be effectively controlled by changing the cycle length. This control is useful because different virtual world applications could have different size of an event. If an application is required to cache large events, the length ofQd will be reduced for the same space of event cache.Figure 16
Trend of delivery queue (Qd) length with different garbage collection (GC) cycle length.


#### 8.3.3. Performance of Time Synchronization

The performance improvement through time synchronization is shown in Figures17 and 18. The main purpose of the experiment is to show that the time synchronization mechanism has positive effect on interaction latency reduction and garbage collection. Thus, the experiment compares the performance of event handling in two different settings: one with time synchronization and the other without time synchronization. Clock error is added to the timing of event sending to simulate the scale of clock synchronization loss between the event senders and recipients. Network jitter is fixed to 50ms and the message drop rateploss is fixed to 0 to eliminate their interference to the result.Figure 17
Interaction latency with different clock offset.Figure 18
Delivery queue (Qd) length with different clock offset.Figure17 shows that if the clocks between event senders and event recipients are out-of-sync, there is an increase of interaction latency along with clock offset, because time synchronization loss increases the chance of triggering consensus for event delivery. Note that the interaction latency increase with clock offset is almost linear, clearly showing the impact of synchronization loss. In contrast, if time synchronization is applied before event transmission, the interaction latency is less than 1 second. This is because the number consensus can be reduced and thus the communication steps for event delivery can be minimized accordingly.Figure18 shows the increase of the delivery queue (Qd) also along with clock offset. Due to clock synchronization loss, more cycles are delivered with empty events, and thus more empty events are at the trail ofQd. According to the rule of garbage collection, trailing rounds with empty events cannot be removed fromQd. Thus, clock synchronization loss weakens the effectiveness of the garbage collection mechanism. Note that when the clock offset exceeds 300ms, the increase ofQd will become large. In contrast, if time synchronization is applied, the length ofQd does not increase along with clock offset.


### 8.4. Discussion

The experiment results for the overall performance show similar results to the theoretical analysis. Specifically, the proposed fast event delivery approach is reliable and can provide opportunistically high responsiveness, compared with the consensus-based total-order approach and the primary-backup approach, because this approach has the highest update delivery rate, and almost the same interaction latency as the primary-backup approach when the network latency is low. Thus, the overall performance of the proposed approach is better than the other two alternative approaches. The results also imply that, in practice, it is better to select cache nodes which are close to clients so that most cycle events can arrive on time at all replicas and they can be delivered without consensus. Then, interaction latency can be minimized.The experiment results for the individual improvements show their effectiveness on system performance improvement. Specifically, the experiment result of late event handling shows that the proposed dynamic cycle event delivery approach can largely increase update delivery rate. High update delivery rate can reduce the chance of event resending which will lower down responsiveness in interaction and impact user experience. The experiment result of garbage collection shows its effectiveness in limiting the length of the event delivery queue. This is important, because it can not only avoid buffer overflow, but also restrict the time in traversingQd, if searching for a specific event is needed. Traversing a large buffer is slow and reduces system responsiveness. Lastly, the evaluation result of time synchronization shows its importance. Without the time synchronization between event senders and event recipients, the advantage of the fast event handling approach and the effect of the garbage collection mechanism diminishes.


## 8.1. Simulation Setup

The proposed model is evaluated by simulating distributed computing. Experiments are run in OMNeT++ to simulate message transmission in a network and event-based programming (simulation code at https://github.com/sunniel/VirtualNetEventHandling). The simulation is run by sending events from 10 clients to a replica group, representing 10 neighbors. The replica group size is configured to 5. Cycle length is set to 200ms. In experiments, each client sends more than 9000 events to the replica group, which can simulate a half-hour game session with 200ms user operation interarrival time, applicable to most game genres [32]. After events are sorted and handled, updates will be transmitted to clients for collecting the statistic result. New replicas are generated by the Rendezvous; if the group size is lower than the availability threshold new replicas will be generated by the Rendezvous.The network traffic model includes packet latency and packet loss. The packet loss rate is varied to simulate different rate of message loss rateploss. The packet delay is calculated by one-trip communication delay and network jitter. To facilitate simulation, network traffic is generated by a generating function from the analytical result of real data. Reference [33] suggests that the one-way delay between two hosts H1 and H2 can be modelled bydelay(H1, H2) =Dmin+ jitter, whereDmin is the minimum single-trip delay.jitter is the network jitter caused by network congestion. In the experiments,Dmin is configured to 50ms andjitter is modelled by an exponential distribution and varied to simulate the variation of network latency.To simulate replica failure, replica dynamics is characterized by session length which measures the length of time that a peer is continuously connected to a given P2P network, from its arrival to its departure [34]. Session length of P2P applications can be depicted by different stochastic models. Reference [34] shows that Weibull distribution or log-normal distribution fits the observation best. In this study, replica session length is modelled by a Weibull distribution with the mean value of half hour.


## 8.2. Experiment Results for Overall Performance

To verify the overall performance of event handling, three alternative event delivery approaches are implemented, including primary-backup, consensus-based total-order, and fast event delivery, for comparing their performances. Reliable primary-backup is not included in the comparison, since its performance is in-between the unreliable primary-backup approach and the consensus-based approach.First, responsiveness is evaluated by comparing the interaction latencies in different approaches. Interaction latency includes both the round-trip end-to-end delay between an event sender and a group of replicas and the synchronization delay. The mean value of network jitter is fixed to 50ms, and the standard deviation is changed from 50ms to 250ms to simulate the scenario that events occasionally come late and out-of-order. The experiment result in Figure11 shows that the fast event delivery approach provides much lower latency than the consensus-based total-order approach. Especially when the network latency is small, the responsiveness of the proposed approach is close to the primary-backup model. This is because the rate of triggering the consensus protocol decreases, when most events arrive before the end of cycles.Figure 11
Interaction latency comparison in different models.Second, end-to-end update delivery rate is evaluated by varying the message drop rate to simulate the change ofploss from 0.3 to 0.7. In an asynchronous network, message loss cannot be distinguished from long message delay. Thus, update delivery timeout is used to cover both situations, which is configured to 5 seconds. The mean value of network jitter is fixed to 50ms to eliminate the interference of late events.Figure12 shows the update delivery rate of the three different approaches. Specifically, the update delivery rate of the primary-backup approach is much lower than the other two approaches. Moreover, it drops quickly from around 0.7 to below 0.3 with the increase ofploss, showing the rapid increase of update loss rate. In contrast, the update delivery rate of the consensus-based total-order approach and the proposed approach (overlapped) can remain high. Beforeploss is lower than 0.5, the update delivery rate of these two approaches is close to 1. Whenploss is lower than 0.5, the drop of the update delivery rate of them becomes evident. This is because, with the increase of message drop rate, more messages are received by none of the replicas.Figure 12
Update delivery rate with different message drop rate.In the same experiment, interaction latency is also studied with the change message drop rate. Figure13 shows that, with the increase of message drop, a replica has a higher chance to miss the cycle events, such thatΠ(s, c) ≠Ω(s, c) and more consensus instances are triggered by replicas for event synchronization. This means that increasing message drop has a similar effect of increasing network jitter on the fast event delivery approach in interaction latency.Figure 13
Interaction latency with different message drop rate.


## 8.3. Experiment Results for Individual Improvements

### 8.3.1. Performance of Late Event Handling

The experiment result in this section verifies the late event handling approach. The proposed approach is compared with the simple discard approach which simply discards any late events. In the experiment, the timing of event sending is modified with clock error which is modelled with a normal distribution (μ = 0). The standard deviation of the clock error is changed from 0 to 400ms to increase the rate of late event. Moreover, network jitter is fixed to 50ms and the message drop rateploss is fixed to 0 to eliminate their interference to the result.Figure14 shows that the proposed approach has a much higher update delivery rate than the simple discard approach. Especially when the clock error is higher than 300ms, simply discarding late events results in that almost no message is delivered, since most events will come late. On the other hand, through the proposed approach, the update delivery rate can be maintained as high as close to 1. But the update delivery rate is lower than 1, because a few late events do not meet the deliverability condition.Figure 14
Update delivery rate with different late event handling approaches.


### 8.3.2. Performance of Garbage Collection

Garbage collection is tested to verify its effectiveness. The main purpose of the experiment is to show that the proposed mechanism can effectively limit the length ofQd from overgrowth. Thus, the experiment is conducted with two different settings: one with garbage collection and the other without garbage collection. The increase of the delivery queue length (Qd) is observed and compared for the two settings. Network jitter is fixed to 50ms and the message drop rateploss is configured to 0 to remove the interference of event loss in both settings, so that the length ofQd is only determined by the number of events and garbage collection. In the second setting, the length of the garbage collection cycle is fixed to 5 seconds. The experiment result is shown in Figure 15. In the case that garbage collection is not applied, the length ofQd quickly increases from several thousand events to tens of thousands of events within 500 seconds. On the other hand, if garbage collection is applied, the change ofQd is restrained within 300 hundred events. The comparison result shows that the proposed garbage collection protocol can effectively preventQd from unlimited growth or even overflow.Figure 15
Delivery queue (Qd) length along with simulation time with and without garbage collection (GC).Moreover, the cycle length of the gossip protocol is changed to show the control of the protocol onQd length. The experiment result is shown in Figure 16. When the cycle length of the gossip protocol increases from 1 second to 10 seconds, the length ofQd changes from around 50 events to around 500 events. This experiment result shows that the length ofQd is approximately linear to the cycle length of the gossip protocol. It implies that the length ofQd can be effectively controlled by changing the cycle length. This control is useful because different virtual world applications could have different size of an event. If an application is required to cache large events, the length ofQd will be reduced for the same space of event cache.Figure 16
Trend of delivery queue (Qd) length with different garbage collection (GC) cycle length.


### 8.3.3. Performance of Time Synchronization

The performance improvement through time synchronization is shown in Figures17 and 18. The main purpose of the experiment is to show that the time synchronization mechanism has positive effect on interaction latency reduction and garbage collection. Thus, the experiment compares the performance of event handling in two different settings: one with time synchronization and the other without time synchronization. Clock error is added to the timing of event sending to simulate the scale of clock synchronization loss between the event senders and recipients. Network jitter is fixed to 50ms and the message drop rateploss is fixed to 0 to eliminate their interference to the result.Figure 17
Interaction latency with different clock offset.Figure 18
Delivery queue (Qd) length with different clock offset.Figure17 shows that if the clocks between event senders and event recipients are out-of-sync, there is an increase of interaction latency along with clock offset, because time synchronization loss increases the chance of triggering consensus for event delivery. Note that the interaction latency increase with clock offset is almost linear, clearly showing the impact of synchronization loss. In contrast, if time synchronization is applied before event transmission, the interaction latency is less than 1 second. This is because the number consensus can be reduced and thus the communication steps for event delivery can be minimized accordingly.Figure18 shows the increase of the delivery queue (Qd) also along with clock offset. Due to clock synchronization loss, more cycles are delivered with empty events, and thus more empty events are at the trail ofQd. According to the rule of garbage collection, trailing rounds with empty events cannot be removed fromQd. Thus, clock synchronization loss weakens the effectiveness of the garbage collection mechanism. Note that when the clock offset exceeds 300ms, the increase ofQd will become large. In contrast, if time synchronization is applied, the length ofQd does not increase along with clock offset.


## 8.3.1. Performance of Late Event Handling

The experiment result in this section verifies the late event handling approach. The proposed approach is compared with the simple discard approach which simply discards any late events. In the experiment, the timing of event sending is modified with clock error which is modelled with a normal distribution (μ = 0). The standard deviation of the clock error is changed from 0 to 400ms to increase the rate of late event. Moreover, network jitter is fixed to 50ms and the message drop rateploss is fixed to 0 to eliminate their interference to the result.Figure14 shows that the proposed approach has a much higher update delivery rate than the simple discard approach. Especially when the clock error is higher than 300ms, simply discarding late events results in that almost no message is delivered, since most events will come late. On the other hand, through the proposed approach, the update delivery rate can be maintained as high as close to 1. But the update delivery rate is lower than 1, because a few late events do not meet the deliverability condition.Figure 14
Update delivery rate with different late event handling approaches.


## 8.3.2. Performance of Garbage Collection

Garbage collection is tested to verify its effectiveness. The main purpose of the experiment is to show that the proposed mechanism can effectively limit the length ofQd from overgrowth. Thus, the experiment is conducted with two different settings: one with garbage collection and the other without garbage collection. The increase of the delivery queue length (Qd) is observed and compared for the two settings. Network jitter is fixed to 50ms and the message drop rateploss is configured to 0 to remove the interference of event loss in both settings, so that the length ofQd is only determined by the number of events and garbage collection. In the second setting, the length of the garbage collection cycle is fixed to 5 seconds. The experiment result is shown in Figure 15. In the case that garbage collection is not applied, the length ofQd quickly increases from several thousand events to tens of thousands of events within 500 seconds. On the other hand, if garbage collection is applied, the change ofQd is restrained within 300 hundred events. The comparison result shows that the proposed garbage collection protocol can effectively preventQd from unlimited growth or even overflow.Figure 15
Delivery queue (Qd) length along with simulation time with and without garbage collection (GC).Moreover, the cycle length of the gossip protocol is changed to show the control of the protocol onQd length. The experiment result is shown in Figure 16. When the cycle length of the gossip protocol increases from 1 second to 10 seconds, the length ofQd changes from around 50 events to around 500 events. This experiment result shows that the length ofQd is approximately linear to the cycle length of the gossip protocol. It implies that the length ofQd can be effectively controlled by changing the cycle length. This control is useful because different virtual world applications could have different size of an event. If an application is required to cache large events, the length ofQd will be reduced for the same space of event cache.Figure 16
Trend of delivery queue (Qd) length with different garbage collection (GC) cycle length.


## 8.3.3. Performance of Time Synchronization

The performance improvement through time synchronization is shown in Figures17 and 18. The main purpose of the experiment is to show that the time synchronization mechanism has positive effect on interaction latency reduction and garbage collection. Thus, the experiment compares the performance of event handling in two different settings: one with time synchronization and the other without time synchronization. Clock error is added to the timing of event sending to simulate the scale of clock synchronization loss between the event senders and recipients. Network jitter is fixed to 50ms and the message drop rateploss is fixed to 0 to eliminate their interference to the result.Figure 17
Interaction latency with different clock offset.Figure 18
Delivery queue (Qd) length with different clock offset.Figure17 shows that if the clocks between event senders and event recipients are out-of-sync, there is an increase of interaction latency along with clock offset, because time synchronization loss increases the chance of triggering consensus for event delivery. Note that the interaction latency increase with clock offset is almost linear, clearly showing the impact of synchronization loss. In contrast, if time synchronization is applied before event transmission, the interaction latency is less than 1 second. This is because the number consensus can be reduced and thus the communication steps for event delivery can be minimized accordingly.Figure18 shows the increase of the delivery queue (Qd) also along with clock offset. Due to clock synchronization loss, more cycles are delivered with empty events, and thus more empty events are at the trail ofQd. According to the rule of garbage collection, trailing rounds with empty events cannot be removed fromQd. Thus, clock synchronization loss weakens the effectiveness of the garbage collection mechanism. Note that when the clock offset exceeds 300ms, the increase ofQd will become large. In contrast, if time synchronization is applied, the length ofQd does not increase along with clock offset.


## 8.4. Discussion

The experiment results for the overall performance show similar results to the theoretical analysis. Specifically, the proposed fast event delivery approach is reliable and can provide opportunistically high responsiveness, compared with the consensus-based total-order approach and the primary-backup approach, because this approach has the highest update delivery rate, and almost the same interaction latency as the primary-backup approach when the network latency is low. Thus, the overall performance of the proposed approach is better than the other two alternative approaches. The results also imply that, in practice, it is better to select cache nodes which are close to clients so that most cycle events can arrive on time at all replicas and they can be delivered without consensus. Then, interaction latency can be minimized.The experiment results for the individual improvements show their effectiveness on system performance improvement. Specifically, the experiment result of late event handling shows that the proposed dynamic cycle event delivery approach can largely increase update delivery rate. High update delivery rate can reduce the chance of event resending which will lower down responsiveness in interaction and impact user experience. The experiment result of garbage collection shows its effectiveness in limiting the length of the event delivery queue. This is important, because it can not only avoid buffer overflow, but also restrict the time in traversingQd, if searching for a specific event is needed. Traversing a large buffer is slow and reduces system responsiveness. Lastly, the evaluation result of time synchronization shows its importance. Without the time synchronization between event senders and event recipients, the advantage of the fast event handling approach and the effect of the garbage collection mechanism diminishes.


## 9. Conclusions

With the popularity of mobile virtual worlds, scalability becomes an outstanding challenge in infrastructure development. The possibility of P2P technology is discussed to address the scalability problem. Different from existing P2P virtual worlds, client unreliability raises a new problem in mobile settings. This paper tries to solve the problem with a new hierarchical P2P computing model. Yet, rather than introducing every detail of the computing model, we focus on object state update to avoid reinventing wheel. The core problem of state update is to maintain the replica state consistency without compromising system responsiveness. To address the problem, a fast event delivery approach is proposed. Based on this approach, we introduce the new virtual world interaction model to enable the interaction between multiple users.Our work is important in providing a scalable infrastructure for mobile P2P virtual worlds. Based on the proposed Virtual Net architecture, there are some new research problems for building virtual world applications. First, our current approach still has the limitation in high responsiveness, since it belongs to the opportunistic category. To further improve system responsiveness without compromising state consistency, we plan to employ conflict-free replicated data types (CRDT) [35] to replace the consensus approach in event handling. With CRDT, events can be delivered in any sequence. However, events delivery in different sequences may cause user confusion with respect to continues events, such as avatar movement. Thus, it can be expected that the problem will be a combination of human-computer interaction (HCI) distributed computing. Moreover, the future study also includes the application and adaptation of cloud-fog computing techniques for contributed resource management, including cache node allocation, and P2P virtual world techniques to provide a complete and practical mobile P2P virtual world solution.



---

*Source: 9749187-2018-11-08.xml*