D Abouri
email: driss_abouri@yahoo.fr

A Parry
email: aparry@clarnart.oilfield.slb.com

A Hamdouni
email: ahamdoun@univ-lr.fr

A STABLE FLUID RIGID BODY INTERACTION ALGORITHM: APPLICATION TO INDUSTRIAL PROBLEMS

Fluid-mechanism interactions occur in a wide range of flow meter categories including turbine and positive displacement systems as well as many flow control devices. This paper outlines computational methods for calculating the dynamic interaction between moving parts and the flow in a flow meter system. Coupling of phenomena is allowed without need for access to the source codes and is thus suitable for use with commercially available codes. Two methods are presented one with an explicit integration of the equations of motion of the mechanism and the other with implicit integration. Both methods rely on a Navier-Stokes equation solver for the fluid flow. The more computationally expensive implicit method is recommended for mathematically stiff mechanisms such as piston movement. Example industrial applications shown are for positive displacement machines and axial turbines. The advances in mesh technology including deforming meshes with non-conformal sliding interfaces opens up this new field of application for Computational Fluid Dynamics and mechanical analysis in flow meter design.

INTRODUCTION

There are many different groups of flow metering devices [I], some of which include moving parts such as turbines and positive displacement meters and some which are static for example ultrasonic, fluidic and pressure drop based systems. In the present note we describe the application of CFD and mechanical analysis in the study of transient fluid-structure interaction in measuring elements or flow control devices comprising moving parts and in particular where the moving parts play an important role in the measurement or control. We restrict the explanation to the case where the components that move relative to each other do not undergo internal deformation, that is the components are considered as rigid-bodies.• However there is no limitation on the displacement of each rigid body. The principles developed are general and could be extended to include small or large internal deformations of the moving components. Applications of the methods described are made for an oscillating piston meter, a meter belonging to the positive displacement group.

A non-linear analysis to predict turbine-forced response is presented by Sayma et al. [START_REF] Sayma | Turbine forced response prediction using an integrated non-linear analysis[END_REF] using a coupling method of the fluid and structural models, the structural response is described by a linear model. Blom [START_REF] Blom | A monolithical fluid-structure interaction algorithm applied to the piston problem[END_REF] investigated time-lagged schemes where coupling is included by sequential solutions of fluid and structure models. In an implicit variant the sequential solutions are repeated with interface boundary conditions updated until convergence is achieved. An algorithm is introduced to calculate fluid-structure interaction in a time marching fashion where both fluid and structure have to be integrated in time simultaneously.

In this paper two methods of coupling algorithm are explained.

The theory necessary for fluid/rigid-body interaction calculations is developed in section I. The explicit method and more computationally intensive implicit method, requiring the repetition of each time step, are explained. In section 2, an industrial application of the implicit coupling algorithm is given for the oscillating piston meter and the explicit scheme is employed to study the dynamics of an accelerating spinner used for flow indication. The fluid flow analysis software utilised for the calculations included in this paper was Star-CD [START_REF]Methodology & User Guide[END_REF].

DESCRIPTION OF CALCULATION METHODS

Fluid rigid body interaction problem

As described in figure 1, suppose that a fluid-structure interaction problem has to be solved, where the fluid occupies the domain Q F , and the solid body described in Lagrangian coordinates occupies the domain

Q s .
They have the common moving boundary

r(t) = Q F (t)
l di vu == 0 Pr(! +u•Vu)==di va F +f {I)
The body moves due to flow-induced forces, in addition to fluid flow, one has to compute the body motion by solving the equations of motion (in general six degrees of freedom) :

{ dv 0 F. F m--= s+ r dt . J dw +wx( J w)==M s + M1 dt ( 2
)
where J is the operator of inertia of the solidS in the centre of inertia (written in a reference frame related to the solid), m is the mass of the solid, F s is the resultant of the external efforts solid/solid and gravity.

The surface forces (pressure and shear) exerted by the fluid on the solid are given by : where a F is the constraint ofCauchy in the fluid: aF ==-pi +v( Vu+' Vu)

and the moment of the efforts exerted by the fluid on the solid, to the centre of inertia G, is given by :

Mr == JGAixaF •nsdr r
As the solid is rigid,

VMEr(t), v(M)==v(G)+wxGM

The condition of non-slip is thus written as follow:

VxEr(t), u(x}==v(G)+wxx

In addition, we have to have force equilibrium across the interface :

0' F • n lr<l) == 0' s • n lr<•J
where n 1ntl = ns j n • l = -n Fj n t l , is the unitary normal vector of the solid wall r .

1.2

Arbitrary Lagrangian Eulerian Formulation

In continuum mechanics one can describe fluid motion with two classical formulations. In the Lagrangian approach, the independent variables are taken to be the initial position, a , of a material point and time t . Lagrangian description prove extremely useful in large deformation problems in solid mechanics. Nevertheless, this formulation include severe distortions as the mesh deform with the material.

In the Eulerian description, the independent variables are spatial position x and time t . Eulerian approach are most often used in fluid mechanics. The mesh is fixed in space so the description undergo no distortion due to material motion.

For problems involving moving wall boundaries, it is necessary to have a middle formulation following the boundary motion and preserving the volume shape in the same time. To enable the computational mesh to remain regular even in presence of large structure displacements, Arbitrary Lagrangian-Eulerian formulation (ALE) has been introduced by by Noh [START_REF] Nob | A time dependent two space dimensional coupled Eulerian Lagrangian code[END_REF] and Hirt et al. [START_REF] Hirt | An arbitrary Eulerian Lagrangian method for all flow speeds[END_REF] for finite difference formulation. Hughes et al. [START_REF] Hughes | Lagrangian-Eulerian finite element formulation for incompressible viscous flows[END_REF], Belytschko et al. [START_REF] Belyschko | Finite element method with user-controlled meshes for fluid structure interactions[END_REF], Liu et al. [START_REF] Liu | Viscous flows for large free surface motion[END_REF], Benson [1 0] introduced the Finite element ALE formulation for incompressible viscous flows. Recently, the ALE method has been successfully applied to such moving boundary problems considering a rigid body structure [START_REF] Nomura | An Arbitrary Lagrangian Eulerian finite element method for interaction of fluid and rigid body[END_REF] and [START_REF] Sarrate | Arbitrary Lagrangian Eulerian formulation for fluid-multi rigid bodies interaction problems[END_REF]. The aim of the ALE formulation is to capture the advantages of both Lagrangian and Eulerian description while minimizing the disadvantages. The equations of motion are written in a form which accounts for the relative motion of the grid with respect to the fluid.

In the ALE description, each node is defined by the co-ordinates X .

The figure 2 define domains in space and associated mappings from one domain to another. x = rp(a,t) Consider a physical property g(x,t) expressed in the spatial representation : g(x,t}== g(rp(a,t�t ) = g (a,t}

G Q F ( O ) � f ( O ) QF(t) G x rq)
Now taking the time derivative of (3) with the material co-ordinates held fixed, we get :

g == ��� . = Z\ . +u•V,g where u = axl is the material velocity. ot a (4)
Therefore, the mapping rp relate the Eulerian and ALE space reference co-ordinates :

x = �(z,t)

Thus the physical property g(x, t) can be expressed in the spatial representation as follow : g(x,t} == g( �(x,t�t)== g ( x ,t ) [START_REF] Nob | A time dependent two space dimensional coupled Eulerian Lagrangian code[END_REF] with the following time derivative expression :

g= o gl = o gl +w•Y' g o tz o t, X where w = o x! is the mesh velocity. at z (6)
Finally, we obtain a fundamental relationship which enables us to translate any Jaw expressed in material (Lagrangian) variables into an equivalent law expressed in mixed variables :

g =g+(u -w) •Y'xg (7)
The arbitrary Lagrangian-Eulerian description may thus be viewed as a mapping of the initial configuration of the continuum into the current configuration of the reference frame. The Jacobian determinant J == de{�=) provides a link between mixed and material coordinates.

The Jacobian J relates the current volume element dV in the spatial frame to the associated volume element dV0 in the referential frame:

dV = J(a,t)dV0 , where J(a,O)=l One may show that the time rate of change of the mixed Jacobian is given by Consider a material co-ordinate a taken to be the initial position, we get:

that we write :

J pf == P o using the time derivative, we get mass conservation law :

p1 + p 1 divu == 0 (8)
Using this law and relation [START_REF] Hughes | Lagrangian-Eulerian finite element formulation for incompressible viscous flows[END_REF], we obtain the expression in the ALE formulation :

(9)

Using the same approach, we obtain momentum conservation law expressed in the ALE formulation.

In Eulerian form, we get :

p 1 (8 u l + u.Vu)=divu+ f at X using the relation [START_REF] Hughes | Lagrangian-Eulerian finite element formulation for incompressible viscous flows[END_REF] for the physical property U , we obtain :

it= Oul +u. Vu = �+(u-w)•Vu o t X
+(u-w)•V xu)=divxu F +f inO F (t) (IJ)
The Geometric Conservation Law is invoked in the formulation in order to avoid errors induced by deformation of control volumes (see Thomas et al. [13] or Dernirzic et al. [START_REF] Demirzic | Space Conservation Law In Finite Volume Calculations Of Fluid Flow[END_REF]). The surface of a control volume V is described by S and the surface vector n . In the case of moving grids, the space-conservation law (SCL) has to be satisfied: The option of arbitrarily moving the mesh in the ALE description offers interesting possibilities. In fact, moving boundaries can be tracked with the accuracy characteristic of Lagrangian methods and the interior mesh can be moved so as to avoid mesh distortion. Several procedures for updating the mesh are explained in the literature [START_REF] Souli | ALE formulation for fluid-structure interaction problems[END_REF][START_REF] Hughes | The finite element method. Linear static and dynamic finite element analysis, Englewood Cliff s[END_REF][START_REF] Blom | Investigations on computational fluid-structure interaction, These[END_REF][START_REF] Van Leer | Flux-Vector Splitting for the Euler Equations[END_REF][START_REF] Batina | Implicit flux-split Euler schemes for unsteady aerodynamic analysis involving unstructured dynamic meshes[END_REF]]. Here in our application, the mesh motion is prescribed a priori based on the known of the rigid-body boundaries calculated at every instant.

.!!_ f dV-f w • ndS == 0 dt J v

Fully implicit coupled iteration schemes

We assume that the domains for the the fl uid have been discretised

appropriately, and has to be solved in a time-implicit manner.

The rigid-body movement is described by a set of ordinary differential equations of the form :

{ m dv =F(v,x,t) dt dx -=V dt ( 12
)
where V is the velocity and x is the position of the body.

In the context of transient fluid-rigid body interaction, we have the choice of either explicit or implicit time integration of these ordinary differential equations. An example of velocity equation explicit discretization is:

F(v x t) v ••• =v.+!lt •• n> n (13) m
Certain problems are better solved using an implicit discretization, particularly for problems with sensitive force velocity behaviour, known as stiff problems in the mathematical sense. For stability reasons, we would also like a time-implicit procedure for the overall time step. An example of velocity equation implicit discretization is :

_ !lt (F(v., x., t. )+ F(v •••, x •• , , t •• , )) v n +l -v n + 2 m
To calculate V n+l, we have to solve a non linear system:

G(v ) = v -v _ !it (F ( v , ,
x , , t, ) + F( v .. . ,, x ,., , t,., )

} = 0 n+l 11+ 1 1/ 2 m
As is well known, in order to accelerate convergence the most widely used and most robust method for the solution of non linear system is Newton-Raphson method. It require the evaluation of derivatives that we approximate by finite differences. With the implicit method, we have to repeat the application of the above equations until convergence for each time step.

G(v,., ) = 0 {v�. , initial guess v::, ' = v: • . -[v a(v:., )j ' a(v:.,)

The Newton's method is an iterative procedure. To begin the iterative procedure, usually the initial value v�., is predicted by an explicit scheme of the same order or simply from the result of the last time step ( v�., = v, ). In our application, v�., is predicted with an explicit Adams-Bashforth scheme of order two :

0 !it ( 3 F( v ,,
x , , t, ) _ F � ( v !!.:.! " -' ..;__ ' X ..!!: " -�" ...! !:. t "_:!.!. J)

v =v +- - "+ 1 " 2 m m
Below is the description of the fully implicit coupled iteration solution algorithm for nonlinear fl uid-rigid body interaction problems :

I. Explicit prediction of the interface velocity v�., = ( v i r r• ' :

v� + l = ( v i r r +% !it(ai r r -� !it(a i r r-l

2. Prediction of the interface position x ,., = x , + !it v:.,

Energy conserving and stability aspects

For fluid structure interaction problems with large displacements, it is necessary to have consistent and energy conservative interface boundary conditions at the moving fluid solid interface. The coupling algorithm have to be stable and the discretisation in time and space should respect the forces equilibrium at fluid solid interface. The fully implicit coupling algorithm developed in this paper respects this crucial property taking the real velocity field at interface as test function for convergence. When the structure is assumed to be rigid, Abouri [START_REF] Abouri | A Fluid Rigid Body Interaction Algorithm : Application to Volumetric Flow Meter[END_REF] demonstrates that the fully implicit scheme verifes that the variation of the sum of the kinetic energy of the system is equal to the difference between the energy introduced by the external boundary conditions and the energy dissipated by viscous effects inside the fl uid.

Grandmont [START_REF] Grandmont | Analyse mathematique et numerique de quelques problemes d'interaction fluide-structure[END_REF] demonstrates this principle of Energy conservation for the case of linear elastic structure.

Le Tallec et al. [START_REF] Le Tallec | Fluid structure interaction with large structural displacements[END_REF] proposes a stability demonstration for an implicit fixed point relaxation algorithm : it couples an implicit Euler treatment on the fluid domain and a mid-point rule for the structural equation. Similarly, Abouri [START_REF] Abouri | A Fluid Rigid Body Interaction Algorithm : Application to Volumetric Flow Meter[END_REF] proposed a stability demonstration for the fully implicit coupling algorithm implemented here in the case of a rigid structure. The key point of the demonstration is to consider a global

APPLICATION TO COMPLEX INDUSTRIAL FLOWS

Description of the Oscillating Piston Flow Meter [23]

The moving element consists of a hollow cylindrical piston with a horizontal web, contained within a cylindrical working-chamber provided with a cover as we see in figure 4 .

Cover Oscillating Piston

Working Chamber The friction in the n, t plane on the piston bottom or top surface can be expressed using the hypothesis that the repartition of the normal reaction force in the z direction is uniform. The choice of this treatment of friction for the plane contact on the bottom or top of the piston has proved to be useful when compared with experimental data.

2.3

Results of calculations

Inlet and outlet ports are positioned on the ends (top and/or bottom) of the working chamber to allow the 'positive displacement' of fluid. The guide plate serves also to isolate incoming and outgoing fluid.

Figure 10 shows the mesh interface between two domains of fluid, one static (the inlet and outlet parts) and one deforming (the annular chamber with piston).

FIG. 10: Evolution of mesh interface

Below are images of calculated results in an oscillating piston flow meter.

Figure 11 shows at left the velocity vectors in a plane through the meter and at right the contour pressure in a plane through the meter.

We note the higher pressure (dark colour) in the inlet volumes to overcome piston friction, inlet/outlet losses and inertial effects.

Time and space discretisation tests

To demonstrate the robustness of the solution algorithm, time step and grid size dependence tests were carried out with the same boundary conditions and at high flow rate.

We compare the rotating velocity of the piston induced by fluid forces.

We note N, x N B x N, CV the control volume number used with respectively N,, N B and N, subdivisions in the direction r, () and z in the cylindrical reference frame related to the center of the box. Calculations were performed on four numerical grids, one coarse with a 13 x 90 x 8 CV and one refined with a 26 x 270 x 16 CV.

For the coarsed one, three time increments were used : !:it = T I 82 , !1t = T /164 and !1t = T /328 . Here T represent the time period corresponding to one cycle of piston revolution.

Figure 13 shows a comparison of the rotating piston velocity calculated on the coarsed grid with three different time steps during a revolution of about T ==0.0492 s. One does not observe a significant difference between the results, which indicates that the temporal errors are small.

  FIG. I :Diagram showing fluid and solid domains If one assumes the fluid is incompressible, the flow field variables are calculated from a set of equations which express in the spatial fluid domain Q F the conservation of fluid momentum and volume, the Navier-Stokes equations as follows :

FIG. 2 :

 2 FIG. 2 : Representation of Eu/erian, Lagrangian and Arbitrary reference domains Therefore, the mapping rp relate the Eulerian and Lagrangian space reference co-ordinates :

Finally equation ( 7 )

 7 is a fundamental relationship which enables us to translate any law expressed in spatial (Eulerian) variables into an equivalent law expressed in mixed (ALE) variables: p1 (�+(u -w}• Vu)= divu + f Consider the relation : u( x , t) = u( �{x ,t 1 t) = u o�{x ,t) (10) Now taking the time derivative of (10) with the mixed co-ordinates held fixed : �= Q u O � � at z If one assumes the fluid is incompressible, the mass and momentum conservation equations are formulated as follows : {d ivxu=O inOF(t) P 1 (:1.

Js

  To cope with large domain deformations and displacement, in addition to the ALE we need a means of treating sliding interfaces within the calculation domain of the fluid flow. Commercially available fluid flow solvers are available with both these essential features for calculating fluid dynamics phenomena in domains undergoing large displacement/deformation. These methods are usually based on finite element or finite volume formulations.

3 . 6 .FIG. 3 :

 363 FIG. 3: Flow diagram showing stages of fluid structure interaction calculation 1.4

  continuum mechanics equation including both fluid and solid using variable functions for the physical quantities like density or velocity field.If a simple explicit algorithm is used, we obtain a limitation in the time step and an instable response. The explicit method is first order accurate, but only conditionally stable. In fact, the explicit staggering algorithm does not conserve energy at the interface because at each timestep the energy introduced by the fluid loading a; + ' on the structure is not equal to the energy change in the fluid. The difference between these two energies is J a;+' . (v.+, -u .. +J nd y . rul For the explicit method, we have ( u 1 r f + ' == ( v1 r f . So the difference between the energies is Ju;+'.(v.+1-v.)• nd y which is not equal to r ul zero. The explicit coupling algorithm is not adequate to solve this type of problem because the delay between the two solvers fluid and structure creates energy dissipation. The kinematic condition implies equality of the velocities on the interface ( ( u l r r+l ::; (v i r r+l ), the dynamic condition requires forces equilibrium across the interface (a;+ ' • n 1r .. , =a;+ ' • n 1 r . . , ). Those coupling conditions at the end of each new step are well fulfilled for the implicit scheme because of exchanging the coupling variables and updating of the fluid domain at each sub-iteration of each timestep. The implicit method can be very useful to solve the fluid and the structure at the same time and avoid energy dissipation creating by the delay between the two solvers created by an explicit method.

FIG 4 :FIG. 5 : 2 FIG. 9 :

 4529 FIG 4 : 30 view of Working Chamber and Oscillating Piston A top view of an oscillating piston flow meter composed of a slotted piston which oscillates in a working chamber comprising a partition I guide plate is shown figure 5. A partition plate between inlet and outlet

4 3FIG. 11 :Figure 12 FIG. 12 :

 4111212 FIG. 11 : Piston movement cycle 1-2-3-4: Dark regions representing high pressure in flow

FIG. / 3 :

 3 FIG. /3 : Comparison of predicted rotating piston velocity versus time using the coarse grid (/3 x 90 x 8 CV) and various time steps

Figure 14 FIG. / 4 : 5

 1445 Figure14shows comparison between fine and coarse grid results during a revolution both obtained with !1t = T /82 . As the grid is refined the results tend to the same solution. No significant differences exist, these comparisons show that the spatial discretization errors are small enough to demonstrate the robustness of the scheme. Although for numerically accurate results for particle tracking for example, further grid refi nement is necessary. But for predict pressure drop or calibration curves in the optic of an optimisation form of the product, the numerical accuracy achieved on the I 3 x 180 x 8 CV and At = T I 82 suffices....

FIG. 15 :

 15 FIG. 15: Dynamic response of the spinner (fluid is water, flow velocity =/ mls, initial spinner velocity=O rpm,ft=60 degrees, r==B mm)


Luiz A Rodrigues
email: luiz.rodrigues@unioeste.br

Elias P Duarte

João Paulo De Araujo

Luciana Arantes
email: luciana.arantes@lip6.fr

Pierre Sens
email: pierre.sens@lip6.fr

Bundling Messages to Reduce the Cost of Tree-Based Broadcast Algorithms

Keywords: Distributed systems, Fault-Tolerant Broadcasts, Spanning trees

Hierarchical broadcast strategies based on trees are scalable since they distribute the workload among processes and disseminate messages in parallel. In this work we propose an efficient best-effort broadcast algorithm that employs multiple spanning trees to propagate messages that are bundled on tree intersections. The algorithm is autonomic in the sense that it employs dynamic trees rooted at the source process and which rebuild themselves after processes crash. Experimental results obtained with simulation are presented showing the performance to the algorithm in terms of the latency and the number and sizes of messages employed.

Introduction

A process of a distributed system uses broadcast to propagate a message to all other processes in the system. Besteffort broadcast ensures that all correct processes deliver the message if the source does not fail. If the source process can fail, another type of broadcast must be employed: reliable broadcast. Furthermore it is possible to define the order in which messages are delivered, such as those guaranteed by FIFO, causal and atomic broadcast [START_REF] Hadzilacos | Fault-tolerant broadcasts and related problems[END_REF].

Several broadcast algorithms are based on trees [START_REF] Schneider | Fault-tolerant broadcasts[END_REF], [START_REF] Fragopoulou | Edge-disjoint spanning trees on the star network with applications to fault tolerance[END_REF], [START_REF] Kim | FaReCast: Fast, reliable application layer multicast for flash dissemination[END_REF], [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF], [START_REF] Raynal | A simple broadcast algorithm for recurrent dynamic systems[END_REF]. If a single tree is employed, each message is first sent to the root of the tree, that will start the broadcast. The main problem of this approach is that the root can become a bottleneck. In addition, these solutions need the extra step in which an initial message is sent to the root to start the broadcast. As faults are unavoidable in distributed systems, the algorithms should be able to build and maintain the tree even as faults occur.

One way to mitigate these problems is to use multiple adaptive trees. In [START_REF] Rodrigues | A robust permission-based hierarchical distributed k-mutual exclusion algorithm[END_REF], [START_REF] Rodrigues | An autonomic implementation of reliable broadcast based on dynamic spanning trees[END_REF], [START_REF] Jeanneau | An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detector[END_REF] we proposed broadcast algorithms based on the VCube [START_REF] Duarte | VCube: A provably scalable distributed diagnosis algorithm[END_REF]. VCube is hypercubelike virtual topology that reconfigures itself and maintains multiple logarithmic properties even after processes crash. The broadcast algorithm propagates messages along spanning trees which are embedded on the VCube. We call the solution autonomic in the sense that the broadcast and the trees tolerate and automatically adapt to process crashes.

Whenever multiple trees are built on a given network, if those trees overlap this can be harnessed by bundling together messages that come to the intersections and are supposed to be forwarded to the same routes. Not only the number of messages is reduced but also the overhead of running the algorithm on the network.

In this paper, we discuss and evaluate the impact of bundling messages to reduce the communication cost of tree-based broadcast algorithms. We present a new besteffort broadcast algorithm based on message bundling. The algorithm was implemented, and simulation results are presented which evaluate the benefits of message bundling through a comparison with an alternative without bundling. Both fault-free and faulty (crash) scenarios were considered, with multiple other features, such as the size of messages and the number of processes. Results confirm the efficiency of the proposed solution considering: (i) the latency to deliver the message to all the correct processes; (ii) the total number of messages, including retransmissions in case of failures; and (iii) size of messages.

The rest of this paper is organized as follows. Section 2 gives an overview of related work. Section 3 describes the system model and the VCube, the virtual topology used. The spanning tree algorithm and the motivation for bundling messages are presented in Section 4. The broadcast algorithm is presented in Section 5. Performance results are discussed in Section 6. Section 7 concludes the paper.

Related Work

Many distributed systems and application on different research areas such as Peer-to-Peer (P2P) Overlay Networks [START_REF] Gupta | Efficient routing for peer-topeer overlays[END_REF], [START_REF] Hidalgo | An aggregationbased routing protocol for structured peer to peer overlay networks[END_REF], [START_REF] Shudo | Message bundling on structured overlays[END_REF], Internet of Things (IoT) [START_REF] Schmidt | Dht-based distributed ale engine in rfid middleware[END_REF], [START_REF] Koike | Iot network architecture using packet aggregation and disaggregation[END_REF], Wireless Sensor Networks (WSN) [START_REF] Rajagopalan | Data-aggregation techniques in sensor networks: A survey[END_REF], [START_REF] Weng | Data aggregation with multiple spanning trees in wireless sensor networks[END_REF], [START_REF] Son | In-network processing for wireless sensor networks with multiple sinks and sources[END_REF], Parallel Discrete Event Simulation (PDES) [START_REF] Chetlur | Optimizing communication in time-warp simulators[END_REF],among others, employ message aggregation/combination in order to reduce the communication cost and thus improve the performance of their solutions.

In [START_REF] Hidalgo | An aggregationbased routing protocol for structured peer to peer overlay networks[END_REF], a structured P2P routing protocol combines multiple lookup messages into a single one with the goal of reducing the average number of hops messages traverse. In [START_REF] Gupta | Efficient routing for peer-topeer overlays[END_REF], the identifier space of the P2P system is divided into slices, coordinated by a leader node. The latter collects all membership change notifications sent from the nodes of its slice during a period of time and, aiming at reducing bandwidth usage, aggregates the notifications into a single message before sending them to the other slice leaders. Similarly, in [START_REF] Shudo | Message bundling on structured overlays[END_REF], a message bundling technique improves network throughput by reducing the number of packet transmissions and mitigates the load of nodes on the overlay.

The main motivation of data aggregation in WSN and IoT is to save energy by reducing the number of message transmissions. However, this may have an impact on other performance metrics such as latency, load processing, or fault tolerance [START_REF] Rajagopalan | Data-aggregation techniques in sensor networks: A survey[END_REF], [START_REF] Weng | Data aggregation with multiple spanning trees in wireless sensor networks[END_REF], [START_REF] Son | In-network processing for wireless sensor networks with multiple sinks and sources[END_REF], [START_REF] Villas | A scalable and dynamic data aggregation aware routing protocol for wireless sensor networks[END_REF]. In this type of work, the goal is usually to group redundant data into a single message which is delivered to the sink. For example, the authors in [START_REF] Villas | A scalable and dynamic data aggregation aware routing protocol for wireless sensor networks[END_REF] present a technique for building dynamic data aggregation trees in wireless sensor networks that minimize the number of redundant messages between transmitters and collectors.

In [START_REF] Reinhard | Message handling in parallel radiance[END_REF], message bundles are used to reduce the number of messages required by a parallel algorithm to communicate data and task information. Messages are bundled according to their importance in the context of the algorithm.

A control message bundling framework was proposed in [START_REF] Khanna | Control message aggregation in group communication protocols[END_REF] for multicast environments and hierarchical protocols. The aggregation mechanism is based on the maximum number of messages and the timeout limit of each message in the packet. Contrarily to our work, application messages are not combined into packets and the impact of aggregation on trees with known structure is presented as an open issue.

Finally, there are other broadcast algorithms based on spanning trees built on hypercube-like topologies [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF], [START_REF] Wu | Optimal broadcasting in hypercubes with link faults using limited global information[END_REF], [START_REF] Liebeherr | HyperCast: A protocol for maintaining multicast group members in a logical hypercube topology[END_REF]. The main difference is that they assume a physical hypercube deployed in hardware on top of which the algorithms run.

System Model

We consider a distributed system that consists of a finite set P of n > 1 processes {p 0 , .., p n-1 } that communicate only by message passing. Processes are organised in a logical hypercube of dimension d = log 2 n. Each single process executes one task and runs on a single processor. Therefore, the terms node and process are used interchangeably in this work.

Processes communicate by sending and receiving messages using atomic point-to-point primitives. The network is fully connected, but processes are organized on a virtual hypercube-like topology, called VCube (Section 3.1). Processes can fail by crashing and there is no recovery. If a process never crashes during a run, it is considered correct or fault-free; otherwise it is considered to be faulty. After any crash, the topology changes, but VCube maintains its logarithmic properties. There is no network partitioning. Links are reliable, and, thus, messages exchanged between any two correct processes are never lost, corrupted or duplicated.

The system is synchronous, i.e., relative processor speeds and message transmission delay are bounded. In this scenario, VCube implements a perfect failure detector, i.e., faults are detected within a finite amount of time and there is no false suspicion.

The VCube Topology

VCube [START_REF] Duarte | VCube: A provably scalable distributed diagnosis algorithm[END_REF] is a distributed diagnosis algorithm that organizes the correct processes of the system P on a virtual hypercube-like topology. In a hypercube of d dimensions, called d-VCube, there are n = 2 d processes. From the point of view of process i the other n -1 processes are grouped in log 2 n clusters, denoted by c i,s , where s = 1, ..., log 2 n is the cluster index; cluster c i,s has size 2 s-1 . The ordered set of processes in each cluster can be computed with the function below, in which ⊕ denotes the bitwise exclusive or operator (xor).

c i,s = i ⊕ 2 s-1 c i⊕2 s-1 ,k | k = 1, .., s -1 (1)
Process i executes tests on other processes in c i,s to check whether it is correct or faulty. The test consists of comprehensive procedure that allows the tester to confirm the state of the tested node. If a correct reply is received within an expected time interval, the monitored process is considered to be alive (correct). Otherwise, it is considered to be faulty. In terms of the properties proposed by Chandra and Toueg [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF] for unreliable failure detectors, VCube ensures the strong completeness property (eventually every process that crashes is permanently suspected by every correct process) and strong accuracy (correct processes are never suspected to have failed, i.e., no false suspicious). Figure 1 shows an example of the hierarchical organization of process p 0 in a hypercube with four dimensions (n = 2 4 processes). Each cluster is presented in the table. For example, in the first round, process p 0 tests the first process (p 1 ) in the cluster c 0,1 = (1) and obtains information about the state of the other processes stored in p 1 . Then p 0 tests the process p 2 , which is the first process in the cluster c 0,2 = (2, 3). Next, p 0 runs tests in process p 4 of the cluster c 0,3 = (4, 5, 6, 7). Finally, p 8 is tested by p 0 in cluster c 0,4 = (8, 9, .., 15). As each process performs tests concurrently at the end of the last round each process will be tested at least once by another process. This ensures that an event is detected by all correct processes in log 2 2 n rounds. Nodes keep state information as timestamps, which are state counters initialized as zero and incremented every time a state change is detected. If tests are represented by arcs from tester to tested node, each process i connects itself to one fault-free process of each cluster s, if there is one. If there are no faults, a complete logical hypercube is created.

In order to avoid that several processes test the same processes in a given cluster, process i executes a test on process j ∈ c i,s only if process i is the first faulty-free s c0,s c1,s c2,s c3,s c4,s c5,s c6,s c7,s .. process in c j,s . Thus, any process (faulty or fault-free) is tested at most once per round. The average latency can be reduced if every time a fault-free node is tested the tester and tested node exchance new information that was not available the last time they communicated.

The Spanning Tree Algorithm

Let G = (V, E) be a graph that represents a distributed system with |V | nodes and |E| links. We consider that G consists of a single connected component. A spanning tree is defined as a connected and acyclic graph that contains all vertex of G [START_REF] Gallager | A distributed algorithm for minimum-weight spanning trees[END_REF].

Based on the VCube topology, We define the following two functions:

• cluster i (j) = s: Let i and j be two nodes of the system, i = j. Function cluster i (j) = s returns the index s of the cluster of node i that contains node j, 1 ≤ s ≤ log 2 N . For instance, in the 4-VCube shown in Figure 1, cluster 0 (1) = 1, cluster 0 (2) = cluster 0 (3) = 2, cluster 0 (4) = 3, and cluster 0 (8) = 4. Note that for any i, j, cluster i (j) = cluster j (i).

• F F neighbor i (s) = j (FF=Fault-Free), returns the first correct process j in cluster s of process i, i.e., j is the first correct process of the list generated by the c i,s . For example, in the table of Figure 1,

F F neighbor 0 (1) = 1, F F neighbor 0 (2) = 2, F F neighbor 0 (3) = 4 and F F neighbor 0 (4) = 8. If process 2 is faulty, F F neighbor 0 (2) = 3.
We then define function subtree i (j) as the set of neighbors of process i related to a source process j :

subtree i (j) = {∀k = F F neighbor i (s)} s = 1.. log 2 n, if i = j 1..(cluster i (j) -1), otherwise (2)
Let correct i be the set of nodes that node i considers to be correct, based on the tests executed and information received by node i through the VCube.

Using the above functions, the following algorithm, proposed in [START_REF] Rodrigues | An autonomic implementation of reliable broadcast based on dynamic spanning trees[END_REF], creates a spanning tree, rooted at i, propagating m over all non faulty nodes of the system: Algorithm 1 Spanning tree algorithm at process i

1: correcti ← {0, .., n -1} 2: procedure STARTTREE( ) 3: for all k ∈ subtreei(j) do 4: SEND( m ) to p k 5: upon RECEIVE m from pj 6: if j ∈ correcti then 7: for k ∈ subtreei(clusteri(j) -1) do 8: SEND( m ) to p k 9: upon notifying CRASH(j) 10: correcti ← correcti {j} 11: if ∃k = F F neighbori(clusteri(j)) then 12: SEND( m ) to p k
The set of children of i, the root of the spanning tree, are given by subtree i (log 2 n). Whenever a node k receives m from its parent p, k becomes the root of a subtree with s = cluster k (p) -1 children. It identifies its non faulty children by calling subtree k (p) and then forwards m to them. The latter behave similarly, if they do not fail neither are leaves. Node k is a leaf if either cluster k (p) = 1 or there is no correct processes in c p,s , s = cluster p (k) -1.

All correct processes learn about the state of the other processes through VCube. If a crash is detected, say j, all processes execute the event CRASH(j) (line 9). Process j, is removed from the local list of correct processes and m is sent to the next correct process k in the same cluster that contains j (if one exists).

Actually, a VCube spanning tree creates a binomial tree [START_REF] Cormen | Introduction to Algorithms[END_REF]. A binomial tree of order 0 is a single node (2 0 ). The binomial spanning tree of order d has 2 d nodes and it is recursively built from a root node whose children are roots of binomial trees of orders d -1, d -2, .., 1, 0. In fact, each child of a process i is the root of a subtree of the cluster in which it is the first correct process according the c i,s . Note that, if there exist faulty processes, a incomplete binomial tree is built.

For example, considering a fault-free scenario, the spanning tree of process 0 in Figure 1 is build by sending the message to the first correct processes in each cluster s = 1, .., log 2 n, represented by the processes 1, 2, 4 and 8. When these process receives the message, they become the root of the subtree in their own cluster. Figure 2(a) shows the full tree of process 0.

Message Bundling for Overlapping Trees

Message bundling is a way to optimize resource usage in distributed systems by reducing the number of messages sent, and decreasing the overhead of transport and routing protocols. The trees in Figure 2 show the potential of bundling broadcast messages that are sent on multiple trees built on a VCube. Comparing the trees of p 0 and p 4 , for example, it is possible to see that many small subtrees are overlapped. If we compare p 0 and p 8 's trees, we note that only the edge between the two processes themselves is not shared. In this case, a message sent by p 0 can be bundled with a message sent by p 8 , and a single message can be sent on a subtree with half the number of nodes in the system.

The Hierarchical Broadcast Algorithm

Best-effort broadcast ensures the deliver of the messages from a correct source to all correct processes in the system, contrarily to the reliable broadcast which guarantees message delivery even if the source fails.

An algorithm of best-effort broadcast should ensure the Validity and Integrity properties. Validity states that if a correct process broadcasts a message m, then it eventually delivers m; and Integrity guarantees that every correct process delivers the same message at most once (no duplication) and only if that message was previously broadcast by some process (no creation).

Several broadcast algorithms use spanning trees to propagate messages since they are scalable and avoid the ack implosion problem. In this section we present a best-effort broadcast algorithm which exploits spanning tree built over the VCube topology as well as a bundling message strategy.

The Best-Effort Broadcast Algorithm

Algorithm 2 presents our hierarchical best-effort broadcast algorithm with message bundling. It dynamically builds spanning trees on VCube which also provide information about the state (correct or faulty) of the processes of the system. The algorithm tolerates up to n -1 process crashes.

Each message m from the application have three attributes: (1) the identification of the source process, i.e., the processes that starts the broadcast, represented by m.src;

(2) the timestamp, a message counter m.ts that uniquely identifies each message broadcast by the same source; and (3) the size of the message (m.size).

The algorithm uses two types of messages: • T REE, m : identifies the application message m being propagated; • ACK, (src, ts) : confirms the receipt of m by the destination, src = m.src and ts = m.ts. Two parameters are required by the algorithm: maxDelay, which is the maximum delay that a bundled message can be held by a node before forwarding; and maxP ayload, which corresponds to the maximum packet size.

The local variables kept by process i are: • correct i : set of processes considered to be correct by process i; • rcv base i [n]: keeps, for each process j, the timestamp of a message m broadcast by j and delivered by i such that all messages broadcast by j before m were also delivered by i. We denote m the last message delivered in order. • rcv win i [n]: for each processes j, it keeps the list of messages delivered by i whose timestamp is greater than rcv base i [j], i.e., if m ∈ rcv win i [j] not all messages whose timestamp is smaller then m.ts were delivered by i. • ack set i : the set with all pending acks for process i.

For each message T REE, m received by process i from a process j and forward to process k, an element j, k, (m.src, m.ts) is added to this set; • msg set i : set of messages with pending ack at process i, used for retransmissions in case of faults; • delay msg i [n]: list of bundled messages waiting to be sent to the same destination process; • timer i [n]: for each neighbor j, timer i [j] controls the remaining time that i can keep a bundled message to be sent to j. When timer i [j] expires, i must forward the bundled message to j. The function STOP timer i [j] turns off the timer related to process j and the function START timer i [j] starts the timer of process j with the value of the parameter maxDelay.

The asterisk is used as a wildcard to select ACKs in the set ack set. An element j, * , m , for example, represents all pending acks for a message m received by process j and forward to any other process.

Source process i broadcasts message m by invoking the BROADCAST procedure, which calls HANDLE MESSAGE to handle m, with m.src identifying the source process and m.ts the message timestamp. The total message size is computed using the length(m) function based on the application data in the message (m.size) plus fields introduced by the broadcast layer.

In order to be able, in case of failure, to retransmit a previously sent message, every message T REE, m sent by i to its neighbors is temporarily kept in msg set i (line 11) while there exist pending acks for this message (line 84). Then, line 13, using rcv base i and rcv win i variables, verifies if m has not already been delivered by i, ensuring, therefore, the no duplication integrity property. If m is the first message received by i from m.src, i.e., rcv base i [m.src] = ⊥ or the messages has not been delivered yet (if it is the case, m.ts will be either smaller than rcv base i [m.src] or m ∈ rcv base i [m.src]), m is delivered (line 14) and the procedure UPDATE WINDOW is called (line 15) for updating rcv base i and rcv win i in order to guarantee that i will not deliver m again (Integrity property). Being m the first message received by i from m.src, if m is also the first message broadcast by m.src The maximum size of a set of bundled messages for all p = x, q = y, (src, ts) = z : x, y, z ∈ ack seti do 78:

if {src, p} correcti then 79:

Remove pending acks 80:

ack seti ← ack seti { p, q, (src, ts) }

81:

else if q = j then Send m to the new correct neighbor k, if exists 82:

if k = ⊥ and p, k, (src, ts) / ∈ ack seti then By calling the procedure FORWARD, message m is either forwarded to to every correct neighbor k or kept in a buffer to be latter forwarded to k (CHECK BUNDLE). Then, for each k, an ack j, k, (m.src, m.ts) is included in the set of pending acks (ack set i ). If i has no correct neighbor or it is a leaf of the spanning tree (cluster i (j) = 1), no ack is included in ack set i and the procedure is complete and i sends an ACK message to j by calling function CHECK ACKS (line 17).

Procedure CHECK BUNDLE is responsible for bundling and forwarding T REE and ACK messages of process i to process k. If the size of the message is equal or greater than the maximum size of the network packet, denoted as maxP ayload, the message is immediately sent (line 37). If the size of message m plus the size of those messages to k that have been delayed and kept in delay msg i [k] is greater than (resp. equal to) maxP ayload, the messages in delay msg When receiving message m of type T REE from process j (line 62), i will handle the message by calling HAN-DLE MESSAGE, provided that the source of m (m.src) and j are both correct. If it is not the case, the reception is aborted since if j is faulty, the process that sent m to j, when detecting j's crash will retransmit the message. Thus j and i will receive m through a new spanning tree that does not contain j. If m.src is faulty, it is not necessary to continue forwarding m since best effort broadcast does not guarantee that all correct processes will deliver m if m.src has failed. On the other hand, when a message ACK, (src, ts) is received by i, the set ack set i is updated and, if there are no more pending acks related to m : m.src = src, m.ts = ts, CHECK ACKS removes m from the set msg set i . If the process k, which has sent m to i, is not i itself and both the source of m and k are correct, then an ACK message is sent to k. If k = i, the latter is the source of m and the broadcast terminates.

Upon the detection that node j has crashed (CRASH event), (1) i updates the list of correct processes, (2) removes from the set ack set all the acks which have process j as the destination of or those that have j as the source of a message, and (3) retransmits to the first neighbor k of i in the same cluster of j, (if such a k exists) those messages sent to j that have not been acknowledge by it. These retransmissions to k will lead to other retransmissions over the newly rebuilt spanning tree.

The size of a message depends on its type. A T REE message contains, besides the data from the application (AP P ), a header H which is composed by the type of the message type as well as the identifier of the source process (src) and the timestamp of the message ts, as previously described. On the other hand, an ACK message contains just the header H composed by the type type and the necessary information to identify the message which is acknowledged, i.e. (src, ts). The difference of the sizes of the two types of messages is basically the size of the application message. Therefore, we have:

H = type, (src, ts) length(ACK) = length(H) length(T REE) = length(H) + length(AP P ) (3)
Note that the size of a bundled message is given by the sum of the size of messages T REE and ACK that it carries.

Performance Results

In this section we present the results of the simulation experiments comparing the proposed best-effort broadcast algorithm using bundling messages with the same algorithm without bundling. The algorithms were implemented using Neko [START_REF] Urbán | Neko: A single environment to simulate and prototype distributed algorithms[END_REF] 1 . The tests are divided in two parts. First the results are presented for fault-free scenarios, and then for scenarios with faulty processes. The use of multiple shared trees is presented in Section 6.2.

Simulation Parameters

For a process to send a message to more than one destination it executes primitive SEND sequentially to each destination in turn. For each message, t s time units are used to the send the message at the source and t r units to receive the message at the destination. The transmission delay t t refers to the time it takes to transmit the message on each communication channel.

To evaluate the performance of broadcast solutions, three metrics are used: (1) the latency to deliver the broadcast message to all the correct processes; (2) the total number of messages sent by the algorithm, including acknowledgments; and (3) the message sizes, in bytes. In each experiment a single message is broadcast at the beginning of the simulation.

The proposed algorithm was evaluated in scenarios with different numbers of processes and, in faulty scenarios, with different numbers of faulty processes. The time intervals were set as t s = t r = 0.1 and t t = 0.8 time units. The testing interval of the VCube is 30.0 units of time. In addition, a process is considered to be faulty if a reply does not arrive at the tester after 4 * (t s + t r + t t ) time units.

Five different scenarios were generated by varying the following parameters: (1) the maximum packet size of bundled messages; (2) the maximum delay for sending a packet;

(3) the size of T REE messages; and (4) the size of ACK messages. The parameters used in each scenario are shown in Table 1, in which each column represents one of the scenarios.

In the scenario (NO-AGGR), no message is bundled. To avoid changes to the algorithm, the maximum packet and message size of T REE and ACK has been set to 1, and the maximum delay is zero. In the other scenarios, the sizes of the messages and the delay for sending messages varied. In SMALL scenarios, the size of T REE is 24, slightly larger than that of ACK which is 20, representing applications that propagate little information, e.g. a value reported by a sensor. For BIG scenarios, the ACK size remains 20 and the T REE messages have size 500. The maximum delay was set to 2 or 10 time units and this is identified by the label of the scenario. In the SMALL2 scenario, for example, the maximum packet size is 1460, the T REE messages have size 24, and the maximum delay is 2. In the BIG10 1 The complete source code and configuration files are available at www.inf.unioeste.br/ ∼ luiz scenario, the maximum packet size is also 1460, the T REE messages have size 500, and the maximum delay is 10. For comparison purposes, the NO-AGGR scenario assumes message sizes equivalent to the compared scenario.

The Impact of Multiple Spanning Trees

In order to evaluate the proposed strategy on extreme scenarios we executed an experiment in which 16 processes broadcast messages on a varying number of trees. Each process broadcasts a single message using a fixed set of trees, for a total of 16 messages. Initially, a single tree is used by all processes, in this case all trees totally overlap, but the contention for using that tree increases. Then two trees are used, and so on until each process uses its own tree. The trees used in each scenario are employed processes with identifiers that are smaller than the number of trees, i. e., with one tree, p 0 's tree is used to send 16 messages; with two trees, p 0 and p 1 's trees are used, each one sending 8 messages. We only present scenarios in which the number of messages is divisible by 16 (the number of processes).

In Table 2 we present the latency and number of messages for each scenario, and the multiple trees employed. Results show that in the non-aggregation scenario (NO-AGGR) the latency decreases when multiple trees are used, reaching a reduction of more than 100% when each process uses its own tree. This is due to the contention for the root whenever a tree is shared by multiple processes, which is especially high in the scenario with a single tree, in which p 0 's tree is used by all the processes. Remember that in the proposed model, for each message sent there is a cost in terms of the processing time. The number of messages (TREE and ACK) of the non-aggregation scenarios is constant and equal to n(2n -2), since there are no failures. In scenarios with bundled messages the latency includes the delays for aggregating messages and the propagation in the tree. However, there is an advantage in sharing the trees in terms of the number of messages required, since the trees overlap multiple times.

Fault-Free Scenarios

Figure 3 shows the results obtained for systems of different sizes and without faulty processes. The latency represents the total time to complete the broadcast for all the processes in the five proposed scenarios, that is, the total simulation time considering that all processes execute a single broadcast. The number of messages shown was The scenario with no bundling presents lower latency in comparison with the scenarios with bundling for systems with fewer than 256 processes, although the number of messages is much higher. In scenario SMALL2 the application messages are small the latency and number of messages are the best of all scenarios. Also noticeable is that although SMALL10 presents the same latency as BIG10, it employed a significantly smaller number of messages. Note that the delays for sending the messages have a similar impact on the latency in the scenarios with bundling, regardless of the number of messages bundled per packet. However, it appears that the impact tends to decrease as the load increasing in systems with smaller messages systems (SMALL), as happened for the 1024 process scenarios. Figure 4(a) shows a comparison of the performance of the fault-free SMALL2 and BIG2 scenarios, in which p 0 executes broadcast with bundling in a system with 1,024 processes. Due to the smaller size of SMALL2 application messages, the number of messages that can be bundled in a single packet is higher, especially at the beginning of the simulation. For BIG2, blundling has a greater impact at the end of the simulation, as ACKs have smaller size. Still comparing the 1,024 processes for SMALL2 and BIG2 in terms of the size of the messages sent by the process p 0 , it can be observed in Figure 4(b) that SMALL2 is able to take better advantage of bundling given the packet size (1460 bytes) as the number of messages increases. However, BIG2 still shows good performance especially given ACK bundling.

In terms of the total of bytes transmitted, we compared SMALL2 and BIG2 with NO-AGGR scenarios. In fault-free systems with 1,024 processes, 2,046 messages per broadcast are generated (1,023 TREEs and 1,023 ACKs). Comparing SMALL2 with NO-AGGR using the message size parameters of Table 1 and a network with standard header of 40 bytes, this generates a header overhead of 2,095,104 * 40 = 80 Mb and 106,496 * 40 = 4 Mb, respectively. Note that the difference is reduced due to the effectiness of bundling in NO-AGGR with larger messages, which confirms the advantage of bundling for applications that exchange small messages frequently, as in the SMALL scenarios.

Faulty Scenarios

To evaluate the impact of failures on the proposed solution, experiments were performed simulating process crashes. Two types of experiments were performed. In the first, a single process fails at the beginning of the simulation; in the second experiment failures were generated randomly during the simulation. Fault of a single process. Initially process p 1 was set to fail at time t = 0.0, i.e., at the beginning of the simulation. The crash is detected by p 1 's VCube neighbors (p 0 , p 3 and p 5 ) and propagated according to the VCube strategy. Each process, upon detecting the crash of p 1 , performs the steps indicated by the CRASH event of the algorithm. New T REE messages are transmitted as the VCube reconfigures itself.

Table 4 compares the average number of messages (TREE and ACK) transmitted by each correct process in a fault-free execution (FF) and with faulty process p 1 (FY). In the scenario without bundling, each broadcast requires with one less message, i.e. the ACK that is not returned by the faulty process. Note that in the beginning of the simulation the processes do not yet know that p 1 is faulty and, therefore, the T REE messages are sent to it normally. The VCube detection latency causes an increase of the execution time in the faulty scenarios as shown in Table 3. Although it has an impact on all scenarios, VCube's latency is most evident in scenarios without bundling (NO-AGGR) or with small messages (SMALL2 and BIG2). In the SMALL10 and BGI10 scenarios the aggregation delay dominates the fault detection latency. Multiple Faults. Finally, multiple crashes were injected in the scenarios, where the number of faulty processes was equal to (log 2 n) -1. The faulty processes and the time at which the failures were generated were random. Each scenario was run with 10 different fault configurations. Table 5 shows the latency obtained. The number of messages was omitted due to lack of space and because the time instant a process fails has a direct impact on the number of messages sent, what is not useful without an in-depth analysis of each case. We observed a greater variation in latency for systems with smaller number of processes, since in these systems, the tree propagation latency is lower and the crash detection time has more impact on the total time. The confidence interval (CI) shows the impact that failures have on systems with a higher proportion of failed processes, as in scenarios with a smaller number of processes.

Conclusion

This paper presented an approach to bundle messages along spanning tree intersections which are frequently employed by broadcast algorithms. We proposed a best-effort broadcast algorithm with message bundling. This is an autonomous algorithm builds and dynamically maintains spanning trees rotted at each source process are on top of a VCube, a scalable topology which adapts itself after process crashes. Simulation results comparing the proposed solution with a alternative that does not bundle messages show the efficiency of the proposed strategy in fault-free and faulty scenarios, especially in terms of the number and size of the messages required. Future work includes adapting the algorithm for the asynchronous model, evaluting the impact of bundling messages on other types of broadcast (e.g. causal) and also implementing a TCP/IP broadcast tool based on the algorithm.

Figure 1 . 4 -

 14 Figure 1. 4-VCube hierarchical organization.

Set of messages with pending acks 4 : 11 :: else 23 :: else 27 :

 4112327 correcti = {0, .., n -1} Set of correct processes 5: ∀j ∈ 0..n -1 : rcv basei[j] ← ⊥ ts of the last message from j delivered in order 6: ∀j ∈ 0..n -1 : rcv wini[j] ← ∅ ts of the messages from j delivered out of order 7: ∀j ∈ F F neighbori(s) | s = 1.. log 2 n : delay msgi[j] = ∅, timeri[j] is turned off 8: procedure BROADCAST(message m) 9: HANDLE MESSAGE(T REE, m , i) 10: procedure HANDLE MSG(message T REE, m , process j) msg seti ← msg seti ∪ {m} 12: if rcv basei[m.src] = ⊥ or (m.ts > rcv basei[m.src] 13: and m / ∈ rcv wini[m.src]) then REE, m , j) 17: CHECK ACKS((m.src, m.ts), j) 18: procedure UPDATE WINDOW(message m) 19: if (rcv basei[m.src] = ⊥ then 20:if m.ts = 0 then 21: rcv basei[m.src] ← m.ts 22rcv wini[m.src] ← rcv wini[m.src] ∪ {m} 24: else if m.ts = rcv basei[m.src] + 1 then 25: rcv basei[m.src] ← m.ts 26rcv wini[m.src] ← rcv wini[m.src] ∪ {m} 28: while ∃ m ∈ msg win[m.src] | 29: m .ts = rcv basei[m.src] + 1 do 30: rcv basei[m.src] ← m .ts 31: rcv wini[m.src] ← rcv wini[m.src] {m } Forward m to all fault-free neighbors 32: procedure FORWARD(message T REE, m , process j) 33: for all k ∈ subtreei(m.src) do 34: CHECK BUNDLE( T REE, m , k) 35: ack seti ← ack seti ∪ { j, k, (m.src, m.ts) } 36: procedure CHECK BUNDLE(message T, c , process k) 37: if length( T, c ) ≥ maxP ayload then 38: SEND( T, c ) to p k 39: else if length(delay msgi[k] ∪ T, c ) > maxP ayload then 40: SEND(delay msgi[k]) to p k 41: delay msgi[k] ← { T, c } 42: stop timeri[k] 43: else if length(delay msgi[k] ∪ T, c ) = maxP ayload then 44: SEND(delay msgi[k] ∪ { T, c }) to p k 45: delay msgi[k] ← ∅ 46: stop timeri[k] 47: else 48: delay msgi[k] ← delay msgi[k] ∪ { T, c } 49: if timeri[k] is off and delay msgi[k] = ∅ then 50: start timeri[k] 51: procedure CHECK ACKS(ack (src, ts), process k) 52: if ack seti ∩ { k, * , (src, ts) } = ∅ then 53: msg seti ← msg seti {m} : m.src = src, m.ts = ts 54: if k = i and {src, k} ⊆ correcti then 55: CHECK BUNDLE( ACK, (src, ts) , k) 56: upon RECEIVE (set< T, c > msgs) from pj 57: for all T, c ∈ msgs do 58: if T = T REE then 59: RECEIVE( T REE, m = c , j) 60: else if T = ACK then 61: RECEIVE( ACK, (src, ts) = c , j) 62: procedure RECEIVE(message T REE, m , process j) 63: if {m.src, j} correcti then 64: return 65: HANDLE MSG( T REE, m , j) 66: procedure RECEIVE(message ACK, (src, ts) , process j) 67: k ← x : x, j, (src, ts) ∈ ack seti 68: ack seti ← ack seti { k, j, (src, ts) } 69: CHECK ACKS((src, ts), k) 70: upon timeri[k] expiration 71: SEND(delay msgi[k]) to p k 72: delay msgi[k] ← ∅ 73: upon notifying CRASH(process j) j is detected as faulty 74: correcti ← correcti {j} 75: delay msgi[j] ← ∅; stop timeri[j] 76: k ← F F neighbori(clusteri(j))77:

83 : 8 Figure 2 .

 8382 Figure 2. Examples of spanning trees in a 4-VCube.

  i [k] (resp. delay msg i [k] and m) are sent to k, delay msg i [k] will keep just m (resp. no message) and the timer timer i [k] is stopped. Otherwise, m is included in delay msg i [k]. Then if the timer timer i [k] has been stopped, it will be restarted to maxDelay. Upon the expiration of timer i [k] (line 70), the messages in delay msg i [k] are sent within a single packet to k.

Figure 3 .

 3 Figure 3. Latency and average number of messages to broadcast one message per process in a fault-free execution.

Figure 4 .

 4 Figure 4. Number of bundled messages and message sizes at process p 0 in the SMALL2 and BIG2 scenarios with 1024 processes (fault-free execution).

  Algorithm 2 Best-Effort Broadcast with Bundling Messages at process p i Require: maxDelay Maximum time a message can be delayed Require: maxP ayload

TABLE 1 .

 1

	SCENARIO CONFIGURATION PARAMETERS
		NO-AGGR SMALL2 BIG2 SMALL10 BIG10
	Maximum packet length	1	1460 1460	1460	1460
	TREE message length	1	24	500	24	500
	ACK message length	1	20	20	20	20
	Maximum delay	0	2	2	10	10

TABLE 2 .

 2 LATENCY (LAT.) AND NUMBER OF MESSAGES (#MSG) USING MULTIPLE TREES WITH 16 PROCESSES

		NO-AGGR SMALL2	BIG2	SMALL10 BIG10
	Trees Lat. #msg Lat. #msg Lat. #msg Lat. #msg Lat. #msg
	1	14.7 480 24,7	30 25,5 168 88.7	30 88.7 162
	2	11.6 480 24,7	60 24,7 188 88.7	60 88,7 190
	4	9.0 480 24,7 104 24,7 192 88.7 104 88.7 192
	8	7.2 480 24,7 176 24,7 192 88.7 176 88.7 192
	16	6.1 480 24,7 272 24,7 304 88.7 272 88.7 304
	computed as the average number of messages sent by each
	process.

TABLE 3 .

 3 LATENCY TO FAULT-FREE (FF) AND ONE-FAULTY PROCESS (FY) SCENARIOS

	Number of	NO-AGGR	SMALL2	BIG2	SMALL10	BIG10
	Processes	FF	FY	FF	FY	FF	FY	FF	FY	FF	FY
	8	6.5	12.8	18.5 24.8	18.5	24.8	66.5	66.6	66.5	66.6
	16	8.7	15.4	24.7 31.1	24.7	31.1	88.7	88.8	88.7	88.8
	32	11.2	18.4	30.9 37.4	30.1	36.5	110.9 111.0	110.9 111.0
	64	17.6	23.3	37.1 43.7	36.2	42.7	133.1 133.2	133.1 133.2
	128	30.3	35.0	43.3 49.8	42.6	48.8	155.3 155.4	155.3 155.6
	256	55.8	66.2	49.5 56.0	50.4	56.9	177.5 177.6	177.5 177.8
	512	106.9 125.8	55.4 61.8	63.8	72.7	199.7 199.9	199.7 200.2
	1,024	209.2 243.9	58.4 67.8	92.6 104.2	214.4 222.3	224.8 231.9

TABLE 4 .

 4 NUMBER OF MESSAGES IN FAULT-FREE (FF) AND ONE-FAULTY PROCESS (FY) SCENARIOS

	Number of	NO-AGGR	SMALL2	BIG2		SMALL10	BIG10
	Processes	FF	FY	FF	FY	FF	FY	FF	FY	FF	FY
	8	112	91	80	67	80	67	80	59	80	59
	16	480	435	272	247	304	273	272	235	304	256
	32	1,984	1,889	800	766	1,024	981	800	749	1,024	952
	64	8,064	7,860	2,240	2,191	3,584	3,429	2,240	2,167	3,520	3,349
	128	32512	32,079	6,016	5,947	11,904	11,635	6,016	5,917	12,032	11,742
	256	130,560	129,643	15,104	15,019	42,240	41,624	15,104	14,985	42,240	41,802
	512	523,264	521,350	39,424	38,639	155,136 153,280	40,448	40,032	155,136 154,020
	1,024	2,095,104 2,091,167	106,496 105,188	587,776 580,983	100,352 100,580	581,632 576,723

TABLE 5 .

 5 LATENCY TO MULTIPLE FAULTS WITH 95% CONFIDENCE INTERVAL (CI)

	Number of	NO-AGGR	SMALL2	BIG2		SMALL10	BIG10
	Processes	Avg.	CI	Avg.	CI	Avg.	CI	Avg.	CI	Avg.	CI
	8	22.2 11.5	32.3 10.6	32.3 15.5	72.5	6.2	72.5	6.2
	16	35.9	9.8	50.8 10.1	50.8 19.2	109.5 10.8	110.1 10.5
	32	62.0	6.0	80.7	5.9	80.7 23.2	154.3	5.9	154.2	6.3
	64	63.0	3.5	84.8	3.6	84.8 24.2	176.2	3.8	175.7	4.1
	128	70.1	2.4	89.8	2.7	89.7 24.2	196.1	3.0	197.2	3.2
	256	85.2	0.4	90.6	0.2	91.5 22.2	212.0	0.3	213.4	0.5
	512	129.4	0.1	96.3	0.1	103.5 19.1	233.3	0.0	233.4	0.0
	1,024	247.0	0.3	102.1	0.0	129.4 14.7	255.3	0.2	267.6	0.3

Acknowledgment

This work was partially supported by grants Fundac ¸ão Araucária/SETI 341/10 and CNPq-309143/2012-8.