Tasnim Hamza

Jean-Luc Scharbarg

Christian Fraboul

Priority assignment on an avionics switched Ethernet Network (QoS AFDX)

AFDX (Avionics Full Duplex Switched Ethernet) standardised as ARINC 664 is a major upgrade for avionics systems. For current aircrafts, it implements a FIFO scheduling policy and allows the transmission of sporadic flows between avionics functions distributed on a set of end systems. The certification imposes to guarantee that the end-to-end delay of any frame transmitted on the network is upper-bounded and that no frame is lost due to buffer overflow. This guarantee is obtained thanks to a worst-case analysis which is based on either network calculus or trajectory approach. However it leads to an over-dimensioning of the network.

For future aircraft, it is envisioned to use a Fixed Priority scheduling policy in order to better use network resources (QoS AFDX). Existing AFDX switches implement two priority levels. A worst-case analysis of such a network exists, based on the Trajectory approach. Thus, the remaining issue is to assign efficiently the available priorities to the flows.

The contribution of this paper deals with this issue. It proposes to assign the priorities to the flows using the well-know Optimal Priority Assignment algorithm (OPA) which was first defined for monoprocessor preemptive systems. The proposed solution is applied on two case studies. The overall worst-case delay is reduced by 30 % on a small configuration and 20 % on a realistic one.

I. INTRODUCTION

Designing and manufacturing new civilian aircrafts has lead to an increase of the number of embedded systems and functions. The AFDX [START_REF]Arinc specification 664: Aircraft data networks, parts 1[END_REF] brings an answer by multiplexing a huge amount of communication flows over a full duplex switched Ethernet network. It has become the reference communication technology in the context of civilian avionics and provides a backbone network for the avionics platform.

Since flows are multicast, each frame of a given flow follows a set of paths. It experiences a delay along each path. This delay is the sum of transmission delays on links and latencies in switches. There are no collisions on full duplex links. Thus transmission delays are directly derived from link rates and frame lengths. Latencies in switches mainly depend on the waiting times in output queues. Indeed each output port is shared by a set of flows. Since AFDX flows are asynchronous, frames from competing flows can arrive at any time in an output port. Their order of transmission is determined by the scheduling policy.

AFDX switches implement a fixed priority scheduling at each output port, with two priority levels. For current aircraft, one single priority level is used. It comes to consider a first come first served (FCFS or FIFO) scheduling policy.

For certification purpose, it is mandatory to upper bound the end-to-end delay of all the frames transmitted on the AFDX. Three main approaches have been proposed for this worst-case analysis in the context of FCFS scheduling. The network calculus approach provides sure upper bounds [START_REF] Bauer | Improving the worstcase delay analysis of an afdx network using an optimized trajectory approach[END_REF] and it has been used for the certification of the AFDX on board of the A380 and A350. The trajectory approach provides tighter sure upper bounds [START_REF] Bauer | Improving the worstcase delay analysis of an afdx network using an optimized trajectory approach[END_REF]. It has been shown [START_REF] Kemayo | Optimistic problems in the trajectory approach in fifo context[END_REF] that, for some corner cases, this approach introduces some optimism. However these cases never occur in existing AFDX configurations. The last approach is based on model checking. It gives exact worst-case delays on limited configurations, due to the well-known combinatorial explosion problem [START_REF] Adnan | Minimizing the search space for computing exact worst-case delays of AFDX periodic flows[END_REF].

Results show that the worst-case delay can be very different for different flows. On a typical aircraft configuration, it varies from 2 to 15 ms, depending on the considered flow. Actually, it is impacted by the distribution of the flows on the available paths. This variation is an issue when the constraint on the delay is the same for all the flows of the configuration, which is a classical situation. Obviously this worst-case delay constraint cannot be less than 15 ms. If it appends to be less than this value, then, there exist several solutions. 1) Reduce the number of flows: most of the time, this is impossible, due to applicative constraints. 2) Use extra switches and links: it is often too costly.

3) find another static routing which reduces the overall worst-case delay: the idea is to better distribute the flows among the available paths. 4) use the two available priority levels: the goal is to limit the delay variation, thus the overall worst-case delay.

Solutions 3 and 4 are the most interesting ones, since they have no impact on the application nor on the networks architecture.

In this paper, we consider solution 4. Two problems have to be addressed:

• allocate the priorities to the flows • upper-bound the delays of these flows with priorities.

A solution to the second problem (worst-case analysis) has been proposed in [START_REF] Bauer | Worst-case backlog evaluation of avionics switched ethernet networks with the trajectory approach[END_REF]. It is based on the trajectory approach. It has been shown that it gives tight upper bound on delays for flows with priorities transmitted on an AFDX network.

The allocation of priorities to flows transmitted on an AFDX network is the topic of this paper. The problem of priority allocation has been widely studied in the context of real-time systems. An Optimal Priority Assignment algorithm (OPA) has been proposed in the context of monoprocessor preemptive Systems [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF]. This algorithm has been extended to other types of systems (e.g. multiprocessor systems) [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF]. OPA is based on a schedulability test which has to respect a set of conditions.

The contribution of this paper is to show that OPA can be extended to the context of an AFDX network implementing a fixed priority scheduling. The schedulability test is based on the Trajectory approach. Then we show that this priority assignment algorithm can be used in order to significantly reduce the overall worst-case end-to-end delay on the network.

The paper is organised as follows. Section II gives the key features of the AFDX network and summarised the Trajectory approach in the context of Fixed Priority scheduling. Section III describes the Optimal Priority Assignment algorithm and shows how it can be applied in the context of AFDX. Section IV presents results on two case studies. Section V concludes the paper and gives some directions for future work.

II. CONTEXT

This section gives the key features of the AFDX network and summarises the worst-case delay analysis of the AFDX based on the Trajectory approach for Fixed Priority scheduling.

A. AFDX network and traffic model

AFDX (Avionics Full Duplex Switched Ethernet), standardised as ARINC 664 [START_REF]Arinc specification 664: Aircraft data networks, parts 1[END_REF], has been tailored in order to take into account avionics constrains. Avionics function are distributed on a set of End Systems which are interconnected by a full Duplex switched Ethernet network. An illustrative example is depicted in Figure 1. It is composed of 7 End Systems (ES) (e 1 to e 7 ) and 3 switches (S 1 to S 3 ). Each switch uses a store and forward pattern. Switches have no buffers on input ports and buffers on output ports. Each switch has a switching latency bounded by a constant value L max = 16µs. Each ES is connected to exactly one switch port and each switch port is connected to at most one ES. End Systems exchange frames through Virtual Links (VLs). A VL statically defines a unidirectional virtual communication channel between one source ES and one or more destination ESs. For instance, in Figure 1, VL v1 is defined by the path {e1 -S1 -S3 -e6}. The definition of a VL includes also the Bandwidth Allocation Gap (BAG) and the minimum and the maximum frame length (S min and S max ). BAG is the minimum delay between two consecutive frames of the associated VL (a VL is a sporadic flow). Table I gives BAGs and frame lengths of the ten VLs of the configuration in Figure 1.

A combined Fixed Priority and First In, First Out (FP/FIFO) scheduling policy is implemented in each AFDX An avionics network has to be certified. Thus, it is mandatory to prove that the End-To-End delay is upper bounded for each flow transmitted on the network. Moreover, the output buffers have to be dimensioned so that no frame is lost due to buffer overflow.

Many work has been devoted to the worst-case analysis of an AFDX network. Up to now, the computation of an exact worst-case End-to-End delay is not possible in a reasonable time on an industrial size configuration (roughly 1000 flows) [START_REF] Adnan | Minimizing the search space for computing exact worst-case delays of AFDX periodic flows[END_REF]. Conversely, the computation of a sure upper bound of this End-To-End delay in the context of FIFO scheduling can be obtained by at least two approaches, namely Network Calculus [START_REF] Frances | Using network calculus to optimize the afdx network[END_REF] and Trajectory approach [2][9]. The latest approach can also cope with FP/FIFO scheduling [START_REF]Applying trajectory approach with static priority queuing for improving the use of available afdx resources[END_REF].

The goal of the work presented in this paper is to assign priorities to flows such that timing constrains of flows are respected. The verification of this timing constrains is based on the trajectory approach with FP/FIFO scheduling. This approach is summarised in the next paragraph.

B. Worst-case analysis based on Trajectory approach

The trajectory approach [START_REF] Martin | Schedulability analysis of flows scheduled with fifo: application to the expedited forwarding class[END_REF] has been developed to get deterministic upper bounds on end-to-end (ETE) response time in distributed systems. It identifies for a packet m belonging to a flow τ i the worst-case scenario on its trajectory. This approach has been applied and optimised in the context of AFDX network with FIFO output port policy [START_REF] Bauer | Improving the worstcase delay analysis of an afdx network using an optimized trajectory approach[END_REF] [START_REF] Bauer | worst-case end-to-end delay analysis of an avionics afdx network[END_REF]. It has been extended to the case of QoS AFDX with fixed priority (FP)/FIFO output port policy [START_REF]Applying trajectory approach with static priority queuing for improving the use of available afdx resources[END_REF] based on existing results for combined FP and FIFO [START_REF]Worst case end-to-end response times of flows scheduled with fp/fifo[END_REF]. This last extension of the approach is now summarized and illustrated on the example in Figure 1.

The trajectory of a frame includes a set of output ports (including the links) and a set of switch fabrics. In the context of AFDX, the delay of a switch fabric is bounded, while the delay in an output port highly depends on the competing frames. Indeed, depending on the scheduling policy implemented in the nodes, a given frame is delayed by the transmission of the frames with a higher priority and the frames with the same priority which have arrived in the output port before the considered frame.

Let us consider a VL v i (i ∈ [1, n]) following a path P i . The frame f i of VL v i generated at time t is under study. v i is characterised by its period BAG i and its processing time C i = S maxi /R, where S maxi is the maximum size of frames of v i and R = 100M b/s is the AFDX link rate (all the AFDX links work at the same rate). The VL v i is emitted by the source node f irst i and it follows a statically defined path P i . Its last visited node is denoted last i . On a QoS AFDX, v i is assigned a priority p i . The set of VLs having a fixed priority level strictly higher, equal or strictly lower than this of v i are denoted resp. hp i , sp i and lp i .

In order to compute the worst-case end-to-end delay of frame f i , the Trajectory approach considers the longest possible busy period ending with frame f i at each node in the path P i . Such a busy period bp(h) is a temporal interval with no idle time in node h. The busy periods along the path

P 3 = {e 2 , S 2 , S 3 } of v 3 in Figure 1 are illustrated in Figure 2.
Let f (h) denote the first frame of bp h which crosses h and comes from the node preceding h in P i . The starting instant of the busy period bp(h) i.e. the arrival time of f (h) is denoted M (h, i), while a(h, f i ) denotes the arrival time of the studied frame f i at the node h.

e2 S2 f(e2) f(S2) fi f(S2) f(S3) fi f(S3) fi S3 bp(S2) bp(e2) bp(S3) M(S2,i) M(S3,i) a(s2,fi) a(S3,fi) Fig. 2. Busy periods of v 3
Frames from competing VLs generated by other source nodes and crossing the VL v i will delay its frames.

For example, frames of VLs having the same priority level as v i , (i.e ∈ sp i ) arriving no earlier than M (h, i) and no later than a(h, f i ) delay the frame f i . The maximum waiting delay of f i generated by competing VLs ∈ sp i in a busy period bp h is obtained by maximising the number of frames of these VLs joining v i in the interval [M (h, i), a(h, f i )]. Frames with higher priorities are also considered, as it will be shown later. This process propagates till the last node.

The computation of the worst-case ETE delay of any VL v i according to the Trajectory approach for FP/FIFO is bounded by:

R i = max t≥0 (W lasti i,t + C i -t) ( 1
)
last i is the last node of flow τ i and W lasti i,t
is an upper bound on the latest starting time of a frame m generated at time t on its last visited node. The definition of W lasti i,t given in [START_REF]Applying trajectory approach with static priority queuing for improving the use of available afdx resources[END_REF] is:

W lasti i,t = j∈spi∪{i} Pj ∩Pi =∅ 1 + ⌊ t + A i,j T j ⌋ .C j (2)
+ j∈hpi Pj ∩Pi =∅ 1 + ⌊ W lasti,j i,t + B i,j T j ⌋ .C j (3)
+ h∈Pi h =lasti    max h∈hpi∪spi∪[i] h∈Pj {C j }    (4)
+ (|P i | -1) .L max (5)
+ h∈Pi δ h i (6)
+ h∈Pi h =f irsti ∆ h (7)
-C i (8)
Let's have a look at each term of this definition.

Term (2) represents the workload of all the competing VLs with the same priority as the one of v i under study. The principle is to determine the maximum number of frames of each of those competing VLs which can delay frame f i . Let us consider a VL v j which joins v i in a node h = f irst i,j . v j is assigned the same priority as v i . A frame of v j can delay f i if it arrives in f irst i,j during the busy period where f i is transmitted from f irst i,j and no latter than the arrival of f i at f irst i,j . Since the transmission of a frame of VL v j from its source node f irst j to the node f irst j,i requires at least S f irstj,i minj and at most S f irstj,i maxj , the earliest generation time of a frame of VL v j at its source node must be M (f irst i,j , i)-S f irstj,i maxj -J j and the latest generation time must be t + S f irstj,i maxi -S f irstj,i minj . Thus we have:

A i,j = S f irstj,i maxi -S f irstj,i minj -M (f irst i,j , i) + S f irsti,j maxj + J j (9)
Term (3) represents the workload of all the competing VLs with higher priority than v i . The difference with the previous term is that, due to FP scheduling, a frame from a competing VL can delay f i in h even if it arrives at h after a(h, f i ). Thus the computation considers W lasti,j i,t , the latest starting time of f i at its last shared node last i,j with v j According to [START_REF] Martin | Schedulability analysis of flows scheduled with fifo: application to the expedited forwarding class[END_REF], f (h+1) has to be counted twice in each node, except the slowest one. In AFDX context, the slowest node is arbitrary chosen as the last one [START_REF]Applying trajectory approach with static priority queuing for improving the use of available afdx resources[END_REF] since all nodes work at the same speed. In order to guarantee the end-to-end delay upper bound, the frames counted twice are those with the largest size. Thus, this part of the delay is given by:

h∈Pi h =lasti    max h∈hpi∪spi∪[i] h∈Pj {C j }    (10)
Due to physical constraint, for a frame f i visiting |P i | -1 switches, there is a switch-dependent delay L max computed as follows:

(|P i | -1) .L max (11)
The trajectory computation also integrates the non-preemption effect. Actually, when a frame arrives in the output port it has to wait until the end of the frame under transmission in this port, regardless of the priority of the frame. Thus, with FP/FIFO policy, f i can be delayed at most by one lower priority frame. If we consider that at each node h of P i , f i is delayed by the frame ∈ lp i with the maximum size (denoted δ h i ) the delay due to non-preemption is bounded by:

N h ∈Pi δ h i (12)
In [START_REF] Bauer | Improving the worstcase delay analysis of an afdx network using an optimized trajectory approach[END_REF] an optimisation of the trajectory approach is proposed in order to take into account the fact that frames transmitted by the same input link are serialised and they cannot arrive at an output port at the same time. Therefore, a serialisation factor is subtracted from the computation. This factor sums for each node h in P i the duration between the beginning of bp h and the arrival of the first frame coming from the preceding node in P i , i.e. h -1. It is computed by:

h∈Pi h =f irsti ∆ h (13)
In [START_REF]Applying trajectory approach with static priority queuing for improving the use of available afdx resources[END_REF], Bauer and al. establish a lower bound on ∆ N h ∀N h ∈ P i in the context of AFDX with FP/FIFO policy. The serialisation term is lower bounded by the maximum of 0 and max

1≤x≤k h min(l h x ) -max(l h 0 )
Now, We illustrate the trajectory approach computation on the sample AFDX configuration depicted in Figure 1. It includes seven ES (e 1 to e 7 ), three switches (S 1 to S 3 ) and ten VLs (v 0 to v 9 ). VL features (BAGs and frame lengths) are summarized in Table I. We assume that v 0 , v 1 , v 2 , v 3 have the lowest priority (1) while the six other VLs have the highest priority [START_REF] Bauer | Improving the worstcase delay analysis of an afdx network using an optimized trajectory approach[END_REF]. Every link works at 100 Mb/s and the switching delay is 16 µs. The transmission time of a frame of 500 (resp. 1000) bytes on a link is 40 (resp. 80) µs. Let us analyse the worst-case response time of VLs v 4 . The sequence producing worst-case ETE delay with FP/FIFO policy is illustrated in Figure 3. The frame from v 4 is generated at time 0. Let's calculate each term of trajectory approach computation.

Term 2 concerns frames from v 4 and competing VLs with the same priority as v 4 . Here, there is one single frame from each VL (v 4 , v 5 , v 6 , v 7 , v 8 , v 9 ). Thus term 2 is 480 µs.

Term 3 concerns frames from VLs with higher priority than this of v 4 . There are no such VLs in the configuration. Thus term 3 is null.

Term 4 represents the extra delay due to frames which have to be counted twice. There is one frame with maximal size for e 4 and S 2 , which leads to 160 µs.

Term 5 is the sum of switching latencies (16 µs per switch). v 4 crosses two switches. Thus term 5 is 32 µs.

Term 6 concerns the delay induced by lower priority VLs.

There are no such VLs in e 4 and S 2 . There are two of them in S 3 . They have the same transmission time (40 µs). Thus, term 6 is 40 µs.

Term 7 takes into account the impact of the serialization effect. There is no such impact in our case. Thus term 7 is null.

The worst-case delay of v 4 is the sum of all these terms, which is 712 µs.

III. ASSIGNMENT OF PRIORITIES TO VLS

The trajectory approach presented in the previous section allows a worst-case delay analysis of an AFDX network implementing a FP/FIFO scheduling of VLs (QoS AFDX). Such a QoS AFDX is envisioned for future aircrafts in order to better use the available resources [START_REF]Applying trajectory approach with static priority queuing for improving the use of available afdx resources[END_REF]. The remaining issue of such a network is to efficiently assign the priorities to the VLs.

An Optimal Priority Assignment algorithm (OPA) has been proposed in the context of monoprocessor preemptive Systems [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF]. This algorithm has been extended to other types of systems (e.g. multiprocessor systems) [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF]. In this paper we show that it can be extended to the context of QoS AFDX.

A. OPA overview

OPA considers a mono-processor preemptive system executing a set of real-time tasks [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF]. It has been proved that, for an asynchronous periodic task set, OPA generates an optimal priority ordering while using a polynomial number of schedulability tests [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF].

OPA proceeds as follows. It first assigns the lowest priority to one task which respects its deadline with this lowest priority. It continues till the remaining unassigned set of tasks is empty. If at a step no task can be assigned the current priority, no feasible priority assignment exists. An overview of OPA process is given by the following algorithm.

for each priority level i, lowest first do for each unassigned task t do if t feasible with priority i assuming that all unassigned tasks have higher priority then assign priority i to t; break; end; end; if no task is feasible with priority i then return unschedulable; end; end; return schedulable; At each step, a schedulability test is applied to the task which is assigned the current priority in order to determine whether it respects its deadline or not. Let us assume a set of n tasks. At the first step, at most n schedulability tests are applied (n is reached if only one task is feasible with the lowest priority and this task is tested at last). Similarly, at step i, ni + 1 tasks are in the remaining set. Thus at most ni + 1 schedulability tests are applied. Consequently the maximum number of feasibility tests leading to a priority ordering for n tasks is given by:

n + (n -1) + ... + 1 = (n 2 + n)/2
The OPA algorithm is applied provided that schedulability test respects the following condition [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF] (it is then considered OPA compatible):

• Condition 1: Schedulability of a task may, according to the test, be dependent on the set of higher priority tasks, but not on their relative priority ordering.

• Condition 2: Schedulability of a task may, according to the test, be dependent on the set of lower priority tasks, but not on their relative priority ordering.

• Condition 3: When the priorities of any two tasks of adjacent priority are swapped, the task being assigned the higher priority cannot become unschedulable according to the test, if it was previously deemed schedulable at the lower priority.

Let us illustrate OPA algorithm on the example task set in Table II. Classically, each task T i has a period P i , deadline D i , computation time C i and offset O i . For sake of simplicity, task offsets are supposed null. We assume that all tasks are independent and that the system is preemptive. Since we have 3 tasks, we consider 3 priority levels {1,2,3} where 1 is the lowest one and 3 is the highest one. The feasibility test used in this example, proposed in [START_REF] Joseph | Finding response time in real-time system[END_REF], consists on the computation of the task response time R i . At the first step, OPA looks for one task which can be assigned the lowest priority level 1. The first candidate is T 1. Assuming that T 1 is assigned priority 1 while T 2 and T 3 are assigned higher priority levels, the worst-case response time of T 1 is R 1 = 6. Since R 1 > D 1 , T 1 exceeds its deadline and therefore is not feasible with priority 1. OPA moves then to a new candidate, T 2. Assuming that T 2 is assigned priority 1 while T 1 and T 3 are assigned higher priority levels, the worstcase response time of T 2 is R 2 = 7. Since R 2 ≤ D 2 , T 2 respects its deadline and therefore is assigned priority 1. The next step is to assign priority 2. Task T 1 is the first candidate. Assuming that task T 3 has a higher priority, R 1 = 4. Since R 1 ≤ D 1 , task T 1 is assigned the priority 2. Finally, we assign the priority 3 to the remaining task T 3. We find that R 3 = 3 ≤ D 3 which means that T 3 is feasible at the priority level 3.

B. Minimising priority levels

The basic OPA algorithm considers that the system supports one priority level per task. Such an assumption might be unrealistic since concrete systems support a limited number of priority levels. In order to overcome this problem, an extension of the OPA algorithm has been proposed in [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF]. It allows to minimise the number of priority levels requested for a feasible priority ordering. Actually, a priority is no longer assigned exclusively to one single task; it can be assigned to more than one task.

The minimum number of priority levels is achieved by successively maximising the number of tasks assigned to priority levels from the lowest one to the highest one. This extended version of the algorithm is described as follows.

for each priority level i, lowest first do for each unassigned task t do if t feasible with priority i assuming that all unassigned tasks have higher priority then assign priority i to t; end; end; if no task is feasible with priority i then return unschedulable; end; if no unassigned task remains then break; end; end; return schedulable;

C. Extending OPA to the AFDX case

In this section, we show that OPA algorithm can be used in order to assign priorities to the VLs transmitted on a QoS AFDX network. We consider the extended OPA algorithm which minimises the number of priority levels. Indeed, the number of priority levels available on AFDX switches is low (two in existing switches). The schedulability test is based on the trajectory approach. A deadline is associated to each VL and the worst-case End-To-End delay of each VL is computed by the trajectory approach for FP/FIFO.

It is mandatory to check that the trajectory approach is OPA compatible, i.e. it respects the three conditions given in section III-A. This point is addressed in the following paragraphs.

1) Condition 1: impact of higher priority VLs: Due to FP policy, the time spent by a frame f i of VL v i in a switch depends on the static higher priority frames in the switch that arrives before the start time of the transmission of f i . The term (3) of the Trajectory computation illustrates this effect.

Obviously, the Trajectory approach takes into account the impact of competing VLs with priority levels higher than this of v i (i.e. ∈ hp i ). However, this impact do not depend on their relative priority order, since the priority levels are not considered in Term (3). Thus, the trajectory approach meets condition 1 required for OPA compatibility.

2) Condition 2: impact of lower priority VLs:

The impact of lower priority VLs ∈ lp i on the end-to-end delay of frame f i appears through the non-preemption effect on the AFDX network. It is taken into account in the Trajectory computation by Term [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF]. Since it computes an upper bound of the end-to-end delay of f i , the Trajectory approach takes into account a maximum size frames of competing VLs ∈ lp i at every visited node in P i . This latter does not depend of the relative priority ordering of lp i VLs.

Clearly, the non-preemption effect do not depend on the priority ordering of flows ∈ lp i . It can be concluded that the trajectory computation meets Condition 2 for OPA compatibility.

3) Condition 3: variation of R i as a function of priority levels: Condition 3 of OPA compatibility imposes the following: If the priority levels of two VLs are swapped, the one being assigned the higher priority must remain feasible if it was initially feasible with the lower priority level. In order to demonstrate that the Trajectory computation meets this condition, we prove that the worst-case end-to-end delay of a given VL v i , computed with the Trajectory approach, does not increase if a higher priority is assigned to v i .

Let's illustrate this property with VL v 4 of the configuration in Figure 1. Figures 4 and5 depict the worst-case delay of v 4 for two different priority assignments. We assume three priority levels. In Figure 4, v 4 , as well as v 5 , v6 and v 7 are assigned priority 2 (medium). v 0 , v 1 , v 2 and v 3 are assigned priority 1 (low) while v 8 and v 9 are assigned priority 3 (high). v 4 is delayed by one frame of each VL with the same or a higher priority and one frame of lower priority (e.g. v 0 ) in S 3 .

In Figure 5, priorities of v 4 and v 8 are swapped. v 4 is delayed by less frames in both S 2 and S 3 (e.g. one single lower priority frame from e 4 , i.e. v 6 or v 7 ). Thus its worstcase delay is reduced. Now, we analyse the general case. Let us consider two VLs v i and v j to whom was assigned resp. the priorities p i and p j (p i < p j ). We suppose that v i is feasible with priority level p i , i.e. it respects its deadline according to the trajectory computation. Now, we swap the priorities of v j and v i , i.e. v i is assigned a higher priority level p j . Let us analyse the impact of the increasing of v i priority on its end-to-end delay. The terms ( 5) and ( 8) are not considered in this analysis given that they do not depend on the priority level of the VLs. a) Impact of VLs ∈ (sp i ∪ hp i ): As explained in Sect.II-B, a frame f i of vi is delayed by frames of competing VLs having the same priority as v i . This delay is bounded by Term (2) in the trajectory computation, from which we subtract the serialisation (term [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF]). f i is also delayed by frames of competing VLs having a higher priority than that of v i (Term (3)).

Since p i ¡ p j , we have (sp j ∪ hp j ) ⊂ hp i . Therefore, we have (sp j ∪ hp j ) ⊂ (sp i ∪ hp i ). That means that with priority level p j , the VL v i has a lower number of competing VLs ∈ (sp i ∪ hp i ). Consequently, the delay induced by VLs with priority level equal or higher than that of v i decreases.

b) Impact of VLs ∈ lp i : As explained in Section II-B, due to FP scheduling policy, a frame f i of vi is delayed by at most one lower priority frame on each node visited by f i . This delay is illustrated by Term (6) of the Trajectory computation. The frame of lp i introducing the non-preemption related delay at a given node h is the one having the maximum size among lp i crossing h. Since lp j ⊃ lp i , the maximum size of frame in lp j might be greater or equal to that in lp i .

Let's suppose that max f k ∈lpj size(f k )} > max f k ∈lpi size(f i )}.
The frame corresponding to max f k ∈lpj size(f k )} was counted in Term (2) when v i was assigned priority p i . Consequently, assigning priority p j to v i reduces Term (2) by the size of this frame and increases Term [START_REF] Audsley | On priority assignment in fixed priority scheduling[END_REF] by

max f k ∈lpj size(f k )} -max f k ∈lpi size(f i )}.
Overall, the worst-case delay of v i is smaller.

IV. CASE STUDY

In this section, the proposed solution is evaluated on two case studies. The first one considers a small configuration including 18 VLs. The second one copes with a realistic configuration including 1000 VLs. For both configurations, the goal is to achieve an overall minimisation of the worstcase end-to-end delay of all the flows transmitted on this AFDX configuration. As explained in the introduction, such a minimisation is relevant in the context of avionics where a classical timing constraint is an upper bound on the delay of any frame transmitted on the network. Paragraph IV-A details the algorithm implemented in order to achieve this goal. Paragraphs IV-B and IV-C gives the network configuration and the results.

A. Implemented algorithm

At the beginning of the process no priority assignment has been done. Thus all the VLs of the considered AFDX configuration have the same priority (it comes to a FIFO scheduling).

In the first step the worst-case end-to-end delay R i for each VL v i is computed using the trajectory approach for FIFO. Then we determine the maximum value R max among all these worst-case delays R i . R max is an upper bound of the end-toend delay of any frame of any VL transmitted on the network.

In the second step priorities are assigned to the VLs in order to reduce as much as possible this R max . The goal is an overall minimisation of the worst-case end-to-end delay of all the flows transmitted on the network.

More formally, the goal is to find the smallest possible overall worst-case delay R ′ max such that the priority assignment is feasible. It comes to find the smallest real value x in [0, 1] such that:

• R ′ max = x × R max • There exist at least one priority assignment for the VLs of the configuration such that no VL has a worst-case end-to-end delay greater than R ′ max .

The implementation of this second step consists in decreasing the value of x till the priority assignment becomes not feasible.

A tool implementing this process has been developed in Python. It is based on the tool implementing the trajectory approach for FP/FIFO [START_REF]Applying trajectory approach with static priority queuing for improving the use of available afdx resources[END_REF].

B. Case study 1: a small configuration

An overview of the AFDX configuration under study is depicted in the upper part in Figure 6. It includes 7 end systems, 3 switches and 18 VLs. The features of the different VLs are given in Table III.

First the worst-case end-to-end delay for each VL is computed, considering a FIFO scheduling policy. Results are shown in the lower part in Figure 6 (FIFO curve). The maximum worst-case ETE delay R max is that of VL v 56 . It is equal to 378 µs. This value is taken as the reference in order to define a schedulability condition for the different flows, i.e. the factor x which is applied to R max in order to get the reduced overall maximum end-to-end delay R ′ max . The smallest value x which leads to a feasible priority assignment is 0.7 (reduction of 30 %). Thus, we have: R ′ max = 0.7 × R max = 265 µs The resulting worst-case end-to-end delays for the VLs are shown in the lower part in Figure 6 (OPA curve). The priorities These results show that OPA can bring a significant reduction on the overall worst-case delay. Next section gives results on a realistic AFDX configuration.

C. Case study 2: a realistic configuration

A general overview of the configuration considered in this case study is depicted in Figure 7. This configuration has been presented in [START_REF] Charara | Methods for bounding end-to-end delays on an AFDX network[END_REF]. It includes 123 end systems, 18 switches, roughly 1000 Virtual Links and 6400 VL paths per network (due to VL multicast characteristics). BAGs are harmonic between 2 and 128 ms.

The goal of this case study is to evaluate the reduction of Fig. 7. Realistic AFDX configuration the maximum worst-case delay provided by the utilization of the two priority levels available in existing AFDX switches.

First the worst-case end-to-end delay for each VL is computed. The maximum worst-case ETE delay R max is 15.413 ms.

The direct application of the proposed algorithm on such a large configuration requires to execute the worst-case delay analysis for each priority assignment to a VL. It means at least 1000 execution of the trajectory computation on the whole network, probably much more since many priority assignments lead to an exceeded delay. In order to manage this amount of computation, it is necessary to minimize the computation time for each trajectory computation. The solution would be to keep all the results of the FIFO computation, then to only modify the values which are impacted by the priority assigned to each VL, in a step by step process. Such an incremental computation is still an open issue.

In a first step, we apply a heuristic. We assign the low priority to the largest possible set of VLs which have the smallest worst-case delay with FIFO (we check that the delay of these VLs do not exceed R ′ max ). Then the high priority is assigned to all the remaining VLs and the R ′ max constraint is checked on these VLs. The number of execution of the trajectory computation is drastically reduced: one per tested set for the low priority and one at the end. Of course, the drawback is that it can lead to a significantly suboptimal priority assignment.

The application of this heuristic on the configuration in Figure 7 leads to a reduction of 20 % of the overall worstcase delay. 970 VLs out of 1000 are assigned the low priority. This result is very promising.

V. CONCLUSION

This paper deals with the assignment of priorities to flows transmitted on an avionics switched Ethernet network (QoS AFDX) implementing a fixed priority/FIFO scheduling policy. The proposed solution uses the well-known Optimal Priority Assignment algorithm (OPA) which was first defined for monoprocessor preemptive systems. The schedulability test used by the algorithm is based on the Trajectory approach.

Thus we show that this approach is OPA-compatible. Then we show on two case studies is efficient, since the overall worst-case delay of flows is reduced by 30 % for a small configuration and 20 % on a realistic one.

The computation still needs to be optimized in order to be able to cope efficiently with a realistic configuration with roughly 1000 Vls.

The proposed approach considers the worst-case delay as the key constraint of an AFDX network. Another very important feature is the maximum size of buffers needed in each switch in order to guarantee that no frames are lost. It is determined thanks to the computation of the maximum backlog in each switch. Such a computation has been proposed in the FIFO context, based on the Trajectory approach [START_REF] Bauer | Worst-case backlog evaluation of avionics switched ethernet networks with the trajectory approach[END_REF]. An extension of this computation with two priority levels has been proposed in [START_REF] Garikiparthi | Calculation of worst case backlog for afdx buffers with two priority levels using trajectory approach[END_REF]. We plan to assign priorities in order to minimise the buffer sizes in the switches.

Fig. 1 .

 1 Fig. 1. Illustrative AFDX configuration

Fig. 3 .

 3 Fig. 3. Worst-case scenario for v 4

Fig. 4 .

 4 Fig. 4. Worst-case scenario for v 4 with priority 2

Fig. 5 .

 5 Fig. 5. Worst-case scenario for v 4 with priority 3

Fig. 6 .

 6 Fig. 6. Sample AFDX configuration

TABLE I

 I

	.	VL FEATURES
	switch output port. Up to now, all the VLs are assigned the
	same priority, leading to a FIFO scheduling in existing AFDX
	switch.

TABLE II

 II

	.	TASK SET SCHEDULABLE WITH OPA

TABLE III

 III

	.	VL FEATURES
	assigned to the VLs are shown on the curve. Four priority
	levels are used by OPA for this configuration. 13 VLS are
	assigned the lowest priority (1), while respectively 2, 1 and 2
	VLs are assigned priority levels 2, 3 and 4.


Leila Amgoud
email: amgoud@irit.fr

An axiomatic approach for persuasion dialogs

Keywords: Argumentation, Dialog, Postulates

Several systems were developed for supporting public persuasion dialogs where two agents with conflicting opinions try to convince an audience. For computing the outcomes of dialogs, these systems use (abstract or structured) argumentation systems that were initially developed for nonmonotonic reasoning.

Despite the increasing number of such systems, there are almost no work on high level properties they should satisfy. This paper is a first attempt for defining postulates that guide the well-definition of dialog systems and that allow their comparison. We propose six basic postulates (including e.g. the finiteness of generated dialogs). We then show that this set of postulates is incompatible with those proposed for argumentation systems devoted for nonmonotonic reasoning. This incompatibility confirms the differences between persuading and reasoning. It also suggests that reasoning systems are not suitable for computing the outcomes of dialogs.

I. INTRODUCTION

Argumentation theory has become a hot topic in Artificial Intelligence. It is studied for modeling agent's internal reasoning, namely for handling inconsistent/incomplete and uncertain information (e.g., [START_REF] Besnard | A logic-based theory of deductive arguments[END_REF], [START_REF] García | Defeasible logic programming: an argumentative approach[END_REF]) and for making decisions (e.g., [START_REF] Amgoud | Using arguments for making and explaining decisions[END_REF], [START_REF] Fox | Arguing about beliefs and actions[END_REF]). There is also an extensive literature devoted to modeling agent's interactions, namely dialogs in which agents may exchange arguments with each other, like persuasion (e.g., [START_REF] Amgoud | Modelling dialogues using argumentation[END_REF], [START_REF] Prakken | Coherence and flexibility in dialogue games for argumentation[END_REF]), negotiation (e.g., [START_REF] Kakas | Adaptive agent negotiation via argumentation[END_REF], [START_REF] Parsons | Agents that reason and negotiate by arguing[END_REF]) and deliberation (e.g., [START_REF] Mcburney | The eightfold way of deliberation dialogue[END_REF]). In all these disparate applications, an argumentation theory [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] consists of a set of arguments justifying claims, attacks among those arguments and a semantics. This latter is a set of criteria describing which arguments are acceptable together.

Persuasion is a type of dialog in which two agents having conflicting opinions about an issue try to convince each other either in public, i.e., in presence of an audience (e.g. [START_REF] Bonzon | On the outcomes of multiparty persuasion[END_REF], [START_REF] Cabrio | Natural language arguments: A combined approach[END_REF], [START_REF] Kontarinis | Picking the right expert to make a debate uncontroversial[END_REF]) or in private, i.e., in absence of any audience (e.g. [START_REF] Amgoud | Modelling dialogues using argumentation[END_REF], [START_REF] Prakken | Coherence and flexibility in dialogue games for argumentation[END_REF], [START_REF] Zabala | Beliefs, reasons and moves in a model for argumentative dialogues[END_REF]). In both cases persuasion is done by exchanging arguments. An important feature of private persuasion is the evolution of the argumentation systems of both agents by adding the arguments received from the other party. An agent is persuaded if the subject of the dialog is supported by its system at a given step of the dialog. Thus, this kind of dialogs is more concerned with the dynamics of the argumentation systems of the agents.

In this paper, we focus on public persuasion in which agents try more to convince an audience rather than the other party. In the debate between Holland and Sarkozy before the presidential election, both candidates tried to convince the voters. Systems that support this type of dialogs have three main components: i) a protocol which is a set of rules that define coherent dialogs, ii) a set of reasoning systems of agents involved in dialog and iii) a system for computing the outcomes of dialogs. In existing literature, the reasoning system of an agent is either a Dung style abstract argumentation system [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] or one of its logic-based instantiations (e.g., [START_REF] D2 | Towards a consensual formal model: inference part[END_REF], [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF]). The system that is used for computing the outcomes of dialogs is exactly of the same nature as those of the agents. However, its arguments come from the exchanges made by the agents during the dialog and the attacks are the conflicts among them.

Despite the increasing number of works on modeling public persuasion, there are almost no work on high level requirements expected from dialog systems. Consequently, apart from the termination of their dialogs, it is not clear what other properties they satisfy. This makes their proper evaluation difficult if not impossible. This paper provides a first attempt for defining postulates that guide the welldefinition of dialog systems. We focus on systems that use Dung style argumentation systems both for modeling the reasoning of agents and for computing the outcomes of dialogs. We propose six basic postulates that any such dialog system should satisfy. Some of them (non-triviality, naturalattacks-allowanceand dissimulation) ensure that a dialog system captures natural language dialogs. The three other postulates (finiteness, consistency and non-determinism) are more about the quality of dialogs. Since one cannot speak about a dialog without referring to its subject thus to its content, then in what follows we consider dialog systems whose various argumentation systems are logic-based. Our postulates hold for any instantiation of Dung's framework. However, for illustration purposes, we have chosen those based on deductive logics [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF]. The second main contribution of the paper consists of comparing the six postulates with those proposed for argumentation systems devoted for nonmonotonic reasoning, i.e., the systems used by the agents. We show that the two sets are incompatible. This incompatibility confirms the differences between persuading and reasoning. It also suggests that reasoning systems are not suitable for computing the outcomes of dialogs.

The paper is organized as follows: Section II recalls both the argumentation system proposed in [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF] for reasoning about inconsistent information and the set of postulates it should enjoy. Section III defines a public persuasion system and Section IV proposes a set of postulates the system should satisfy. Section V compares the two sets of postulates. The last section is devoted to some concluding remarks.

II. ARGUMENTATION FOR REASONING

This section recalls the argumentation system proposed in [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF] for reasoning about inconsistent information. It is a logicbased instantiation of Dung's framework [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. Note that the same kind of results could also be obtained for rule-based systems like ASPIC [START_REF] D2 | Towards a consensual formal model: inference part[END_REF].

A. Basic definitions

In [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF], the argumentation system is grounded on Tarski's logics [START_REF] Tarski | Logic, Semantics[END_REF]: i.e., pairs (L, CN) where L is a set of well-formed formulas and CN is a consequence operator that satisfies the following basic properties: For X ⊆ L,

• Expansion: X ⊆ CN(X) • Idempotence: CN(CN(X)) = CN(X) • Absurdity: CN({x}) = L for some x ∈ L
The notion of consistency is defined as follows:

A set X ⊆ L is consistent wrt a logic (L, CN) iff CN(X) = L. It is inconsistent otherwise. Arguments are built from a knowledge base Σ ⊆ L.

Definition 1 (Argument): An argument built from a knowledge base Σ is a pair (X, x) s.t.

•

X ⊆ Σ • X is consistent • x ∈ CN(X) • ∄X ′ ⊂ X such that x ∈ CN(X ′ ) An argument (X, x) is atomic iff X = {y} and CN({x}) = CN({y}). It is a sub-argument of (X ′ , x ′ ) iff X ⊆ X ′ .
Example 1: Let Σ = {¬wh, ¬wh → f e, vs → ¬f e, vs} be a knowledge base representing the following information: Mary does not work hard (¬wh), if somebody does not work hard then he will fail his exams (f e), if somebody is very smart (vs) then he will not fail his exams, Mary is very smart. The following arguments may be built from Σ: a 0 = (∅, f e ∨ ¬f e), a 1 = ({¬wh}, ¬wh), a 2 = ({¬wh, ¬wh → f e}, f e), a 3 = ({vs, vs → ¬f e}, ¬f e).

The following proposition shows that it is possible to build an atomic argument from any formula that is neither a tautology nor a contradiction.

Property 1: Let Σ be a knowledge base. For all x ∈ Σ, if x ∈ CN(∅) and CN({x}) = L then ({x}, x) is an (atomic) argument.

Proof: For all x ∈ Σ, it holds that {x} ⊆ Σ, moreover if CN({x}) = L then {x} is consistent. Due to expansion, x ∈ CN({x}). Since ∅ is the only strict subset of {x}, if x ∈ CN(∅) then ∄X ⊂ {x} such that x ∈ CN(X).

Note that for most classical logics (instances of Tarski's ones, e.g. propositional logic, first order logic ...), the set of all arguments that may be built from a (finite) knowledge base is infinite.

Notation 1: Supp and Conc are two functions that return respectively the support X and the conclusion x of an argument (X, x). Sub is a function that returns all the sub-arguments of a given argument. An argumentation system is defined as follows.

Definition 2 (Argumentation system): An argumentation system (AS) over a knowledge base Σ is a pair T = (A, R) such that A is a set of arguments built from Σ using Definition 1, R ⊆ A × A is an attack relation. For a, b ∈ A, (a, b) ∈ R (or aRb) means that a attacks b. In the next sections, we will show that, for a reasoning system and for a dialog system, the set A of arguments should not be chosen in an arbitrary way. There are some constraints that should be fulfilled. The attack relation R is left unspecified in the sequel since our analysis is independent from its exact definition. Finally, arguments are evaluated using any Dung's semantics [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. The following definition recalls some of them.

Definition 3 (Semantics): Let T = (A, R) be an AS over a base Σ and E ⊆ A s.t. ∄a, b ∈ E s.t. aRb.

• E is an admissible set iff E defends all its elements (i.e., it attacks any attacker of its arguments). • E is a preferred extension iff E is a maximal (for set inclusion) admissible set. • E is a stable extension iff ∀a ∈ A \ E, ∃b ∈ E s.t. bRa. Ext(T ) returns the set of extensions of the AS T under a given semantics. The extensions are used in order to define the plausible conclusions to be drawn from Σ. The idea is to infer a formula x from Σ iff x is the conclusion of an argument in each extension. Output(T ) is the set of all such formulas. Definition 4 (Output): Let T = (A, R) be an AS over a knowledge base Σ.

Output(T ) = {x ∈ L | ∀E ∈ Ext(T ), ∃a ∈ E s.t. Conc(a) = x}.

B. Basic postulates for reasoning systems

A set of desirable properties that the previous systems should satisfy was proposed in [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF]. The postulates are compatible (i.e., can be satisfied all together). The first one ensures that each extension supports consistent conclusions. The second postulate concerns the closure of its output under the consequence operator CN. The third postulate concerns sub-arguments. It ensures that the acceptance of an argument should imply also the acceptance of all its sub-parts.

Consistency: Let T = (A, R) be an AS over a base Σ. For all E ∈ Ext(T ), {Conc(a) | a ∈ E} is consistent.

Closure under CN: Let T = (A, R) be an AS over a base Σ. For all E ∈ Ext(T ), {Conc(a) | a ∈ E} = CN({Conc(a) | a ∈ E}).

Closure under sub-arguments: Let T = (A, R) be an AS over a base Σ. For all E ∈ Ext(T ), if a ∈ E, then Sub(a) ⊆ E.

The following simple property is useful for our discussion in next sections. It shows that an argumentation system which is closed under sub-arguments and which admits non empty extensions contains a set of atomic arguments. Moreover, if the system is closed under CN then it should contain all arguments supporting tautologies.

Proposition 1:

Let T = (A, R) be an AS. For all E ∈ Ext(T ), if E = ∅ then: • If T is closed under sub-arguments, then ∀x ∈ ∪ a∈E Supp(a), if x ∈ CN(∅), then ({x}, x) ∈ E. • If T is closed under CN, then ∀x ∈ CN(∅) (∅, x) ∈ E.
Proof: Let T = (A, R) be an AS and Ext(T ) its set of extensions under a given semantics. Assume that E ∈ Ext(T ) and E = ∅.

Let a ∈ E. Assume that Supp(a) = ∅. For all x ∈ Supp(a), {x} is consistent (since Supp(a) is consistent and due to Property 2 in [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF]). If

III. PUBLIC PERSUASION DIALOG SYSTEMS

This section defines an abstract public persuasion system that may be used, for instance, in online debate platforms. The system is abstract since it keeps one of its main components, protocol, unspecified. Moreover, the notion of audience is not explicitly represented.

A dialog system has three main components: a set of agents represented by their reasoning models, a protocol, and a rule for computing the outcome of any dialog that takes place between the agents. A protocol specifies the set of rules governing the well-definition of dialogs (e.g., who is allowed to say what and when?). In the sequel, we leave this component unspecified. Thus, our system can be instantiated by any protocol.

For the purpose of our paper and without loss of generality, we focus on persuasion dialogs between two agents P and C. Each of them is equipped with a knowledge base Σ k (with k ∈ {P, C}) and an argumentation system (in the sense of Definition 2)

T k = (A k , R k ).
It is worth mentioning that the two agents may use two distinct attack relations (for instance, P may use the undercut relation [START_REF] Pollock | How to reason defeasibly[END_REF] whereas C assumption attack [START_REF] Elvang-Gøransson | Acceptability of arguments as logical uncertainty[END_REF] (see section IV)). They may also choose distinct semantics for the evaluation of arguments. However, they use the same underlying monotonic logic (L, CN). Indeed, in order to be able to understand each other they should at least share the same language.

Before defining the third component of a dialog system, i.e., its rule for computing the outcomes of dialogs, let us first define what is a persuasion dialog. The notion of move is the backbone of a dialog. It consists of two agents (a speaker and a hearer) and a speech act together with a content. The speech act is taken from a set S1 . The only restriction on S is that it should contain at least two kinds of speech acts: "Argue" for exchanging arguments and "Assert" for making claims.

Definition 5 (Move): Let S be a set of speech acts symbols containing at least "Argue" and "Assert" symbols. A move m is a triple s, h, a s.t.

• s ∈ {P, C} is the agent that utters m.

• h ∈ {P, C} is the agent to whom the move is addressed.

• a = act : content s.t. act ∈ S and content ∈ L ∪ A P ∪ A C . If act = Argue (respectively act =Assert) then content ∈ A P ∪ A C (resp. content ∈ L).
Act and Content are two functions s.t. Act(m) = act and Content(m) = content. A persuasion dialog is a "valid" sequence of moves, i.e., a sequence that satisfies all the rules of the protocol. Since we do not focus on particular protocols, then we use the term 'valid' without defining it formally. Besides, the subject of a persuasion dialog is a claim made via an Assert move by one of the agents. Arguments are exchanged in order to increase or decrease its acceptability.

Definition 6 (Persuasion dialog): A persuasion dialog D generated by a dialog system DS2 is a non-empty (finite or infinite) valid sequence of moves

(m i ) s.t. Act(m 1 ) = Assert. The subject of D is Subject(D) = Content(m 1 ).
For computing the outcome of a persuasion dialog, an argumentation system in the sense of Definition 2 is used. Its arguments are those exchanged in the dialog in addition to the atomic arguments built from the assertions made in the dialog. The idea is to consider all the different kinds of claims (either in form of assertions or arguments) made by the agents. Defining the attack relation of this system is more tricky since the agents may use different relations. In what follows, we assume the existence of a third relation denoted R which results from a merging of the two relations R P and R C using an operator ⊕ not specified in this paper. Thus, R = R P ⊕ R C . An example of a merging operator is the union which considers all the attacks which hold either in R P or in R C . We can go further by checking wether the agent who asserted the subject wins or not the dialog.

Definition 9 (Dialog winner): Let D be a persuasion dialog generated by a dialog system DS with m 1 = s, h, a . If Subject(D) ∈ Output(AS D ) then s wins the dialog D and h looses it. Otherwise, h wins and s looses the dialog. Let Winner be a function such that Winner(D) returns the agent that wins the dialog D.

IV. BASIC POSTULATES FOR DIALOG SYSTEMS

In the previous section, we have defined what a dialog system is. It generates non-empty persuasion dialogs. In what follows, we propose some key features, called also postulates, that should be satisfied by the system and the dialogs it generates.

The first postulate concerns the finiteness of the generated dialogs. This requirement is already known in the literature. In [START_REF] Johnson | When are two protocols the same? In Communication in Multiagent Systems[END_REF], protocols should ensure termination. Here, we require finiteness not only for the number of moves but also for the content of each move. For instance, it is not allowed to assert x ∧ x ∧ . . .. Finiteness: Finiteness holds for a dialog system DS iff for all persuasion dialog D generated by DS, size(D) ∈ N where size(D) = m∈D sizemove(m) with sizemove(m) is the number of occurrences of atoms and operators used in the content of m.

As said before, a protocol guides the well-definition of dialogs and is common to all agents. However, the outcome of a dialog depends on the strategies of the agents. This is captured by the next postulate which constrains the dialog system to be able to generate at least one dialog in which a subject is accepted and one dialog in which it is not.

Non-determinism: A dialog system DS is non-determinist iff for all formula x ∈ L, s.t. x ∈ CN(∅) and CN({x}) = L, there exist at least two dialogs D 1 and D 2 generated by DS, such that Subject(D 1 ) = Subject(D 2 ) = x and Output(D 1 ) = Output(D 2 ).

Note that if the set of non-trivial formulas of L (i.e., without considering tautologies and contradictions) is infinite then any dialog system satisfying non-determinism can generate an infinite number of dialogs.

The third important postulate concerns the formalism that is used for computing the outcomes of dialogs. In our context, Dung's system should ensure sound results. Namely, extensions (under any semantics) represent various positions in a dialog. Thus, each of them should be coherent. This leads to a consistency postulate similar to the one presented for reasoning systems in [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF].

Consistency: A dialog system DS ensures consistency iff for all persuasion dialog D generated by DS, for all E ∈ Ext(AS D ), {Conc(a) | a ∈ E} is consistent.

The aim behind building systems for persuasion dialogs is to automate such dialogs and to conduct efficient ones. However, these systems should capture as much as possible natural dialogs. Works by linguists [START_REF] Quiroz | How counterargumentation works[END_REF], [START_REF] Salavastru | Logique, Argumentation, Interprétation. L'Harmattan[END_REF] have emphasized the main forms of counter-argumentation that may take place in everyday life dialogs. The first one, known as "rebuttal" in [START_REF] Elvang-Gøransson | Acceptability of arguments as logical uncertainty[END_REF], consists of undermining the conclusion of another argument. The second form, known as "assumption attack" in [START_REF] Elvang-Gøransson | Acceptability of arguments as logical uncertainty[END_REF], consists of undermining a premise in the support of another argument. It is thus important for a dialog system to capture these two forms of attacks. The following postulate ensures this by constraining the attack relation R.

Natural-attacks-allowance: A dialog system DS allows for natural attacks iff for all persuasion dialog D generated by DS, for all a, b ∈ Args(D),

• if a rebuts b then (a, b) ∈ R, and

• if a assumption-attacks b then (a, b) ∈ R.
It is well-known that in public persuasion dialogs, agents try to convince others about a given claim even if they think that this latter does not hold. They then hide arguments and information in order to reach their objectives. A dialog system should thus allow dissimulation of information. More formally a dialog system allows dissimulation if it can generate some dialogs in which the winner would have change if one of the agents had uttered (had not concealed) some argument.

Dissimulation: A dialog system DS allows dissimulation iff there exists a persuasion dialog D between two agents (say k and l) generated by DS such that ∃a ∈ A k , such that

Winner(D) = Winner(D; k, l, a )
The last postulate is about the efficiency of persuasion dialogs. Recall that in such dialogs, agents try to convince other parties to accept some assertion by putting forward arguments. These latter are intended to justify the assertion by new evidences. Thus an argument in which an assertion is justified by the assertion itself fails to meet the objective of arguing. Assume a politician who tries to convince a population that taxes should be increased. Nobody will accept an argument of the form: "taxes should be increased because they should be increased". This does not mean that nobody will accept the idea of increasing taxes especially people who have good reasons in favor of tax increase. Thus, for a persuasion to be efficient, atomic arguments should be avoided. Similarly, tautologies are not allowed in dialogs since they are not informative. To put it differently, they do not bring new information and this is certainly not suitable in persuasion dialogs.

Non-triviality: A dialog system DS ensures non-triviality iff for all persuasion dialog D generated by DS, for all a ∈ {Content(m) | m ∈ D, Act(m) = Argue}, a is not atomic and Conc(a) is not a tautology (i.e., Conc(a) / ∈ CN(∅)). The postulates are compatible (i.e., can be satisfied all together by a dialog system). There is however a problem for ensuring consistency together with natural-attacksallowance. This is due to Dung's framework, when it is instantiated by symmetric attack relations the system is not able to guarantee to obtain consistent conclusions. Indeed, in [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF], an example of violation of the consistency postulate in the context of symmetric attack is described. Nevertheless, the non compatibility of consistency and natural-attacksallowance in Dung's framework does not mean that the two postulates are not required for dialog systems.

Proposition 2: Finiteness, consistency, natural-attacksallowance, non-triviality, non-determinism and dissimulation are compatible.

Proof: (Sketch) Let (L 0 , ⊢) be a propositional language whose vocabulary contains at least two propositional variables Let A 0 be the arguments built from L 0 by using Definition 1 and let R 0 ⊂ A 0 ×A 0 an arbitrary non reflexive attack relation containing rebut and assumption-attack.

Let DS based on (L 0 , ⊢), with {P, C} the set of agents and s.t. a sequence of moves D = (m i ) is a valid dialog wrt to the protocol iff D = (m1) or D = (m1, m2) such that m1 = s, h, Assert : ϕ and m2 = s, h, Argue : a where s ∈ {P, C}, h ∈ {P, C} and ϕ ∈ L 0 and ϕ is finite and a ∈ A 0 such that a is not atomic and not supporting a tautology and Conc(a) is finite. Let the output of D be computed under stable semantics. Finiteness, non-triviality, natural-attack allowance hold by construction. Consistency is ensured by the fact that there is at most two arguments, they could be together in the basic extension only if their conclusions are consistent (due to the presence of rebuttal attack). Non determinism and dissimulation can be shown by using a dialog with only the first assert move compared to a dialog in wich an argument against it is added.

Proposition 3: Finiteness, consistency, natural-attacksallowance, non-triviality, non-determinism and dissimulation are independant.

Proof: (sketch) For each postulate, we may provide a dialog system in which every postulate holds except the one considered.

V. DIALOG SYSTEMS POSTULATES VS. REASONING SYSTEMS POSTULATES

A dialog system, with two participating agents, uses three argumentation systems of the same kind. They are all logical instantiations of the abstract framework of Dung [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. Two of the systems are used for modeling the nonmonotonic reasoning of the agents and should thus obey to postulates like those recalled in Section II-B. The third argumentation system is devoted to a completely different purpose which is computing the outcomes of persuasion dialogs. The difference of tasks raises the question of the suitability of the postulates of the two reasoning systems for the one that computes the outcomes of dialogs. More generally, are those postulates compatible with the ones proposed previously for dialog systems? In this section we show that the two sets of postulates are incompatible.

A. Reasoning postulates in a dialog context

The first postulate that a reasoning system should satisfy concerns the consistency of its extensions. It ensures that the system returns sound results. A similar postulate is required for a dialog system, namely for its argumentation system that computes the outcomes of dialogs. While this postulate is compatible with the two closure ones, in case of dialogs this is unfortunately not guaranteed. Indeed, we have shown in the previous section that consistency is not compatible with natural-attacks-allowance, namely when symmetric attack relations are used. It is worth mentioning that in reasoning, symmetric attack relations can be avoided. Indeed, there exist non-symmetric attack relations that ensure the consistency postulate (see [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF]). However, things are not so simple in dialogs. Getting rid of rebuttals in dialogs would constrain the kind of moves agents may utter. This would also mean that it is not possible to design dialog systems (based on Dung's system) that capture everyday life dialogs in which rebuttals are very common.

Closure under CN is a suitable postulate for reasoning systems since it guarantees a form of "completeness" of their outputs. Tautologies are among the plausible conclusions that are ensured. These formulas, even if they are trivial, may serve as a basis for testing the quality of those systems. However, in a dialog context, they are not suitable since they are not "informative". Thus, closure under CN is not a required postulate for dialog systems. We can even show that it is incompatible with the non-triviality postulate.

Proposition 4: Let DS be a dialog system. If CN(∅) = ∅ and DS satisfies non-triviality, then for all dialog D generated by DS, if the argumentation system AS D admits at least one extension then it violates closure under CN.

Proof: Let DS be a dialog system and CN(∅) = ∅. Since DS satisfies non-triviality then for any dialog D generated under DS, ∄a ∈ Args(D) such that Conc(a) ∈ CN(∅).

Let E be an extension of the system AS D under a given semantics and let ϕ ∈ CN(∅). Then, ϕ ∈ {Conc(a), a ∈ E}. However, ϕ ∈ CN({Conc(a), a ∈ E}) since ∅ ⊆ {Conc(a), a ∈ E} and from the monotonicity of CN, it follows that CN(∅) ⊆ CN({Conc(a), a ∈ E}). Hence, AS D violates closure under CN.

Some dialog systems may even miss some non trivial conclusions. Let us consider a dialog in which only two arguments ({x ∧ y}, x) 3 and ({z ∧ t}, z) are exchanged. The argumentation system associated with this dialog has only one stable/preferred extension which contains only the two arguments. It is easy to check that this extension is not closed under CN since, for instance, y, t and x ∧ z are not supported by arguments in the extension.

Closure under sub-arguments is another postulate which makes sense for reasoning systems but not for dialog ones. Indeed, in a dialog context, this postulate is ensured in case agents utter all the sub-arguments of their arguments. This is certainly not realistic. Let us consider the following dialog between Carla and Peter.

Carla: Mary will miss her exams. She did not work hard. Peter: She worked hard. Her eyes are encircled and she is very tired. The corresponding argumentation system contains the two exchanged arguments and one attack from the argument (say b) of Peter to that of Carla (say a). This system has one stable/preferred extension: {b}. This extension is not closed under sub-arguments since b has at least two sub-arguments (one for "Mary's eyes are encircled" and one for "Mary is very tired") which are not in the extension. In order to satisfy the postulate, Peter should utter two additional arguments for the two statements. The following result shows that this postulate is even not compatible with the non-triviality one.

Proposition 5: Let DS be a dialog system. If DS satisfies non-triviality, then for all dialog D generated by DS whose argumentation system AS D admits non-empty extensions, AS D violates closure under sub-arguments.

Proof: Let D be a dialog generated by a dialog system DS. Let AS D be its argumentation system and E be a nonempty extension of AS D under a given semantics. Thus, ∃a ∈ E. Since E ⊆ Args(D) and DS satisfies non-triviality, then Supp(a) = ∅. Consequently, ∃ϕ ∈ Supp(a). There are two possible cases:

• ϕ ∈ CN(∅). Then, (∅, ϕ) is a tautological argument and (∅, ϕ) / ∈ Args(D) since DS satisfies non-triviality. Thus, (∅, ϕ) / ∈ E. • ϕ / ∈ CN(∅). Then, ({ϕ}, ϕ) is an atomic argument and ({ϕ}, ϕ) / ∈ Args(D) since DS satisfies non-triviality. So ({ϕ}, ϕ) / ∈ E. 3 We assume here that (L, CN) is propositional logic.

Both arguments (∅, ϕ) and ({ϕ}, ϕ) are sub-arguments of a and do not belong to E. Thus, AS D is not closed under sub-arguments.

B. Dialog postulates in a reasoning context

This section discusses the suitability of the postulates of dialog systems in a reasoning context. We start with the finiteness postulate which ensures finite dialogs. An important question is: do argumentation systems for reasoning need to be finite (i.e., have a finite number of arguments)? From a computational perspective, finiteness is certainly a desirable property since the computation of the extensions of infinite systems would be hard if not impossible. However, in practice the finiteness property depends broadly on the logic (L, CN) underlying the argumentation system. For a broad class of logics, the set of all arguments that may be built from a knowledge base is infinite. This is particularly the case for classical logics. Nevertheless, it was shown in [START_REF] Amgoud | On the equivalence of logic-based argumentation systems[END_REF] that for some logics it is possible to consider only a subset of the whole set of arguments. The corresponding argumentation system, called core, returns exactly the plausible conclusions of the argumentation system that takes as input all the arguments built from the base. For some logics, as shown below, the core is finite. Before presenting the formal result, let us first introduce some useful notations.

F ′ = (A ′ , R ′ ) s.t. A ′ ⊆ A, R ′ ⊆ R, Output(F) = Output(F ′ ) and A ′ is finite.
Proof: Let F = (A, R) be an argumentation system built over a knowledge base Σ. In [START_REF] Amgoud | On the equivalence of logic-based argumentation systems[END_REF], it is shown that each argumentation system has a core. The idea is to take exactly one argument from each equivalence class of arguments of A. Let F ′ = (A ′ , R ′ ) s.t. A ′ ⊆ A, R ′ ⊆ R be that system. Theorem 4 of [START_REF] Amgoud | On the equivalence of logic-based argumentation systems[END_REF] shows that F and F ′ have equivalent extensions. Thus, Output(F) = Output(F ′ ). Besides, Theorem 5 of [START_REF] Amgoud | On the equivalence of logic-based argumentation systems[END_REF] shows that in this case A ′ is finite. However, the core may be infinite for some other logics. To sum up, two cases can be distinguished:

1) Argumentation systems that have finite cores, which, then, can be replaced by systems that satisfy the finiteness postulate. 2) Argumentation systems that have infinite cores which, thus, violate the finiteness postulate. Note that the notion of core is crucial in reasoning since it gathers the key arguments that are necessary and sufficient to define the plausible conclusions of an argumentation system. Recall that in such systems, generated from a knowledge base without discrimination. However, in dialogs, agents choose the arguments to utter and may hide some of them. Thus, the argumentation system associated with a dialog does not necessarily contain its core. This will impact the outcome of the dialog since, as shown in [START_REF] Amgoud | On the equivalence of logic-based argumentation systems[END_REF], when a system does not contain its core, then the status of its arguments are not final and may evolve.

Proposition 7: Let DS be a dialog system satisfying non-triviality. If L contains tautologies and R does not contain attacks against tautoligical arguments, then for all non-empty dialog D generated by DS, Output(AS D ) = Output(CAS D )

where CAS D = (Arg( a∈Args(D) Supp(a)), R) and for S ⊆ L, Arg(S) is the set of all arguments that may be built from S using Definition 1.

Proof: Indeed, if D is non-empty then Args(D) is not empty, thus CAS D contains tautological arguments. These arguments should belong to Ext(CAS D ). Thus, tautologies should belong to Output(CAS D ) but due to non-triviality they cannot appear in Output(AS D ).

As said before, consistency may be violated by the argumentation system that computes the outcomes of dialogs due to the use of the rebutting relation (imposed by the natural-attacks-allowancepostulate). This is particularly the case when the knowledge base contains a ternary or more minimal inconsistent subset as shown below:

Example 2: Assume a dialog D whose AS is as follows: The set {a 1 , a 5 , a 6 } is a preferred extension of this system. However, its set {x, y, ¬x ∨ ¬y} of conclusions is clearly inconsistent.

a 1 = ({t ∧ x},
The inconsistency problem can be avoided by getting rid of the natural-attacks-allowancepostulate, reducing thus the kind of natural language dialogs that may be conducted. This is certainly not a desirable solution.

Non-triviality postulate (which consists of avoiding atomic arguments and arguments supporting tautologies) is violated by reasoning systems as shown by Proposition 1.

Non-determinism postulate expresses that for any nontrivial formula, it should be possible to generate two dialogs with opposite conclusions. This is very important in dialogs to ensure strategic debates. However, this postulate is not suitable for reasoning systems since these latter should determine in an objective way whether a formula holds or not.

Dissimulation postulate is clearly not compatible with a reasoning system. It highlights a main difference between reasoning and persuading. While in reasoning one looks for the truth of formulas and considers thus all available information, in persuading one looks for convincing another agent about an issue. This may be done by hiding crucial information which run counter the issue.

VI. CONCLUSION

Since early nineties, there is an increasing number of works trying to formalize dialogs in which agents may exchange arguments. Persuasion and negotiation dialogs have received particular attention from AI community. Several systems were developed for each of them. In those systems arguments are exchanged in order to support claims in persuasion dialogs and offers in a negotiation context. The arguments are then evaluated using argumentation systems that were originally developed for nonmonotonic reasoning or for reasoning about inconsistent information.

In this paper, we focused on persuasion dialogs, and more precisely on public persuasions where two agents with conflicting opinions try to persuade each other in presence of an audience. Note that the aim here is rather to persuade the audience. We studied whether the approach followed in the literature for defining dialog systems is sound or not. For that purpose, we considered a recent argumentation system proposed in [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF] for reasoning about inconsistent information. Note that our study holds for any other logic-based instantiation of the abstract framework of Dung [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], like ASPIC system [START_REF] D2 | Towards a consensual formal model: inference part[END_REF]. We then proposed a general persuasion dialog system. This persuasion system is general since one of its basic components (the protocol) is left unspecified. For each of the reasoning and persuading systems, we propose a set of postulates that should hold. For reasoning systems, we considered the three basic postulates defined in [START_REF] Amgoud | Postulates for logic-based argumentation systems[END_REF], namely the consistency of the conclusions supported by the extensions, their closure under the consequence operator, and finally the closure under sub-arguments of the extensions. Regarding dialog systems, we proposed six postulates: the finiteness postulate ensures termination of the dialog. Non-determinism postulate imposes that the system may generate dialogs with different outcomes. The third postulate imposes consistency of the outcomes of dialogs. This postulate ensures that the system that is used for evaluating the arguments exchanged in a dialog is sound. The fourth postulate aims to capture as much as possible life use of counter-argumentation. The dissimulation ensures that an agent may hide some information. The last postulate ensures that agents do not utter trivial arguments during a dialog. An important contribution of this paper consists of investigating the compatibility of the two sets of postulates. We have shown that the three postulates of reasoning systems cannot be satisfied by a dialog system since in this latter the set of exchanged arguments is not complete (due to the finiteness of dialogs and also to the fact that in dialogs, some arguments are considered as trivial and thus do not need to be exchanged). Similarly, we have shown that four postulates of the dialog system cannot be satisfied by the argumentation system. Moreover, we have established that the outcome of a dialog system can be different from the outcome that should be obtained by a reasoning system that would use a knowledge base containing all the formulas exchanged during the dialog. To sum up, the study has revealed that a dialog system needs particular argumentation systems for evaluating its outcomes. Those systems should obey the nature of dialog. This work can be extended in different ways. The first one consists of defining argumentation systems that are more suitable for public persuasion dialogs and that ensure the postulates discussed in this paper. Another future work consists of defining new postulates for dialogs, namely for capturing manipulation in dialogs. Finally, we are planning to undertake a similar study in the context of negotiation dialogs. Recall that in those systems, the outcome of a negotiation is evaluated by argumentation systems developed for making decisions.

  x / ∈ CN(∅), then ({x}, x) is an argument. Moreover, it is a sub-argument of a. T being closed under sub-arguments, this means that ({x}, x) is also an argument of E. By monotonicity of CN, since ∅ ⊆ {Conc(a)|a ∈ E} then CN(∅) ⊆ CN({Conc(a)|a ∈ E}). If T is closed under CN then CN(∅) ⊆ {Conc(a)|a ∈ E}. This means that ∀x ∈ CN(∅), ∃a ∈ E such that Conc(a) = x. Due to Definition 1, Supp(a) = ∅. Hence, (∅, x) ∈ E.

Definition 7 (

 7 AS of a persuasion dialog): Let D be a persuasion dialog generated by a dialog system DS. The argumentation system associated with D is the pair AS D = (Args(D), Confs(D)) s.t. • Args(D) = {Content(m) | m ∈ D and Act(m) = Argue} ∪ {({Content(m)}, Content(m)) | m ∈ D and Act(m) = Assert} • Confs(D) = {(a, b) | a, b ∈ Args(D) and (a, b) ∈ R} The outcome of a persuasion dialog D is the status of its subject wrt AS D . Definition 8 (Dialog output): Let D be a persuasion dialog generated by a dialog system DS. Subject(D) is true iff Subject(D) ∈ Output(AS D ).

•

  An argument a rebuts an argument b iff the set {Conc(a), Conc(b)} is inconsistent. • An argument a assumption-attacks an argument b iff ∃x ∈ Supp(b) s.t. the set {Conc(a), x} is inconsistent.

Notation 2 :

 2 For X ⊆ L, Cncs(X) = {x ∈ L | ∃Y ⊆ X s.t. CN(Y ) = L and x ∈ CN(Y )} is the set of formulae that are drawn from consistent subsets of X, and (Cncs(X)/ ≡ ) = {[x] | x ∈ X } with [x] = {x ′ ∈ L | CN({x ′ }) = CN({x})} is the quotient set of Cncs(X) wrt logical equivalence.Proposition 6: Let F = (A, R) be an argumentation system built over a knowledge base Σ. If (Cncs(Σ)/ ≡) is finite, then there exists an argumentation system

x) a 2 =

 2 ({y, x → ¬y}, ¬x) a 3 = ({x, y}, x ∧ y) a 4 = ({x, x → ¬y}, ¬y) a 5 = ({v ∧ ¬y}, ¬y ∨ ¬x) a 6 = ({y ∧ z}, y)

In the literature the following set of basic speech acts is often used S = {Assert, Argue, Declare, Question, Request, Challenge, Promise}.

Throughout the paper we refer to a dialog system by DS without specifying its components.