Fehmi H'mida
email: fehmi.hmida@esti.rnu.tn

Pierre Lopez
email: pierre.lopez@laas.fr

Multi-site scheduling under production and transportation constraints

Keywords: Production and transportation scheduling, constraint programming, cumulative resource, packing problem

For the enterprises organized in several distributed production sites, usually, production scheduling models presume either an instantaneous delivery of products or an unlimited number of available vehicles for transporting products. However, the transportation of the intermediate products to the sites is an important activity within the whole process of manufacturing, and the efficient coordination of production and transportation becomes a challenging problem in the actual higher collaborative and competitive environments. This work focuses on the integrated production and transportation scheduling properly managing the resources capacity, material flows and temporal interdependencies between sites. A casestudy is reported and the industrial problem under consideration is modeled as a Constraint Satisfaction Problem (CSP). Besides scheduling under resource constraints, the model presented in this paper expands the packing problem to the area of transportation operations scheduling. It is implemented under the constraint programming language CHIP V5. The provided solutions determine values for the various variables associated to the production and transportation operations realized on the whole multi-site, as well as the curves with the profile of the total consumption of resources in time.

INTRODUCTION

A multi-site enterprise is a company with several distributed production sites, where sites are using the intermediate products of other sites to manufacture the products of the enterprise [START_REF] Sauer | Integrating Transportation in a Multi-Site Scheduling Environment[END_REF]. The scheduling problem is the temporal assignment of activities to resources where a number of goals and constraints have to be regarded.

For production scheduling, numerous researches have been proposed in the literature to address the problem in process industries. Various types of methods have been employed such as the mathematical programming approaches, heuristic and rule-based procedures. Extensive reviews of planning and scheduling methodologies, as well as contributions reported in the field, can be found in [START_REF] Shah | Single and multisite planning and scheduling: Current status and future challenges[END_REF], [START_REF] Pekny | Towards the convergence of theory and practice: A technology guide for scheduling/planning methodology[END_REF], [START_REF] Reklaitis | Overview of planning and scheduling technologies[END_REF], [START_REF] Floudas | Continuous-time versus discrete-time approaches for scheduling of chemical processes: A review[END_REF] and [START_REF] Méndez | State-of-the-art review of optimization methods for short-term scheduling of batch processes[END_REF].

Usually, production scheduling models presume either an instantaneous delivery of products or an unlimited number of available vehicles for transporting products. However, the problem in which a limited number of vehicles available in a site can be found in most of the production sites, involving assignment, routing and timing decisions in a multi-site scheduling framework.

Thus, interacting production and transportation activities requires the consideration of additional features and constraints. Departure times of vehicles depend on the availability of products in site tied to the production scheduling defined, as well as on the availability of the assigned vehicle and on the capacities production of sites. The efficient coordination of production and transportation operations remains an open area for research [START_REF] Erengüç | Integrated production/distribution planning in supply chains: An invited review[END_REF][START_REF] Sarmiento | A review of integrated analysis of production -Distribution systems[END_REF][START_REF] Chen | Integrated production and distribution operations: Taxonomy, models and review[END_REF][START_REF] Elmaraghy | Concurrent design of product modules structure and global supply chain configurations[END_REF]. In general, literature related to the production-transport scheduling problems focuses mainly on the integration in strategic and tactical levels of analysis; the start times of transportation and production operations, the allocation of vehicles, the resource capacities in site and the products to be delivered, are issues rarely addressed jointly. This work focuses on the integrated scheduling of the production and transportation operations, consuming resources (respectively machines and vehicles) with limited capacities.

We propose a multi-site scheduling approach optimizing the end date of the production, while satisfying at the same time the constraints between operations and the resource constraints, that is, at every time, the sum of the resource consumptions for the operations should not exceed the production and the transportation capacities in sites. We model the problem in the CSP (Constraint Satisfaction Problem) form. The constraint programming paradigm consists in finding among the possible values of a set of variables those which satisfy all the constraints simultaneously. We are principally interested in the respect of the capacity resources and the synchronization operations, for jointly production and transportation scheduling in the multi-site. Besides scheduling under resource constraints, the model presented in this paper expands the packing problem to the area of transportation operations scheduling. Analogous to placing rectangular box onto a 3D space, we model the transportation multi-site scheduling by placing the transportation operations onto a space with three dimensions temporal, geographical and assignment. For solving, we implement the cumulative and packing global constraints concept, which provides a compact and concise description of the problem.

The remainder of the paper is organized as follows. The industrial problem considered is defined in Section 2. Section 3 recalls the basic principles of constraint programming and presents the cumulative and packing global constraints concept. Section 4 defines the parameters, variables and constraints of the industrial problem and formulates the multi-site scheduling model under production and transportation constraints. In Section 5, the proposed approach is implemented under the constraint programming language CHIP V5; some results are presented. Finally, Section 6 is devoted to the concluding remarks and some future research directions.

INDUSTRIAL PROBLEM STATEMENT

The industrial problem handled in this work appears as follows: 5 production sites appertaining to the same company, and realizing 11 types of products (Table 1). The manufacturing of a product requires a succession of production operations, realized each on a given site. The transfer between sites is provided by transportation operations (Figure 1). The term "operation" is employed to characterize a "workload".

Product Quantity Q x Site 1 Site 2 Site 3 Site 4 Site 5 A 180 X X X X B 120 X X C 150 X D 130 X X X X E 140 X X X X F 150 X X G 20 X M 70 X X X X N 180 X X X O 100 X X X X K 30 X X X X
Table 1: Quantity and process production of products A site is defined by its production capacity and its transportation capacity. The number of resources (i.e. of machines) in a site limits the production capacity (Table 2).

Site

Maximal number of machines

Maximal number of trailers The transportation is realized by vehicles composed by two types of resources: tractors and trailers (Figure 2). Trailers, properties of the company, are defined by their incorporation bases (sites), their availability over the planning period, and their maximal number in every site (Table 2). Every trailer can contain a maximal number of 40 products. A subcontracting transport company, supplying tractors to deliver trailers loaded from a site to the other one, ensures the transportation operations. The subcontractor can guarantee a simultaneous availability of 10 tractors at most. A tractor trip consists in towing a loaded trailer from its incorporation site to the delivery site followed by its delivery to the departure site (Table 3). The deliveries are realized by product. The elaboration of production plans of the 11 products for all the 5 sites supposes a horizontal synchronization of all the sites to assure the manufacturing and the provision of products in due course. This entails that the scheduling decisions integrate strictly the production constraints and the transportation constraints. In this treated problem, the decisions to make consist:

ST 1 4 5 ST 2 5 4 ST 3 3 5 ST 4 3 5 ST 5 3 -
-To determine for every site, the start dates of the production operations while respecting the limitation of the production resources capacity (number of machines in site) -To determine for every site, the start dates of the transportation operations while respecting the limitation of the transportation resources capacity (number of trailers in site)

-To allocate tractors to the transportation operations within the limits of the simultaneous availability of 10 tractors, and by considering the geographical disparity of sites.

Thus, it is a matter of finding a solution that minimizes the production end date of all the products, by respecting at the same time precedence, cumulative and assignment constraints.

This multi-site scheduling problem is approached by considering the case of a company within which there is a central logistic department. It is a matter of distributing and coordinating production and transportation between sites while leaving to every site autonomy at the local scheduling level.

CONSTRAINT PROGRAMMING

Many decision problems in industry can be viewed as satisfiability or optimization problems.

Different formulations (models) can be associated with the problem under study, and several criteria could be considered to evaluate a formulation. Two paradigms have reached a high degree of sophistication from the viewpoint of both theory and implementation: Constraint Programming (CP) and Mixed Integer Programming (MIP). The CP and MIP paradigms have strengths and weaknesses that can complement each other. The major difference between both techniques is the inference method. Inference is the act of revealing implicit constraints from the existing ones, in order to reduce the search space. On the one hand, CP, through the use of sophisticated propagation techniques, privileges primal inference. On the other hand, MIP, through the techniques of relaxation and strengthening through cutting planes, privileges dual inference [START_REF] Salvagnin | Constraint programming techniques for mixed integer linear programs[END_REF].

In the last years, several researchers from the CP and MIP communities have investigated the possibility to integrate the methodologies proper to these paradigms [START_REF] Hooker | Integrated Methods for Optimization[END_REF][START_REF] Milano | Constraint and Integer Programming: Toward a Unified Methodology[END_REF]. Such an integration has the potential to yield important benefits, and the literature on this topic is recent but growing.

In this work, we privileged the Constraint Programming approach, and particularly the use of [START_REF] Gyssens | Decomposing constraint satisfaction problems using database techniques[END_REF][START_REF] Van Hentenryck | Constraint satisfaction using constraint logic programming[END_REF][START_REF] Vargas | Modélisation du processus de conception en ingénierie des systèmes mécaniques : Mise en oeuvre basée sur la propagation de contraintes[END_REF][START_REF] Chan | A simulation study with quantity flexibility in a supply chain subjected to uncertainties[END_REF].

The CSP formalism

A CSP is defined as a triplet (X, D, C) [START_REF] Montanari | Network of constraints: Fundamental properties and applications to picture processing[END_REF][START_REF] Dechter | Constraint Processing[END_REF] with:

• X = (X1, X2, ..., Xn) is the set of variables of the problem;

• (D = D1, D2, ..., Dn) is the set of domains. Each variable Xi ! " X, 1 ≤ i ≤ n, is associated with one domain Di ! " D which represents all the possible values for Xi. These domains are finite, but of any kind, symbolic or numerical;

• C = (C1, C2, ..., Ck) is the set of constraints. Each constraint Cj is a relation between some variables of X. These constraints are of any kind, linear (e.g., X1 + X2 ≤ 4) or nonlinear (e.g., X3 ≠ X4).

Given a CSP (X, D, C), a feasible solution is an instantiation of all the variables, so that all the constraints are simultaneously satisfied.

CSP solving

General CSPs belong to the class of NP-complete problems. Their solving is based on the application of constraint propagation techniques (filtering phase) and on tree search (decisionmaking phase).

Filtering phase: It consists in removing the values of the variables that have no chance to be among a solution. Within the filtering algorithms, the arc-consistency (AC) is probably the most used. This algorithm checks the consistency of a constraint between two variables of a CSP. Since the seminal AC-3 [START_REF] Mackworth | Consistency in networks of relations[END_REF], many more powerful versions have been proposed [START_REF] Mohr | Arc and path consistency revisited[END_REF][START_REF] Bessière | Arc-consistency and arc-consistency again[END_REF]. However, the easy implementation of AC-3, its adaptability to broader frameworks than the classical CSP, as well as recent improvements of the basic version [START_REF] Zhang | Making AC-3 an Optimal Algorithm[END_REF][START_REF] Bessière | An optimal coarse-grained arc consistency algorithm[END_REF][START_REF] Arangu | AC3-OP: An Arc-Consistency Algorithm for Arithmetic Constraints[END_REF]) make this algorithm a widely used filtering technique.

Decision-making phase: It consists in finding a complete instantiation (a solution) satisfying all the constraints. Such an instantiation is carried out by means of various algorithms based on tree search, e.g., Backtrack [START_REF] Bitner | Backtracking programming techniques[END_REF], Limited Discrepancy Search [START_REF] Harvey | Limited Discrepancy Search[END_REF], Randomization & Restart [START_REF] Gomes | Boosting Combinatorial Search Through Randomization[END_REF]. Some of them are hybrid algorithms in the sense they perform a certain level of filtering on each variable instantiation in the tree expansion (Forward-Checking, Real-Full-Look-Ahead [START_REF] Nadel | Constraint Satisfaction Algorithms[END_REF],

Maintaining Arc-Consistency [START_REF] Sabin | Contradicting conventional wisdom in constraint satisfaction[END_REF]).

Last, let us mention that scanning the search space can be improved by ordering heuristics (order of the variable instantiations and choice of a value for a given variable).

Global constraint

Combinatorial problems generally present independent substructures easily identifiable, all of which being formulated by a group of constraints. This is the reason for introducing the concept of "global constraint". A global constraint is a subset of constraints, corresponding to a substructure of the original problem. Several types of global constraints have been developed: alldifferent, diffn, cycle, sequence, cumulative, etc. In the example of the global constraint "alldifferent (X1, ...., Xn)", each of the variables X1, ..., Xn must take a different value, i.e., X1 ≠ X2 ≠… ≠ Xn. To each global constraint, at least one specific filtering algorithm is associated. A global constraint takes into account the group of constraints as a whole, in a more effective manner than standard propagation techniques applied to separate constraints.

Cumulative constraint

Scheduling under resource constraints handles the problem taking, on the one hand, a set of tasks i in which every task is defined by a start time S i , a processing time p i as well as the quantity of resource consumption r i,k , and, on the other hand, a limit of resource not exceeding R k . This capacity limitation of resource k imposes that at every time, the sum of the resource consumptions for the tasks in process should not exceed the resource capacity. It yields:

R k k k i, (t) T i r ≤ ∈ ∑ with T k (t) = {i} i=1..n with t ∈ [S i , S i + p i ) .
This problem can be classified in the category of RCPSPs (Resource-Constrained Project Scheduling Problems), for which a variety of methods were employed for its resolution: linear programming, constraint programming, heuristics and metaheuristics, and tree search ( (Baptiste and Le Pape, 1997;[START_REF] Beldiceanu | Solving resourceconstrained project scheduling with CHIP[END_REF][START_REF] Dorndorf | A Survey of Interval Capacity Consistency Tests for Time-and Resource-Constrained Scheduling[END_REF][START_REF] Brucker | Resource-constrained project scheduling problem: Notation, classification, models and methods[END_REF]GOThA, 2006;[START_REF] Özdamar | A survey on the resource constrained project scheduling problem[END_REF] and more recently and very promisingly satisfiability-based solving (Coelha and Vanchoucke, 2011). In constraint programming, the cumulative global constraint [START_REF] Aggoun | Extending CHIP in order to solve complex scheduling and placement problems[END_REF] found in the RCPSP a particularly favourable field of application.

Form: Cumulative ([S 1 , ..., S n ], [p 1 , ..., p n ], [E 1,k , ..., E n,k ], [r 1,k , ..., r n,k ], R k , Z k ).
In the cumulative global constraint, a set of n tasks has to be planned on resource k; E i,k corresponds to the energy required and Z k the calculation of the completion time of the tasks on resource k (Figure 3). It consists in the evaluation, for a given interval, of the sum of the resource consumptions required to perform the tasks; if this number exceeds the resource capacity then a contradiction is detected.

(1) The first filtering algorithms were related to the notion of compulsory part of a task [START_REF] Lahrichi | Scheduling: the notions of hump, compulsory parts and their use in cumulative problems[END_REF]. They compute a cumulated resource profile of all the compulsory parts of the tasks and prune the origins of the tasks with respect to this profile in order to not exceed the resource capacity. These methods are sometimes called timetabling. Even if these methods are quite local, i.e., a task has a non-empty compulsory part only when the difference between its latest start and its earliest start is strictly less than its duration, it scales well and is therefore widely used. Later on, more global algorithms based on the resource consumption of the tasks on specific intervals were introduced: energetic reasoning [START_REF] Erschler | Energy-based approach for task scheduling under time and resource-constraints[END_REF]), taskinterval [START_REF] Caseau | Cumulative Scheduling with Task Intervals[END_REF], cores-times (Klein and Scholl, 1999), etc.

Packing constraint

Given a set of components and one container (an available space area), a packing problem consists in finding the position variables of components in the container in effort to minimize a set of objectives, while respecting certain constraints. Every packing problem presents at least non-overlapping constraints between components and, in most of the cases, appertaining constraints to the container. They define the packing constraint.

∀ i ∈ [1,m], ∀ j ∈ [1,m], i≠j, ∃ k ∈ [1,n] such as O ik ≥ O jk + L jk ∨ O jk ≥ O ik + L ik (2) ∀ k ∈ [1,n], i ∈ [1,m] Maximum (O ik + L ik ) ≤ End k (3) i ∈ 1..m
Generally, components (boxes) are physical objects. In the literature, certain authors also consider abstract objects, presenting a direct analogy with the problem at hand [START_REF] Dyckhoff | A typology of cutting and packing problems[END_REF]. State of the art on packing problems shows that all types of optimization techniques (mathematical programming, constraint programming, heuristics and metaheuristics, etc.)

were used for their resolution [START_REF] Cagan | A survey of computational approaches to threedimensional layout problems[END_REF][START_REF] Dowsland | Three dimensional packing -solutions approaches and heuristic development[END_REF].

In constraint programming, the packing global constraint noted "diffn" [START_REF] Beldiceanu | Introducing Global Constraints in CHIP[END_REF] imposes the non-overlapping of a set of multidimensional rectangular boxes (Equation 2) and their appertaining in a limited space (Equation 3). The global constraint "diffn" imposes simultaneously these two types of constraints and then offers a more concise and integrated modelling of the packing problem. A first possible method for filtering is to use constructive disjunction. The idea is to try out each alternative of a disjunction (e.g., given two boxes B 1 and B 2 that should not overlap, we successively assume for each dimension that B 1 finishes before B 2 , and that B 2 finishes before B 1 ) and to remove values that were pruned in all alternatives. For the two-dimensional case of diffn a second possible solution used in [START_REF] Verdier | Résolution de problèmes d'aménagement spatial fondée sur la satisfaction de contraintes[END_REF] is to represent explicitly the twodimensional domain of the origin of each rectangle by a quadtree [START_REF] Samet | The design and analysis of spatial data structures[END_REF] and to accumulate all forbidden regions within this data structure. As for conventional domain variables, a failure occurs when a two-dimensional domain get empty. A third possible filtering algorithm based on sweep is described in [START_REF] Beldiceanu | Sweep as a Generic Pruning Technique Applied to the Non-Overlapping Rectangles Constraints[END_REF].

Form: diffn([[O11,…,O1n,L11,…,L1n],…,[Om1,…,Omn,Lm1,…,Lmn]], [End1,..,Endn])

MULTI-SITE SCHEDULING MODEL

In Section 2, we posed the industrial problem. In the sequel, we propose the associated multisite scheduling model in the form of a constraint satisfaction problem.

The proposed model is based around the definition of the parameters, the variables and the constraints translating the various characteristics related on times, the products and the logistical system. A solution consists in assigning a start time to each production and transportation operation by satisfying all the constraints.

Parameters

The data of the multi-site scheduling problem are represented by the following parameters:

• Elementary period of time t: It is the unit of time in terms of scheduling,

• Decision horizon H, t∈[1, H]: It is the period over which the scheduling decisions are made,

• The set of production sites ST i : ST = (ST 1 , ST 2 , ST 3 , ST 4 , ST 5 ),

• The set of products: X = (A, B, C, D, E, F, G, M, N, O, K),

• The set of production operations x i : T = (A1, A3, A4, A5, B1, B5, C1, D1, D3, D4, D5, E2, E3, E4, E5, F2, F5, G1, M2, M3, M4, M5, N1, N3, N4, O2, O3, O4, O5, K2, K3, K4, K5),

• The set of transportation operations x ii' : T T = (A13, A34, A45, B15, D13, D34, D45, E23, E34, E45, F25, M23, M34, M45, N13, N34, O23, O34, O45, K23, K34, K45).

The achievement of each product requires the processing of a set of operations x i and x ii' .

Each operation is performed on a different site. Example: Product B requires the realization of 3 operations: (B1, B15, B5). B1 and B5, production operations, are respectively carried out on site 1 and site 5. B15 corresponds to the transportation operation from site 1 to site 5.

• Production and transport capacity, R k et R T k : They represent for each production site, respectively the maximal number of resources k (machines), and the maximal number of resources k T (trailers) being able to be used during various periods T (Table 2),

R 1 = 4; R 2 = 5; R 3 = 3; R 4 = 3; R 5 = 3; R 1 T = 5; R T 2 = 4; R T 3 = 5; R T 4 = 5,
• Energy required E x i : It denotes the energy required to perform the production operation x i on unit resource k,

• Energy required E x ii' : It denotes the energy required to perform the transportation operation

x ii' on unit resource k T ,

• Transport unit duration D ii' : It corresponds to the time of one transportation operation

x ii' (round trip) between a site ST i and a site ST i ' (Table 3),

• Limit β: It corresponds to the maximal number of tractors exploitable simultaneously.

This value agreed suited with the subcontracting transport company corresponds to 10.

Variables

The various variables that intervene in the scheduling model are the following:

• Start time Sx i : variable corresponding to the start time of the production operation x i ,

• Start time Sx ii' : variable corresponding to the start time of the transportation operation

x ii' ,

• Consumption r x i : number of machines allocated to the production operation x i ,

• Consumption r x ii' : number of trailers allocated to the transportation operation x ii' ,

• Duration px i : duration of the production operation x i ,

• Duration px ii' : duration of the transportation operation x ii' ,

• Completion time Z i : completion time of all production operations x i on site ST i ,

Z i = max (Sx i + px i ) for i ∈ {1, 2, 3, 4, 5}, x ∈ {A, B, C, D, E, F, G, M, W, O, K} (4)
Example: Z 1 =max(SA 1 + pA 1 , SB 1 + pB 1 , SC 1 + pC 1 , SD 1 + pD 1 , SG 1 + pG 1 , SW 1 + pW 1 )

• Completion time Z i T : completion time of all transportation operations x ii' from site ST i to sites ST i' ,

Z i T = max (Sx ii' + px ii' ) for i ∈ {1, 2, 3, 4}, i' ∈ {2, 3, 4, 5}, (5)

and x ∈ {A, B, C, D, E, F, G, M, W, O, K} with i ≠ i'

Example: Z 1 T =max(SA 13 + pA 13 , SB 15 + pB 15 , SC 13 + pC 13 , SN 13 + pN 13 )

• Total completion time: completion time of all production and transportation operations on all sites,

Z = max(Z 1 , Z 2 , Z 3 , Z 4 , Z 5 , Z 1 T , Z 2 T , Z 3 T , Z 4 T ) (6)
• Tx ii' : number of tractors transporting the trailers allocated to the transportation operation x ii' , Tx ii' = r x ii'

(7)

• Lx ii' : index of the first tractor in the list of tractors allocated to the transportation

operation x ii' , Lx ii' ∈ {1, 2,…,10} (8)
• Wx ii' : number of round trips realized by tractors to assure the transportation operation

x ii' , Wx ii' ∈ {1, 2,…,20} (9)

Constraints

The problem is subject to five types of constraints: the energy constraints, the resource capacity constraints, the precedence constraints, the synchronization constraints, and the packing constraints.

• Energy constraints:

This corresponds to the energy consumption of an operation on a resource [START_REF] Lopez | Ordonnancement de tâches sous contraintes : une approche énergétique[END_REF]. It expresses the existing relation between the variation of the operation duration px i (respectively px ii' ) according to the number of resources r x i (resp. r x ii' ) allocated for its processing.

For production operations E

x i = px i * r x i = constant (10)
For transportation operations E x ii' = px ii' * r x ii' = constant (11) Figure 5 shows an example of a production operation A 1 with E x i = 6. In this case, the possible values of px i and r x i , are: ((2.3), (3.2), (6.1)). The solution (2.3) means that production operation A 1 requires 3 resources during 2 time units.

(E A 1 = 6, pA 1 = 2, r A 1 = 3)
• Capacity resource constraints:

For each resource k (respectively k T ), they express the fact that, at every time, the total number of machines (resp. trailers) used by a set of operations x i (resp. x ii' ) processed at time

t, Sx i ≤ t ≤ Sx i + px i (resp. Sx ii' ≤ t ≤ Sx ii' + px ii' ) does not exceed a certain capacity R k (resp.

R k T

). They are used to model the cumulative resource constraints.

For production operations For

i ∈ {1, 2, 3, 4, 5}, k ∈ (1, 2, 3, 4, 5), x ∈ {A, B, C, D, E, F, G, M, W, O, K}, ∀ t ∈ [min (Sx i ), max (Sx i + px i )] R k px Sx t Sx x r i i i i ≤ ∑ + < < (12)
For transportation operations For i = {1, 2, 3, 4}, i' = {2, 3, 4, 5}, k = (1, 2, 3, 4)

, x ∈ {A, B, C, D, E, F, G, M, W, O, K} with i ≠ i', ∀ t ∈ [min(Sx ii' ), max(Sx ii' + px ii' )] R T k px Sx t Sx x r ii' ii' ii' ' ii ≤ ∑ + < < (13)
• Precedence constraints:

The precedence constraints between production operations are of two types; those corresponding to the process plan of a product and those imposed by the production manager.

They have the form i → j, prohibiting the start of the second operation, j, before the end of the first, i.

-Process plan constraints: for each product a process plan sets a sequence of production operations necessary for its realization.

Sx j ≥ Sx i + px i (14)
For example, the process plan of product A is: (A1, A3, A4, A5). The associated precedence constraint states: A4 → A5 is SA 5 ≥ SA 4 + pA 4 .

-Production constraints: some products must be processed before others (constraints imposed by the manager production). These inter-products constraints are expressed as follows:

G → E: SE 3 ≥ SG 1 + pG 1 (15)

• Synchronization constraints:

These constraints concern the synchronization of the production and transportation.

Indeed, the transportation of every product x from the site ST i to the following site ST i' cannot begin before the end of production operation x i in the site ST i . Also, the production of a product x on a site i' can begin only after the delivery of all the quantity of Product x coming from Site i, and given that every trailer can contain only a maximal number of products ( 40), it means that the delivery of the total quantity of a product can require several successive round trips. Constraint ( 16) constitutes a coordination rule in the definition of the master planning of the multi-site company.

∀ i = {1, 2, 3, 4}, i' = {2, 3, 4, 5} et x ∈ {A, B, C, D, E, F, G, M, W, O, K} with i ≠ i' Sx ii' ≥ S x i + px i Λ Sx i' ≥ Sx ii' + px ii' (16)
Furthermore, the duration of a transportation operation of a product x must be multiplied by the associated transport unit duration. This means that it must be equal to the round trips Wx ii' multiplied by the transport unit duration D ii' .

px ii' = D ii' * Wx ii' ( 17
)
For example, the transportation duration of Product B from the production site ST 1 towards ST 5 is equal to WB 15 (number of round trips) multiplied by 12 hours (transport unit duration): pB 15 = WB 15 * 12.

• Packing constraints:

In a not conventional way, we exploit the packing constraints to model the scheduling of the transportation operations on the production sites. Concretely, the transportation operations correspond to rectangular boxes to position in a limited three-dimensional space (Figure 6):

- In Figure 6, the transportation operation x 1i' begins in a date Sx 1i' from the site ST 1 to the site ST i' with one tractor (and r x 1i' = 1 , Lx 1i' = 5). The transportation operation x 3j' begins in a date Sx 3j' from the site ST 3 to the site ST j' with 2 tractors (and r x 3j' = 2, Lx 3j' = 1). By combining the three dimensions, the objective is to place in the time every transportation operation, and on the other hand to assign to each a number of tractor(s), this without overlapping the operations, and within the limits of a space (δ: departure sites; H: scheduling horizon and β:

maximal number of tractors).

The non-overlapping and appertaining constraints (2 and 3) are translated in this model by the following equations:

-Non-overlapping constraints:

∀ x ii' ∈ T T , ∀ x jj' ∈ T T , x ii' ≠ x jj' with i and j ∈ {1, 2, 3, 4} Sx jj' ≥ Sx ii' + px ii' ∨ Sx ii' ≥ Sx jj' + px jj' ∨ Lx jj' ≥ Lx ii' + r x ii' ∨ Lx ii' ≥ Lx jj' + r x jj' (18)
-Appertaining constraints:

∀ x ii' ∈ T T Maximum (Sx ii' + px ii' ) ≤ H (19) Maximum (Lx ii' + r x ii' ) ≤ β (20) Maximum (Q ii' ) ≤ δ (21)
Find a multi-site scheduling plan solution consists in determining the start time and the allocation of resources of each production and transportation operation, which satisfy simultaneously all the presented constraints: energy constraints, resource capacity constraints, precedence constraints, synchronization constraints, and packing constraints.

The objective function of the proposed model is to find an optimal multi-site scheduling plan that minimizes the Total completion time (completion time of all production and transportation operations on all sites),

Min [Z = max(Z 1 , Z 2 , Z 3 , Z 4 , Z 5 , Z 1 T , Z 2 T , Z 3 T , Z 4 T )] (22)

EXPERIMENTS

Various propagation and solving algorithms of CSPs have been integrated into Constraint

Programming languages. Many environments have been developed and distributed. Among these environments, some were developed in a commercial perspective (e.g., CHIP, ILOG-Solver), other are pure academic tools (e.g., Oz, Gnu-Prolog, CIAO SICStus). The scheduling model we developed was implemented with CHIP V5. The solving is based on the application of constraint propagation techniques (AC-3 arc-consistency filtering algorithm) and on tree search (Forward-Checking in the decision-making phase). For the ordering heuristics, we used the most_constrained and mindomain rules (most_constrained chooses the variable which has the smallest ratio of the number of values in its domain over the variable degree; mindomain fixes the variable with the smallest value in its domain).

Model implementation

The implementation consists to declare the domain variables (decision), to post the constraints, and finally to enumerate and/or optimize the solutions. The variables are declared as domain variables that take their values in finite sets of integers. The constraints implemented are of two types. The constraints of the first type are written in form of arithmetic linear constraints. The second type uses the concept of global constraints.

Therefore, the cumulative global constraint was used to integrate two specific constraints: the cumulative constraints and the energy consumptions, in turn, the packing global constraint was used to integrate two other particular constraints: the non-overlapping constraints and the appertaining constraints.

Cumulative global constraints

The cumulative constraint imposes that at each time t, if we consider all the present operations, the accumulation of their consumed resources quantity should not exceed the limit of available resources. It is expressed in CHIP V5 by the following predicate:

Cumulative (+Starts, +Durations, +Surfaces, +Resources, +High, +End) Thus, we associated, in every production site, two cumulative constraints, the first relative to the production capacity and the second relative to the transportation capacity.

We present, below, that relative to the limitation of the production capacity on site ST 1 .

Cumulative (Sx 1 , px 1 , E x 1 , r x 1 , R1, Z1)

The variables Sx 1 = [SA1, SB1, SC1, SD1, SG1, SN1], px 1 = [pA1, pB1, pC1, pD1, pG1, pN1], [rA1, rB1, rC1, rD1, rG1, rN1] and Z1 correspond respectively to start times Sx 1 , durations px 1 , number of machines allocated r x 1 of the production operations A1, B1, C1, D1, G1, N1, and to the completion time Z1 of these six operations on site ST 1 . The constants

r x 1 =
E x 1 = [EA1, EB1, EC1, ED1, EG1, EN1
] and R1 correspond respectively to the energy required E x 1 for the realization of each operation A1, B1, C1, D1, G1, N1, and to the production capacity R1 in number of machines on site ST 1 . The rest of the cumulative constraints relative to the production capacities of sites ST 2 , ST 3 , ST 4 and ST 5 take the same form.

We present below the cumulative constraint relative to the capacity of the transportation products from the production site ST 1 .

Cumulative (Sx 1i' , px 1i' , E x 1i' , r x 1i' , R T 1, Z T 1)

The variables Sx 1i' = [SA13, SB15, SD13, SN13], px 1i' = [pA13, pB15, pD13, pN13], [rA13, rB15, rD13, rN13] and Z T 1 correspond respectively to start times Sx 1i' , durations px 1i' , number of trailers allocated r x 1i' of the transportation operations A13, B15, D13, N13 and the completion time Z T 1 of these four operations from site ST 1 . The constants EB15,ED13,EN13] and R T 1 correspond respectively to the energy required E x 1i' for the realization of each operation A13, B15, D13, N13 and the transportation capacity R T 1 in number of trailers on the site ST 1 . The rest of the cumulative constraints relative to the transportation capacities of sites ST 2 , ST 3 and ST 4 take the same form.

r x 1i' =
E x 1i' = [EA13,
According to its commercial description, the processing of cumulative global constraints in CHIP V5 is performed by about twenty of methods. Among the known and effective methods, we can particularly note the energy reasoning and the timetable constraints. The first allows, on the basis of balance between the consumptions of a resource by activities over a time interval and the energy offered by this resource on the same interval, to determine a lower bound on the amount of the resource that can be used [START_REF] Lopez | Ordonnancement de tâches sous contraintes : une approche énergétique[END_REF]. The second has the same goal, but it gets on the basis of constraints called timetable, based on the concept of compulsory part [START_REF] Lahrichi | Scheduling: the notions of hump, compulsory parts and their use in cumulative problems[END_REF], interval of time over which the task is necessarily processed.

Packing global constraints

The packing constraint imposes that, at each time t, the transportation operations (rectangular boxes) do not overlap, and do not exceed the limited three-dimensional space. It is expressed in CHIP V5 by the following predicate:

diffn(+Rectangles, +End)

Therefore we associated to all the transportation operations the following packing global constraint:

diffn([[Sx ii' , Q ii' , Lx ii' , px ii' , 1, r x ii' ]],[H, δ, β])
In the three-dimensional space (temporal, geographical and tractors allocation), the position elements of every transportation operation x ii' are its origins and its lengths. The origins are: the variable Sx ii' (start operation), the parameter Q ii' (departure site, Q ii' = i)

and the variable Lx ii' (tractor index), and the lengths of the transportation operation are:

the variable px ii' (operation duration), the value 1 (a single site of departure) and the variable r x ii' (number of tractors allocated to the operation). The space domain is limited by the scheduling horizon H, the number of sites δ and the number of tractors exploitable simultaneously β. The filtering algorithm applied for the diffn constraint is based on sweep, and it is described in [START_REF] Beldiceanu | Sweep as a Generic Pruning Technique Applied to the Non-Overlapping Rectangles Constraints[END_REF].

Results

The visualization of the consumption on each resource is information making it possible to undergo the satisfaction of all constraints of the problem, and particularly the packing and cumulative global constraints. The presentation of the results wants to be didactic; we then present as an example only the cumulative production and transportation curve of site ST 1 , and the three-dimensional Gantt chart of the total transportation operations. The curve and analysis presented in this section relate to the optimal solution.

Production operations

The production capacity of site ST 1 is equal to 4. It realizes the 6 production operations: A1, B1, C1, D1, G1, and N1. The following table presents the solution values of the operations x 1 realized on site ST 1 . The production cumulative curve of site ST 1 is presented in

Transportation operations

The transportation capacity of site ST 1 is equal to 5 trailers. They are used for the 4 transportation operations: A13, B15, D13 and N13. The following table presents the solutions values of the operations x 1i' .

Operation x 1i'

Energy required The transportation cumulative curve of site ST 1 is presented in

E x 1i'

Start times

Sx 1i'

Three-dimensional packing

The transportation operations are assured by sets (trailer + tractor). The cumulative constraint allows in particular calculating schedules according to the limitation and availability of the resources (machines and trailers). On the other hand, it does not determine how to specify the assignment of trailers to shared tractors. Hence, the implementation of the packing constraint allows us to provide this complementarity and to assure the position without overlapping of the transportation operations in the threedimensional space (time, sites, and tractors).

The 3D space is limited by the values H=100, δ=5 and β=10, corresponding to the scheduling horizon, number of sites and number of tractors, respectively. Table 6 presents the values solutions of the transportation operations x ii' for the 11 products between the 5 production sites.

CONCLUSIONS

The proposed multi-site scheduling model is based on a constraint satisfaction approach. It formalizes a set of decision variables to be managed and a set of constraints to be satisfied. In

Figure 1 :

 1 Figure 1: The multi-site company

Figure 2 :

 2 Figure 2: The transportation vehicle [Tractor + Trailer]

Figure 3 :

 3 Figure 3: Example of a cumulative resource k

  Consider a list of m rectangular boxes of dimension n of which the sides are parallel to n axes of a limited space [End 1 ,…, End n ]. Every box is defined by the Cartesian coordinates O ik of its origin and its lengths L ik(i∈ [1,m], k ∈ [1,n]). The non-overlapping and appertaining constraints are respectively expressed by the formulas (2 and 3):

Figure 4 :

 4 Figure 4: Illustration of the packing global constraint "diffn" (2 dimensions)

Figure 5 :

 5 Figure 5: Example of a production operation A 1(E A 1 = 6, pA 1 = 2, r A 1 = 3)

  A geographical dimension allowing the localization of the departure site of a transportation operation, -A temporal dimension allowing the localization of a transportation operation in the time, -An assignment dimension indicating to which tractor(s) is assigned a transportation operation.

Figure 6 :

 6 Figure 6: Positioning of transportation operations in the limited three dimensional space

Figure 7 .Figure 7 :

 77 Figure 7: Cumulative production curve on site ST 1 (R 1 = 4)

Figure 8 .

 8 The X-axis presents the time (in hours) and the Y-axis the number of trailers used by each transportation operation. The red horizontal line indicates the maximum number of trailers in site ST 1 (R T 1 =5).

Figure 8 :

 8 Figure 8: Cumulative transport curve of site ST 1 (R T 1 = 5)

Figure 9 :Figure 10 :

 910 Figure 9: 3D view of the transportation operations between the sites production

  this framework, we have developed an integrated production/transportation operations model and implemented the associated cumulative and packing global constraints. The model takes into account the existing alternatives to the duration of an operation according to the number of resources used for its realization, while respecting the capacity of production and transportation resources in each site. The solving provides the optimal solution that determines the minimum time required to complete producing and delivering all the considered products over all sites. It integrates the production/transportation operations and schedules them jointly in a coordinated way. The different elements presented in the model were implemented through the constraint programming system CHIP V5. The results are delivered in numerical form and in the form of curves tracing, for a given site, the profile of the total consumption of resources over time. 2D and 3D view of transportation operations scheduling over all sites are also presented.Further works plan to take account of the dynamic features of scheduling. That leads us to adopt an approach which is based on the Dynamic Constraint Satisfaction Problem formalism. The objective is to avoid starting again research from scratch after each change in the problem definition. Moreover, the more or less precise knowledge of the decision variables implies their controllability. This leads us to consider Conditional Constraint Satisfaction Problem with variables and constraints dependent on a situation and having conditions of presence.

Table 2 :

 2 Production and transportation capacity of sites

Table 3 :

 3 Transportation duration inter-site (round trip)

	Origin	Destination	Duration
	Site	site	(h)
	ST 1	ST 3	8
	ST 1	ST 5	12
	ST 2	ST 3	5
	ST 3	ST 4	5
	ST 2	ST 5	10
	ST 4	ST 5	6

Operation x 1 Energy required E x 1 Start times Sx 1 Operation duration px 1 Machine number

					r x	1
	A1	24	6	8	3
	B1	19	14	19	1
	C1	24	14	24	1
	D1	29	6	29	1
	G1	15	1	5	3
	N1	30	14	30	1

Table 4 :

 4 Values of the variables production operations realized on site ST 1

Operation duration px 1i' Trailer number r x 1i'

	A13	40	14	8	5
	B15	36	33	36	1
	D13	32	35	16	2
	N13	40	69	8	5

Table 5 :

 5 Values of the variables transportation operations from site ST 1


Carole Delporte-Gallet

Hugues Fauconnier

Rachid Guerraoui

Anne-Marie Kermarrec

Eric Ruppert

Hung Tran-The

Byzantine Agreement with Homonyms Accord Byzantin avec des Homonymes †

Keywords:

Dans un système réparti, on suppose le plus souvent que chaque processus a une identité unique. Plus rarement certains travaux s'intéressent au cas où les processus sont anonymes. Ces deux cas sont les deux extrêmes d'un modèle général où n processus utilisent ℓ identités différentes. Dans ce modèle, combien faut-il d'identifiants pour permettre l'accord lorsque t processus peuvent être byzantins ? On montre que 3t + 1 identifiants sont nécessaires et suffisants pour obtenir l'accord Byzantin dans un système synchrone. Mais de manière surprenante le nombre d'identifiants doit être supérieur à n+3t 2 dans un système partiellement synchrone. Ceci montre deux différences avec le modèle classique (ℓ = n) : (1) dans le modèle classique, les conditions pour permettre l'accord byzantin dans un système synchrone sont les mêmes que dans un système partiellement synchrone. Ici il y a des valeurs de ℓ pour lesquelles ce n'est pas le cas, (2) dans un système partiellement synchrone augmenter le nombre de processus corrects peut rendre l'accord impossible. Les preuves d'impossibilité utilisent le fait qu'un processus byzantin peut envoyer plusieurs messages à un même processus dans une ronde. On montre que si on enlève cette possibilité, l'accord byzantin devient plus facile à obtenir et que t + 1 identifiants sont suffisants, même dans un système partiellement synchrone.

Introduction

We consider a distributed system with Byzantine failures in which ℓ distinct identifiers are assigned to n processes, where 1 ≤ ℓ ≤ n. Several processes may be assigned the same identifier, in which case we call the processes homonyms. If a process p receives a message from a process q with identifier i, then p knows that the message sent by some process with identifier i, but p does not know whether the message was sent by q or another process q ′ having the same identifier i. This is true even if q is Byzantine : a Byzantine process cannot change its own identifier. A process cannot direct a message it sends to a particular process, but can direct the message to all processes that have a particular identifier.

This model generalizes the classical scheme where processes have distinct identifiers (i.e., ℓ = n), and the less classical scheme where processes are anonymous (i.e., ℓ = 1). Studying systems with homonyms provides a better understanding of the importance of identifiers in distributed computing, and there are two additional motivations for the new model. Firstly, assuming in systems such as Pastry or Chord [RD01, SMK + 01] that all processes have unique (unforgeable) identifiers might be too strong an assumption in practice. We may wish to design protocols that still work if, by a rare coincidence, two processes are assigned the same identifier. This approach is also useful if security is breached and a malicious process can forge the identifier of a correct process, for example by obtaining the correct process's private key. Secondly, in many cases, users of a system may wish to preserve their privacy by remaining anonymous.

Unfortunately, in a fully anonymous system where no identifiers are used, very few problems are solvable. In particular, Okun observed that Byzantine agreement is impossible in the fully anonymous model [START_REF] Okun | Agreement among unacquainted Byzantine generals[END_REF], even with a single faulty process. With a limited number of identifiers, more problems become solvable, and some level of anonymity can be preserved by hiding, to some extent, the association between users and identifiers. For example, users of a distributed protocol might use only their domain names as identifiers. Others will see that some user within the domain is participating, but will not know exactly which one. If several users within the same domain participate in the protocol, they will behave as homonyms.

We ask in this paper how many distinct identifiers are needed to reach agreement in a system of n processes, up to t of which can be Byzantine. We need only to consider systems where n > 3t : this assumption is known to be a requirement for solving Byzantine agreement, even when ℓ = n [PSL80,LSP82], and it thus applies also for systems with homonyms. For the synchronous case, we prove using a scenario argument that 3t + 1 identifiers are necessary. The matching synchronous algorithm is obtained by a simulation that transforms any synchronous Byzantine agreement algorithm designed for a system with unique identifiers to one that works in a system with ℓ > 3t identifiers. For the partially synchronous case, we prove using a partitioning argument that the lower bound becomes ℓ > n+3t 2 . (The bound n+3t 2 is strictly greater than 3t because n > 3t.) We show that this bound is also tight by giving a new partially synchronous Byzantine agreement algorithm. This bound is somewhat surprising because the number of required identifiers ℓ depends on n as well as t. Counter-intuitively, increasing the number of correct processes can render agreement impossible. For example, if t = 1 and ℓ = 4, agreement is solvable for 4 processes but not for 5. Another difference from the classical situation (where ℓ = n) is that the condition that makes Byzantine agreement solvable is different for the synchronous and partially synchronous models.

To strengthen our results, we show that (a) both the synchronous and partially synchronous lower bounds hold even if correct processes are numerate, i.e., can count the number of processes that send identical messages in a round and (b) the matching algorithms are correct even if processes are innumerate. In systems with unique identifiers, senders can append their identifier to all messages, making it trivial for the receiver to count copies of messages. This is not possible in systems with homonyms, so the distinction between numerate and innumerate processes is important.

What has more impact, however, is the ability for a Byzantine process to send multiple messages to a single recipient in a round. In a classical system with unique identifiers, the Byzantine process has no advantage in doing this : algorithms could simply discard such messages. In systems with homonyms, there is a clear advantage. In fact, we prove that if each Byzantine process is restricted to sending a single message per round to each recipient (and processes are numerate), then t + 1 identifiers are enough to reach agreement even in a partially synchronous model. We also show this bound is tight using a valency argument : t + 1 identifiers are needed even in the synchronous case. The fact that t + 1 identifiers are sufficient to reach agreement with restricted Byzantine processes has some practical relevance : In some settings, it is reasonable to assume that Byzantine processes are simply malfunctioning ordinary processes sending incorrect messages, and not malicious processes with the additional power to generate and send more messages than correct processes can.

Our results are summarized in Table 1. For lack of space, we refer the reader to the long version [DGFG + 11] for formal definitions, theorems and proofs.

Synchronous Partially synchronous Innumerate processes

ℓ > 3t ℓ > n+3t 2 Numerate processes ℓ > 3t ℓ > n+3t 2
Numerate processes, restricted Byzantine processes ℓ > t ℓ > t TABLE 1: Necessary and sufficient conditions for solving Byzantine agreement in a system of n processes using ℓ identifiers and tolerating t Byzantine failures. In all cases, n must be greater than 3t.

Definitions

We consider a distributed message-passing system with n ≥ 2 processes. Each process has an identifier from the set {1, ..., ℓ}. We assume that n ≥ ℓ and that each identifier is assigned to at least one process. In the case where n > ℓ, one or more identifiers will each be shared by several processes. We assume algorithms are deterministic. Processes with the same identifier execute the same code but processes with different identifiers may behave differently.

A correct process does not deviate from its algorithm specification. A process that is not correct is called Byzantine. The maximum possible number of Byzantine processes is denoted t, where 0 < t < n. We need only to consider systems where n > 3t : this assumption is known to be a requirement for solving Byzantine agreement, even when ℓ = n [PSL80, LSP82], and it thus also applies to systems with homonyms. A Byzantine process may choose to send arbitrary messages (or no message) to each other process.

Without loss of generality, we assume a broadcast model : when a correct process sends a message, it can sends the same message to all processes. Byzantine processes are not bound by this assumption : they may send different messages to different processes, even if the recipients have the same identifier.

In the synchronous model, computation proceeds in rounds. In each round, each process can send messages to all other processes and then receive all messages that were sent to it during that round.

For the partially synchronous model we use the definition of Dwork, Lynch and Stockmeyer [DLS88] : computation proceeds in rounds, as in the synchronous model. However, in each execution, a finite number of messages might not be delivered to all of their intended recipients. As argued in [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF], this basic partially synchronous model is equivalent to other models with partially synchronous communication.

As mentioned in the introduction, we also consider variants of the models in which each Byzantine process is restricted to sending at most one message to each recipient in each round. In general, we consider unrestricted Byzantine processes unless the restriction is explicitly mentioned. We also distinguish the cases where processes are innumerate from the case where they are numerate. We say that a process is innumerate if the messages it receives in a round form a set of messages : the process cannot count the number of copies of identical messages it receives in the round. We say that a process is numerate if the messages it receives in a round form a multiset of messages : the process can count the number of copies of identical messages it receives in the round.

The goal of an agreement algorithm is for a set of processes proposing values to decide on exactly one of these values. We consider the classical Byzantine agreement problem [START_REF] Michael | Easy impossibility proofs for distributed consensus problems[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF], defined by the following three properties : (Validity) If all correct processes propose the same value v, then no value different from v can be decided by any correct process, (Agreement) No two correct processes decide different values, and (Termination) Eventually, each correct process decides some value.

An algorithm solves Byzantine agreement in a system of n processes with ℓ identifiers tolerating t failures if these three properties are satisfied in every execution in which at most t processes fail, regardless of the way the n processes are assigned the ℓ identifiers.

Synchronous Model

We prove the condition ℓ > 3t is necessary even if processes are numerate using a scenario argument, in the style of Fischer, Lynch and Merritt [START_REF] Michael | Easy impossibility proofs for distributed consensus problems[END_REF].

Our agreement algorithm that solves Byzantine agreement assuming ℓ > 3t is generic : given any synchronous Byzantine agreement algorithm for ℓ processes with unique identifiers (such algorithms exist when ℓ = n > 3t, e.g., [START_REF] Lamport | The Byzantine generals problem[END_REF]), we transform it into an algorithm for n processes and ℓ identifiers, where n ≥ ℓ. In our transformation, we divide processes into groups according to their identifiers. Each group simulates a single process. If all processes within a group are correct, then they can reach agreement and cooperatively simulate a single process. If any process in the group is Byzantine, we allow the simulated process of that group to behave in a Byzantine manner. The correctness of our simulation relies on the fact that more than two-thirds of the simulated processes will be correct (since ℓ > 3t), which is enough to achieve agreement. Our algorithm solves synchronous Byzantine agreement even with innumerate processes if ℓ > 3t.

Partially Synchronous Model

We prove that having ℓ > 3t+n 2 is necessary and sufficient for solving Byzantine agreement in a partially synchronous system, regardless of whether the processes are numerate or innumerate. Intuitively, this condition means that at least 3t + 1 of the identifiers must each be assigned to a single process (since 2ℓn > 3t).

We prove the necessity of the condition ℓ > n+3t 2 using a partitioning argument. We show that if there are too few identifiers, and messages between two groups of correct processes are not delivered for sufficiently long, then the Byzantine processes can force processes in the two groups to decide different values.

Our algorithm is based on the algorithm given by Dwork, Lynch and Stockmeyer [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] for the classical case where n = ℓ, with several novel features. Generalizing the algorithm is not straightforward. Some of the difficulty stems from the following scenario. Suppose two correct processes share an identifier and follow the traditional algorithm of [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]. They could send very different messages (for example, if they have different input values), but recipients of those messages would have no way of telling apart the messages of the two correct senders, so it could appear to the recipients as if a single Byzantine process was sending out contradictory information. Thus, the algorithm has to guard against inconsistent information coming from correct homonym processes as well as malicious messages sent by the Byzantine processes.

Restricted Byzantine Processes

We now consider the effect of restricting the Byzantine processes so that each Byzantine process can send at most one message to each recipient in each round. This restriction reduces the number of identifiers needed to reach agreement if processes are numerate but does not help if processes are innumerate. With numerate processes, having ℓ > t is necessary and suf ?cient for solving Byzantine agreement. With innumerate processes, the previous results remain unchanged.

With numerate processes, the algorithm that solves partially synchronous Byzantine agreement is similar to the one presented in Section 4. Like this algorithm, it uses an authenticated broadcast primitive [START_REF] Srikanth | Optimal clock synchronization[END_REF], that ensures the agreement property, but here accept actions have an extra parameter indicating the multiplicity of the accepted message. This multiplicity is greater than the number of correct processes that sent the message and does not exceed the number of correct processes by more than the actual number of Byzantine processes in the execution. Eventually, all correct processes agree on the multiplicity of each message. As ℓ > t, at least one identifier is assigned only to correct processes ensuring the termination property.

† This work has been accepted for publication at PODC 2011 [DGFG + 11].This work is partially supported by the ERC Starting Grant project 204742 and the ANR VERSO SHAMAN.