Carole Delporte-Gallet

Hugues Fauconnier

Hung Tran-The
email: hung.tran-the@liafa.jussieu.fr

Homonyms with forgeable identifiers

We consider here the Byzantine Agreement problem (BA) in synchronous systems with homonyms in the case where some identifiers may be forgeable. More precisely, the n processes share a set of l (1 ≤ l ≤ n) identifiers. Assuming that at most t processes may be Byzantine and at most k (t ≤ k ≤ l) of these identifiers are forgeable in the sense that any Byzantine process can falsely use them, we prove that Byzantine Agreement problem is solvable if and only if l > 2t + k. Moreover we extend this result to systems with authentication by signatures in which at most k signatures are forgeable and we prove that Byzantine Agreement problem is solvable if and only if l > t + k.

Introduction

Most of distributed algorithms assume that each process has an unique identity. Yet assuming that every process has unique identity given by a checkable identifier might be too strong (and costly) an assumption in practice especially if some processes are malicious. For example, very simple systems giving MAC addresses as identifier are not reliable, because MAC addresses may be duplicated and more sophisticated mechanisms using for example digital signatures are costly and difficult to implement. Moreover, for privacy reason, the processes may prefer to not have an unique identifier. For example, agents may be registered as members of groups and may want to act as member of the groups not as individuals. Hence it could be useful and interesting to relax the unicity of identifiers assumption. However, lack of identifiers is very restrictive and in fully anonymous systems very few problems are solvable (e.g. [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF][START_REF] Boldi | An effective characterization of computability in anonymous networks[END_REF][START_REF] Buhrman | On the importance of having an identity or, is consensus really universal?[END_REF][START_REF] Guerraoui | Anonymous and fault-tolerant shared-memory computing[END_REF]).

In [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF], the authors presented a general model with homonyms in which processes may share the same identifier and may then be homonyms. In this model n processes share a set of l identifiers (1 ≤ l ≤ n). More precisely, each process p has an unique identifier belonging to the set of l identifiers, but several processes may have the same identifier. The processes cannot distinguish between processes having the same identifier. A process may only send messages to all the processes with some identifier and when a process receives a message it knows only the identifier of the origin of the message without knowing which particular process it is. When l = n each proces has its own identifier and at the other extreme the case l = 1 corresponds to the fully anonymous system.

An important point in the model described in [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF] is that there is no "masquerading" and even a Byzantine process is not able to lie about its identifier: if any process p receives a message, then process p knows that the sender of this message has identifier id. Hence even a Byzantine process cannot lie about its identifier. Yet it is rather natural that Byzantine processes may at least form a coalition and "exchange" their identifiers.

In this paper we present an extension of homonyms processes in which some identifiers are "forgeable" and a Byzantine process may freely use any such identifier. Moreover we restrict ourselves to the classical synchronized rounds model. More precisely, we keep on ensuring that each process has an unique identity, but some identifiers are forgeable in the sense that Byzantine processes may use such an identifier id to send messages. A process receiving this message falsely believes that the identifier of the sender is id. Of course the set of forgeable identifiers is not known by the processes, we only assume that we have l identifiers for the n processes, and among these identifiers at most k are forgeable. As Byzantine are able to form coalitions and exchange their identifies, we assume that the set of forgeable identifiers contains at least all identifiers of Byzantine processes. Hence if t is the maximum number of Byzantine processes, we have t ≤ k ≤ l.

To determine the power of the model of homonyms with forgeable identifiers, as in [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF], we are going to consider the problem of Byzantine agreement [START_REF] Lamport | The Byzantine generals problem[END_REF]. As a Byzantine process is able to send in each round messages with all forgeable identifiers, intuitively, it means that it is the same as having at least one Byzantine process per forgeable identifier. Recall from [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF] that Byzantine agreement is solvable in the homonyms model if and only if l > 3t, then considering forgeable identifiers as similar to groups of processes with Byzantine processes, we get directly a solution with l forgeable identifiers if l > 3k and we could suppose that we have a solution if and only if l > 3k. But surprisingly, we prove a better bound, we prove that there is solution for the Byzantine agreement with k forgeable identifiers if and only if l > 2t + k. In fact, this result comes from the fact that if a Byzantine process forges the identifier a group of process containing correct processes, this group of processes has the same behaviour as a group of processes containing Byzantine process and correct processes together and it is proven in [START_REF] Delporte-Gallet | Byzantine agreement with homonyms in synchronous systems[END_REF] that such groups of processes are weaker adversaries than groups containing only Byzantine processes.

From a more practical point of view, it is easy to implement homonyms with help of digital signatures as with [START_REF] El | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] in which at each identifier is associated a public key and processes with the same identifiers share corresponding private keys. In this way we get a (strictly) stronger authentication mechanism as defined in [START_REF] Pease | Reaching agreement in the presence of faults[END_REF]. With this authentication mechanism a process cannot retransmit falsely messages. More precisely, if the identifier is unforgeable, then it is not possible for any process q to wrongly pretend that it received message m coming from a process with this identifier. It is well known that with this kind of authentication, the Byzantine agreement problem can be solved if and only if n > 2t in the classical case in which all processes have unique and different unforgeable identifiers, giving a n > 2k bound with k forgeable identifiers. With homonyms and at most k forgeable identifiers, we prove that Byzantine agreement is solvable if and only if l > t + k. Again the a priori expected result would be l > 2k.

Due to the lack of space some proofs are omitted and will appear in the full version of the paper.

The rest of the paper is organized as follows. Section 2 describes the model of homonyms with forgeable identifiers and gives the specification of Byzantine Agreement. Then in Section 3 we prove the impossibility results concerning Byzantine Agreement with homonyms and forgeable identifiers. In Section 4, we propose a specification of Authenticated Broadcast and give a corresponding algorithm. Section 5 contains the algorithm for Byzantine Agreement using Authenticated broadcast. Then, in Section 6 we study the authentication case. Finally in Section 7, we discuss some related work and perspectives.

Model and definitions

Identifiers and homonyms. We consider a distributed message-passing system of n processes. Each process gets an unique identifier from a set of identifiers L = {1, 2, . . . , l}. We assume that each identifier is assigned to at least one process but some processes may share the same identifier. Hence we have l ≤ n. If p is a process then Id(p) is the identifier of process p. 1 For an identifier id, the group of processes with identifier id, G(id), is the set of all processes with identifier id.

For example, if l = 1 then the system is fully anonymous and if n = l each process has an unique identifier.

Process failure. A correct process does not deviate from its algorithm specification. Some processes may be Byzantine, such a process can deviate arbitrarily from its algorithm specification. In particular, a Byzantine process may send different messages than its algorithm specifies or fails to send the messages it is supposed to. In the following t is an upper bound on the number of Byzantine processes.

From [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF], we know that Byzantine Agreement is impossible to solve if n < 3t, so we assume n > 3t.

Forgeable Identifiers. To each message m is associated the origin group of m that is an identifier in L denoted f rom(m). When the sender of the message m is a correct process p, this identifier is the identifier of this process: f rom(m) = Id(p). Remark that f rom(m) enables only to know the origin group but does not enable to know which process in this group is the sender.

We assume that Byzantine processes have the power to forge some identifiers. The set of identifiers that can be forge by Byzantine processes is a subset of L and is denoted F. In the following k designs an upper bound of the number of identifiers that can be forged:

|F| = k.
Let id f be an identifier in F, a Byzantine process with identifier id may send a message m to group id ′ with the forged identifier id f . In this case, a process p with identifier id ′ receives the message m with f rom(m) = id f . As a Byzantine process acts as an adversary it may divulge any information, then we assume here that if p is a Byzantine process then Id(p) is also in F.

Consequently, if a process p receives a message m with f rom(m) = id, p knows that this message has been either sent by a correct process with identifier id or sent by a Byzantine process which has forged the identifier id.

We name (n, l, k, t)-homonym model such a model. In the following a correct group designs a group of processes with some identifier that contains only correct processes and whose its identifier is not forgeable.

Synchronous rounds.

We consider a synchronous model of rounds. The computation proceeds in rounds. In each round, each process first sends a set of messages, which depends on its current state, to some identifiers. Then, each process receives all the messages sent to its identifier in the same round and finally changes its state according to the set of received messages.

As several processes may share the same identifier, in a round a process may receive several identical messages coming from processes with the same identifier (or Byzantine process that has forged this identifiers). But we assume here that when a process receives a message m with f rom(m) = id, it does not know how many correct processes with identifier id (or Byzantine process that has forged id) have sent this message. 2A Byzantine process can deviate arbitrarily from its algorithm specification and Byzantine process may send any set of messages (possibly an empty set) with any identifiers in F. Moreover, contrary to correct processes, we assume that Byzantine processes are able to send different messages to different processes in the same group.

Byzantine Agreement. In the following we are interested in the Byzantine agreement problem [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF]. Recall that solutions to this problem are the basis of most of fault tolerant algorithms (e.g. [START_REF] Schneider | Implementing fault-tolerant services using the state machine approach: A tutorial[END_REF]). Byzantine Agreement is an irrevocable decision problem that has to satisfy the following properties:

1. Validity: If all correct processes propose the same value v, then no value different from v can be decided by any correct process. 2. Agreement: No two correct processes decide different values. 3. Termination: Eventually every correct process decides some value.

Impossibility result

Following the spirit of the impossibility of Byzantine Agreement in [START_REF] Michael | Easy impossibility proofs for distributed consensus problems[END_REF], we prove our impossibility results in (n, l, k, t)-homonym model.

Proposition 1. Byzantine Agreement is unsolvable in (n, l, k, t)-homonym model if l ≤ 2t + k.
Proof. It suffices to prove there is no synchronous algorithm for Byzantine Agreement when l = 2t + k. To derive a contradiction, suppose there is an algorithm A for Byzantine agreement with l = 2t + k. Let A i (v) be the algorithm executed by a process with identifier i when it has input value v.

We divide the set of processes into 4 subsets:

A = ∪ 0<i≤t G(i), B = ∪ t<i≤2t G(i), C = ∪ 2t<i≤3t G(i) and F = ∪ 3t<i≤k+2t G(i).
We consider a system of 8 sets: two sets A 0 and A 1 (resp B 0 and B 1 , C 0 and C 1 , F 0 and F 1 ) with the same number of processes and the same repartition in group as A (resp. B, C, F ). Each process of A 0 with identifier i executes the code A i (0) and the analog for others sets and other input values.

Imagine setting up a system S as shown in Figure 1. Every process correctly executes the algorithm assigned to it. Communication between groups are indicated by continuous line. A dash arrow from group X to group Y indicates that processes of X send its message also to Y . (We do not pretend that we have a Byzantine Agreement algorithm for this system.) 1. communication from a process registered on serverl2 to processes on server l3.

A 0 B 0 C 0 C 1 A 1 F 1 F 0 B 1 Fig.
We now define three executions of the algorithm A. In execution α, processes of A, B and F are correct and have input 1, all the processes in C are Byzantine and the identifiers in F may be forged. By validity, all the correct processes must decide 1. A process c in C sends (1) the same messages to processes in A and F as the corresponding process in C 0 in system S, (2) the same messages to processes in B and F as the corresponding process in C 1 in system S, Moreover one process in C sends the same messages as processes in F 0 to processes in A, B and F .

In execution β, processes of B, C and F are correct and have input 0, all the processes in A are Byzantine and the identifiers in F may be forged. By validity, all the correct processes must decide 0. A process a in A sends (1) the same messages to processes in C and F as the corresponding process in A 1 in system S, (2) the same messages to processes in B and F as the corresponding process in A 0 in system S, Moreover one process in A sends the same messages as processes in F 1 to processes in A, B and F .

In execution γ, processes of A, C and F are correct. Processes of A and F have input 1 and processes of C have input 0. All the processes in B are Byzantine and the identifiers in F may be forged. Processes in B send (1) the same messages to processes in A and F as the corresponding processes in B 1 in system S (and the same that in α) (2) the same messages to processes in C as the corresponding processes in B 0 in system S (and the same that in γ)

Moreover one process in B sends the same messages as processes in F 0 to processes in A, C and F . Note that processes in F and this Byzantine process sends the same message to processes in A as in run α and to processes in C as in run γ.

So, for the correct processes in A executions α and γ are undistinguishable and they decide 1. For the correct processes in C executions β and γ are undistinguishable and they decide 0. This decision in execution γ contradicts the agreement property of the Byzantine agreement.

Authenticated Broadcast

Our algorithms for Byzantine Agreement use an adaptation of Authenticated Broadcast as introduced by Srikanth and Toueg [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF] in the classical case where each process has a different identifier (n = l).

First, recall some principles for Authenticated Broadcast. Authenticated Broadcast in [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF] is defined by two primitives: Broadcast(p, m, r) and Accept(p, m, r). Computation is broken up in superrounds. Roughly speaking a process p broadcasts a message m in superround r by Broadcast(p, m, r). If the process p is correct all processes receive the message and Accept(p, m, r). If the process p is a Byzantine process, the Authenticated Broadcast guarantees that if some process Accept(p, m, r) at some superround r ′ then all correct processes Accept(p, m, r) no later than in superround r ′ +1. Furthermore no correct process can Accept(p, m, r) from a correct process p if p has not broadcast it.

Considering the (n, l, k, t)-homonym model, we decompose the synchronous computation in superrounds too. All the processes of a group have to invoke broadcast of a message m in the superround r in order to ensure that this message will be accepted in the following superround.

More precisely, our Authenticated Broadcast is defined by two primitives: Broadcast(i, m, r) and Accept(i, m, r) where i is the identifier of some group. We assume that a process broadcasts at most one message in a superround. The Authenticated Broadcast primitive is specified as follows:

1. Correctness: If all the processes in a correct group i perform Broadcast(i, m, r) in superround r then every correct process performs Accept(i, m, r) during superround r. 2. Relay: If a correct process performs Accept(i, m, r) during superround r ′ ≥ r then every correct process performs Accept(i, m, r) by superround r ′ + 1.

Unforgeability:

If some correct process performs Accepts(i, m, r) in superround r ′ ≥ r then all correct processes in group i must Broadcast(i, m, r) in superround r.

The algorithm is described in Figure 2. A superround r is composed of the two rounds 2r and 2r + 1.

First, recall the principles of the algorithm of [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF] with T Byzantine processes. To propose a value v in superround r, process p sends message (init, p, v, r) to all processes (including itself). A process receiving such a message becomes a "witness" for (p, v, r) and sends a message of type echo to all processes. Any process that has T + 1 witnesses for (p, v, r) becomes Our algorithm follows the line of the algorithm in [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF] defined in the classical case where each process has a different identifier (n = l). One of the main difference here is the fact that the behaviour of groups of processes is different from the behaviour of processes. In particular, correct processes in groups with forgeable identifiers or in groups containing Byzantine processes have to decide and have to participate to the decision.

The algorithm proceeds in synchronous superrounds (set of successive rounds). In this algorithm, 1 is the only value that may be broadcast and value 0 is decided upon by default if 1 is not decided. Hence, all processes in superround 1 broadcast 1 if their input is 1. A process p sets variable value to 1 (and then will decides 1) in superround r < 2k, if it has (1) accepted (i u , 1, 1) messages from t + 1 distinct identifiers i u , and ( 2) accepted (j u , 1, r u ) from (r + 1)/2 with r u ≥ 2. Condition (1) ensures that at least one correct group has broadcast and condition (2) corresponds to the one of [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF]. Condition (1) ensures the validity property of consensus and the condition (2) ensures the agreement property. The correctness and relay properties of Authenticated Broadcast ensure that by the next superround (superround r + 1), all messages accepted by process p are also accepted by all correct processes. Hence, they all set the variable state to true. By superround r + 2, they broadcast and by correctness and relay properties, all correct processes decide 1 by setting value to 1. If p decides in superround 2k + 2, then it can be proved that at least one group of correct processes set its variable value to 1 by superround 2k, and all correct processes decide by superround 2k + 2.

We now prove that the algorithm of Figure 3 satisfies the specification of Byzantine agreement. First we give without proofs the easy following lemmata:

Lemma 1. If, at superround r, a correct process p has |A r | ≥ t + 1 then at each superround r ′ with r + 1 ≤ r ′ ≤ 2k + 2 each correct process has |A r ′ | ≥ t + 1.
Lemma 2. If every process of a correct group with identifier i 0 broadcasts some message in some superround r > 1, then every correct process sets value to 1 by superround r.

Proposition 3. (Validity) If all correct processes propose the same initial value v then no value different from v can be decided by any correct process.

Proof. Assume all correct processes propose 1.

In superround 1, every process of correct group with identifier i broadcasts (i, 1, 1) message. The correctness of the authenticated broadcast ensures that every correct process will accept (i, 1, 1) message. As there are at least l -k > t, it is easy to verify that |A 1 | of every correct process is greater than t. Thus every correct process sets state to true in superround 1 Line 8. In superround 2, every correct process p broadcasts (Id(p), 1, 2) . As l > t + k there is at least one correct group i in which every process broadcast (i, 1, 2). By Lemma 2, every correct process sets value to 1 in Line 15 and will decide 1.

Assume now that all the correct process propose 0. We prove that no correct process sets value to 1. For contradiction, assume that some correct process p sets value to 1 in some superround r. Thus, |A r | of p must be greater than t. Since there are at most t Byzantine processes, there is at least one correct group, say i, in A r . By unforgeability property, all processes of this group broadcast (i, 1, 1) in superround 1 and then the input value of every process in this group must be 1, a contradiction. Thus, every correct process keeps value to 0 and decides 0 Line 22. Assume that, in the execution, some correct process sets value to 1 at Line 15, and decides 1. Let r 1 be the first superround in which some correct process sets value to 1. Let p 1 be such a correct process that set value to 1.

With the help of Lemma 2, we prove: Lemma 3. If r 1 ≤ 2k, then every correct process sets value to 1 by superround r 1 + 2.

When r 1 is greater than 2k, p 1 has accepted (j u , 1, r u ) from 2k+2 2 distinct processes j u , then from at least k + 1 distinct processes. Then there is at least one correct group, say i 0 , in this set. Then we get: Proof. Assume that some correct process sets value to 1 at Line 15 and decides 1. Let r 1 be the first superround where some correct process sets value to 1.

Lemma 4 shows that if 2k + 2 ≥ r 1 > 2k then every correct process sets its value variable to 1 by superround r 1 . Lemma 3 shows that if r 1 ≤ 2k then every correct process sets its value variable to 1 by superround r 1 + 2. Thus, all correct processes decide 1.

Otherwise, if no correct process sets value to 1 then value is 0 for all correct processes and they decide 0.

We have:

Theorem 1. Assuming if l > t + k, algorithm of

Authentication

Authentication [START_REF] Pease | Reaching agreement in the presence of faults[END_REF] ensures that Byzantine process may "lie" about its own values but may not relay altered values without betraying itself as faulty. Currently this property may be ensured with a system of signatures using public keys cryptography.

The implementation of homonyms with authentication is rather natural: the members of a group share a secret key. The origin group of a message may be verified by a signature scheme of this group. Messages m are authenticated by the identifier of the sender. Each process can verify if a message carries the signature of a given identifier. As before we assume that the signatures of at most k identifiers can be forged.

With homonyms and this scheme of authentication, if id is not forgeable (any process with this identifier is correct) then it is not possible for any process to wrongly pretend that it has received some messages coming from identifier id, hence we get the authentication property of [START_REF] Pease | Reaching agreement in the presence of faults[END_REF].

For this model with authentication, we improve our bound: l > t + k is necessary and sufficient to achieve Byzantine Agreement. (Recall that in the classical model in which each process has its own identifier and without forgeable identifiers the bound is n > 2t.)

The proofs of the lower bound is essentially the same as for the case without authentication in Section 3.

The Byzantine Agreement algorithm of Figure 3 directly works with l > t + k if we have an Authenticated Broadcast. It remains to get an Authenticated Broadcast with l > k + t.

In [START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF], in the classical case in which each process has its own identity, Authenticated Broadcast can be obtained simply with authentication: it suffices to verify the signatures: A process that receives a message (p, m, r) accepts it if it can verify p's signature (and then forwards this message). But if we apply this simple mechanism in our model, we do not get the unforgeability property. In a forgeable group with identifier i containing some correct processes, it is possible that some correct accepts (i, m, r). Indeed, this message has been sent by a Byzantine process that has forged the identifier i.

To implement Authenticated Broadcast, we use the signatures and the mechanism of witnesses as in our previous algorithm. The implementation is based on the one presented in Section 4 ans some easy changes.

At some point, in algorithm 2 when a process receives some messages in round R, it will send echo in the next rounds. The process will forward all messages that produced this echo. In this way it gives a proof that it has the right to send echo. We get an Authenticated Broadcast algorithm from algorithm Figure2 by: (1) removing from the received message all messages with a bad signature, (2) forwarding the proof of each new echo message, (3) replacing the line 13 of algorithm 2 by: if received (echo, h, m, r) and the proof of (echo, h, m, r) and, (4) replacing the line 15 of algorithm 2 by if received (echo, h, m, r) and the proof of (echo, h, m, r) from at least l -t distinct groups We have: Theorem 2. With authentication Byzantine Agreement is solvable in (n, l, k, t)-homonym model if and only if l > t + k,

Related works and perspectives

When processes share identifiers and some of theses processes may be Byzantine, it is rather natural that some of these identifiers may be forged. Hence this work is a natural extension of [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF] to forgeable identifiers.

At least for the authentication case, groups signature as introduced first in [START_REF] Chaum | Group signatures[END_REF] are close to our model. Groups signature enables to sign messages on behalf of a group and clearly can be used to implement the model of homonyms. Note that group signatures generally ensures other properties than the one we consider here. Groups signatures may be a valuable way to implement models with homonyms.

In other works [START_REF] Bansal | Vasishta. Byzantine agreement using partial authentication[END_REF][START_REF] Gordon | Authenticated broadcast with a partially compromised public-key infrastructure[END_REF][START_REF] Gupta | Authenticated byzantine generals in dual failure model[END_REF], a mixed adversary model is considered in the classical (l = n): the adversary can corrupt processes actively (corresponding to Byzantine process) and can forge the signature of some processes.

In some way, we combine here the idea of group signatures and forgeable signatures but contrary to group signatures the goal is not to develop protocol ensuring strong properties like anonymity or unforgeability but try to develop algorithms (like agreement) in presence of groups of processes with Byzantine processes and forgeable identifiers.

Here we proved that with forgeable identifiers and homonyms Byzantine Agreement can be solved in a "reasonable" way (and without any assumption about cryptographic system). Interestingly, the solvability of Byzantine Agreement depends only on the number of identifiers and the number of forgeable identifiers. Hence adding correct processes does not help to solve Byzantine Agreement.

A natural extension of this work could be to consider partially synchronous models. As Byzantine Agreement is the basis for replication systems in the classical models in which each process has its own identity, a natural question is to know if it is still the case and envisage to develop algorithms for more difficult problems.

Proposition 4 .

 4 (Termination) Eventually every correct process decides some value.Proof. A correct process decides at superround 2k + 2 Line 20 or Line 22.

Lemma 4 .

 4 If r 1 > 2k, then every correct process sets value to 1 by superround r 1 . Proposition 5. (Agreement) No two correct processes decide different values.

Figure 3 Corollary 1 .

 31 implements Byzantine Agreement using Authenticated Broadcast in (n, l, k, t) homonym model.Combining this with algorithms for Authenticated Broadcast we get: If l > 2t + k, the algorithms of Figure3and 2 implement Byzantine Agreement in (n, l, k, t) homonym model.

  Fig. 3. Synchronous Byzantine Agreement algorithm with at most k forgeable identifiers and at most t Byzantine processes

	5 Byzantine Agreement Algorithms
	Code for process p with identifier i
	Variable:
	1 input = {v};	/* v ∈ {0, 1} is the value proposed value */
	2 value = 0;
	3 state = f alse;
	Main code:
	4 SUPERROUND 1
	20	DECIDE 1
	21	else
	22	DECIDE 0;

5

if input = 1 then Broadcast(i, 1, 1)

6 Let A1 = {h : p has Accepted(h, 1, 1)} 7 if |A1| ≥ t +

1 then 8 state = true 9 SUPERROUND r from 2 to 2k + 2 10 if state = true then 11 Broadcast(i, 1, r) 12 state = f alse; 13 Let Ar = {h : p has Accepted(h, 1, 1)} 14 if |Ar| ≥ t + 1 and has Accepted(iu, 1, ru) from r+1 2 distinct identifiers iu with ru ≥ 2 15 then value = 1 16 if |Ar| ≥ t + 1 and has Accepted(iu, 1, ru) from r 2 distinct processes iu not including i with ru ≥ 2 17 then state = true; 18 AT THE END OF SUPERROUND 2k + 2 19 if value = 1 then

For convenience, we sometimes refer to individual processes using names like p but these names cannot be used by processes in the algorithms.

Our results can be extended to the model of numerate processes as defined in[START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF] for which each process receives in a round a multiset of messages and is able to count the number of copies of identical messages they receive in the round.

Code for process p with identifier i ∈ {1, ..., l} Variable: itself witness (because at least one correct process has sent this message). When a process receives more than (2T + 1) witnesses, it accepts (p, v, r) (T + 1 correct processes have sent this message then all correct processes will find T + 1 witnesses of this message).

The algorithm follows the same principles, to propose a value v in supperround r process p with identifier i sends message (init, i, v, r) to all processes (including itself) (line 4). A process receiving such a message from some processes with identifier i becomes "witness" for (i, v, r) and sends a message of type echo to all processes (line 10). Any process having l -2t witnesses for (i, v, r) becomes itself witness (if l -2t > k at least one process in a correct group has sent this message) (line 13). When a process receives more than (l -t) witnesses, it accepts (i, v, r) (at least t + 1 processes from correct groups have sent this message) (lines 15 to 16). In this way we ensure correctness and relay properties To ensure the unforgeability property, a correct process that has no message to broadcast in a superround broadcast a noinit message in the corresponding even round. In this way, if some correct process with identifier i has no message to broadcast in superround r, every correct process gets M [i, 2r] (line 9) different from one message init and wil not become witness of any message (i, * , r).

The formal proof is standard and will be omitted due to lack of space. We have:

Proposition 2. If l > 2t + k, the algorithm Figure 2 implements Authenticated Broadcast in (n, l, k, t)-homonym model.


Frédérique Bassino
email: bassino@lipn.univ-paris13.fr.

Cyril Nicaud
email: cyril.nicaud@univ-mlv.fr.

Pascal Weil
email: pascal.weil@labri.fr.

Generic properties of random subgroups of a free group for general distributions

Keywords: Free group, Random groups, Small cancellation

We consider a generalization of the uniform word-based distribution for finitely generated subgroups of a free group. In our setting, the number of generators is not fixed, the length of each generator is determined by a random variable with some simple constraints and the distribution of words of a fixed length is specified by a Markov process. We show by probabilistic arguments that under rather relaxed assumptions, the good properties of the uniform word-based distribution are preserved: generically (but maybe not exponentially generically), the tuple we pick is a basis of the subgroup it generates, this subgroup is malnormal and the group presentation defined by this tuple satisfies a small cancellation condition.

Our starting point is a classical distribution on the set of finitely generated subgroups of a free group, for which the properties of "typical" subgroups were abundantly studied in the literature. Using a probabilistic approach (rather than a more combinatorial one), we describe a vast class of generalizations of this classical distribution, for which most "typical" properties of subgroups remain valid.

Interest for the typical properties of groups can be traced to Gromov [START_REF] Gromov | Essays in Group Theory, chapter Hyperbolic groups[END_REF], who introduced several models for random groups: he considers the statistical properties of finitely presented groups given by random sets of relators of size at most n, see [START_REF] Ollivier | A January 2005 invitation to random groups, volume 10 of Ensaios Matemáticos[END_REF] for a survey.

A growing body of literature considers another model of random groups, by focusing on the statistical properties of random finitely generated subgroups of free groups (and not necessarily the corresponding finitely presented groups). To randomly generate a finitely generated subgroup, one may either generate a tuple of reduced words and consider the subgroup they generate (the classical case, see Arzhantseva and Ol'shanskiȋ [START_REF] Goulnara | Ol ′ shanskiȋ. Generality of the class of groups in which subgroups with a lesser number of generators are free[END_REF], Jitsukawa [START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF], Kapovich, Miasnikov, Schupp and Shpilrain [START_REF] Kapovich | Generic-case complexity, decision problems in group theory, and random walks[END_REF] and Section 1.1 below), or directly generate a Stallings graph [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF][START_REF] Bassino | Statistical properties of subgroups of free groups. Random Structures and Algorithms[END_REF].

In these schemes, instances (say, tuples of generators) of size at most n (say, the maximum length of a generator) are considered equally likely, and one considers the probability p n that a property P holds for a randomly chosen instance of size n. The property P is called (exponentially) negligible if p n tends to 0 (exponentially fast), and (exponentially) generic if its complement is (exponentially) negligible.

In [START_REF] Kapovich | Generic-case complexity, decision problems in group theory, and random walks[END_REF][START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF], an integer k ≥ 1 is fixed and one draws uniformly at random k-tuples of reduced words of length at most n. This is what we call the uniform word-based distribution. It is known that, exponentially generically, the k-tuple is a basis of the subgroup it generates and this subgroup is malnormal, see [START_REF] Goulnara | Ol ′ shanskiȋ. Generality of the class of groups in which subgroups with a lesser number of generators are free[END_REF][START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF] and Section 2.1 . Proofs in this context are mostly combinatorial: the number of reduced words of length n is 2r(2r -1) n-1 (where r is the rank of the free group) and many properties can be computed directly. A bit of care and an extra injection of probability theory are however necessary to establish exponential genericity in some cases.

We propose to generalize this uniform word-based distribution as follows: the number of generators is not fixed, but determined by a random variable; the length of each generator is also determined by a random variable (excluding the possibility of a significant number of short words, and normalized so that its expected value is n); and the distribution of words of a fixed length is specified by a Markov process. Precise definitions are given in Section 2.2. We show that under rather relaxed assumptions, the good properties of the uniform word-based distribution are preserved: generically (but maybe not exponentially generically), the tuple we pick is a basis of the subgroup it generates and this subgroup is malnormal.

However, all the proofs must be revisited in a probability-theoretic spirit, as we cannot rely any more on enumeration formulas and on probabilities computed as a quotient of set cardinalities. In particular, if h = (h 1 , . . . , h k ) is a tuple of reduced words and

h ± = (h 1 , h -1 1 , . . . , h k , h -1 k ),
we estimate the probability that the height of the trie of h is larger than a function τ (n), according to the growth rate of τ (which may be linear, or grow much slower). This probability tends to 0 more or less fast (exponentially so, or super-polynomially so) if the random variables governing the number and the length of the generators satisfy certain technical properties. We also estimate in the same fashion the probability that long words have several occurrences in the words of h ± .

Besides the consequences on the statistical properties of subgroups already mentioned (being freely generated by h, malnormality), we also draw consequences on the groups presented by these tuples. We give conditions on the distribution which ensure that these groups generically satisfy the small cancellation property C ′ ( 1 6 ) (see [START_REF] Lyndon | Combinatorial group theory[END_REF]), implying that they are generically torsion-free, word-hyperbolic, with solvable word and conjugacy problems.

We note finally that Champetier also generalized the uniform word-based distribution, in a different fashion [START_REF] Champetier | Propriétés statistiques des groupes de présentation finie[END_REF]: he also considers a fixed number of generators k, words of equal length are still equally likely, but he requires that their minimum length should tend to infinity. Proofs in that context are quite different.

Definitions

Free groups and reduced words

Let A be a non-empty set, which will remain fixed throughout the paper, and let à be the symmetrized alphabet, namely the disjoint union of A and a set of formal inverses A -1 = {a -1 ∈ A | a ∈ A}. By convention, the formal inverse operation is extended to à by letting (a -1 ) -1 = a for each a ∈ A. A word in à * (that is: a word written on the alphabet Ã) is reduced if it does not contain length 2 factors of the form aa -1 (a ∈ Ã). If a word is not reduced, one can reduce it by iteratively removing every pattern of the form aa -1 . The resulting reduced word is uniquely determined: it does not depend on the order of the cancellations. For instance, u = aabb -1 a -1 reduces to aaa -1 , and thence to a.

The set F of reduced words is naturally equipped with a structure of group, where the product u • v is the (reduced) word obtained by reducing the concatenation uv. This group is called the free group on A. More generally, every group isomorphic to F , say, G = ϕ(F ) where ϕ is an isomorphism, is said to be a free group, freely generated by ϕ(A). The set ϕ(A) is called a basis of G. It is important to note that F has infinitely many bases: A is always a basis, but each set {a n ba m , a} is one as well (if A = {a, b}). The rank of F (or of any isomorphic free group) is the cardinality |A| of A, and one shows that this notion is well-defined in the following sense: the free groups on the sets A and B are isomorphic if and only if

|A| = |B|.
A group G is generated by a subset X if every element of G can be written as a product of elements of X and their inverses. It is finitely generated if it admits a finite set X of generators. In this paper, we are interested especially in the finitely generated subgroups of finite rank (i.e., finitely generated) free groups. Recall that every subgroup of a free group is free (Nielsen-Schreier theorem), and hence it has a rank as well, but that the rank of a subgroup may well be greater than that of the group: the free group of rank 2 has subgroups of every finite rank.

Graphical representation of subgroups of free groups

A privileged tool for the study of subgroups of free groups is the Stallings graph of a subgroup of H, a finite directed graph of a particular type uniquely representing H, whose computation was first made explicit by Stallings [START_REF] Stallings | Topology of finite graphs[END_REF]. The mathematical object itself is already described by Serre [START_REF] Serre | Trees[END_REF]. The description we give below differs slightly from Serre's and Stallings', it follows [START_REF] Weil | Computing closures of finitely generated subgroups of the free group[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Nicholas | A fast algorithm for Stallings' folding process[END_REF][START_REF] Miasnikov | Algebraic extensions in free groups[END_REF][START_REF] Silva | On an algorithm to decide whether a free group is a free factor of another[END_REF] and it emphasizes the combinatorial, graph-theoretic aspect, which is more conducive to the discussion of algorithmic properties.

A finite A-graph is a pair Γ = (V, E) with V finite and E ⊆ V × A × V , such that if both (u, a, v) and (u, a, v ′ ) are in E then v = v ′ , and if both (u, a, v) and (u ′ , a, v) are in E then u = u ′ . Let v ∈ V . The pair (Γ, v) is said to be admissible if the underlying graph of Γ is connected (that is: the undirected graph obtained from Γ by forgetting the letter labels and the orientation of edges), and if every vertex w ∈ V , except possibly v, occurs in at least two edges in E.

Every admissible pair (Γ, 1) represents a unique finitely generated subgroup H of F (A) in the following sense: if u is a reduced word, then u ∈ H if and only if u labels a loop at 1 in Γ (by convention, an edge (u, a, v) can be read from u to v with label a, or from v to u with label a -1 ). Moreover, each finitely generated subgroup H of F (A) is represented in that sense by a unique admissible pair, which we call the Stallings graph of H and write (Γ(H), 1).

Some algebraic properties of H can be directly seen on its Stallings graph (Γ, 1). For instance, the rank of H is exactly |E| -|V | + 1. See [START_REF] Stallings | Topology of finite graphs[END_REF][START_REF] Weil | Computing closures of finitely generated subgroups of the free group[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Miasnikov | Algebraic extensions in free groups[END_REF] for more information about Stallings graphs.

The Stallings graph of a given finitely generated subgroup H can be computed effectively, and efficiently. A quick description of the algorithm is as follows. Let h = (h 1 , . . . , h k ) be a tuple of reduced words generating H. We first build a graph with edges labeled by letters in Ã, and then reduce it to an A-graph using foldings. First build a vertex 1. Then, for every 1 ≤ i ≤ k, build a loop with label h i from 1 to 1, adding |h i | -1 new vertices. Change every edge (u, a -1 , v) labeled by a letter of A -1 into an edge (v, a, u). At this point, we have constructed the so-called bouquet of loops labeled by the h i .

Then iteratively identify the vertices v and w whenever there exists a vertex u and a letter a ∈ A such that either both (u, a, v) and (u, a, w) or both (v, a, u) and (w, a, u) are edges in the graph (the --→ 2 is then changed into 2 a -→ 1 to have positive labels only; since 2 and 4 both have an edge labeled with a ending in the same vertex 1, they are merged. The foldings halts here on this small example, since there are no vertex with two incoming or outgoing edges with the same label.

corresponding two edges are folded, in Stallings' terminology). An example is depicted on Fig. 1.

The resulting graph Γ is such that (Γ, 1) is admissible, the reduced words labeling a loop at 1 are exactly the elements of H and, very much like in the (1-dimensional) reduction of words, that graph does not depend on the order used to perform the foldings.

Genericity

Let us say that a function f , defined on N and such that lim f (n) = 0, is super-polynomially small (resp.

exponentially small) if f (n) = o(n -d ) for every d > 1 (resp. if f (n) < e dn
for some d > 0 and for n large enough).

Given a sequence of probability laws (P n ) n on a set S, we say that a subset X ⊆ S is negligible if lim n P n (X) = 0 and generic if its complement is negligible.

We also say that X is super-polynomially negligible (resp. exponentially negligible) if P n (X) is superpolynomially small (resp. exponentially small). And it is super-polynomially generic (resp. exponentially generic) if its complement is super-polynomially negligible (resp. exponentially negligible).

Generic properties of finite rank subgroups of free groups

We concentrate on the (classical) approach (following [2, 1, 7]), where a subgroup is given by a tuple of words generating it, that is, we consider a sequence of probability laws (P n ) on the set of tuples of elements of F .

The uniform distribution on k-tuples of words

In a situation often considered, an integer k > 0 is fixed, and we consider the uniform probability P n on the set of k-tuples of reduced words of length at most n. [START_REF] Goulnara | Ol ′ shanskiȋ. Generality of the class of groups in which subgroups with a lesser number of generators are free[END_REF][START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF] that, for each 0 < α < 1, µ( h) ≥ αn exponentially generically. Moreover, let τ ( h) be the length of the longest prefix common to two words in h ± . Then, for every 0 < β < 1 2 α, τ ( h) ≤ βn exponentially generically [START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF]. It follows that, exponentially generically, the Stallings graph Γ(H) consists of a "small" central tree (namely the trie of h ± , rooted at vertex 1) and "long" outer loops, one for each h i . This geometry of the Stallings graph of H implies that H is freely generated by h, and hence has rank k. Moreover, in that same geometry, the tuple h is determined by Γ(H), up to the order of its elements and the direction in which they are read. In particular, exponentially generically, a given subgroup will be produced by a fixed number of tuples h (among the k-tuples of reduced words of length at most n) and hence, the random generation of such k-tuples is an acceptable way of randomly generating rank k subgroups of F . We refer the reader to [START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF][START_REF] Bassino | Statistical properties of subgroups of free groups. Random Structures and Algorithms[END_REF] for further details on these results.

Let h = (h 1 , . . . , h k ) be a k-tuple of reduced words, let h ± = (h 1 , h -1 1 , . . . , h k , h -1 k ) and let µ( h) = min i |h i |. It was observed in
We also observe that, in that situation, Γ(H) can be computed in linear time, simply by computing the initial cancellation in the tuple h ± .

Under the same sequence of uniform distributions (P n ), H is exponentially generically malnormal [START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF]. By definition, H is malnormal if, for every x ∈ H, H ∩ x -1 Hx = {1}. This algebraic property of H translates exactly to the following combinatorial property of the Stallings graph of H: no non-trivial word u labels a loop at two distinct vertices of Γ(H) (see [START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF]).

In the exponentially generic situation described above, any loop in Γ(H) must run along at least one outer loop (so it must have length at least µ( h) -2τ ( h)), and the portions of its travel inside the central tree are each of length at most 2τ ( h). A more detailed analysis shows the following result.

Lemma 2.1 Let h be a tuple of reduced words and let

H = h . If τ ( h) < 1
8 µ( h) and H is not malnormal, then there exists a word of length 1 8 µ( h), with two distinct occurrences in the words of h ± sitting at distance at least 1 8 µ( h) from the extremities of these words. We already know that, under the sequence of uniform distributions (P n ), τ ( h) < 1 8 µ( h) exponentially generically. It also holds that, exponentially generically, the words of h ± do not have common factors of length 1 8 µ( h) [START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF][START_REF] Bassino | Statistical properties of subgroups of free groups. Random Structures and Algorithms[END_REF]. Therefore, exponentially generically, H is malnormal.

Relaxing the parameters of the distribution

We now relax all the parameters of the distributions of tuples of reduced words, with the objective of preserving the genericity of the properties discussed in Section 2.1.

In our scheme, the probability P n on the set of tuples of reduced words is determined as follows. The size of the tuple and the lengths of the words are determined by random variables K n and L n , on which we impose the following restrictions: the number of words in our tuple, given by K n , cannot be too large and generically a tuple does not contain short words; in addition, the average length of a word, E(L n ), is equal to n (a sort of normalization). More precisely:

• E(L n ) = n and there exists a function µ(n) such that lim n µ(n) = ∞ and L n ≥ µ(n) generically:

if we let upper µ = P[L n < µ(n)], then lim n upper µ = 0. One may think of µ(n) as a function of the form n λ for some 0 < λ < 1, or some logarithmic function.

• There exists a function ν(n) such that K n ≤ ν(n) generically: if we let lower ν = P[K n > ν(n)],
then lim n lower ν = 0. We will consider situations where

ν(n) is a constant function, or O(log d n) or O(n d ) for some d > 0.
Moreover, we do not consider the uniform distribution on the set of reduced words of a given length, but the distribution given by a Markovian scheme which we now proceed to describe.

Markovian automata

A Markovian automaton (i) A consists of (i) This notion is different from the two notions of probabilistic automata, introduced by Rabin [14] and Segala and Lynch [START_REF] Segala | Probabilistic simulations for probabilistic processes[END_REF], respectively.

(A) • a deterministic transition system (Q, •) on alphabet X, where Q is a finite non-empty set called the state set, and for each q ∈ Q, x ∈ X, q • x ∈ Q or q • x is undefined; • an initial probability vector γ 0 ∈ [0, 1] Q , i.e. a vector such that q∈Q γ 0 (q) = 1;

1 3 2 3 a | 1 b -1 | 1 2 b | 1 2 1 3 1 3 1 3 b | 1 a | 1 2 b | 1 2 a | 1 (A ′ )
• for each p ∈ Q, a probability vector (γ(p, x)) x∈X ∈ [0, 1] X , such that γ(p, x) = 0 if and only if p • x is undefined. If u = x 1 • • • x n ∈ X * , we write γ(q, u) = γ(q, x 1 )γ(q • x 1 , x 2 ) • • • γ(q • (x 1 • • • x n-1 ), x n ) for n ≥ 1 and γ(q, u) = 1 if n = 0.
We also write γ 0 (u) = q∈Q γ 0 (q)γ(q, u).

For each n ≥ 0, γ 0 determines a distribution on the set of elements of X * of length n, and hence a probability law on that set. We denote this probability law by P n . In particular, we are only defining the probability of a subset of X * that consists of equal length elements.

Markovian automata are very similar to hidden Markov chain models, except that symbols are output on transitions instead of on states. In our context, Markovian automata are more convenient since sets of words (languages) are naturally described by automata. See the examples below, all set in the context of group theoretic applications, and Section 2.4.

Uniform distribution on length n elements of F : We exploit the fact that the set of reduced words is rational, and hence is accepted by an automaton, and we set uniform probabilities on the transitions of that automaton. The state set is Q = Ã. For each a ∈ Ã, there is an a-labeled transition from every state except a -1 , ending in state a. If all of these transitions have the same probability, namely 1 2r-1 , r being the rank of F , and if the initial probability vector is uniform as well, with each component equal to 1 2r , then the Markovian automaton yields the uniform distribution on length n elements of F . We can also tweak these probabilities, to favor certain letters over others, or to favor positive letters (the letters in A) over negative letters.

Distributions on rational subsets of F : The support of the distribution (the words with non-zero probability) does not have to be equal to the set of all reduced words. We can consider a rational subset L of F , or rather a deterministic automaton accepting only reduced words, and impose probabilistic weights on its transitions to form a Markovian automaton. The resulting distribution gives non-zero weights only to prefixes of elements of L. This can be applied to the case where L = A * , the set of positive words, or when L is a finitely generated subgroup of F and the automaton is constructed from the Stallings graph of that subgroup. ) 2 , bb -1 and b -1 b, and the support of the distribution defined by A ′ consists of the words on alphabet {a, b}, without occurrences of a 2 or b 3 . Both are regular sets of unique representatives of the elements of P SL(2, Z) (the first is the set of geodesics of P SL(2, Z), and also the set of Dehn-reduced words with respect to the given presentation of that group; the second is a set of quasi-geodesics of P SL(2, Z)). Note that the underlying graphs of the markovian automata of Fig. 2 are parts of de Bruijn graphs since they are defined by forbidden finite factors. Notice that the distribution produced by A ′ is not uniform on words of length n of its support.

Markov chains and Markovian automata

A Markovian automaton hides (rather poorly) a Markov chain. If A is a Markovian automaton on alphabet X, with state set Q, we define a Markov chain M (A) on Q as follows: its transition matrix is given by M (p, q) = x∈X s.t. p•x=q γ(p, x) for all p, q ∈ Q, and its initial vector is γ 0 .

Recall that the Markov chain M (A) is irreducible if, for all p, q ∈ Q, M (A) n (p, q) > 0 for some n > 0: this is equivalent to the strong connectedness of A. Recall also that M (A) is aperiodic if, if for each q ∈ Q, M (A) n (q, q) > 0 for all large enough n: this is equivalent to stating that A has loops of every large enough length at every state, equivalent again to stating that A has a collection of loops of relatively prime lengths. If both these properties hold, we say that A itself is irreducible and aperiodic and we can apply the classical theorem on Markov chains: there exists a stationary vector γ and the distribution defined by A converges to that stationary vector exponentially fast (see [START_REF] Levin | Markov chains and mixing times[END_REF]Thm 4.9]). In the vocabulary of Markovian automata, this yields the following theorem.

If u ∈ X * has length n, let Q p n (u) be the state of A reached after reading the word u starting at state p.

Theorem 2.2 Let A be an irreducible and aperiodic Markovian automaton on alphabet X, with state set Q (|Q| ≥ 2) and stationary vector γ. For each q ∈ Q, γ(q) = lim n→∞ P[Q p n = q]. More precisely, there exist K > 0 and 0 < c < 1, such that |P[Q p n = q] -γ(q)| < Kc n for all n large enough.

Remark 2.3

The constant c in Theorem 2.2 is the maximal modulus of the non-1 eigenvalues of M (A).

The Markovian automaton discussed in Section 2.3, relative to the uniform distribution on reduced words of length n is aperiodic and irreducible, as well as the two Markovian automata related to P SL(2, Z). The respective values for c are 1 2r-1 , 1 2 and 1 √ 2 . We also record the following statement, on the exponential decrease of the probability of a word.

Lemma 2.4

Let A be an irreducible and aperiodic Markovian automaton on alphabet X. There exist constants K 1 > 0 and 0 < c 1 < 1 such that, for each state q and for each word

v of length n, γ 0 (v), γ(v), γ(q, v) ≤ K 1 c n 1 .
Proof. Let ℓ be the maximum length of an elementary cycle (one that does not visit twice the same state) and let δ be the maximum value of γ(q, κ) where κ is an elementary cycle at state q. Since A is irreducible and aperiodic, we always have γ(q, κ) < 1, so δ < 1.

Every cycle κ can be represented as a composition of at least |κ|/ℓ elementary cycles (here, the composition takes the form of a sequence of insertions of a cycle in another). Consequently γ(q, κ) ≤ δ |κ| ℓ . Finally, every path π can be represented as a product of cycles and at most |Q| individual edges. So, if π starts at state q, γ(q, π) ≤ δ |π|-|Q| ℓ

. We get the announced result by letting

K 1 = δ -|Q| ℓ and c 1 = δ 1 ℓ . ⊓ ⊔

Cancellation properties

The random variables K n and L n , and the irreducible and aperiodic Markovian automaton A are now fixed, and the constants K, K 1 , c and c 1 are those discussed in Section 2.4. Let h = (h 1 , . . . , h s ) be a randomly chosen tuple of reduced words and let H = h . We first consider initial cancellation on h, that is, the existence of common prefixes between the words in h ± , measured by the parameter τ ( h) (see Section 2.1). In Section 3.2, we will also estimate the probability of the existence of long common factors in the middle part of the words of h ± . Applications to subgroup properties are discussed in Section 4.

Initial cancellation

Let T n be the random variable, relative to the probability law P n , given by T n ( h) = τ ( h). Our main theorem on initial cancellation is the following. Here we only sketch the main steps of the proof, which is rather technical. The first step is to observe that the probability that T n ( h) > τ (n) is bounded above by the sum of the following probabilities:

-the probability lower ν that K n > ν(n); -the probability P 1 that K n ≤ ν(n) and for some i < j, h i and h j have a common prefix of length greater than τ (n) (or h i and h -1 j , or h -1 i and h -1 j , or h -1 i and h -1 j ); -the probability P 2 that K n ≤ ν(n) and for some i, h i and h -1 i have a common prefix of length greater than τ (n).

The proof now consists in bounding P 1 and P 2 .

First we have P 1 ≤ ν(n) 2 (P 1,1 + P 1,2 + P 1,3 + P 1,4 ), where P 1,1 (resp. P 1,2 , P 1,3 , P 1,4 ) is the probability for a pair of words (h, h ′ ) that h and h ′ (resp. h and h ′ -1 , h -1 and h ′ , h -1 and h ′ -1 ) have a common prefix of length t = 1 + τ (n).

Since h and h ′ are drawn independently, we have

P 1,1 = |u|=t P n [h ∈ u à * ]P n [h ′ ∈ u à * ]. Note that |u|=t P n [h ∈ u à * ] = |u|=t P n [h ∈ à * u -1 ] = 1. So P 1,1 ≤ max |u|=t P n [h ∈ u à * ] = max |u|=t γ 0 (u). In view of Lemma 2.4, it follows that P 1,1 ≤ K 1 c t 1 .
The same reasoning yields the same bound for P 1,2 and P 1,3 . It also yields the inequality P 1,4 ≤ max |u|=t P[h ∈ Ã * u]. This can be bounded using Theorem 2.2, provided we know that h is long enough. Thus we get, for all n large enough, P 1,4 ≤ upper µ + K 1 c t 1 + K|Q|c µ(n)-t . Next we bound P 2 . We first get P 2 ≤ ν(n

) |u|=t P n [h ∈ u à * u -1 ].
For each u of length t and for all h long enough, using Theorem 2.2, we have

P n [h ∈ u à * u -1 ] = p∈Q γ 0 (p)γ(p, u)   q∈Q P[Q p•u |h|-2t = q]γ(q, u -1 )   ≤ p∈Q γ 0 (p)γ(p, u)   q∈Q (γ(q) + Kc |h|-2t )γ(q, u -1 )   ≤ γ 0 (u)   γ(u -1 ) + Kc |h|-2t q∈Q γ(q, u -1 )   ≤ γ 0 (u) K 1 c t 1 + |Q|Kc |h|-2t K 1 c t 1 .
Therefore, summing for all u of length t:

P 2 ≤ ν(n) upper µ + K 1 c t 1 + |Q|Kc µ(n)-2t K 1 c t 1 .
The remainder of the proof of Theorem 3.1 is a simple application of these upper bounds, to make sure that all are exponentially small, super-polynomially small, or simply tend to 0.

Probability of multiple occurrences of long factors

In view of Lemma 2.1, we are interested in bounding the probability that a word of length βµ(n) has several occurrences in the words of h ± , at distances at least βµ(n) from the extremities (and then take β = 1 8 , another value for β will be chosen in Section 4). This probability itself is bounded by the sum of the following probabilities:

-the probability P 1 that such a word has two occurrences in h ±1 i and h ±1 j for some i = j; -the probability P 2 that such a word has two occurrences in h i (or in h -1 i ) for some i; -the probability P 3 that such a word has an occurrence in h i and an occurrence in h -1 i for some i. Proposition 3.2 There exist constants b 1 , b 2 , b 3 > 0, L 1 , L 2 , L 3 > 0 and 0 < d 1 , d 2 , d 3 < 1, depending on the Markovian automata, the constant β and the size of the alphabet, such that, for i = 1, 2, 3:

-if µ(n) > b i log n, then P i tends to 0;

-if the length of the words generated is at most d

-1 4 µ(n) i , then P i ≤ L i d 1 2 µ(n) i .
Sketch of proof. We first sketch the proof concerning P 1 . Let 0 < a < β: the probability that h 1 and h 2 have a common factor of length aµ(n) at distance at least βµ(n) from the extremities, is greater than or equal to P 1 . Let v be a word of length aµ(n) and let i > βµ(n).

Using Theorem 2.2 and Lemma 2.4, we find that the probability that v occurs as a factor of h starting at position i is

p,q∈Q γ 0 (p)P[Q p i = q]γ(q, v) ≤ γ(v) + Kc βµ(n) ≤ K 1 c aµ(n) 1 + Kc βµ(n) .
It follows that the probability P 1 (v, i, j) that v occurs as a factor in h 1 and h 2 , in positions i and j respectively, i, j > βµ(n), satisfies

P 1 (v, i, j) ≤ γ(v) + Kc βµ(n) 2 ≤ γ(v) K 1 c aµ(n) 1 + 2Kc βµ(n) + K 2 c 2βµ(n) .
Therefore, the probability that h 1 and h 2 have a common factor of length aµ(n) starting at fixed positions i, j > βµ n , P 1 (i, j) = |v|=aµ(n) P 1 (v, i, j), satisfies

P 1 (i, j) ≤ K 1 c aµ(n) 1 + 2Kc βµ(n) + 2r 2r -1 (2r -1) aµ(n) K 2 c 2βµ(n) .
Thus, if a < -2β log c log(2r-1) (so that (2r -1) a c 2β < 1), we have

P 1 (i, j) ≤ L ′ 1 d µ(n) 1
for some constants L 1 and d 1 (with d 1 = max(c a 1 , c β , (2r -1) a c 2β )). Now P 1 ≤ i,j>βµ(n) P 1 (i, j), and bounding this sum raises a difficulty as we have not assumed, so far, that L n is bounded.

We can get simple convergence to 0 without assuming bounded length, if µ(n) grows sufficiently fast: if µ(n) > b log n for some b > -2 log d1 and if

1 < d < -b 2 log d 1 , then P[L n > n d ] < n -d E(L n ) = 1 n d-1
(using Markov's inequality and the fact that E(L n ) = n). So

P 1 ≤ P[L n > n d ] + n d 2 L ′ 1 d µ(n) 1 ≤ L ′ 1 n 2d d µ(n) 1 ≤ L ′ 1 n b log d1+2d ,
and our assumptions guarantee that b log d 1 + 2d < 0.

We also obtain a genericity result by imposing a generic bound on the length of the words under consideration. More precisely, if

|h 1 |, |h 2 | ≤ d -1 4 µ(n) 1
, then the probability P 1 satisfies

P 1 ≤ d -1 4 µ(n) 1 2 L ′ 1 d µ(n) 1 ≤ L ′ 1 d -1 2 µ(n) 1
. This is sufficient to conclude the proof concerning P 1 .

To bound P 2 , we observe that if a word w has two occurrences in some h, these occurrences may overlap but whatever the situation, the prefix of w of length 1 4 |v| has two occurrences separated by a gap of at least 1 4 |v|, using classical combinatorics on words. So we want to bound the probability that h 1 contains two occurrences of a word v of length aµ(n), a < β 4 has occurrences at positions i > βµ(n) and j > i + β 2 µ(n). Using again Theorem 2.2 and Lemma 2.4, we find that for v, i and j fixed, this probability satisfies P 2 (v, i, j) = p,q,q ′ ∈Q γ 0 (p)P[Q p i = q]γ(q, v)P[Q q•v j-i-aµ(n) = q ′ ]γ(q ′ , v)

≤ γ(v) 2 + 2KK 1 c βµ(n) 1 + K 2 c 2βµ(n) .
The proof then follows the same steps as for the bound of P 1 .

As for P 3 , we note that if w and w -1 both have occurrences in some reduced word h, then these occurrences may not overlap: if v is the prefix of w of length 2 3 |w|, then v and v -1 have occurrences in h, separated by a gap of at least 2 3 |w|. The proof then follows the same steps as for the bound of P 2 . ⊓ ⊔

Fig. 1 :

 1 Fig. 1: Starting with {a -1 bb, ba}, a loop labeled by each word is built around 1; the edge 1 a -1

Fig. 2 :

 2 Fig. 2: Markovian automata A and A ′ .

  Distributions related to the group P SL(2, Z) = a, b | a 2 , b 3 : Figure 2 represents two Markovian automata: the transitions are labeled by a letter and a probability, and each state is decorated with the corresponding initial probability. The support of the distribution defined by automaton A is the set of words over alphabet {a, b, b -1 } without occurrences of the factors a 2 , b 2 , (b -1

Theorem 3 . 1

 31 Let 0 < α < 1 and let τ (n) be a function such that τ (n) ≤ αµ(n). • Exponential genericity case: If τ (n) grows at least linearly, ν grows sub-exponentially (ν(n) = o(d n ) for every d > 1) and upper µ and lower ν are exponentially small, then T n ≤ τ (n) exponentially generically. • Super-polynomial genericity case:If τ (n) grows faster than log n (log n = o(τ (n))), ν grows at most polynomially (ν(n) = O(n d ) for some d > 1) and upper µ and lower ν are super-polynomially small, then T n ≤ τ (n) super-polynomially generically. • Genericity case: Suppose now that lim τ (n) = ∞. Any one of the following conditions implies that T n ≤ τ (n) generically: -ν(n) is bounded; -ν(n) = O(log d n) for some d > 0, upper µ = o( 1 log 2d n ) and τ (n) grows faster than log log n; -ν(n) = O(n d ) for some d > 0, upper µ = o(n -2d ) and τ (n) grows faster than log n.

Work supported by ANR 2010 BLAN 0204 MAGNUM. Work supported by ANR 2010 BLAN 0204 MAGNUM. Work supported by ANR 2010 BLAN 0202

Applications

As observed in Section 2.1, if T n ( h) < 1 2 min |h i |, then the Stallings graph Γ(H) is in the shape of a central tree, of height T n ( h), and of a collection of outer loops, one for h i . In that situation, h freely generates the subgroup H. Moreover, Γ(H) is constructed in linear time, simply by computing the initial cancellation in the tuple h ± . Theorem 4.1 (Base) Under the hypotheses of Theorem 3.1, a randomly chosen tuple is a basis of the subgroup it generates exponentially generically (resp. super-polynomially generically, generically).

Touikan [START_REF] Nicholas | A fast algorithm for Stallings' folding process[END_REF] proposed an algorithm that computes the folding of the bouquet (see Section 1.2) of h in time O(m log * N ), where N is the size of the bouquet, and m is the number of states that have been merged in the process. Using this result in our generic settings, we obtain the following theorem. By Lemma 2.1, the probability that H is not malnormal is bounded by the sum that T n ( h) > 1 8 µ(n) and the probabilities that, assuming T n ( h) ≤ 1 8 µ(n), a word of length 1 8 µ(n) has two occurrences in the words of h ± , at distance at least 1 8 µ(n) from the extremities. In view of Proposition 3.2, this leads to the following statement. Let lbound L be the probability that

Theorem 4.3 (Malnormality) Let h be a tuple of elements of F generated at random and let H = h .

If µ grows at least linearly, ν grows sub-exponentially and upper µ , lower ν and lbound L are exponentially small, then H is exponentially generically malnormal.

If µ grows faster than log n, ν grows at most polynomially and upper µ , lower ν and lbound L are superpolynomially small, then H is exponentially generically malnormal.

Each of the following conditions is sufficient to guarantee that H is generically malnormal:

• ν is bounded and upper µ , lower ν and lbound L tend to 0; We finally discuss the properties of the quotient of F by the normal closure of a random subgroup under our model. Recall that a reduced word h its cyclically reduced when every cyclic permutation of u is reduced. To any reduced word h we associate its cyclic reduction c(h) obtained by repeatedly remove the first and the last letter while they are the inverse of each other. The normal subgroup generated by a set h = {h 1 , . . . , h k } is the same as as the one generated by c = {c(h 1 ), . . . , c(h k )}. The small cancellation theory [START_REF] Lyndon | Combinatorial group theory[END_REF] can greatly help in studying the properties of the quotient: if whenever a word u is a factor of two distinct cyclic conjugates of c then |u| ≤ λ min i∈{1...k} |c(h i )|, then h is said to satisfy the small cancellation property C ′ (λ). If h satisfies C ′ (1/6), then the quotient has a lot of nice algebraic properties; we state some in the following theorem and, due to the lack of space, refer to [START_REF] Lyndon | Combinatorial group theory[END_REF] for the definitions.