J.-P Poli
email: poli_jp@univ-corse.fr

E Guinoiseau

A Luciani

Y Yang

M.-J Battesti

J Paolini

J Costa

Y Quilichini

L Berti

V Lorenzi

Jean-Pierre Poli

Key role of hydrogen peroxide in antimicrobial activity of spring, Honeydew maquis and chestnut grove Corsican honeys on Pseudomonas aeruginosa DNA

Keywords: antimicrobials, honey, mechanism of action, oxidation, pseudomonas

HAL is

Introduction

thousand times higher than usual values (10 8 /10 9 ) [START_REF] Maci A | Hypermutation is a key factor in development of multiple-antimicrobial resistance in Pseudomonas aeruginosa strains causing chronic lung infections[END_REF]. Its ability to form biofilms on inert surfaces such as rock or medical apparatus further enhances its resistance [START_REF] Stover | Complete genome sequence of Pseudomonas aeruginosa PAO1, an opportunistic pathogen[END_REF][START_REF] Campeau | Antibiofilm activity of Manuka honey in combination with antibiotics, antibiofilm activity of Manuka honey in combination with antibiotics[END_REF].

Pseudomonas aeruginosa is a very common cause of nosocomial diseases, from 11 to 13Á8% worldwide, and more in intensive care units, where infection rates range

Pseudomonas aeruginosa is a Gram-negative bacterium found in soil, coastal marine habitats and marshes. It is known to be multidrug-resistant, notably due to its ability to acquire new resistance to antibacterial agents [START_REF] Roberts | Manuka honey is bactericidal against Pseudomonas aeruginosa and results in differential expression of oprF and algD[END_REF]. Its spontaneous mutation rate can be up to a from 13Á2 to 22Á6%. It is the second most frequent cause of hospital-acquired, ventilator-and healthcare-associated pneumonia, after Staphylococcus aureus infections [START_REF] Driscoll | The epidemiology, pathogenesis and treatment of Pseudomonas aeruginosa infections[END_REF]. Researchers are currently seeking naturally occurring substances to produce new antibiotics or agents able to restore antibiotic action towards this bacterium.

The antibacterial activity of honeys can be attributed to various factors. In most samples, it relies greatly on levels of hydrogen peroxide (H 2 O 2 ) [START_REF] Brudzynski | Effect of hydrogen peroxide on antibacterial activities of Canadian honeys[END_REF], which is, along with gluconic acid, a by-product of glucose oxidation by the bee enzyme glucose oxidase (FAD-oxidoreductase, EC 1.1.3.4). Water plays a key role in the reaction, facilitating the enzyme's access to its substrate. Hydrogen peroxide production in diluted honeys is known to produce a long-lasting antiseptic effect [START_REF] Manzoori | Application of crude extract of kohlrabi (Brassica oleracea gongylodes) as a rich source of peroxidase in the spectrofluorometric determination of hydrogen peroxide in honey samples[END_REF]. However, some New Zealand Manuka honeys have been shown to maintain their growth inhibitory levels even after removal of hydrogen peroxide [START_REF] Molan | Non-peroxide antibacterial activity in some New Zealand honeys[END_REF]. Antibacterial action of those honeys was later related to methylglyoxal [START_REF] Molan | The Antibacterial Activity of Honey[END_REF]). Nonperoxide activity is mostly due to acidity, osmolarity [START_REF] Wahdan | Causes of the antimicrobial activity of honey[END_REF][START_REF] Molan | The Antibacterial Activity of Honey[END_REF] or phenolic compounds [START_REF] Aljadi | Isolation and identification of phenolic acids in Malaysian honey with antibacterial properties[END_REF]. Phenolic compounds are widespread in plants, being their most abundant secondary metabolites (over 8000 phenolic structures already discovered). They are known to be involved in defence against aggression by pathogens [START_REF] Dai | Plant phenolics: extraction, analysis and their antioxidant and anticancer properties[END_REF]. Antibacterial activity can also be expressed by the action of antimicrobial peptides such as bee-defensin-I ( [START_REF] Kwakman | How honey kills bacteria[END_REF].

In a previous study, we tested the antibacterial activity of some protected designation of origin 'Miel de Corse -Mele di Corsica' Corsican honey samples on several strains [START_REF] Poli | Investigating the antibacterial action of Corsican honeys on nosocomial and foodborne pathogens[END_REF]. We showed that P. aeruginosa was very sensitive to some Corsican honeys. So, the work reported here focus on this particular strain: we set out to make a more thorough study of the entities involved and their mechanisms of action on this bacterium at the cell level.

Results and discussion

Antibacterial activity of 'spring', 'chestnut grove' and 'honeydew maquis' honeys on P. aeruginosa Minimal inhibitory concentration (MIC 90 ) values of 'spring' (SPR), 'chestnut grove' (CG) and 'honeydew maquis' (HDM) samples for P. aeruginosa are given in Table 1: MIC 90 is the concentration of diluted honey that inhibits 90% of the bacterial growth.

Corsican honeys might offer a way to help fight the highly resistant strain P. aeruginosa. Indeed, both CG and HDM Corsican honeys were particularly active on this Gram-negative bacterium: measured MIC 90 values (7 or 8%) were below those obtained with different Manuka honeys (12Á5 or 14%) [START_REF] Alzahrani | Antibacterial and antioxidant potency of floral honeys from different botanical and geographical origins[END_REF][START_REF] Ku S | Activity of polish unifloral honeys against pathogenic bacteria and its correlation with colour, phenolic content, antioxidant capacity and other parameters[END_REF]. Their activity was also higher than in acacia, lavender or wild carrot honeys (respectively 13, 21 and 12%) [START_REF] Alzahrani | Antibacterial and antioxidant potency of floral honeys from different botanical and geographical origins[END_REF], and in Gelam, Kelulut, pineapple and Tualang Malaysian honeys (respectively 10, 20, 25 and 12Á5%) [START_REF] Zainol | Antibacterial activity of selected Malaysian honey[END_REF]. Despite a lower antimicrobial activity with an MIC value of 13%, SPR can still be considered as moderately active according to the literature. These results are supported by scanning electron microscopy (SEM) observations of CG 2 (Fig. 1).

Compared with the homogenous and very dense flora of the control (Fig. 1a), bacterial cells observed in the presence of CG 2 at its MIC 90 were dispersed throughout the support (Fig. 1b). However, no morphological alteration or structural damage appeared on micrographs. Furthermore, when honey concentration reached 2 MIC 90 , P. aeruginosa cells were no longer able to survive (Fig. 1c). Similar results were observed in SEM micrographs of CG 1, HDM 1, HDM 2 and SPR (data not shown). As previously described in the literature (Brudzynski et al. 2012a), we investigated the putative link between the cell death observed and DNA damage.

P. aeruginosa plasmidic DNA degradation

As shown in Fig. 2, after incubating P. aeruginosa with active honeys diluted to their MIC 90 values, we observed plasmid DNA degradation.

The control shows a visible fragment of DNA corresponding to c. 23 kb of undamaged plasmid [START_REF] Raja | Plasmid profile and curing analysis of Pseudomonas aeruginosa as metal resistant[END_REF]. Moreover, this DNA was digested by EcoRI restriction enzyme showing three visible strips and no sign of smear. In the presence of MIC 90 diluted honeys, a smear of lower intensity was identified under the control fragment. These phenomena were mostly visible for CG 2 and HDM 1, which had similar amounts of hydrogen peroxide (Table 1). The appearance of a smudge of small DNA fragments is known to indicate that its degradation has involved irreparable double-strand cuts, which are lethal for the cell (Brudzynski et al. 2012a). Also, incubating P. aeruginosa at twice the MIC 90 values showed no visible strip (data not shown).

In honeys, key factors in DNA damage are reactions of phenolic auto-oxidation and production of radical oxygen species (ROS) involving hydrogen peroxide as a central entity (Brudzynski et al. 2012b): MIC 90 values rose to 25% (Table 1) when H 2 O 2 was removed by catalase in in the moderately active (SPR) honey: the total phenolic content ranged from 73Á62 mg gallic acid equivalent (GAE)/100 g of honey in HDM 1, to 86Á15 mg GAE/ 100 g of honey in HDM 2, whereas only 24Á07 mg GAE/100 g of honey was detected in SPR. These results are in agreement with those of [START_REF] Ciappini | Determination of antioxidant capacity, flavonoids, and total phenolic content in eucalyptus and clover honeys[END_REF], although the overall range was greater (5-265 mg GAE/100 g of honey in various clover and multifloral honeys from Chile and Czech Republic). ORAC assay values lay between 5Á89 lmol l À1 of trolox equivalents (TE)/g of honey for CG 1 and 8Á6 lmol l À1 TE/g of honey in HDM 2. In SPR, ORAC values were significantly lower (2Á76 lmol l À1 TE/g of honey). So, CG and HDM honeys have higher antioxidant capacity than SPR honey. The same range of ORAC values were found for monofloral honeys of clover (5Á37 lmol l À1 TE/g of honey), blueberry (4Á59 lmol l À1 TE/g of honey) or borage (1Á99 lmol l À1 TE/g of honey) (Brudzynski et al. 2012b). ORAC assay was preferred to the hydroxyl radical generating activity. Indeed, Brudzynski et al. (2012a) showed that it isn't possible to conclusively identify ˙OH radicals as the inducers of bacterial cell death.

According to [START_REF] Dai | Plant phenolics: extraction, analysis and their antioxidant and anticancer properties[END_REF], under conditions that favour their auto-oxidation (high pH with high concentrations of transition metal ions and molecular oxygen) phenolic antioxidants behave like pro-oxidants. Despite a high antioxidant capacity (ORAC, Table 2), the high content of hydrogen peroxide in active honeys, which induces an elevated amount of ROS, explains the pro-oxidant behaviour of phenolic compounds. It seems that the presence of these two types of entity confers antibacterial activity on Corsican honeys via plasmid DNA degradation.

In conclusion, we showed that P. aeruginosa is sensitive to several Corsican honeys. Indeed, CG and HDM honeys are the most active (MIC 90 value between 7 and [START_REF] Bogdanov | Minerals in honey: environmental geographical and botanical aspects[END_REF], produces hydroxyl radicals. These radicals are generated via a Fenton reaction (H 2 O 2 + Cu + or Fe 2+ ? Cu 2+ or Fe 3+ + OH + ·OH À ) and are, according to the literature [START_REF] Storz | Oxidative stress[END_REF], more often responsible for DNA damage than endogenous H 2 O 2 . Moreover, hydrogen peroxide hydrolysis also produces oxygen, which speeds up auto-oxidation processes of polyphenols with simple structures like coumarin identified in some honeys [START_REF] Cowan | Plant products as antimicrobial agents[END_REF]Jerkovic et al. 2011). Those kind of molecules are known to exert antibacterial and fungicidal activities [START_REF] Cowan | Plant products as antimicrobial agents[END_REF] because they tend to lose their antioxidant capacity and become pro-oxidant. Table 2 represents the concentration of phenolic compounds and oxygen radical absorbent capacity (ORAC) assay values in Corsican honeys.

In both cases, they were significantly higher in the active honeys (CG 1, CG 2, HDM 1 and HDM 2) than 8%), while SPR honey can be considered as a moderately active honey (MIC 90 value equal to 13%). Their antibacterial efficiency seems to arise from an interaction between hydrogen peroxide and phenolic compounds. However, H 2 O 2 is a key factor in phenolic compound auto-oxidation and in Fenton's reaction, which lead to reactive oxygen species formation. These ROS may be responsible for the P. aeruginosa plasmid degradation we highlight in this work. Since SEM micrographs showed no morphological degradation, this mechanism of action could be involved in Corsican honeys antibacterial activity. An in-depth study is now required to establish the complete phenolic profile for all the honeys and so identify active entities.

Materials and methods

Honey samples

Five honey samples from the year 2014, one 'spring' (SPR), two 'chestnut grove' (CG 1 and CG 1) and two HDM 1 and HDM 2, were purchased commercially from local apiarists and stored in darkness at 4°C. Sensory analyses were performed to check good conservation.

Bacterial strains and growth conditions

The in vitro antibacterial activity of Corsican honeys was tested against a laboratory-controlled strain of P. aeruginosa (CIP A22) routinely grown at 37°C on Mueller-Hinton 2 Agar (BioM erieux, Marcy l'Etoile, France).

Antibacterial assay

The antibacterial activity was expressed as the minimum inhibitory concentration (MIC) of honey that reduced bacterial growth spectrophotometrically by 90%. The test was adapted from [START_REF] Zainol | Antibacterial activity of selected Malaysian honey[END_REF] with slight modifications. Working bacteria culture was adjusted to be equal to 0Á5 McFarland standard (10 8 CFU per ml), and further diluted 200-fold in Mu€ eller-Hinton broth (MHB, oxoid) to reach 0Á5 9 10 6 CFU per ml. Honey samples were diluted (from 50 to 1%) in MHB and then filtered through 0Á2 lmol l À1 filters (Sartorius AG, G€ ottingen, Germany). A volume of 190 ll of each honey dilution was aseptically transferred into 96-well microplates (Nunc TM , Roskilde, Denmark) with eight replicates per dilution. The first two wells of each honey dilution served as dilution sterility controls (supplemented with another 10 ll of the respective honey dilution); six others were the test wells, in which 10 ll of bacteria culture was mixed. The last two rows were reserved for batch sterility (200 ll of MHB) and growth (10 ll of bacterial culture in 190 ll of MHB) controls. Plates were incubated in a shaker incubator (Stuart, Stone, UK) at 120 rev min À1 , at 37°C for 18-24 h. The absorbance of the wells was read at 620 nm using a microtitre plate reader (Sunrise, Tecan TM ) after incubation. Percentage bacterial growth inhibition was calculated using the following formula: Throughput (HTP) Assay Innovotech Inc., Edmonton, AB, Canada) was fitted. These pegs allow bacterial development in a biofilm. The microplates were shaken at 37°C for 36 h. The pegs were immersed in 2Á5% glutaraldehyde (Electron Microscopy Science TM , Hatfield, PA, USA) fixing solution in sodium cacodylate (Sigma-Aldrich TM , Saint-Louis, MO, USA) buffer 0Á1 mol l À1 (pH 7Á2) for 2-3 h at 4°C; they were washed in two successive 10 min baths of sodium cacodylate buffer, dried out for 120 h, and then metallized using a gold/palladium mixture. The pegs were then examined under a scanning electron microscope (Hitachi TM s-3400n, Tokyo, Japan) with an accelerating voltage of 5 or 10 kV. Each experiment was performed in triplicate. Scanning electron microscopy micrographies are a representation of the homogenous observation of the entire pegs surface.

Plasmid DNA extraction

Bacteria cultures adjusted to 10 7 CFU per ml were incubated overnight, and shaken at 37°C in MHB with most active honeys used at concentrations of MIC and 2 9 MIC. Plasmid DNA was isolated using Quantum â prep plasmid miniprep kit (Bio-Rad TM , Hercules, CA, USA) following the manufacturer's instructions.

Agarose gel electrophoresis

Aliquots of plasmid DNA (30 ll) were analysed by agarose gel (1%) electrophoresis with ethidium bromide in Tris base, acetic acid and EDTA 1X. Migration was ORAC (lmol l À1 ol TE/ g of honey)

Moderately active honey

SPR 24Á07 c AE 1Á2 2 Á76 c AE 0Á28 Active honeys CG 1 76Á01 b AE 3Á8 5 Á89 b AE 1Á03 CG 2 78Á41 b AE 3Á92 6Á98 b AE 1Á47 HDM 1 73Á62 b AE 3Á68 7Á2 ab AE 0 HDM 2 86Á15 a AE 4Á31 8Á6 a AE 0
CG 1, chestnut grove 1; CG 2, chestnut grove 2, SPR, spring; HDM 1, honeydew maquis 1; HDM 2, honeydew maquis 2.

Lowercase letters indicate significant differences between experimental conditions for total phenolic content (concentration) or ORAC (concentration) assays according to a Kruskal-Wallis test at the 95% confidence level.

1À ðabsorbance of test well À absorbance of corresponding control wellÞ ðabsorbance of assay growth control À absorbance of sterility controlÞ Â100

Each experiment was performed in triplicate.

Scanning electron microscopy

Scanning electron microscopy allowed the behaviour of bacteria to be observed in solution with honey samples. For this purpose, 7Á5 ll of each honey dilution was placed in a 96well microplate containing 142Á5 llof a0Á5 McFarland standard diluted to reach 0Á5 9 10 6 CFU per ml. A plastic lid with 96 identical pegs protruding downward (MBEC TM High carried out at 85 V for 40 min. Plates were examined under UV light. EcoRI restriction enzyme was used as a digestion control of untreated plasmid.

H 2 O 2 assay and catalase treatment Hydrogen peroxide in honey was measured with the Amplex â Red hydrogen peroxide/peroxidase assay kit (Molecular Probes, Invitrogen, Burlington, ON, Canada).

The assay detects H 2 O 2 using Amplex Red reagent (10acetyl-3,7-dihydroxyphenoxasine), which reacts with hydrogen peroxide to produce the red fluorescent oxidation product resorufin. The assay was conducted according to the manufacturer's instructions. Fluorescence was measured with a spectrofluorimeter (FMP-850, Jasco TM Oklahoma City, OK, USA) at an emission wavelength of 590 nm using an excitation wavelength of 545 nm. The H 2 O 2 standard curve was plotted using dilutions of a 100 lmol l À1 stock solution. Similarly, 40% honey dilutions were prepared extemporaneously [START_REF] Bucekova | Honeybee glucose oxidase-its expression in honeybee workers and comparative analyses of its content and H 2 O 2 -mediated antibacterial activity in natural honeys[END_REF], and were incubated with Amplex Red reagent for 30 min in the dark at room temperature. The blank was included in each plate and subtracted from the experimental measurements. Data were analysed with Jasco TM SPECTRAMANAGER software. Statistical analyses were performed using R statistical software (www.R-project.org). Multiple mean comparisons were performed with the Kruskal-Wallis test at the 95% confidence level. Honeys of known H 2 O 2 concentration from Amplex Red assays were treated with catalase (Sigma-Aldrich TM ) at a ratio of 1000 U ml À1 for 2 h at room temperature. Catalase-treated honey samples were then used in the antibacterial assay to determine the MIC. Each experiment was performed in triplicate.

Total soluble phenolic content

To determine the total soluble phenolic content in honey samples, a phosphowolframate-phosphomolybdate complex was reduced to blue products by the action of phenolic compounds [START_REF] Ciappini | Determination of antioxidant capacity, flavonoids, and total phenolic content in eucalyptus and clover honeys[END_REF]. Distilled water was used to obtain 25 ml of diluted honey sample (4Á0 AE 0Á01 g), which was then filtered through Whatman No. 1 paper. To 1 ml of this solution,10 ml of distilled water with 1 ml of Folin-Ciocalteu reagent (Sigma-Aldrich) was added, and the mixture shaken gently. After 2 min, saturated sodium carbonate solution (2 ml) was added to the mixture, which was then adjusted to 25 ml with distilled water. The absorbance of the solution was read at 725 nm in a spectrophotometer (UV-1200, UVisco Jasco TM ) after incubation in the dark at room temperature for 2 h. The calibration curve was plotted with gallic acid as standard. The mean of three readings was used and expressed as milligrams of GAE per 100 g of honey. Statistical analyses were performed using R statistical software (ver. 2.13.1, www.R-project. org). Multiple mean comparisons were performed with the Kruskal-Wallis test at the 95% confidence level. Each experiment was performed in triplicate.

Oxygen radical absorbance capacity (ORAC) assay

The ORAC assay was carried out according to the method described by Dudonn e et al. (2009). The reaction was run in 75 mmol l À1 phosphate buffer (pH 7Á4) in black 96well microplates (Greiner Bio-One, Kremsm€ unster, Austria) at 37°C on a Tecan Infinite â 200 PRO multimode reader (Tecan Group Ltd., M€ annedorf, Switzerland). Trolox (0-10 lmol l À1 final concentration) was used as standard; 25 ll of honey solutions (0Á1-1 mg ml À1 final concentration) or trolox were mixed with 150 ll of fluorescein (70 nmol l À1 final concentrations) in the microplate and incubated for 20 min at 37°C; 75 ll of APPH solution (12 mmol l À1 final concentration) was then injected, and the fluorescence was measured every minute for 90 min at excitation and emission wavelengths 485 and 530 nm respectively. All samples were analysed in triplicate, and the ORAC values were expressed in lmol TE/g of honey. Statistical analyses were performed using R statistical software (www.R-project.org). Multiple mean comparisons were performed with the Kruskal-Wallis test at the 95% confidence level. Each experiment was performed in triplicate.

Figure 1

 1 Figure 1 Scanning electron micrographies of Pseudomonas aeruginosa growth in absence (control: a) or in presence of CG 2 honey at MIC90 (b) and twice MIC90 (c). Scale bar = 5 lm.

Figure 2

 2 Figure 2 Action of 'Chestnut grove' (CG1 and CG2), 'Honeydew maquis' (HDM1 and HDM2) and 'Spring' (SPR) Corsican honeys on Pseudomonas aeruginosa plasmidic DNA (Ctrl: control; EcoRI: P. aeruginosa plamisdic DNA digested by EcoRI restriction enzyme).

Table 1

 1 MIC 90 values and hydrogen peroxide concentrations obtained before and after catalase treatment five tested honeys, neutralizing their antibacterial efficiency. This data demonstrate the importance of hydrogen peroxide in antimicrobial activity. As shown in Fig.2, the addition of catalase to the tested honeys showed a strip with the same size as the control, demonstrating that removing hydrogen peroxide abolished the antibacterial action. Measured concentrations of H 2 O 2 (Table1) provide further evidence: the hydrogen peroxide content did not differ substantially in the active CG and HDM honeys (from 47Á6 lmol l À1 to 54 lmol l À1 ), but was significantly lower in the moderately active SPR honey (23 lmol l À1 ). Similar concentrations were found in moderately active Brassica napus and Castanea sativa honeys with H 2 O 2 concentration close to 40 lmol l À1 (MIC 90 values: 20%;[START_REF] Bucekova | Honeybee glucose oxidase-its expression in honeybee workers and comparative analyses of its content and H 2 O 2 -mediated antibacterial activity in natural honeys[END_REF]). These levels were still far from the H 2 O 2 concentration in Abies alba active honeys, ranging around 200 lmol l À1 for a 10% MIC 90 value.Metal-catalysed H 2 O 2 degradation by ions such as Cu + or Fe 2+ , naturally present in honeys

		MIC 90	MIC 90 P. aeruginosa after	Hydrogen peroxide	Hydrogen peroxide after
	Honeys	P. aeruginosa (%)	catalase treatment (%)	(lmol l À1 )	catalase treatment (lmol l À1 )
	Moderately active honey
	SPR	13	25	23 c AE 1Á15	1Á09 9 10 À2 a AE 0Á02
	Active honeys
	CG 1	7	25	47Á6 b AE 2.38	1Á99 9 10 À2 a AE 0Á002
	CG 2	8	25	52Á4 a AE 2.62	2Á96 9 10 À2 a AE 0Á01
	HDM 1	7	25	54 a AE 2.7	5Á84 9 10 À2 a AE 0Á01
	HDM 2	8	25	50 ab AE 2.5	4Á13 9 10 À2 a AE 0Á02
	CG 1, chestnut grove 1; CG 2, chestnut grove 2, SPR, spring; HDM 1, honeydew maquis 1; HDM 2, honeydew maquis 2.
	Lowercase letters indicate significant differences between experimental conditions for hydrogen peroxide (concentration) according to a Kruskal-
	Wallis test at the 95% confidence level.

the

Table 2

 2 Total phenolic content and radical scavenging activity of Corsican honeys

		Total phenolic
		content (mg gallic
		acid equivalent/100 g
	Honeys	of honey)

Acknowledgements

The authors are indebted to the 'Collectivit e Territoriale de Corse'.

Conflict of Interest

No conflict of interest declared.


Silvia Bonomi
email: bonomi@diag.uniroma1.it

Giovanni Farina
email: giovanni.farina@lip6.fr

Sébastien Tixeuil
email: sebastien.tixeuil@lip6.fr

Multi-hop Byzantine Reliable Broadcast with Honest Dealer Made Practical

We revisit Byzantine tolerant reliable broadcast with honest dealer algorithms in multi-hop networks. To tolerate Byzantine faulty nodes arbitrarily spread over the network, previous solutions require a factorial number of messages to be sent over the network if the messages are not authenticated (e.g. digital signatures are not available). We propose modifications that preserve the safety and liveness properties of the original unauthenticated protocols, while highly decreasing their observed message complexity when simulated on several classes of graph topologies, potentially opening to their employment.

Introduction

Designing dependable and secure distributed systems and networks, that are able to cope with various types of adversaries (ranging from simple errors to internal or external attackers), requires to integrate those risks from the very early design stages. The most general attack model in a distributed setting is the Byzantine model, where a subset of system participants may behave arbitrarily (including malicious), while the rest of participants remains correct. Also, reliable communication primitives are a core building block of any distributed system.

We consider the reliable broadcast with honest dealer problem in presence of Byzantine failures i.e., the problem of distributing information from a source to every other process considering that a subset of nodes may act arbitrarily. The reliable broadcast primitive is expected to provide two guarantees: (i) safety i.e., every message m delivered by a correct node has been previously sent by the source and (ii) liveness i.e., every message m sent by a correct source is eventually delivered by every correct node.

We are interested in solving this problem in a multi-hop network, in which nodes are not directly connected to every other (i.e. the network is not complete). In particular, nodes may have to rely on intermediate ones (hops) in order to communicate, forwarding messages till the final destination. In case the entire system is correct the solution to reliable broadcast is trivial: every node has just to forward the received messages to all of its other neighbors (or it has to question a routing table to know which is the next node to route a specific message) and if the network is connected then it is possible for every node to communicate with every other. Contrarily, if just one single node is faulty, specifically Byzantine faulty, two problems may arise: (i ) messages can be modified or generated by faulty nodes that pretend the messages were sent from another node (ii ) and messages can be blocked preventing nodes to communicate. It follows that a more sophisticated protocol has to be put in place to ensure the correct communication between the parties.

Lastly, we are interested in unauthenticated solutions, namely in protocols where messages cannot be directly authenticated (e.g. employing digital signatures) and thus the nodes cannot immediately verify that a specific received message has been previously sent by a specific other node.

The reliable broadcast with honest dealer enables to simulate a completely connected distributed system equipped with reliable and authenticated channels. It follows that all the solutions designed for completely connected distributed system (Byzantine Agreement, Byzantine Reliable Broadcast etc.) can be directly deployed on top of a multi-hop network once the reliable broadcast service has been deployed.

Related Works

The necessary and sufficient condition to solve the reliable broadcast with honest dealer problem on general networks has been identified by Dolev [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF], demonstrating that it can be solved if and only if the network is 2f `1connected, where f is the maximum number of Byzantine faulty nodes. Subsequently, research efforts followed three paths: (i) replacing global conditions with local conditions, (ii) employing cryptographic primitives, or (iii) considering weaker broadcast specifications.

The Certified Propagation Algorithm (CPA) [START_REF] Pelc | Broadcasting with locally bounded byzantine faults[END_REF] is a protocol that solves reliable broadcast in networks where the number of Byzantine nodes is locally bounded, i.e., in any given neighborhood, at most f processes can be Byzantine. This algorithm has been later extended [START_REF] Pagourtzis | Reliable broadcast with respect to topology knowledge[END_REF] along several directions: (i ) considering different thresholds for each neighborhood, (ii ) considering additional knowledge about the network topology, and (iii ) considering the general adversary model.

The Byzantine tolerant reliable broadcast with honest dealer can also be addressed employing cryptography (e.g., digital signatures) [START_REF] Castro | Practical byzantine fault tolerance and proactive recovery[END_REF][START_REF] Drabkin | Efficient byzantine broadcast in wireless ad-hoc networks[END_REF] that enables all nodes to exchange messages guaranteeing authentication and integrity (authenticated protocols). The main advantage is that the problem can be solved with simpler solutions and weaker conditions (in terms of connectivity requirements). However, on the negative side, most of those solutions rely on a third party that handles and guarantees the cryptographic keys, thus the safety of those protocols is bounded to the crypto-system (a potential single point of failure).

Lastly, the broadcast problem has been considered weakening safety and/or liveness property e.g., allowing to a (small) part of correct processes to either deliver fake messages, or to never deliver a valid message [START_REF] Maurer | Byzantine broadcast with fixed disjoint paths[END_REF][START_REF] Maurer | Containing byzantine failures with control zones[END_REF][START_REF] Maurer | Tolerating random byzantine failures in an unbounded network[END_REF].

Let us note that a common assumption considered by Byzantine tolerant reliable broadcast protocols is to use authenticated point-to-point channels, which prevents a process from impersonating several others (Sybil attack) [START_REF] Douceur | The sybil attack. In: Peer-to-Peer Systems[END_REF]. The real difference between cryptographic (authenticated) and noncryptographic (unauthenticated) protocols for reliable broadcast is how the cryptography is employed: non-cryptographic protocols, in fact, may use digital signatures just within neighbors for authentication purposes, whereas the cryptographic protocols make use of cryptographic primitives to enable the message verification even between non-directly connected nodes. Let us finally remark that an authenticated channel not necessarily requires the use of cryptography [START_REF] Zeng | Non-cryptographic authentication and identification in wireless networks[END_REF].

Although the Byzantine tolerant reliable broadcast problem with honest dealer has been extensively studied considering alternative and additional assumptions, the solution provided by Dolev [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF] is the only one for general settings and it has never been revisited from a performance perspective. Indeed, this solution hints at poor scalability since it requires a factorial number of copies (with respect the size of the network) of the same message to be spread and potentially verified in order to be accepted. This suggest that solving reliable broadcast in the weakest system model (i.e., Dolev's solution [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF]) is practically infeasible.

Contributions

We review and improve previous solutions for reliable broadcast in multihop networks, where at most f nodes can be Byzantine faulty, making no further assumption with respect to the original setting [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF]. In more details, (i ) we propose and evaluate modifications to the state of art protocols that preserve both safety and liveness properties of the original algorithms, and (ii ) we define message selection policies in order to prevent Byzantine faulty nodes from flooding the network and to reduce the total number of messages exchanged.

In a preliminary work [START_REF] Bonomi | Multi-hop byzantine reliable broadcast made practical[END_REF], we focused on random network topologies, we defined two modifications to the state of art protocols, we proposed one preliminary message selection technique, and we carried out a performance analysis in the scenario where all processes are correct. In this work, by extensive simulations for variously shaped networks and considering active Byzantine processes spreading spurious messages over the network, we show that our modifications enable to keep the message complexity close to quadratic (in the size of the network). Our work thus paves the way for the practical use of Byzantine tolerant reliable broadcast solutions in realistic-size networks.

System Model and Problem Statement System Model

We consider a distributed system composed by a set of n processes Π " tp 1 , p 2 , . . . p n u, each one having a unique integer identifier. Processes are arranged in a communication network. This network can be seen as an undirected graph G " pV, Eq where each node represents a process p i P Π (i.e. V " Π) and each edge represents a communication channel connecting two of them p i , p j P Π (i.e. E Ă Π Ś Π), such that p i and p j can communicate. In the following, we interchangeably use terms process and node and we refer to edges, links and communication channels similarly.

We assume an omniscient adversary able to control up to f processes allowing them to behave arbitrarily. We call them Byzantine processes. All the processes that are not Byzantine faulty are correct. Correct processes do not a priori know the subset of Byzantine processes. Processes have no global knowledge about the system (i.e. the size or the topology of the network) except the value of f .

Communication channels allow connected processes to exchange messages, providing two interfaces: SENDpp dest , mq and RECEIVE pp source , mq. The former requests to send a message m to process p dest , the latter delivers the message m sent by process p source . Processes that are not linked with a communication channel have to rely on others that relay their messages in order to communicate, in a multi-hop fashion. We assume reliable and authenticated communication channels, which provide the following guarantees: (i) reliable delivery, namely if a correct process sends a message m to a correct process q, then q eventually receives m; (ii) authentication, namely if a correct process q receives a message m with sender p, then m was previously sent to q by p.

We consider a synchronous system, namely we assume that (i) there is a known upper bound on the message transmission delays and (ii) a known upper bound on the processing delays. We assume a computation that evolves in sequential synchronous rounds. Every round is divided in three phases:

(1) send, where processes send all the messages for the current round, (2) receive, where processes receive all the messages sent at the beginning of the current round and (3) computation, where processes execute the computation required by the specific protocol. In a single round, any message can traverse exactly one hop, namely the message exchange occurs only between neighbor processes. We measure the time in terms of the number of rounds.

Problem Statement

We consider the reliable broadcast with honest dealer problem from a source s assuming f Byzantine failures arbitrary spread in the network [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF]. A protocol solves the Byzantine tolerant Reliable Broadcast (BRB) with honest dealer problem if the following conditions are met:

• (Safety) if a correct process delivers a message m, then it has been previously sent by the source;

• (Liveness) if a correct source broadcast a message m, then m is be eventually delivered by every correct process.

Notice that in the case of a correct source, all correct processes deliver the broadcast message. Instead, if the source is Byzantine faulty, then not all correct processes necessarily deliver the broadcast message and/or they may deliver different messages. We referred (following the literature) with message m to a content (i.e. a value) that has been broadcast. Every information spreading protocol place a content inside a message with a specific format, adding protocol related overhead. Therefore, to ease of explanation, we refer with content to the value that has been broadcast and with message to the one exchanged by a protocol. Therefore, a message refers to the union of a content and the overhead added by the employed protocols.

Background

We start by presenting and remarking some definitions and theoretical results to lead the reader in an easier understanding. Subsequently, we present the state-of-the-art protocols solving the BRB problem and we provide an analysis of them.

Basic Definitions and Fundamental Results

For all the definitions and results that follow, let us consider the cube graph Ĝ depicted in Figure 1 as example. Definition 1 (neighbors). Given an undirected graph G " pV, Eq, two nodes u, v are adjacent or neighbors if there is an edge connecting them ( i.e. tu, vu P E).

In graph Ĝ, the neighbors of node u are nodes a, b and c.

Definition 2 (path). Given an undirected graph G " pV, Eq, a path is a sequence of adjacent nodes without repetitions ( i.e. path :" pv 1 , v 2 , . . . , v x q : @i P r1, x ´1s, v i P V, tv i , v i`1 u P E). The two extreme nodes of a path are called ends.

Definition 3 (connected nodes and connected graph). Given an undirected graph G " pV, Eq, two nodes u, v are connected if there exist at least one path with ends u, v, they are disconnected otherwise. The graph G is connected if it exist at least one path between every pair of nodes.

In graph Ĝ, the sequence pu, a, e, vq is a path with ends u and v, thus nodes u and v are connected. Definition 4 (independent/disjoint paths). Given an undirected graph G " pV, Eq, two or more of its paths are independent or disjoint if they share no node except their ends.

In graph Ĝ, the sequence pu, c, f, vq is another path that is disjoint with respect to pu, a, e, vq.

Definition 5 (vertex cut). Given an undirected graph G " pV, Eq, the removal of a set of nodes

C Ă V from G results in a subgraph G C " pV C , E C q, where V C " V ´C and E C Ă E : @tv i , v j u P E, tv i , v j u P E C ðñ v i , v j R C.
Given two not adjacent nodes u, v P V , a vertex cut C Ă V ´tu, vu for u, v is a set of nodes whose removal from the graph G disconnects u from v, namely u, v are disconnected in G C .

In graph Ĝ, the set of nodes td, e, f u is a vertex cut for pu, vq, because its removal will disconnects nodes u from v.

Given an undirected graph G " pV, Eq and two not adjacent nodes u, v, the maximum number of mutually disjoint paths with ends u and v is referred with κ 1 pu, vq, and the size of the smallest vertex cut C separating u from v is referred with κpu, vq.

Remark 1 (Global Menger Theorem). A graph is k-connected (or it has vertex connectivity equals to k) if and only if it contains k independent paths between any two vertices.

Remark 2 (Vertex Cut VS Disjoint Paths). Let G " pV, Eq be a graph and u, v P V . Then the minimum number of vertexes that disconnects u from v in G is equal to the maximum number of disjoint u ´v paths in G, namely κpu, vq " κ 1 pu, vq.

In graph Ĝ, the maximum number of disjoint paths between nodes u, v (κ 1 pu, vq) is 3, as depicted in Figure 1a. Furthermore, at least 3 nodes have to be removed from the network in order to disconnect nodes u, v (Figure 1b), thus showing the equivalence κ 1 pu, vq " κpu, vq.

The reader can refer to [START_REF] Diestel | Graph Theory[END_REF] for addition details.

The Byzantine Reliable Broadcast problem can be solved under the assumptions we considered in the system model when the following condition is met: Remark 3 (Condition for Byzantine Reliable Broadcast [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF]). Given a network G composed of n processes where at most f can be Byzantine faulty, the Byzantine Reliable Broadcast can be achieved if and only if the vertex connectivity of G is at least 2f `1.

Byzantine Reliable Broadcast Protocols

There exists two solutions addressing the Byzantine Reliable Broadcast with honest dealer problem in the system model we considered, that are the Dolev [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF] and the Maurer et al. [START_REF] Maurer | Communicating reliably in multihop dynamic networks despite byzantine failures[END_REF] algorithms. Any other solutions for the BRB problem makes extra or different assumptions (e.g. digital signatures, higher density networks, weaker versions of safety or liveness, etc.).

The protocols that follow are defined by:

• a propagation algorithm, which rules how messages are spread over the network;

• a verification algorithm, that decides if a content can be accepted by a process guaranteeing the safety of reliable broadcast.

The basic idea behind the following protocols is to leverage the authenticated channels to collect the labels of processes traversed by a content, in order to compute the maximum disjoint paths, in the case of Dolev, or the minimum vertex cut, in the case of Maurer et al., of all the paths traversed by the content. Those two methodologies are theoretically equivalent due to the Menger Theorem (Remark 2), i.e. if a message can traverse f `1 disjoint paths in a network, then it can traverse paths such that their minimum vertex cut is f `1 and vice versa. Dolev Reliable Broadcast Protocol (D-BRB) Dolev [START_REF] Dolev | Unanimity in an unknown and unreliable environment[END_REF] defined the seminal algorithm addressing the BRB problem. The messages exchanged by his protocol have the format m :" xs, content, pathy, where s is the label of the process asserting to be the source, content is the content to broadcast and path is a sequence of nodes.

Propagation Algorithm:

1. the source process s sends the message m " xs, content, Hy to all of its neighbors;

2. a correct process p saves and relays any message m " xs, content, path i y sent by a neighbor q to all of other neighbors not included in path i , appending to path i the label of the sender q, namely process p stores and multicasts m " xs, content, path i Y tquy.

The messages carrying path i with loops or path i that includes the label of the receiving process p are discarded at reception.

Verification Algorithm:

1. given a set of messages m i " xs, content, path i y received by process p and carrying the same values for s and content, the content is delivered by p if there exist f `1 disjoint paths among of all the related path i .

Maurer et al. Reliable Broadcast Protocol (MTD-BRB)

Maurer et al. [START_REF] Maurer | Communicating reliably in multihop dynamic networks despite byzantine failures[END_REF] extended and improved the algorithm defined by Dolev to deal with dynamic distributed systems, where the communication network changes over the time. As a matter of facts, a static communication network (our case) can be seen as a dynamic network that never changes, making their solution employable on the system model we are considering.

The format of messages exchanged by their protocol is m :" xs, content, pathsety, again carrying the information about the process s asserting to be the source and the content of broadcast. The difference with respect the previous algorithm is the data structure employed to collect the labels of traversed nodes: pathset, that it discards the traversing order.

Furthermore, MTD-BRB verifies the minimum vertex cut of the pathset traversed by a content instead of the maximum disjoint paths. The reason is that on dynamic networks the Menger theorem (Remark 3) does not hold, specifically the minimum vertex cut may be greater than or equal to the maximum disjoint paths between two nodes [START_REF] Kempe | Connectivity and inference problems for temporal networks[END_REF]. Propagation Algorithm:

1. the source process s sends the m " xs, content, Hy to all of its neighbors;

2. a correct process p saves and relays any message m " xs, content, pathset i y sent by a neighbor q to all of other neighbors not included in pathset i , appending to pathset i the label of the sender q, namely process p stores and multicasts m " xs, content, pathset i Y tquy.

The messages carrying pathset i with duplicates or pathset i that includes the label of the receiving process p are discarded at reception.

Verification Algorithm:

1. given a set of messages m i " xs, content, pathset i y received by process p and carrying the same values of s and content, the content is delivered by p if the minimum vertex cut of the related pathset i is at least f `1.

Discussion

The two protocols we presented are quiescent, namely at a certain point all correct processes stop sending messages. To be precise, this is true only if all processes are correct or at least the additional knowledge about the size of the system is given to the processes to guarantee the termination of message spreading. Contrarily, a Byzantine process may continuously introduce spurious messages carrying path i {pathset i " trandom labelu that are forwarded to all processes. We temporarily assume, for ease of evaluation, that all processes are correct in the analysis that follows. In order to evaluate and compare the protocols reported and the solution we are going to design, we analyze the following metrics:

1. message complexity i.e., the total number of messages exchanged in a single broadcast (the amount of messages exchanged from the beginning of the broadcast till the moment when all processes stop sending messages); 2. delivery computational complexity i.e., the complexity of the procedure executed by a process during the computation phase to decide if a content can be accepted.

3. broadcast latency i.e., the time between the beginning of the broadcast and the time when all correct processes deliver the content.

The message complexity of D-BRB protocol is factorial in the size of the network. The reason is that for every path connecting the source with any other node (i.e. that are order of the permutations over the full set of nodes) a message with related path i is generated. This potentially results in an factorial number of path i to elaborate by every process in order to deliver a single content. For sake of explaination, let us consider the cube graph depicted in Figure 1 and let us assume that process u starts a broacast, thus spreading a content with an empty path that will traverse the paths pu, aq, pu, bq and pu, cq on the communication network. The neighbors of the source will receive the content and its related (empty) path, they will attach the label of the sender and they will forward it to all of their neighbors not already included, e.g. process a will forwards the content with the path puq to processes d and e and thus a message related to the paths pu, a, dq and pu, a, eq will be generated (and the same will be done also by processes b and c). The process d will receive the path puq from a and b (the same happens for processes e and f from different processes). Consequently, a message carring pu, aq will be forwarded by d to b and v and a message carrying pu, bq will be sent by d to a and v. The messages continue to be generated as long as all possible paths are traversed, one message for each path. Furthermore, to the best of our knowledge, the only method available to identify f `1 disjoint path i is the reduction to a NP-Complete problem, Set Packing [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. We refer to this method with DP (Disjoint Paths), namely to the reduction and solution of the associated Set Packing instance. This implies that the delivery complexity of the algorithm is exponential.

The D-BRB guarantees the safety and liveness properties of BRB when the strict enabling condition is met (Remark 3), respectively because the Byzantine processes b 1 , b 2 , . . . b f cannot propagate a different content content ‰ content with source s through no more than f disjoint paths, and assuming a vertex cut of size f made by the faulty processes, f `1 disjoint paths are still available between any pairs of correct processes.

The MTD-BRB protocol is equivalent with respect the message complexity and delivery complexity to D-BRB. Specifically, even if all the paths i over the same set of nodes are all collapsed in a single pathset, they are still factorial in the number of nodes (i.e. they are order of the combinations over the full set of nodes), and messages carrying any possible pathset i are generated, potentially leading to an input of factorial size for the verification algorithm.

Again, to the best of our knowledge, the only method available to identify a vertex cut of size less than or equal to f is the reduction to a NP-Complete problem, Hitting Set [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. We refer to this method as VC (Vertex Cut), namely to the reduction and solution of the associated Hitting Set instance. This implies that the delivery complexity of this algorithm is exponential too.

The safety and liveness properties of BRB are guaranteed by MTD-BRB due to the same argumentation made for D-BRB : the Byzantine processes b 1 , b The broadcast latency of both protocols is bounded by the graph metric called wide diameter [START_REF] Hsu | On container width and length in graphs, groups, and networks-dedicated to professor paul erdös on the occasion of his 80th birthday[END_REF]. Given a k-connected graph G, the wide diameter is the maximum number l such that there exist k internally disjoint pu, vqpaths in G of length at most l between any pair of vertices u and v. This value depends on the graph topology. In the worst case, the wide diameter of a graph is n ´k [START_REF] Hsu | On the k-diameter of k-regular k-connected graphs[END_REF]. It follows that the broadcast latency of both protocols is upper bounded by n ´k, because in at most n ´k rounds k disjoint path are traversed between every pair of nodes. As a clarifying example, let us consider a k-connected generlized wheel graph with n nodes, that is composed by the disjoint union between a cycle and a k ´2 clique (a grafical example is depicted in Figure 5b) and let us chose as source a node on the cycle and let us focus on one of its neighbors on the cycle at distance two. It is possible to verify that in order to interconnect the pair of nodes we are considering through k disjoint paths, one path of length n ´k has to be traversed.

The Table 1 summarizes the presented analysis.

Practical Reliable Broadcast Protocol

Due to the high message complexity and delivery computational complexity of the reviewed protocols, they do no scale and they cannot be successfully employed.

We further analyze some deeper details of the aforementioned protocols and we define simple modifications that result in drastically reducing the message complexity. Specifically, we start by arguing that pathsets and VC should be preferred respectively as message format and verification algorithm. Subsequently, we propose modifications that aim in reducing the amount of messages spread by preventing from forwarding useless messages, thus redefining a protocol solving BRB.

Paths VS Pathsets

It is possible to note that, given the solutions available, there is no reason to prefer path over pathset while collecting the label of the traversed processes, indeed: (i) due to the reduction to set related problems, paths are converted into sets to be analyzed; (ii) two paths over the same set of nodes are not disjoint and have a cut of size equal to 1, and (iii) the pathsets interconnecting two endpoints are fewer than the relative paths. For those reasons we adopt the pathset data structure as message format to collect the labels of traversed processes in designing an improved protocol.

Minimum Vertex Cut VS Maximum Disjoint Paths

We remark that both verification algorithms solve a NP-Complete problems and, considering the Menger theorem in Remark 2, one may conclude that there is no tangible reason to prefer one among VC and DP. As a matter of fact, the equivalence between the two metrics in Remark 2 occurs when no restriction on the length of the paths is assumed. In fact, when the path lenght is bounded, the minimum vertex cut between two nodes may be higher than or equal to the maximum number of disjoint paths interconnecting them [START_REF] Lovász | Mengerian theorems for paths of bounded length[END_REF]. Let us take the example proposed in Figure 2 [START_REF] Lovász | Mengerian theorems for paths of bounded length[END_REF], let us focus on nodes u and v as endpoints and consider only the paths of length at most 5. It can be verified that at least two nodes have to be removed from the graph in order to disconnect u from v considering only the paths of length at most 5. Nevertheless, no two disjoint paths exist considering only the paths with the same constraint. In other words, given a graph G of n nodes and considering only the paths of length at most l ă n, the size of the minimum vertex cut of those interconnecting two nodes may be greater than or equal to the maximum number of disjoint paths interconnecting them. This implies that, whenever a synchronous system is assumed and the paths are all traversed synchronously like in our system model (i.e. the path of length 1 are all traversed in 1 instant (round), the paths of length 2 are all traversed in two instant (round) and so on), it may be possible to interconnect two endpoints with a minimum cut equal to k in fewer hops (i.e. rounds) with respect k disjoint paths. This results also in saving in message complexity if a halting condition is embedded inside the protocol, namely if the message propagation stops when all correct processes delivered the content. For this reason we adopt VC as verification methodology.

Improvements

Practical Reliable Broadcast Protocol (BFT-BRB)

We redefine a protocol for the Byzantine Reliable Broadcast with honest dealer. This protocol employs the same message format and verification algorithm of MTD-BRB, namely the label of the processes traversed by a message are collected in pathsets and the contents are verified through the VC methodology. We introduce four modifications in the propagation algorithm and one in the verification algorithm that aim to reduce the total number of messages exchanged and we prove their correctness, namely that their employment do not prevent the original algorithms of Dolev and Maurer et al. from enforcing safety and liveness of Byzantine Reliable Broadcast with honest dealer when the strict enabling condition is met (Remark 3), because they prevent from forwarding messages that are not useful for the delivery of a content.

Modification 1. If a process p receives a content directly from the source s ( i.e. the source and the sender coincides), then it is directly delivered by p.

Modification 2. If a process p has delivered a content, then it can discard all the related pathsets and relay the content only with an empty pathset to all of its neighbors.

Modification 3. A process p relays pathsets related to a content only to the neighbors that have not yet delivered it.

Modification 4. If a process p receives a content with an empty pathset from a neighbor q, then p can discard from relaying and analyzing any further pathset related to the content that contains the label of q.

Modification 5. A process p stops relaying further pathsets related to a content after it has been delivered and the empty pathset has been forwarded.

The modification 1 follows from the defitions of disjoint paths and vertex cut, indeed a path of lenght two is disjoint with respect every other one with the same ends, and the vertex cut is defined between not adjacent nodes, thus there is no vertex cut between neighbors.. The purpose of modifications 2, 3, and 4 is to reduce the amount of messages exchanged by the protocol and to be analyzed by processes. The modification 2 also provides a transparent way to get the neighbors q of a process p know that a specific content has been delivered by p. This one has already been employed [START_REF] Nesterenko | Discovering network topology in the presence of byzantine faults[END_REF] for the purpose of topology reconstruction.

The modification 5 introduces a halting condition in the protocol with respect the state of art, indeed all correct processes stop from relaying further messages at the round subsequent the last delivery of a process. Furthermore, this modifications makes the original solutions quiescent without assuming that processes know the size of system.

Let us consider the network topology depicted in Figure 1a as an example to detail the advantages introduced by the presented modifications. Let us select node u as source process and let us consider the all the paths of lenght two starting from u, namely pu, c, f q, pu, c, eq, pu, b, f q, pu, b, dq, pu, a, dq, pu, a, eq.

Processes d, e and f , following modification 1 will relay only an empty path instead of extending the paths they received, namely avoiding to generate pu, c, f, vq, pu, c, e, vq, pu, b, f, vq, pu, b, d, vq, pu, a, d, vq, pu, a, e, vq.

Processes d, e and f , leveraging modification 1, know that the nodes a, b and c have already delivered the content associated to the paths. Applying modification 2, processes d, e and f do not relay further paths to a, b and c, namely they do not generate paths pu, c, f, bq, pu, c, e, aq, pu, b, f, cq, pu, b, d, aq, pu, a, d, bq, pu, a, e, cq.

The modification 3 applies in cases a process p receives paths in round r i but it delivers the associated content in a round r j ą r i . A neighbor q of p that has not yet delivered the content will get the extension of paths received by p in r i and potentially the empty path in r j `1. The modification 3 enables q to discard from the analysis in delivering the associated content all paths previously received from p and to consider only the empty pathset.

The pseudo code of our protocol is presented in Figure 3. For the ease of explanation and notation, we show the procedure and variables only related to the broadcast of a single content spread by s.

Initially, every process is not aware about the nodes in its neighborhood but it can easily retrieve them with authenticated channels. For every not delivered content, a process stores (i) the received pathsets related to the content (Pathsets variable), (ii) the pathsets not yet relayed (To Forward variable) and (iii) the labels of neighbors that have delivered the content (Neigh Del variable).

Every process starts the round with the send phase, namely selecting the messages to forward and transmitting them. In particular, it extracts part or all of the message related to a content to relay (select function), and it forwards them to all of its neighbors that have not yet delivered the content, thus applying modification 3 in line 8.

During the receive phase, for every received message related to a content not yet delivered, the label of the sender is attached to the received pathset and the resulting collection is stored in order to be considered for the delivery and to be forwarded (we assume an implicit mechanism avoiding duplicate pathsets). The modification 2 enables a process p to know that a sender q has delivered the content (line 15). Then, the modification 3 allows p to discard part of the pathset previously received (lines 17 ´22) and that may arrive (line 13).

Finally, in the computation phase, all received pathsets related to the content are analyzed. Specifically, in case a process has received the content directly from the source s (i.e. the sender and the source coincides, the receiver has received the pathset tsu, line 26, modification 1) or the minimum vertex cut computed on Pathsets is greater than f , it delivers the content, it discards all the pathsets not yet forwarded and it enqueues to relay the empty pathset, namely applying modification 2 in lines 30, 31.

The implementation of modification 5 can be found in line 12. Indeed, once that a process has delivered the content, it discards all the residual pathsets to forward (line 30). In the receive phase all the messages related to the content already delivered are discarded (line 12) due to modification 4, thus the select function in line 6 only extracts the empty pathset in the round subsequent the delivery.

We prove the correctness of the proposed modifications thought the following theorems (assuming the system model we presented and under the assumption of the strict condition in Remark 3). Theorem 1. Let p be a process executing either the Dolev or the Maurer et al. algorithm to broadcast a content. If p delivers a content received directly from the source, then the safety property continues to be satisfied ( i.e. employing modification 1).

Proof. It follows directly from the property of the channels (reliable and authenticated), indeed the channels guarantee that every received message has been previously sent by the sender, that coincides with the safety property of reliable broadcast. Theorem 2. Let p be a process executing either the Dolev or the Maurer et al. algorithm to broadcast a content. If p delivered a content, then p can relay that content with an empty path/pathset and the safety property continues to be satisfied ( i.e. employing modification 2).

Proof. The aim of the information about the nodes traversed by a content is to enable a process p to decide whether it can be safely accepted. Once it has been delivered, the information about the nodes traversed before reaching p is not useful, because the content has been already verified as safe by p. Theorem 3. Let p be a process executing either the Dolev or the Maurer et al. algorithm to broadcast a content and let us assume that the modification 2 is employed. Even if p does not relay messages carrying the content to its neighbors that already delivered it, the liveness property continues to be satisfied ( i.e. employing modification 3). Proof. Let us assume that there exists three processes p, q, r such that only q has already delivered the content and that, among others, the following communication channels are available: pp, qq, pq, rq. From Theorem 2 we know that process q can safely relay the content with an empty path/pathset (i.e. employing modification 2). Thus, any further path/pathset containing p and q, after the delivery of q, does not affect the results of DP and VC verifying the content on r. It follows that any further transmission related to the content from p to q can be avoided after that q has delivered without compromising liveness. Theorem 4. Let p be a process executing either the Dolev or the Maurer et al. algorithm to broadcast a content and let us assume that the modification 2 is employed. If process p receives an empty path/pathset relative to a content from a neighbor q, than p can discard from its analysis and from relaying further path/pathset containing the label of q and the liveness property continues to be satisfied ( i.e. employing modification 4).

Proof. Let us assume that there exists three processes p, q, r such that only p has already delivered a content and that, among others, the following communication channels are available: pp, qq, pp, rq. We have to prove that process p can discard, verifying the associated content, further path/pathset containing the label of q but tqu without affecting the liveness property. This follows from the fact that path/pathset of unit lenght are included in every solution of the VC and DP and that any path/pathset containing more labels does not increase the value computed by VC and DP. We have to prove that this reasoning extends also for process r, so that process p can avoid relaying further path/pathset over tqu. On process r, any path/pathset that extends tq, pu does not increase the value obtained by VC and DP. It follows that any other path/pathset over tqu has not to be relayed. Theorem 5. Let p be a process executing either Dolev or Maurer et al. algorithm to broadcast a content and let us assume that the modification 2 is employed. If p has delivered and relayed the content with an empty path/pathset to all of its neighbors, then p can stop from relaying further related paths/pathsets and the liveness property continues to be satisfied ( i.e. employing modification 5).

Proof. It follows from the fact that any further path/pathset related to the content received and relayed by p does not increase the minimum cut/the maximum disjoint paths computed on other processes with respect the empty path/pathset relayed by p. Said differently, all the neighbors of p receive the paths/pathset tpu and any further path/pathset relayed by p becomes t. . . , pu, increasing neither the minimum vertex cut nor the maximum disjoint paths.

Preventing Flooding and Forwarding Policies.

We highlighted the fact that the verification algorithm has potentially to analyze a factorial, in the size of the network, amount of pathsets even only considering all processes to be correct. Nevertheless, a Byzantine process b can potentially flood the network with spurious messages (i.e., m :" xs, content, pathsety where s, content and pathset can be invented by the faulty process) that are also diffused by the correct ones. Considering that the amount of messages plays a crucial impact on the employment of the protocol we defined, a countermeasure must be researched.

A common way to limit the flooding capability of Byzantine processes is to constraint the channel capacity of every process, namely limiting the amount of messages that every process is allowed to send in a time window.

Noticed that, by introducing such a constraint, we are limiting the relaying capability of every process, while the Byzantine processes can continuously generate spurious messages potentially preventing the liveness property to be satisfied. It follows that a selection policy among all the messages to relay is demanded.

Every process has to relay pathsets to all of its neighbors that have not yet delivered the content. A pathset that may lead a neighbor q to the delivery of the associated content has not to contain the label of q (because it would be directly discarded), namely a process p has to select among the pathsets to forward the ones that do not include the label of q. There may be many pathsets that do not include q. Thus, we consider and evaluate two selection policies: (i) Multi-Random and (ii) Multi-Shortest . The Multi-Random is an extension of the forwarding policy proposed in [START_REF] Bonomi | Multi-hop byzantine reliable broadcast made practical[END_REF].

The algorithms for the pathsets selection implementing the Multi-Random and Multi-Shortest policies are presented in Figure 4. The selection iteratively picks one pathset and checks if it is "useful" for any neighbor (i.e. if any neighbor to contact is not included in the pathset). This selection continues till (i) all the neighbors to contact receives at least one pathset where they are not included or (ii) the bound on channel capacity has been reached. The Multi-Random policy iteratively picks randomly a possible pathset to forward, the Multi-Shortest gives priority to the shorter ones.

We compare and analyzed them both in the following.

Practical Reliable Broadcast Evaluation

We simulate the protocol and the policies we proposed in order to evaluate their effectiveness and to compare our protocol with the state-of-art solutions.

According to the system model we defined, we simulate single broadcasts that evolves in rounds. Therefore, the passage of time is measured in number of rounds.

We made use of the implementation provided by Gainer-Dewar and Vera-Licona [START_REF] Gainer-Dewar | The minimal hitting set generation problem: Algorithms and computation[END_REF] for the algorithm defined by Murakami and Uno [START_REF] Murakami | Efficient algorithms for dualizing large-scale hypergraphs[END_REF] to solve the VC reduction to the hitting set problem.

We consider the following parameters in our simulation:

• n, i.e. the size of the network considered;

• k, i.e. the vertex connectivity of the network considered;

• topology, i.e. the topology of network considered;

• channel capacity, i.e. the maximum number of messages that a process can send in a link per round;

• kind of failure, i.e. how faulty process behave;

• forwarding policy, i.e. one among Multi-Shortest and Multi-Random .

In order to carry an analysis as complete as possible, we consider the following network topologies:

• k-regular k-connected random graph [START_REF] Steger | Generating random regular graphs quickly[END_REF];

• k-pasted-tree [START_REF] Baldoni | Investigating the existence and the regularity of logarithmic harary graphs[END_REF];

• k-diamond [START_REF] Baldoni | Investigating the existence and the regularity of logarithmic harary graphs[END_REF];

• multipartite wheel;

• generalized wheel [START_REF] Xu | Topological Structure and Analysis of Interconnection Networks[END_REF]; A graph is regular if every node is connected to the same number of neighbors, namely in a k-regular graph every node is connected exactly to k neighbors. The k-regular k-connected graphs have vertex connectivity equals to k with the minimum necessary number of edges. The k-regular kconnected random graphs are the ones uniformly sampled among all possible regular graphs employing the sampling methodology defined in [START_REF] Steger | Generating random regular graphs quickly[END_REF].

• Barabási-Albert graph [2]. (a) (b) (c) (d)
The k-pasted-trees and k-diamond graphs are Logarithmic Harary Graph [START_REF] Jenkins | Logarithmic harary graphs[END_REF], namely topologies designed to be robust to failures and suited for distributed systems where the information spreading occurs by message flooding. Indeed, they are k-connected graphs with a logarithmic diameter and with minimal edges guaranteeing the node-connectivity (i.e. the removal of an edge decreases vertex connectivity of the network). For specific values of network size n and vertex connectivity k they are k-regular. A graphical example of k-pasted-trees and k-diamond are respectively presented in Figures 5c and5d.

We refer with multipartite wheel to a regular graph composed by the concatenation of disjoint groups of k{2 nodes such that every node in a group is connected to exactly all the k{2 nodes in other 2 groups and no node inside a group is connected with others of the same group. A graphical example is provided in Figure 5a.

Notice that k-regular k-connected graphs can be constructed in several ways, indeed we are considering four different constructions that are either always regular or regular for specific settings. The sequel demonstrates that the specific construction impacts protocol performance.

We considered also the Barabási-Albert graphs that models complex and social networks with scale-free power law degree distribution. The aim is to evaluate our protocol also on topologies not designed for distributed systems.

Finally, we consider the generalized wheel, i.e. the topology generated by the disjoint union between a cycle and a k ´2 clique. An example can be found in Figure 5b. It has been considered as a worst case scenario.

We carry our simulations either considering the maximum number of tolerable faulty processes, thus for every k-connected network we assume f " tpk ´1q{2u failures (Remark 3), or we tested all possible values for f between 0 and tpk ´1q{2u. In any case, processes deliver a content only when the related pathsets have a minimum vertex cut greater than tpk ´1q{2u.

We consider two configurations for the channel capacity: bounded and unbounded. The former constrains processes to send a limited number of messages per link in every round, the latter imposes no restriction. For the bounded case we assume a bound for the channel capacity equal to f `1 messages.

The source code of the presented simulations can be found online [START_REF] Bonomi | Multi-hop byzantine reliable broadcast made practical simulation code[END_REF].

Simulating Byzantine Behaviours

We move from the scenario where all processes are correct, to the case where the f Byzantine processes act as crash failures, (thus not relaying any message, we refer to them as passive Byzantines), till the case they spread spurious messages (we refer to them as active Byzantines). Specifically to this last scenario, we have to notice that spurious contents (i.e. contents generated by Byzantine processes b i ‰ s sent inside a message with source s) are never accepted by correct processes (if the BRB enabling condition in Remark 2 is met) and their spreading and verification is disjoint with respect the content broadcast by the source (because they are related to a different scontent). For this reason we impose to Byzantine processes to spread only spurious pathsets in our simulations (thus relaying the content broadcast by the source). The purpose is to flood the correct processes with spurious pathsets trying to not facilitate the achievement of the delivery condition. In detail, the Byzantine processes diffuse pathsets containing the label of one correct neighbor of the receiver in the first round, and pathseths containing one of the correct neighbor of the receiver with a random label in the subsequent rounds. Every Byzantine process sends f `1 messages (the maximum amount allowed by the channel capacity) containing different pathsets on every of its link per round. Additionally, we consider two kinds of active Byzantine processes: omniscient and general. Omniscient active faulty processes know the content that the source is going to spread before receiving it through a message, thus they start flooding correct processes with spourious pathsets from the beginning of broadcast. General active faulty processes, instead, spreads spurious pathsets in the round subsequent the first reception of a message containing the content, namely as soon as they get knowledge about the content through the network. Notice that there are other strategies that Byzantine processes may adopt generating spourious pathsets, especially if such Byzantines are omniscient about the state of all other processes. The Byzantine strategy that we adopted has been choosen to allows faulty processes to generate pathsests that may be selected by the correct process due to their lenght.

In every simulation, the source and the Byzantine processes are randomly placed.

For all the results we are going to show we directly plot all the measures we got as points (except for Figures 6,[START_REF] Kempe | Connectivity and inference problems for temporal networks[END_REF][START_REF] Lovász | Mengerian theorems for paths of bounded length[END_REF] where the mean of the measures is depicted) in order to show their distributions, and we accordingly increase the size of the points with higher density.

Comparison with the state of art

We start comparing the message complexity of the state of art solutions with our protocol. We consider k-regular k-connected random graphs, we assume the vertex connectivity k equal to 3 and 5 and we simulate D-BRB, MTD-BRB and BFT-MTB considering unbounded channels and all correct processes, and we vary the size of the network from n " 6 to n " 20. We previously remarked about the lack in the state of art protocols of a halting condition, indeed they generate all source-to-other paths/pathsets in every execution. It can be noticed in Figure 6 that the modifications we defined have a remarkable impact on the message complexity even in a small and all-correct scenario. It can also be noticed the advantage gained by choosing pathsets over paths, as expected.

Multi-Random VS Multi-Shortest

We proposed as a countermeasure against the capability of Byzantine processes to flood the network a constraint on the channel capacity, namely limiting the amount of messages that a process can send over a link per round, and we set this bound equal to f `1. Then, we proposed two forwarding policies to select which pathsets relay in the actual round. Assuming bounded channels, we compare the presented policies, Multi-Random and Multi-Shortest , considering networks of size n " 100, topologies random regular, multipartite wheel, k-diamond and k-pasted-tree, passive Byzantine failures. The results are presented in Figures 7 and8 (notice that scale of the graphics in Figure 7 are logarithmic). Starting with the Multi-Random policy, it can be seen in Figures 7 that, while for some graphs the Multi-Random policy acts smoothly, the random regular (confirming the results achieved in our preliminary work [START_REF] Bonomi | Multi-hop byzantine reliable broadcast made practical[END_REF]) the multipartite wheel graphs and the k-diamond, there exist topologies where the broadcast latency and message complexity may conspicuously increase (k-pasted-tree). It follows that on some kind of graphs the selections of paths that the Multi-Random policy may take are not equivalment with respect the protocol progression and that additional criterion have to be considered in the selection. This lead us to discard such a policy to be one generally employable. Contrarily, the performance achieved employing the Multi-Shortest policy appears not affected by this misbehaviour (Figures 8). Therefore, we further investigate the Multi-Shortest policy while increasing the size of the network.

Multi-shortest policy detailed evaluation

We assume bounded channels and the Multi-Shortest policy, considering networks of size n " 150 and n " 200, topologies random regular, multipartite wheel, k-diamond and k-pasted-tree, passive and active Byzantine failures. First results are presented in Figures 9 and10. It is possible to see that the trends of the message complexity and broadcast latency keep defined employing our protocol joined with the Multi-Shortest policy while increasing the size of the network and considering passive Byzantine failures. Specifically, the message complexity keeps always close or below the n 2 boundary. It can also be deduced that a regular network not necessarily results in optimal performances employing our protocol, indeed there are notable differences in the results obtained considering different topologies. It can also be noticed from the distribution of the measures that there are several topologies (K-Pasted-Tree, K-Diamond and expecially Multipartite wheel) where the placement of the source and the Byzantine failures plays a remarkable impact on the message complexity. Additional details will be later provided.

To evaluate the effects of the Multi-Shortest policy on the broadcast latency, we simulate the BFT-BRB protocol employing either the Multi-Shortest policy or unbounded channels, considering passive Byzantine processes and networks of size n " 100. It can be deduced (Figure 11) that the policy we defined introduces negligible delays. We move to consider the case of active Byzatine processes, specifically in Figure 12 general active (non omniscient) Byzantine faults are assumed. It can be noticed that, spreading spourious pathsets (using the strategy we defined) once they get knowledge about a content, the Byzantine processes have no negative impact on the message complexity. As a matter of facts they may even help correct processes achieving reliable broadcast (because they relay the content even if they try not to increase the VC on the receiving processes). We consider the case of omniscient Byzantine faulty processes, which start spreading spurious pathset about the content from the beginning of broadcast. The results we obtained are presented in Figures 13,14. It is possible to see that such stronger Byzantine faults are able to remarkably increase the message complexity, nonetheless it keeps close to the n 2 threshold.

Varying the number of failures

We evaluate how the message complexity evolves when the number of faulty processes is not maximized. We plotted the results we obtained in Figures 15,16. Whatever is the amout of failures, processes deliver a content only if the associated minimum cut is greater than tpk ´1q{2u. It is possible to deduce that the resulting message complexity depends on the specific topology considered and on the degree of connectivity. Specifically, both in case of passive and omniscient active Byzantine faults, there are settings where the message complexity remains constant independently from the number of effective failures and others where the message complexity increases exponentially with the number of failures.

Barabási-Albert graph

We separately evaluated in Figure 17 our algorithm in a Barabási-Albert graph while varying the attachment parameter m, in order analyze our protocol on a topology with different degree distribution with respect the previous analyzed. The BFT-BRB protocol and the Multi-Shortest forwarding policy shown to keep performing in the same manner. To allow the reader to make a comparison with the other topologies, we plot in Figure 18 the relation between the attachment parameter m and the network connectivity.

These simulations allow us to conclude that a Byzantine tolerable reliable broadcast protocol practically employable in synchronous systems without considering further assumptions with respect the state of art is achievable.

Worst Case Scenarios

For the ease of completeness, we briefly survey two worst case scenarios: the multipartite wheel and the generalized wheel. In Figure 19a is summarized one of executions we are going to present. Let us consider the multipartite wheel of size n " 21 and k " 6, choose a node as source (in Figure 19a depicted in orange) and place two faulty processes (in red) in its neighborhood in distinct groups (i.e. those neighbor will have different neighbors). It results that only two correct processes per group delivers the content during the first round. Subsequently, they relay the message to all the nodes in the consecutive group. But, none of this node is able to deliver the message: the minimum cut of the generated paths is 2 and processes demand paths with minimum cut at least 3. The nodes succeed in delivering the message only when "the propagation on the two sides met", achieving a minimum cut of 4. It can be noticed that a considerable amount of paths may be generated in this specific worst case scenario while the values of n and k increases. Nonetheless, the BFT-BRB protocol and the Multi-Shortest policy reduced such a message complexity case as shown in Figures 8, 9 and 10. We additionally simulate in Figure 20a our protocol with the Multi-Shortest policy on a multipartite wheel of size n " 100 with passive Byzantine in the worst placement.

(a) (b) Another worst case scenario is depicted in Figure 19b. Let us assume a generalized wheel, pick a source on the cycle and the Byzantine processes always located on the clique. The Figure 20b show that in this specific case our algorithm and the Multi-Shortest policy are less effective in reducing the message complexity while Byzantine processes are located in the clique.

Conclusion

We revisited available solutions for the reliable broadcast in general network hit by up to f arbitrarily distributed Byzantine failures, and proposed modifications following performance related observations. Although the delivery complexity of our protocol remains unchanged with respect the state-ofart solutions, our experiments show that it is possible to drastically reduce the message complexity (from factorial to polynomial in the size of the network), practically enabling reliable broadcast in larger systems and networks with authenticated channels. There are several open problems that may follows: is it possible to define a solution to the hitting set problem suited for the specific input generated by our protocol? Is it possible to remove from the system the contents generated by Byzantine processes? And under which assumption? Which are the graph parameters that govern the message complexity of our protocol? Our results open to the possibility of identifying a polynomial theoretical bound on message complexity solving the reliable broadcast problem with honest dealer. Finally, the Bizantine Reliable Broadcast problem should be analyzed also on dynamic networks.

Even if the protocol we proposed can directly be employed on asynchronous and/or dynamic systems, the achieved gain in message complexity is not guaranteed due to the weaker synchrony assumptions, and probably specific assumption on the evolution of the system must be guaranteed in searching a practical employable solution.

Figure 1 :

 1 Figure 1: Disjoint Paths (a) and Vertex Cut (b) of a cube graph.

Figure 2 :

 2 Figure 2: Graph example to compare minimum vertex cut and maximum disjoint paths.

Figure 3 :

 3 Figure 3: Byzantine Tolerant Reliable Broadcast with honest dealer Protocol.

Figure 4 :

 4 Figure 4: Multi-Shortest and Multi-Random Policies.

Figure 5 :

 5 Figure 5: Graph topologies. n " 24, k " 4. (a) multipartite wheel, (b) generalized wheel, (c) k-pasted-tree, (d) k-diamond.

Figure 6 :

 6 Figure 6: State of art VS our protocol, message complexity. Random regular network, unbounded channels, f =tpk ´1q{2u all correct. (a) k " 3, (b) k " 5.

Figure 7 :

 7 Figure 7: Multi-Random policy n " 100, f =tpk ´1q{2u passive Byzantines, bounded channels, message complexity and broadcast latency.

Figure 8 :Figure 9 :

 89 Figure 8: Multi-Shortest policy, message complexity and broadcast latency, passive Byzantines, bounded channels, n " 100, f =tpk 1q{2u. 25

Figure 10 :

 10 Figure 10: Multi-Shortest policy, message complexity and broadcast latency, passive Byzantines, bounded channels, n " 200, f =tpk 1q{2u. 27

Figure 11 :

 11 Figure 11: Delay forwarding policy. X-axis: network connectivity, Yaxis: broadcast latency, fist row: Multi-Shortest bounded channel, second row: unbounded channel, n " 50, f " tpk ´1q{2u passive Byzantine.

Figure 12 :

 12 Figure 12: Multi-Shortest policy, message complexity with either passive or non omniscient (general) Byzantine. n " 100, f " tpk ´1q{2u, bounded channels. (a) random regular, (b) multipartite wheel (c) k-pasted-tree, (d) k-diamond.

Figure 13 :

 13 Figure 13: Multi-Shortest policy, omniscient Byzantine faults. n " 100, f " tpk ´1q{2u, bounded channels.

Figure 14 :

 14 Figure 14: Multi-Shortest policy, omniscient active Byzantine faults. n " 150, f =tpk ´1q{2u, bounded channels.

Figure 15 :

 15 Figure 15: Multi-Shortest policy, varying the number of faults, message complexity, passive Byzantines. n " 100.

Figure 16 :

 16 Figure 16: Multi-Shortest policy, varying the number of faults, message complexity, active omniscient Byzantines. n " 100.

Figure 17 :

 17 Figure 17: Multi-Shortest policy, Barababasi-Albert Network, message complexity. f =tpk ´1q{2u, bounded channels, n " 100, 150, 200 (a) passive Byzantines, (b) active omniscient Byzantines.

Figure 18 :

 18 Figure 18: Barababasi-Albert Network, relation between the attachment parameter m and the network connectivity

Figure 19 :

 19 Figure 19: Worst case scenarios. Multi-Partite Wheel (a) and Generalized Wheel (b).

Figure 20 :

 20 Figure 20: Multi-Shortest policy, generalized wheel, worst Byzantine placementm passive Byzantine. (a) multipartite wheel, (b) generalized wheel.

Table 1 :

 1 Analysis of state of art protocols source s through pathsets with a minimum vertex cut greater than f and they cannot make a vertex cut on the communication network greater than f .

	Message Complexity	Factorial (Permutations of nodes)	Factorial (Combinations of nodes)
	Delivery Complexity	NP	NP
	Broadcast Latency	ď n ´k	ď n	´k

2 , . . . b f cannot propagate a different content content ‰ content with Dolev Maurer et al.