A Distributed LRTCO Algorithm in Large-Scale DVE Multimedia Systems

Hangjun Zhou , Guang Sun Sha Fu Wangdong Jiang Tingting Xie and Danqing Duan

Abstract: In the large-scale Distributed Virtual Environment (DVE) multimedia systems,one of key challenges is to distributedly preserve causal order delivery of messages in real time. Most of the existing causal order control approaches with real-time constraints use vector time as causal control information which is closely coupled with system scales. As the scale expands, each message is attached a large amount of control information that introduces too much network transmission overhead to maintain the real-time causal order delivery. In this article, a novel Lightweight Real-Time Causal Order (LRTCO)algorithm is proposed for large-scale DVE multimedia systems. LRTCO predicts and compares the network transmission times of messages so as to select the proper causal control information of which the amount is dynamically adapted to the network latency variations and unconcerned with system scales. The control information in LRTCO is effective to preserve causal order delivery of messages and lightweight to maintain the real-time property of DVE systems. Experimental results demonstrate that LRTCO costs low transmission overhead and communication bandwidth, reduces causal order violations efficiently, and improves the scalability of DVE systems.

Keywords: Distributed computing, distributed virtual environment, multimedia system,causality violation, causal order delivery, real time.

1 Introduction

With the rapid development of Cloud Computing, Big Data, Artificial Intelligence and Internet technologies, large-scale multimedia systems are increasingly implemented on the Internet and mobile networks. A DVE multimedia system is a kind of distributed computing system that simulates the real world and regards geographically distributed users as a group of sequential processes among which data are communicated solely by messages [Fujimoto (2000); Balci, Fujimoto,Goldsman et al. (2017)]. One important issue in DVE systems is to preserve the causal order delivery of messages at each process [Lamport (1978); Zhou, Cai and Turner (2007)]. Moreover, since a DVE is a computer-generated virtual world which simulates the real one, messages are requested to be orderly delivered in real time.Presently, how to effectively maintain the real-time causal order delivery of messages is still one of the important and fundamental issues in large-scale DVE systems[Fujimoto (2000); Zhou, Cai and Turner (2007); Evropeytsev, Dominguez, Hernandez et al. (2017)].

Causality of messages has been widely studied in parallel and distributed computing systems. Previously, many distributed causal order control approaches have been proposed. Vector Time [Schwarz and Mattern (1994); Kshemkalyani and Singhal (1998);Cai,Turner and Lee (2005)] and Immediate Dependency Relation (IDR) [Prakash, Raynal and Singhal (1997); Hernandez (2015); Hernandez, Fanchon and Drira (2004)] are two kinds of traditional approaches to keep causal order. They assume data of all messages have unlimited time validity so that they are not mainly researched with real-time issues

[Baldoni, Mostefaoui and Raynal (1996); Zhou, Cai and Turner (2007)]. a Δ-Causal Order [Baldoni, Prakash and Raynal (1998); Yavatkar (1992)] is defined for the distributed systems in which data of messages have limited time validity and real-time constraints. However, this approach can merely set each message with the identical time validityΔ, which may not suit for DVE systems [Rodrigues, Baldoni and Anceaume(2000)]. Moreover, because it uses Vector Time to maintain causal order, the amount of control information with each message is closely coupled with the scale of processes.Hence, when in large-scale DVE systems, Δ-Causal Order needs to attach a large amount of control information to each message, which introduces too high overhead of sending,transmitting and receiving messages to preserve causal order delivery in real time. In Rodrigues et al. [Rodrigues, Baldoni and Anceaume (2000)], another causal order algorithm is proposed to take each message’s own time validity into consideration, but it still uses Vector Time to keep causal order which limits the scalability and degrades the real-time property of the algorithm. Zhou et al. [Zhou, Cai and Turner (2007)] gives a real-time causal order mechanism to define and reduce critical causal order violations.

The control information of each message is irrelevant to the scale of processes by attaching a critical causal pair in it. However, since critical causal order merely preserves the cause-effect relation existing between two immediate dependent events, other causeeffect relations might not be maintained and would change into concurrent relations,which would violate the causal order. In Evropeytsev et al. [Evropeytsev, Dominguez,Hernandez et al. (2017)], a causal protocol CODM is proposed of which the overhead timestamp in each message is based on immediate dependency relation, but it is oriented to a reliable hierarchical overlay network where the direct communication among peers is disabled.

Thus it can be seen that the key challenge is to preserve causal order delivery of messages with the control information of which the transmitting and processing overhead is subject to real-time property in large-scale DVE systems. In this article, we aim to propose a novel Lightweight Real-Time Causal Order (LRTCO) algorithm for large-scale DVE systems. Different to the previous approaches, LRTCO can compute causal control information by the prediction and comparison of transmission delays of messages, and deduce the reasonable termination condition of the computation. Therefore, the causal control information is unconcerned with the scale of processes and dynamically adapted to the network latency variations.

In this way, LRTCO could exclude the redundant data for the control information so that it is efficient to preserve the causality of messages and lightweight to maintain the real-time property of DVE systems. Experimental results demonstrate that the LRTCO algorithm costs low control information overhead and com-munication bandwidth, effectively reduces causal order violation, and is more efficient than the previous approaches in preserving the causal order delivery of messages in real time.

The rest of the paper is organized as follows. Section 2 introduces the formal definition of real-time causal order delivery. A novel distributed LRTCO algorithm to resolve the problem is proposed in Section 3. In Section 4, experiments are implemented to evaluate the efficiency of the algorithm. Conclusions are summarized in Section 5.

2 Real-time causal order delivery of messages

In a DVE multimedia system, geographically distributed users, who connect with each other via LAN/WAN, are usually regarded as a finite set P of n sequential processes{p1, p2,. . . ,pn} that do not have shared memory and communicate merely by exchanging messages(events) through the serverless network. Generally, an event generated at the process piis denoted as e which can be identified with r(e) where r(e) = (i, a) and a is the logical time [Lamport (1978)] when e is generated at pi. Eidenotes all the events that have been generated at pi, Videnotes all the events that have been received at pi, and Hidenotes all the events that have been delivered at pi. E =∪in=1Eidenotes all the events generated at P . As a DVE is real-time multimedia system with wallclock time, t is uesed to denote the current wallclock time of the DVE system and txto denote the time when event exis generated. Base on the above discussions, we have the following definitions.

Definition 2.1 ( Aappen-Before Relationship). I A ex∈ Ei, ey∈ Ej, r ( ex) = (i, a),r(ey) = (j, b), then ex→ eyiff

(1)i=j∧a＜b;

(3)?ez∈E,and(ex→ez)∧(ez→ey).

If?(ex→ ey)∧?(ey→ ex),thenexandeyare concurrent events denoted asex‖ey.

Definition 2.2(Immediate Dependency Relation).Ifex∈Ei,ey∈Ej,exandeyare of immediate dependency relation(denoted asex↓ey)iffex→ eyand?ez∈ E,?(ex→ez→ey).

Definition 2.3(Causal Order Delivery).Ifex∈Ei,ey∈Ej,ex→eyandex,eyare sent to the same processpk,exmust be delivered beforeeyatpk.In this case,we say that there is a causal order betweenexandeyregardingpk,andexis called a causal predecessor of ey.

In DVE multimedia systems,because distinct types of messages usually have different validity time values,the validity time ofeycan be denote asΔTy.The real-time causal order delivery of events is defined as follows.

Definition 2.4(Real-Time Causal Order Delivery).?pdes∈ P,the real-time causal order delivery of events in the messages atpdesis preserved iff

(1)?ey∈ Vdes?Hdes,at the time whent=ty+ΔTyoreyis required to be delivered,?ex∈ Vdes?Hdes,ifex→ ey,exmust be delivered beforeeyatpdes;

(2)?ey∈ Vdes? Hdes, let Fy= {ex|?ex∈ E ∧ ex→ ey}, when ty≤ t ≤ty+ ΔTy, if Fy? Hdes, eymust be delivered immediately at pdes.

3 A lightweight real-time causal order algorithm

3.1 Analysis and basic idea

In this section, we analyze the basic idea to preserveat each pdesof eybase on the following definitions.

Definition 3 .1 (Cause-Effect Relation Graph). G=(E′, D) is acause-effect relation graph iff the ertex et E '? E and the irected edge set D = {d(x,y)|ex↓ ey, ?ex, ey∈ E '}, where exis the initial ertex and eyis the terminal ertex of the irected edge d(x,y).

Definition 3.2 (Cause-Effect Relation P ath). If G = (E′, D), ?ex, ey∈ E′, cause-effect relation path W = (E′, D′), E′? E′, D′? D, linking exand eyis a directed sequence of vertices and edges in the form as w(ex, ey) = exd(x,z)ez. . . evd(v,y)ey.

G = (E′, D) clearly illustrates the cause-effect relation among events in E′, but it is not easy to propose the causal order control approach directly based on the graph. With further analysis, it can be found that ?ex, ey∈ E′, if ex→ eyin G, there is bound to be at least one W = (E′, D′) linking exand ey; if ex||ey, there must not be any directed edge or path between exand ey. Therefore, the cause-effect relations merely exist in directed paths.From Definition 1 , we know the delivery order of concurrent events is not considered in

causal order control approaches, thus as long asof each path is well preserved,of the whole graph is equivalently preserved.

Definition 3 .3 ( Causal L ength). If G = (E′, D), ?ex, ey∈ E′s uch t hat ex→ ey, let W = (E′, D′) = wr(ex, ey) denote any one of cause-effect relation paths from exto eyin G, thus the causal length between exand eyis

Assuming r(ey) = (j, b), pjneeds to compute the causal control information for ey, denoted as CI(ey), to identify ex∈ Vdesand recursively preserve exeyaccording to the item (1) or (2) in Definition 4. After receiving ey, if ty≤ t ≤ ty+ ΔTy, pdeswould periodically use CI(ey) to check whether item (2) in Definition 4 is satisfied. In terms with causal order delivery, if ?ex∈ E such that ex↓ ey, ex∈ Hdes, item (2) in Definition 4 is satisfied, then pdescould delivery eyimmediately for better real-time property. However, it is quite possible, especially on WAN, that When t = ty+ ΔTyor eyis required to be delivered, item (2) is not satisfied due to large transmission delay. For this case, it is necessary for pdesto use CI(ey) to reconstruct the cause-effect relation and preserve exeyaccording to item (1) in Definition 4. Then, the current minimum causal event in a path is defined, and a theorem and its proof about causality preservation is given.

Definition 3.4(Current Minimum Causal Event). ?ey∈ Ej,W(E′,D′)=w(ex,ey),the current minimum causal event,denoted asem,is the one such that at the current momentt,

From the definition, it is known that emmay change with the variation of t and Vdes∩ E′.

Theorem 3.1 ?ey∈ Ej, W (E′, D′) = w(ex, ey), at the time when t = ty+ ΔTyor eyis required to be delivered, if item (2) in Definition 4 is not satisfied, pdescan preserveaccording to item (1) in Definition 4 through using CI(e) to identify eofymw(ex, ey) and reconstructing em↓ eyrelation for w(ex, ey).

Proof. When t = ty+ ΔTyor eyis required to be delivered, assume that there is ex′ ∈Vdes∩ E′, and ex′ /em, ex′ey, then 1 ≤ L(em, ey) ＜ L(ex′ , ey), hence ex′ → em.Because ?ex′′ ∈ E′such that L(ex′′ , ey) ＜ L(em, ey), ex′′ ∈/ Vdes, thus if pdesreconstruct the cause-effect relation between emand ey, it must be em↓ ey. If pdesuses CI(ey) to identify ex′and reconstruct ex′ ↓ ey, it can get that new L(ex′ , ey) = 1. But L(em, ey) isn’t renewed, so L(ex′ , ey) ≤ L(em, ey), i.e. em→ ex′ . That violates the original causal order between ex′ and em. Therefore, the correct way for pdesis to reconstruct em↓ eyrelation,and after that the new L(em, ey) = 1. Recursively, pdesuses CI(em) to identify the current minimum causal event em′ of emand renew L(em′ , ey). The rest may be deduced by analogy until the events in Vdes∩ E′are identified. Then, pdeswould require these events to be delivered in causal order so as to preserve exeyaccording to item (1) in Definition 4. Hence, the theorem.

Furthermore, if CI(ey) can be used to identify emfor item (1) in Definition 4, it can also be used to identify the special emfor item (2) in Definition 4. Thereby, the focus is the way pjconstructs CI(ey) so that pdescould utilize it tofind out em∈ Vdesto preserve causal order delivery. Meanwhile, the amount of CI(ey) greatly affects the transmission overhead so it also needs to be considered particularly. If pjselects too much r(ex) into CI(ey), such as all the r(ex) in the causal history of eyin a extremely case, it is bound for pdesto identify emwith CI(ey), but it also destructs the real-time property of DVE multimedia systems due to the huge transmission overhead. On the other side, if pjselects not enough r(ex)into CI(ey), it may not sufficient for to pdesto identify em. Therefore, in order to preserve exey, the problem is about how to identify emat each pdeswith the proper amount of CI(ey) selected by pj.

3.2 Selection mode of causal control information

For the purpose of dynamically selecting effective CI(ey) adapted to the network latency variation, it might predict the round-trip transmission delay according to the distributed network coordinate algorithm in Dabek et al. [Dabek, Cox and Kaashoek(2004); Agarwal and Lorch (2009)]. The equation to compute and update the network coordinate is as follows.

Xjand Xirespectively denote the distributed network coordinates of pjand pi. δ is an adaptive timestep. u(Xj? Xi) is an unit vector giving the direction of the force on pj.rtt (round-trip time) is the the round-trip latency between pjand pi. ‖Xj? Xi‖ is the distance between the coordinates of pjand piin the chosen coordinate space and it could be regarded as the current round-trip network latency between pjand pi. During the course of communications at the application layer, it could approximately admit that the one-way transmission delay Δtjifrom pjto piis half of the round-trip one, i.e. Δtji= ‖Xj?Xi‖/2.However, Δtjiis peer-to-peer, which is merely enough for pjto compute the CI(ey) solely effective at pi. In this way, if eyis not just sent to one destination process, pjneeds to compute the control information for each pdesrespectively, and then merge to form CI(ey),which computes repeatedly in a great deal. In order to speed up the computation course,the unnecessary computing overhead of CI(ey) needs to be eliminated.

With further analysis, it can be found that the transmission time of eyshould have a certain range, i.e. through prediction, pjcan maintain a transmission time range:[Δtmin, Δtmax],where Δtminindicates the minimum transmission time of eyfrom pjto pdesand Δtmaxindicates the maximum transmission time similarly. Thus, [Δtmin, Δtmax] includes all the transmission times of ey. As eyis sent at time ty, [ty+ Δtmin, ty+ Δtmax] denotes the time range including all the times when eyarrives at pdes. Then, when pjcomputes CI(ey)based on the time range, it needs not to respectively compute the control information for each pdes. Instead, pjcan select CI(ey) suitable for all pdesto preserve exeyat a time, which is beneficial to enhance the real-time property.

?ey∈ Ej, W (E′, D′) = w(ex, ey), pjmay use the arriving time ranges [ty+ Δtmin, ty+Δtmax] and [tx+ Δtxmin, tx+ Δtxmax] to select proper CI(ey) with which pdescould identify em∈ Vdes∩ E′. However, when t = ty+ ΔTyor eyis required to be delivered,Vdes∩ E′of one pdesmay be not identical with that of the other pdesin that the late events may be different at each pdesdue to different transmission delays. Therefore, pjshould select this kind of CI(ey) with which each pdescould identify its own emfrom its own.

Definition 3.5 (Immediate Dependency Relation Reconstructibility). ?ey∈ Ej, W (E′, D′)=w(ex, ey), |CI(ey)| = h, i.e. h is the number of elements in CI(ey), x′∈ [2, h], if the causeeffect relation among eyand all the events that can be identified by CI(ey) has the form of e1↓ e2↓ . . . ↓ eh↓ eyand satisfies

CI(ey) has the immediate dependency relation reconstructibility.

Theorem 3.2 ?ey∈ Ej, W (E′, D′) = w(ex, ey), |CI(ey)| = h, if the selected CI(ey) has the immediate dependency relation reconstructibility, each pdescan use CI(ey) to iden-tify its own emfrom its own Vdes∩ E′.

Figure 1:pjselects CI(ey)through the comparison of time ranges

Furthermore, t′≥ ty+ Δtmin, thus t1+ Δt1max≤ t′, i.e. e1∈ Vdes∩ E′at t′, which is similar to the case when h = 1 ∧ e1↓ ey. Therefore, at any pdes, ifcan be achieved with CI(ey). Hence, the theorem.

Theorem 3.3 ?ey∈ Ej, W (E′, D′) = w(ex, ey), |CI(ey)| = h, if CI(ey) has the immediate dependency relation reconstructibility, pjselects no redundant control information into CI(ey).

Proof. Assume that the time when t = ty+ ΔTyor eyis required to be delivered at pdesis denoted as t′and ?x′∈ [1, h],the time ex′ arrives pdesis denoted as. For CI(ey) has the immediate dependency relation reconstructibility,ifh=1∧e1↓ey,e1is the solely event that can be identified withCI(ey)andem=e1.Obviously,in this case there is no redundant control information inCI(ey).Ifh＞ 1∧?(e1↓ey),assume that?x′∈ [1,h],r(ex′)is redundant inCI(ey).However,it is possible that(≤ t′)∧ (L(ex′,ey)=1 ‖(L(ex′,ey)＞ 1 ∧ (?x′∈ (x′,h],＞ t′)))at somepdes,thusem=ex′is achieved with CI(ey).Thereby,r(ex′)is indispensable inCI(ey).Furthermore,becauset1+Δt1max≤ty+ Δtmin,em=e1can be achieved if?x′∈ [2,h],＞ t′at anypdes.Therefore,any otherr(ex′′)such thatL(ex′′,ey) ＞ L(e1,ey)is redundant or unnecessary forCI(ey).Hence,the theorem.

For example,in the scenario shown Fig.1,w(e1,ey)=e1→e2→e3→ey,t3+Δt3max＞ty+ΔTy,e3may be delayed at somepdes.Thus ifpjonly selectsr(e3)into CI(ey),it’s not enough to identifyemat allpdes.For[t2+ Δt2min,t2+ Δt2max]∩ [ty+Δtmin,ty+Δtmax]Φ,ife2could arrive in time,pjmay selectr(e2)intoCI(ey).But ife2would arrive late either,eme2andCI(ey)containingr(e2)andr(e3)remains not enough for allpdes.Then because[t1+Δt1min,t1+Δt1max]∩[ty+Δtmin,ty+Δtmax]=Φ,e1could arrive timely so that even ife2,e3are late,em=e1atpdes.Therefore,when CI(ey)containsr(e1),r(e2)andr(e3),eachpdeswould identify its ownemandpjcould terminate the selection.

?ey∈ Ej,W(E′,D′)=w(ex,ey),?ex′ ∈ E′,x′/y,before sendingey,pjwould selectCI(ey)according to the ascending order ofL(ex′,ey)untilCI(ey)has the immediate dependency relation reconstructibility, which is the termination condition of CI(ey) selection. Correspondently, pdescould identify the em, whether for item (1) or item (2) in Definition 4, by reading and searching CI(ey) in the same ascending order. Generally, this kind of computing time overhead is negligible as compared to that of transmission delay.Moreover, because each W (E′, D′) in a G = (E′, D) can be traversed with Depth-First Search algorithm, the above selection mode and searching method on W (E′, D′) are also suitable for the whole G = (E′, D). Then, the Definition of CI(ey) of G = (E′, D) could be described as follows.

Definition 3.6 (Causal Information on Cause-Effect G raph). ? ey∈ Ej,G = (E′, D) is the cause-effect graph of ey, ex∈ E′, the causal control information of eyon G = (E′, D)is that CI(ey) = {element(i,a)|element(i,a)= (r(ex), tx, [Δtxmin, Δtxmax], L(ex, ey))},where r(ex) = (i, a) and the subset of CI(ey) on each directed path has the immediate dependency relation reconstructibility.

Because CI(ey) is selected based on the comparison of time ranges, the content of CI(ey)could be dynamically adapted to the network latency variation so as to let pdesidentify emeffectively. In the meanwhile, for the amount of CI(ey) is unconcerned with the scale of processes, the low transmission overhead could be beneficial to preserve ex?ΔT→eywith real-time property in large-scale DVE multimedia systems.

3.3 Sending and receiving algorithms of LRTCO

3.3.1 Sending messages algorithm

With the selection of CI(ey), pjsends it with eyin a message to pdes. Before describing the algorithm of sending the message, several structures of local variants are given as follows.

?V T(pj)—the vector of logical times to track the numbers of messages diffused by processes.The size ofV T(pj)is equal ton.V T(pj)records the logical time ofpj.

?CG(pj)—themulti-linkedliststoringthecurrenteffectivecause-effectrelationgraph ofpj.To represent an event and its relation,each node ofCG(pj)contains four variants:(r(ex),tx,[Δtxmin,Δtxmax],ptr[num]),whereptr[num]is a set of multiple pointers of which each one is pointed to the node that represents the predecessor which has immediate dependency relation with the event represented by this node.ThusL(ex,ey)could be indicated byptr[num].To avoid the unlimited increment ofCG(pj),pjwould periodically delete redundant nodes in it.Assume the current time ist,thent＜ t+Δtmin.If a node(r(ex),tx,[Δtxmin,Δtxmax],ptr[num])meets thattx+Δtxmax＜t,it can obtain thattx+Δtxmax≤t+Δtmin.Thus the other causal nodes of it could be deleted if they are not in multiple paths.

?CI(ey)—the set storing causal information which would be sent topdesto witheyin a message.Each element in it contains four parts:(r(ex),tx,[Δtxmin,Δtxmax],lc[num]).r(ex),tx,[Δtxmin,Δtxmax]could be obtained fromCG(pj)and the function oflc[num]is similar toptr[num]inCG(pj)by storing the indexes of its immediate dependent elements inCI(ey).

?CDM—the vector storing the indexes of the immediate dependent elements containingr(ex)such thatex↓eyinCI(ey).An element inCDMcontains two variants:(r(ex),ltr),whereltrdenotes the index of one immediate dependent element containingr(ex).With theCDM,pdescould begin to traverseCI(ey)using Depth-First Search algorithm.

Figure 2:The form of message M

Figure 3:The algorithm of sending message M

?CN(pj)—the vector storing the pointers to the immediate dependent nodes containingr(ex)such thatex↓eyinCG(pj).An element inCN(pj)has two parts:(r(ex),ptr),whereptrdenotes the pointer to one immediate dependent node containingr(ex).With theCN(pj),pjcould traverseCG(pj)using Depth-First Search algorithm.

In order to effectively preserveexeyatpdes,the form of messageMis set as shown in Fig.2.

The algorithm of sending messageMis implemented as described in Fig.3.

The line 4 of the algorithm described in Fig.3 is the procedure to recursively compute CI(ey)and itsCDM.The starting argument of the procedure is a pointer stored in an element ofCN(pj).Then,pjcould begin to traverseCG(pj)with Depth-First Search algorithm until the subset ofCI(ey)on each directed path has the immediate dependency relation reconstructibility.The procedure is implemented as described in Fig.4.

Figure 4:The procedure to recursively compute CI(ey)and its CDM

Figure 5: The algorithm of receiving message M

3.3.2 Receiving messages algorithm

After receiving the message M containing ey, pdeswould check whether the immediate cause events exof ey, i.e. ex↓ ey, have been delivered. If all the exare delivered, it is necessary for pdesto deliver eyimmediately according to the item (2) in Definition 4 . In this case, em= ex. If there exists any undelivered immediate cause event, pdeswould buffer M. Then, pdesperiodically checks the message buffer tofind out whether all those exhave been delivered. If at the moment t = ty+ ΔTyor M is required to be delivered, all the exare delivered, i.e. em= ex, pdescould directly deliver ey. If there are still delayed and undelivered immediate cause events in some paths, then pdeswould commence to compute emin those paths.

Therefore, there exist different cases for M as follows: If M has been discarded at pdesor current moment t ＞ ty+ ΔTy, i.e. M is expired, M would be abandoned; if M is valid and item (2) in Definition 4 concerned with eyis satisfied at t, pdeswould process M immediately; if M is valid but item (2) in Definition 4 is not satisfied at current moment t,pdeswould buffer M into MQ(pdes).

?MQ(pdes)—messages buffer atpdes.pdeswould periodically scan the buffer,if item(2)in Definition 4 concerned witheyis satisfied,or current momentt=ty+ΔTy,orMis required to be delivered,pdeswould call the procedure to processM.

The algorithm of receiving message M is implemented as described in Fig. 5.

When pdesneeds to process M, it would handle M and its undelivered predecessor messages in causal order, which is realized by recursively calling the procedure in line 10 of Fig. 5. If item (2) in Definition 4 concerned with eyis satisfied, M could be delivered immediately. If there exist delayed messages, pdescould use CI(ey) to create a local message, which contains no actual event but control information, to replace a delayed message so that the recursively calling of the processing procedure can function well.

Figure 6: The procedure to recursively process M

Thus, pdescould identify emand preserve exeyeffectively. Once a message, remotely received or locally created, is delivered at pdes, the new node with relative data of the message would be added into CG(pdes). Then, as pdesis going to send a message, it could select correct control information from CG(pdes). The procedure is described in Fig. 6.

4 Experimental results and analysis

Experiments have been conducted to evaluate the efficiency of LRTCO algorithm in the distributed causality verification environment established on a PC cluster of 30 high performance machines. The framework of the environment is illustrated in Fig. 7. The run time infrastructure of the environment is BH-RTI [Zhao, Zhou and Lu(2008)] developed by Beijing University of Aeronautics and Astronautics following the High Level Architecture (HLA) standard [IEEE (2000, 2001, 2003)]. The middleware between BH-RTI and federates is designed to consist of the network coordinate computation module and the real-time causal order delivery module.

Figure 7: The framework of the distributed causality verification environment

A distributed real-time air battle simulation is developed to run at federates to display the effects of causal order control algorithms. To simulate the transmission delay of WAN, a Spirent ConNIE is utilized to generate network impairments. The ordering mechanism in BH-RTI is set to be Receive Order (RO) in the experiments.

Through the distributed air battle simulation, LRTCO algorithm is compared with the existing real-time causal order control approaches: ERO [Zhou, Cai and Turner (2007)]and DCCO [Rodrigues, Baldoni and Anceaume (2000)]. Multiple experiments are conducted with different scales of entities running as processes and for each scale the three algorithms are implemented in turn. The GUI of distributed air battle simulation is shown in Fig. 8.

For the correctness of the delivery order of events can be evaluated by the numbers of causal order violations, Fig. 9 shows the causal order violations of ERO, DCCO and LRTCO in the experiments. Because each message in ERO merely contains an immediate dependent event as control information, the causal order violations of it are greater than those of DCCO and LRTCO in each scale. When the scale is 3000, the number of violations is approximately 300 while it is over 1400 when the scale is 11000. The complete vector time used by DCCO in each message can reduce causal order violations lower than 100 when scale is 3000, but as the transmission overhead is closely coupled with the scale, the number of violations rises a lot as the scale expands. In 9000 it is approximately 166% of that in 7000 and in 11000 it is about 187% of that in 9000. The violation number of LRTCO is slightly higher than that of DCCO in 3000, but it is lower when the scale is above 3000 due to the control information irrelevant to the scale.Especially when the scale is 11000, the violation number is merely 200 or so, which is approximately 30% of that of DCCO and 15% of that of ERO in the identical scale.

Figure 8:The GUI of the distributed air battle simulation

Figure 9:Causal order violations in different scales

Figure 10: Average causal control information percentage

As the transmission overhead can be estimated by the average amount of causal control information in each message, Fig. 10 shows the percentage of average causal control information of LRTCO compared to the size of vector time of DCCO in different average network transmission delay conditions. As can be seen in scale 3000, when average network transmission delay is 50 ms, the percentage is about 6%. As the transmission delay rises, the number of messages that can not arrive in time may increase, so that the average amount of control information increases either, but when transmission delay is 200 ms, the percentage is merely 27% or so. With the expanding scale, the size of vector time raises a lot, whereas the average amount of causal control information of LRTCO is irrelevant to the scale, so the percentage gradually diminishes. In 3000, the percentage is approximately 6%, 13%, 22% and 27% when the average transmission delay is 50 ms,100 ms, 150 ms and 200 ms. And in 11000, the percentage correspondently decreases to 2%, 3%, 6% and 7%.

5 Conclusions

In the large-scale DVE systems, causal order delivery of events needs to be preserved in real-time. However, some causal events may arrive late due to the large network transmission delay especially on WAN, which would lead to that the cause-effect relations among received events change into concurrent relations and that causal order violations occur if without the causal order control. In this article, we investigate real-time causal order delivery of events. First, the two cases of real-time causal order delivery are defined. Then, we analyze and define the current minimum causal event, and prove that if the proper causal control information selected by the sending process could be used by each destination process to identify its own current minimum causal event in the received events, the two cases of real-time causal order delivery could be preserved. Thus, we discuss the network transmission time range and arriving time range of an event, based on which it is proved that if the selected causal control information has the immediate dependency relation reconstructibility, each destination process could use it to find out its own current minimum causal event in received events and the control information has no redundant data. After the above analysis and proofs, we propose the Lightweight Real-Time Causal Order(LRTCO) algorithm for large-scale DVE systems, which distributedly realizes designing and implementing the procedure to select the causal control information with the immediate dependency relation reconstructibility at sending process, sending messages algorithm,receiving messages algorithm, and the procedure to recursively deliver the received events in real-time causal order at each destination process. At last, multiple experiments are conducted to evaluate the efficiency o f L RTCO a l gorithm compared with theot her existing real-time causal order algorithms in the distributed causality verification e nvironment.The experimental results demonstrate that LRTCO could effectively preserve real-time causal order delivery of events in large-scale DVE systems by greatly reducing the causal order violations at destination processes and costing low transmission overhead and communica-tion bandwidth due to the causal control information dynamically adapted to the network latency variation and irrelevant to the system scale.

In our future work, we would like to implement more large-scale DVE application systems using LRTCO programs on Internet, and evaluate the performance of the distributed computing systems, so as to obtain more evaluation results about LRTCO preservation efficiency of real-time causal order delivery.

Acknowledgement:This research work is supported by Hunan Provincial Natural Science Foundation of China (Grant No. 2017JJ2016), Hunan Provincial Education Science 13th Five-Year Plan (Grant No. XJK016BXX001), Social Science Foundation of Hunan Province (Grant No. 17YBA049), 2017 Hunan Provincial Higher Education Teaching Re-form Research Project (Grant No. 564) and Scientific Research Fund of Hunan Provin-cial Education Department (Grant No. 16C0269 and No. 17B046). The work is also sup-ported by Open foundation for University Innovation Platform from Hunan Province, China (Grand No. 16K013) and the 2011 Collaborative Innovation Center of Big Data for Finan-cial and Economical Asset Development and Utility in Universities of Hunan Province. We also thank the anonymous reviewers for their valuable comments and insightful sug-gestions.