Sami Evangelista
email: evangeli@cnam.fr

Christophe Pajault
email: christophe.pajault@cnam.fr

Some Solutions to the Ignoring Problem

Keywords: explicit model checking, partial order reduction, ignoring problem, cycle proviso

The ignoring problem refers to the fact that some actions may be infinitely postponed by a state space search algorithm that makes use of partial order reduction (POR). The prevention of this phenomenon is mandatory if one wants to verify more elaborate properties than the deadlock freeness, e.g., safety or liveness properties. We present in this work some solutions to this problem. In order to assess the quality of our propositions, we included them in our model checker Helena. We report the result of some experiments which show that our algorithms yield better reductions than state of the art algorithms like those implemented in the Spin tool.

Model checking [START_REF] Clarke | Model Checking[END_REF], or state space analysis, is a formal method to prove that finite state systems match their specification. Given a model of the system and a property, usually expressed in a temporal logic such as LTL, it explores all the possible configurations, i.e., the state space, of the system to check the validity of the property. Despite its simplicity, its practical application is limited due to the well-known state explosion problem: the state space can be far too large to be explored in a reasonable time.

Partial-order reduction (POR) [START_REF] Valmari | A stubborn attack on state explosion[END_REF][START_REF] Peled | All from one, one for all: on model checking using representatives[END_REF][START_REF] Godefroid | Partial-Order Methods for the Verification of Concurrent Systems -An Approach to the State-Explosion Problem[END_REF] is an approach to cope with this problem by tackling one of its main source, the concurrent execution of several components. It is based on the following observation: due to the interleaving semantic of concurrent systems, a set of different executions can have exactly the same effect on the system and be only a permutation of the same sequence. Thus, an efficient way to reduce the state explosion would be to explore only a single or some representative executions and ignore all the others permutations that are equivalent to the chosen ones.

On the basis of this principle, several authors proposed the idea of a selective search algorithm: at each state visited by the algorithm, a set of transitions is computed and only the transitions of this set are used to generate the immediate successors of the state. The execution of the other transitions is postponed and delegated to a future state. Consequently some states may never be explored. In the best case, the state space is reduced in an exponential way.

The ignoring problem, first identified in [START_REF] Valmari | A stubborn attack on state explosion[END_REF], is a pathological situation that may arise if one does not choose sets carefully: a transition may be infinitely delayed. This means that the transition selection function can be totally unfair with respect to some process of the system. Though the prevention of this phenomenon is not mandatory if one wants to check if the system deadlocks, it must be resolved for "higher level" properties, e.g., safety or liveness properties. The idea is to enforce an additional condition, called proviso, which ensures that the selection function will never forget a transition. By strengthening the acceptance conditions of a set, the proviso may unfortunately cause new states to be generated. It is thus crucial to have an efficient proviso that introduce the least number of states.

We propose in this paper two new versions of this proviso which show good results as our experimentations attested it. The first one, designed for safety properties, can be seen as an optimization of the Spin model checker [START_REF] Holzmann | The model checker SPIN[END_REF] proviso while the second one targets liveness properties.

The paper is structured as follows. Section 1 contains some basic elements on model checking and partial-order reduction that are needed for the understanding of this paper. The next section introduces different approaches proposed to deal with the ignoring problem. In section 3 we explain our motivations and we show why, in our sense, there is still a need for other algorithms. Our contribution is the two new versions of the proviso presented in sections 4 and 5. We report in section 6 the results of some experiments done with our model checker Helena [START_REF] Evangelista | High level petri nets analysis with Helena[END_REF] which implements our propositions as well as state of the art algorithms. At last, section 7 summarizes our contribution.

1 Formal background

State transition graphs

We will develop our ideas in the frame of state transition graphs (STG). An STG is a directed graph that describes all the possible evolutions of a system.

Definition 1 (State transition graph).

A state transition graph (STG), is a 4-tuple (S, s 0 , A, →) where S is a finite set of states; s 0 ∈ S is the initial state of the system; A is a set of actions; →⊆ S × A × S is the transition relation, which is such that (s, a, s ′ ) ∈→ ∧(s, a, s ′′ ) ∈→⇒ s ′ = s ′′ .

Let (S, s 0 , A, →) be an STG. If (s, a, s ′ ) ∈→ then we note s a → s ′ and we say that s ′ is a successor of s. An action a ∈ A is enabled for s ∈ S, denoted s a →, iff there exists s ′ ∈ S such that s a → s ′ . We can also note s → s ′ if there exists a ∈ A such that s a → s ′ . The set of enabled actions at a state s ∈ S, denoted en(s), is defined by en

(s) = {a ∈ A | s a →}. A state s is a dead state iff en(s) = ∅. For any natural number n ∈ N, states s i ∈ S and actions a i ∈ A with i ∈ {1 . . . n}, s 1 a1 → . . . s n-1 an-1 → s n is called an execution sequence of length n iff s i ai → s i+1 for all i ∈ {1..n -1}. State s n is said to be reachable from s 1 . A state is reachable iff it is reachable from s 0 .

Partial-order reduction

Partial-order reductions [START_REF] Valmari | A stubborn attack on state explosion[END_REF][START_REF] Peled | All from one, one for all: on model checking using representatives[END_REF][START_REF] Godefroid | Partial-Order Methods for the Verification of Concurrent Systems -An Approach to the State-Explosion Problem[END_REF] restrict the part of the state space that needs to be explored during verification in such a way that all properties of interest are preserved. The reduction is achieved on-the-fly, i.e., during the state space exploration to avoid the construction of the full state space. The underlying principle is to select for each state some enabled actions that will be executed while the others are postponed and delegated to a future state. This selection mechanism is formalized through the notion of reduction function.

Definition 2 (Reduction function). Let (S, s 0 , A, →) be an STG. A reduction function r is a mapping from S to 2 A such that ∀s ∈ S, r(s) ⊆ en(s).

When en(s) = r(s) for some state s the function does not provide any reduction. We say that s is fully expanded. Otherwise, it is partially expanded. An action a is ignored in s iff a ∈ en(s) \ r(s).

By applying such a reduction function, one can build a reduced graph.

Definition 3 (Reduced STG). Let (S, s 0 , A, →) be an STG and r be a reduction function. The reduced STG (S r , s 0r , A r , → r ) is defined by:

-

s 0r = s 0 , A r = A. -s ∈ S r iff there is a finite execution sequence s 0 a0 → . . . an-1 → s n such that s = s n and a i ∈ r(s i ), ∀s i ∈ {s 0 . . . s n-1 }. -(s, a, s ′ ) ∈→ r iff s ∈ S r , (s, a, s ′ ) ∈→ and a ∈ r(s).
Partial-order reduction for dead states detection It is clear that a selection function has to respect some rules to preserve properties of interest. This led to several variations of the reduction according to the kind of property specified. However, since the general principle of the partial-order reduction theory is to exploit the commutativity of concurrent actions to limit useless interleavings, all are based on the key notion of independence of actions. Intuitively, two actions a and b are independent if they cannot disable each other and if they commute in any state of the system. Definition 4 (Independence). An independence relation is a symmetric and anti-reflexive relation I ∈ A × A satisfying the two following conditions for each state s ∈ S and for each (a, b) ∈ I.

Enabledness if a, b ∈ en(s) and s b → s ′ then a ∈ en(s ′ ). Commutativity if a, b ∈ en(s) then s a → s ′′ b → s ′ and s b → s ′′′ a → s ′ .
Two actions a and b are independent iff (a, b) ∈ I. Otherwise, they are dependent and (a, b) belongs to the relation (A × A) \ I. This independence relation is usually computed at compile time, i.e., before the exploration of the state space, on the basis of a static analysis of the model. An action that only manipulate local variables, e.g., an assignment to a local variable will be typically considered as independent from any other action.

We are now able to enumerate the two following conditions which allow us to compute a persistent set (PS) of transitions for a state s. C0 r(s) = ∅ iff en(s) = ∅. C1 an action that is dependent on an action of r(s) cannot be executed without a transition in r(s) occurring first.

A reduction function that compute persistent sets preserves all the dead states of the system [START_REF] Godefroid | Partial-Order Methods for the Verification of Concurrent Systems -An Approach to the State-Explosion Problem[END_REF] and can thus be used for the detection of such states. The only purpose of C0 is to guarantee that the search algorithm with reduction progresses if the normal one does. The intuition behind condition C1 is that after the execution of any sequence that only includes transitions outside r(s) all the transitions of r(s) will still be executable. Thus we can execute them immediately and delay the execution of the others.

Partial-order reduction for safety properties A search algorithm that compute persistent sets may infinitely delay the execution of some transitions and miss states of interest. The following additional constraint, called proviso, can prevent this phenomenon, called action ignoring problem [START_REF] Valmari | A stubborn attack on state explosion[END_REF].

C2 S For any state s ∈ S r , a ∈ en(s) there is s ′ reachable from s in the reduced graph such that a ∈ r(s ′ ).

This condition ensures that any enabled action will be executed in a state reachable from s. If the reduction function satisfies this condition, it can be showed that the reduced graph is, what Godefroid called, a trace automaton. Trace automata have the nice property to preserve the reachability of local states: if a process can reach a given state in the initial graph, then it will also be able to reach this state in the reduced graph. Trace automata can therefore be used to verify a large range of safety properties that include, for example, assertions on local variables.

Partial-order reduction for liveness properties To preserve liveness properties we must ensure that any cycle of the graph does not contain an enabled transition that is never executed (in the states of the cycle). This leads to a strengthened version of the proviso, denoted C2 L .

C2 L A cycle is not allowed if it contains a state in which some action a is enabled, but never included in r(s) for any state s on the cycle.

This condition is usually replaced by the following one, implied by the C1 condition, that can be more easily implemented.

C2 L' Along each cycle of the reduced graph, there is some state s that is fully expanded.

Coupled with another condition (see [START_REF] Clarke | Model Checking[END_REF]) that preserves the interleavings of some interesting actions (the visible actions), the C2 L proviso can be used to compute ample sets [START_REF] Peled | All from one, one for all: on model checking using representatives[END_REF]. A selection function that computes such sets builds a reduced graph that is equivalent to the initial one with respect to LTL-X formulae.

The safety and liveness provisos are stated as properties of the reduced STG whereas we may want to perform the reduction on-the-fly. Therefore they are usually reformulated as conditions that can be efficiently checked during the construction of the reduced STG and, hence, are tightly linked to the way the search algorithm proceeds and the data structures it handles.

For depth first search (DFS), we can use the fact that every cycle contains a transition that reached the search stack at some point during the search. It is then sufficient to forbid to partially expanded states to reach the stack. This gives a first version of the liveness proviso, denoted C2 L s [START_REF] Peled | Combining partial order reductions with on-the-fly model-checking[END_REF]. This proviso is the one implemented by the Spin model checker [START_REF] Holzmann | The model checker SPIN[END_REF].

C2 L

s If r(s) = en(s) then no action in r(s) may reach a state of the stack.

For safety properties a weaker condition can be defined. We may indeed let a transition reach a state on the stack, provided that another transition leads to a state outside this stack [START_REF] Godefroid | Partial-Order Methods for the Verification of Concurrent Systems -An Approach to the State-Explosion Problem[END_REF].

For breadth first search (BFS), a similar version has been recently introduced in [START_REF] Bosnacki | Improving Spin's partial-order reduction for breadth-first search[END_REF].

C2 L

q If r(s) = en(s) then all the actions of r(s) reach a state of the queue.

The intuition behind this condition is that we do not have to worry about ignoring some actions of s since we delegate the problem to the successors of s which all belong to the queue and will be processed later. Once again, the weaker version of this proviso for safety proviso denoted C2 S q requires that at least one action leads to a state of the queue.

This idea has been generalized in [START_REF] Bosnacki | Partial-order reduction for general state exploring algorithms[END_REF] to general state exploring algorithms, that is, any explicit algorithm that partitions the state space into three mutually disjoint sets: the open states that have been met but not expanded yet, the closed states that have been met and expanded (and can potentialy be reopened), and the unmet states. This new proviso can, for example, be used in directed model checking [START_REF] Edelkamp | Directed explicit-state model checking in the validation of communication protocols[END_REF]. An open (or unmet) state is safe in the sense that it can be reached by a partially expanded state without risking to introduce some ignoring phenomenon: the resolution of this problem is delegated to this state that will be explored later. On the other hand, closed states are dangerous destinations since they have already been explored.

In [START_REF] Kurshan | Static partial order reduction[END_REF], a new technique is proposed which aim is to set up the entire reduction mechanism at compile time. The method is then independent from the search algorithm and can be used, for example, in symbolic model checking. Considering a concurrent system, which is a composition of sequential processes, the authors exploit the fact that a cycle in the state space results from some cycle(s) in the sequential processes of the model. The idea is to statically choose an action in each of these cycles and to mark it as sticky. The proviso can then be reduced to the following condition: a persistent set that does not include all the enabled actions may not contain a sticky action.

The two-phase algorithm presented in [START_REF] Nalumasu | An efficient partial order reduction algorithm with an alternative proviso implementation[END_REF] uses an alternative to the in-stack check to verify both safety and liveness properties. It alternates phases in which it fully expand states and phases of expansion of deterministic states, i.e., states in which singleton persistent sets can be computed. For some models the twophase algorithm can achieve significantly better results than a depth first search that uses the C2 L s proviso.

Motivations

Partial order methods can drastically reduce the verification requirements by eliminating redundant interleavings. In the best case the reduction factor is exponential. However, in many cases they are not as efficient as one would expect. This is mainly due to two factors. First of all, the computation of persistent sets relies on a static analysis of the model that sometimes produces coarse approximations. Dynamic partial order reduction, a proposition to cope with this problem, has been recently introduced by Flanagan and Godefroid [START_REF] Flanagan | Dynamic partial-order reduction for model checking software[END_REF].

Another source of inefficiencies can come from the resolution of the ignoring problem. Indeed we can identify models for which the use of the "historical" proviso based on an in-stack check yields poor results. We will illustrate this problem with the help of the Petri net depicted on figure 1(a). This net models a solution to the dining philosophers problem in which a philosopher takes two forks atomically. Some places have been duplicated for the sake of clarity. They are drawn as dashed circles. Places i 1 , i 2 , i 3 and i 4 model the idle state of the 4 philosophers while the eating state is modeled by e 1 , e 2 , e 3 and e 4 . Place f i models the state of the fork of philosopher i. To seat at the table (transition t i ), the philosopher i must take his fork f i and the fork of its neighbor, i.e., f j with j = i mod n + 1. Once is meal finished he goes back to the idle state and puts back his forks (transition r i ).

We have drawn on figure 1(b) the state space of this net built with the C2 L s proviso. Fully expanded states are double circled 1 and states are numbered according to the order they are visited by the algorithm. It appears that this combination does not reduce the number of states but can only save the execution of two transitions. Indeed, the in-stack check often succeeds and this leads to a full expansion of most states. However, it is clear that an optimal proviso (see figure 1(c)) would not introduce any state since all the cycles of the state space reduced with PS contains the initial state which is fully expanded.

With four philosophers this optimal proviso only saves two states but if we generalize the problem to n philosophers the reduction is much more impressive. Indeed, the full state space and the state space reduced with proviso C2 L s both have a size in O(2 n ) while the state space reduced with an optimal proviso has n + 1 states.

i 1 i 2 i 3 i 4 f 1 f 1 e 1 e 2 e 3 e 4 r 1 r 2 r 3 r 4 t 1 t 2 t 3 t 4 f 2 i 1 i 2 f 3 i 3 f 4 i 4 (a) A Petri net model of the dining philosophers 6 3 2 5 1 4 7 r 2 r 1 t 1 t 2 r 3 t 3 r 4 t 4 t 1 t 4 t 3 r 1 r 2 t 2 (b) PS + C2 L s 2 3 5 4
1 (c) PS + an optimal proviso Fig. 1. An example that illustrates our motivations.

Our intuition is that the ignoring problem is a phenomenon that seldom occurs in practice. By taking a too defensive approach traditional implementations of the cycle proviso such as those based an in-stack check can introduce much more states than necessary. Though our example is not representative as it corresponds to the worst case we can think of, it still illustrates the fact that the C2 L s proviso is not adapted for some classes of models.

The static proviso [START_REF] Kurshan | Static partial order reduction[END_REF] may overcome this problem if the sticky transitions are chosen appropriately, e.g., transitions t 1 , t 2 , t 3 and t 4 in our example, but since it is based on a static analysis of the model its performances may vary according to the input formalism of the model checker. For example, since there is no clear notion of process or loop in high-level Petri nets, the language of our model checker Helena [START_REF] Evangelista | High level petri nets analysis with Helena[END_REF], a detection of sticky transitions may produce a coarse approximation containing many useless transitions.

The two phase algorithm [START_REF] Nalumasu | An efficient partial order reduction algorithm with an alternative proviso implementation[END_REF] also achieves an optimal reduction on this example, but it is based on a principle -always selecting singletons -that can, for some models, be too much strong. For instance, it does not behave very well when processes can act indeterministically. Moreover, it prevents the use of some elaborated techniques that refine the dependency relation, e.g., [START_REF] Basten | Enhancing partial-order reduction via process clustering[END_REF].

Our objective is therefore to devise a proviso that (1) can be an interesting alternative when others fail to efficiently reduce the state space; (2) is not linked to a particular formalism and can be implemented by any model checker.

We propose in this section a new version of the safety proviso that is based on a depth-first search algorithm. This one also performs checks in the stack to avoid an infinite postponement of actions but it considerably relaxes the conditions under which a transition is acceptable.

Figure 2 gives the POR algorithm in a pseudo-code form. The principle of our proviso C2 S e is to associate to each state s of the stack an integer expanded that records the number of fully expanded states on the stack below s, i.e., between s 0 and s. The global variable expanded keeps track of this number.

k+1 k DFS Stack 0 s 0 s ′ s ′′ s a k
Then, when an action a leads from a state s to a state s ′ on the stack we compare the number of fully expanded states currently on the stack, i.e., the value of s.expanded, to the number associated to s ′ , i.e., s ′ .expanded. If the first one is strictly greater then this obviously means that there is a fully expanded state s ′′ on the stack between s ′ and s. Hence, s ′′ is reachable from s and the enabled actions of s will necessarily be executed at a state on the path from s to s ′′ . This can be illustrated with the help of the opposite figure. Enclosed in each state is the value of its expanded attribute. Proviso C2 S e is clearly better than C2 S s , in the sense that it will always compute smaller persistent sets (but not necessarily smaller graphs). Indeed it can be viewed as an optimization of C2 S s : by removing the expanded attribute and by changing the condition of function C2 S e we obtain the same proviso. The price to pay is a slight increase of the memory requirements. Our proviso requires an additional integer per state (typically 32 bits) for the expanded attribute. However, some savings can be done by removing the expanded attribute of the states that leave the stack. Indeed, once popped from the DFS stack this attribute is not used anymore by the algorithm. In addition, the space required to store this information is usually small compared to the size of states in a large system. Lastly, we will see in section 6 that this extra memory consumption should, in most cases, be largely compensated by the reduction achieved.

To show the correctness of our proviso we prove that the reduction function has a witness [START_REF] Alur | Partialorder reduction in symbolic state space exploration[END_REF]. This notion is defined below.

Definition 5 (Witness function). Let T = (S, s 0 , A, →) be an STG, r a reduction function of T and T r = (S r , s 0r , A r , → r ) be the reduction of T with respect to r. A mapping W : S r → N is a witness for r iff:

∀s ∈ S r , r(s) = en(s) ⇒ ∃(s, a, s ′ ) ∈→ r such that W (s ′ ) < W (s)
The intuition behind this idea of witness function is that for any state s of the reduced graph that is partially expanded we can find a successor s ′ of s with W (s ′ ) < W (s) and to which we delegate the execution of the actions ignored at s. By reitering this operation on s ′ we obtain a sequence W (s), W (s ′ ), . . . of decreasing numbers. As the state space is finite, we will necessarily find a state Fig. 2. A depth first search algorithm that implements our safety proviso s ′′ which is such that W (s ′′ ) ≥ W (s ′′′ ) for any of its successors s ′′′ . Obviously in such state, r(s ′′ ) = en(s ′′ ) and all the actions ignored in s that haven't been selected on the path from s to s ′′ belong to r(s ′′ ). It is therefore sufficient to prove that the reduced STG has a witness [START_REF] Alur | Partialorder reduction in symbolic state space exploration[END_REF]. Lemma 1. Proviso C2 S e implies the safety cycle proviso C2 S .

Proof. Let W : S r → N be a function that enumerates the states of the reduced STG (S r , s 0r , A r , → r ) in the order they are removed from the stack : s 0 is mapped to |S r | -1 while the first state to be popped is mapped to 0. Let F W be the states of S r that violate the witness conditions, i.e., defined by

F W = {s ∈ S r | r(s) = en(s) ∧ ∀(s, a, s ′ ) ∈→ r , W (s ′ ) ≥ W (
s)} Let us observe the algorithm when it processes a state s ∈ F W . It holds for all the successors s ′ ∈ S r of s that s ′ ∈ H ∧s ′ .inStack. Otherwise s ′ leaves the stack before s and W (s ′ ) < W (s) (⇒ s / ∈ F W ). In addition there must be a state s ′ such that s a → r s ′ for some a ∈ r(s) and s ′ .expanded < s.expanded. Otherwise,

r(s) = en(s) (⇒ s / ∈ F W ). Hence, there is a path s 1 → r s 2 → r . . . → r s n such that s ′ = s 1 , s 1 .inStack ∧ • • • ∧ s n .inStack and r(s n ) = en(s n ). We can define a new function W ′ such that 1 -W ′ (s 1 ) < W (s) and W ′ (s 1 ) < W (s 1 ) 2 -∀s i ∈ {s 2 , . . . , s n }, W ′ (s i ) < W ′ (s i-1 ) and W ′ (s i ) < W (s i ) 3 -∀s / ∈ {s 1 , . . . , s n }, W ′ (s) = W (s) Let us compare F W ′ and F W . Point 1 implies that s / ∈ F W ′ .
In addition, it trivially follows from the three points that F W ′ \F W = ∅, i.e., W ′ does not introduce a new "violating state". Thus we have

|F W ′ | < |F W |.
By reitering the same operation on W ′ until F W = ∅ we obtain a witness W . ⊓ ⊔

The different steps of the construction of the witness function are illustrated with the help of the opposite figure. States are numbered according to function W . At each step, the gray state corresponds to the state s of the proof that violates the witness function conditions. FW FW

A proviso for liveness properties

The conditions that ensure a sound reduction are stronger when one wants to analyze liveness properties, e.g., LTL-X formulae. The reduction must indeed ensure that for any cycle, an action enabled at one of its states will be executed at some state of the cycle. We have seen that a sufficient way to proceed is to fully expand a state on each cycle of the graph. We would like to adapt the idea of the C2 S e proviso, presented in the previous section, to the verification of liveness property. Unfortunately, a direct adaptation does not guarantee the desired behavior. We illustrate this problem with the simple graph depicted below.

s 1 s 2 s 0 s
Let us assume that the algorithm first processes state s 0 , then pushes s 1 that is fully expanded and finally reaches s 2 . Since s 1 is on the stack between s 0 and s 2 the persistent set which consists of the single action that leads from s 2 to s 0 is valid. Now let us suppose that later the algorithm backtracks to s 0 and executes a sequence s 0 → . . . → s such that none of the states of this sequence is fully expanded. According to the C2 S e proviso, the singleton {s → s 2 } is a valid set. Hence, we close a cycle that does not contain any fully expanded state and in which an action may be ignored: s 0 → . . . → s → s 2 → s 0 .

In order to prevent such situations we will have to perform some additional checks possibly leading to less reductions. We will in particular forbid that state s reaches state s 2 without being fully expanded.

The pseudo-code of our algorithm is given in figure 3. In addition to the expanded attribute of proviso C2 S e the new proviso C2 L c , the color proviso, associates some extra information to each state. A state will thus be marked as green, red or orange. This color gives us crucial informations when we want to determine whether an action is allowed or not (see function C2 L c ). green states are safe states. These ones may be reached by any other state without risking of closing an invalid cycle. Intuitively, if a state is green then either it is fully expanded either all its successors are green. red states are dangerous states. A state may not reach a red state without being fully expanded. This could indeed close a "bad" cycle as in our example. Red states do not belong to the stack anymore.

orange states are potentially dangerous states. An orange state is a state of the stack that can be reached by a partially expanded state under the condition of the C2 S e proviso: a fully expanded state appears between the two in the DFS stack.

Colors are then attributed as follows.

When a new state is generated and pushed onto the stack we mark it as green if it is fully expanded or orange otherwise. The orange color is attributed in function push state before the computation of the persistent set P to resolve the case where P contains a self-loop transition. Orange states are therefore all the partially expanded states which are in the stack.

An orange state leaving the stack is colored in green if all its successors are green or red otherwise. Hence, while red and green are final states, i.e., the color of a green or red state can not change, orange is a transitory color: once the search terminated, the stack is empty and all states are marked as red or green.

The purpose of lines 13-18 of procedure dfs is to deal with the situation where the state s is partially expanded and reaches a red state s ′ that was not in H when the persistent set of s was computed. We must then fully expand s, assign it the green color and restart its expansion. In practice we found out that this situation is very unusual.

Let us go back to our previous example and see how our algorithm will proceed on this one. As state s 2 is popped from the stack we color it in red since its only successor, state s 0 , is orange, i.e., partially expanded and on the stack. We then backtrack to state s 0 and reach later s. Since s 2 is a red state the action leading from s to s 2 is not allowed if s is not fully expanded. Consequently, we will have to select another set or to fully expand s.

In order to prove the correctness of our proviso we proceed in two steps. We first show that the reduced STG cannot contain a cycle of red states. Proposition 1. Let T = (S, s 0 , A, →) be an STG and T r = (S r , s 0r , A r , → r ) be its reduction obtained using the algorithm of figure 3. Then, there is no cycle of red states in T r , i.e., ∀s 1 , . . . ,

s n ∈ S r , s 1 → r s 2 → r . . . → r s n → r s 1 ⇒ ∃i ∈ {1..n} | s i .color = green
Proof. Let us suppose that there is a cycle

s 1 → r s 2 → r . . . → r s n → r s 1 with s i .color = red, ∀i ∈ [1.
.n] and such that s 1 is the first state visited by the algorithm, i.e., pushed onto the stack.

Necessarily during the search we reached a configuration in which We again consider two different cases. s j ∈ H when r(s i ) is computed Necessarily, s j .color = red when r(s i ) is computed. Otherwise, s j is on top of s i in the stack and s j .color = orange when we reach s j from s i . It trivially follows from the condition of the if statement at line 3 of C2 L c that s j ∈ H ∧ s j .color = red ⇒ r(s i ) = en(s i ), and hence s i .color = green after the assignment at line 8 of dfs. s j / ∈ H when r(s i ) is computed Then, when s j is reached at line 11 of dfs it holds, by assumption, that s j ∈ H, s j .color = red and s i .color = orange. So, s i is colored in green at line 16. s j .color = orange (⇒ s j is on the stack) State s j was pushed on the stack before s i . Thus we had s j .color = orange when r(s i ) was computed. From function C2 L c , if s j ∈ H ∧ s j .color = orange then s j .expanded < s i .expanded. Otherwise, we would have r(s i ) = en(s i ) and s i would be colored in green at line 8 of dfs. Since s j .expanded < s i .expanded then there exists s k with j < k < i such that r(s k ) = en(s k ). Consequently, s k .color = green from the line 8 of dfs.

So in both cases there is a green state in the cycle.

⊓ ⊔

Secondly, we prove that if a cycle of the reduced STG contains a green state then it contains a fully expanded state. Proposition 2. Let T = (S, s 0 , A, →) be an STG and T r = (S r , s 0r , A r , → r ) be its reduction obtained using the algorithm of figure 3. In any cycle s 1 → r s 2 → r . . . → r s n → r s 1 , if there is s i such that s i .color = green then there is s j such that r(s j ) = en(s j ).

Proof. We consider in this proof a cycle s 1 → r s 2 → r . . . → r s n → r s 1 such that s i .color = green for some i ∈ {1..n}. Let us first suppose that there is a red state in the cycle. If there exists s i with s i .color = red then, necessarily, there are s j and s k such that s j .color = green, s k .color = red and s j → r s k (otherwise, the cycle would only contain red states). Since it trivially holds that a green state with a red successor is fully expanded our claim is proved for this first case. Now let us suppose that ∀i ∈ {1..n}, s i .color = green. Necessarily, during the search a state s i reached a state s j on the stack. Since s j .inStack = true then s j .color ∈ {orange, green}. Let us look at these two possibilities. s j .color = green -It holds for any green state s of the stack that r(s) = en(s). s j .color = orange -When s i leaves the stack (before s j ) it becomes red as it has a non green successor. This goes against our initial assumption that all the states of the cycle are green.

So in both cases there is a fully expanded state in the cycle.

⊓ ⊔

It is then straightforward to prove the correctness of our liveness proviso.

Lemma 2. Proviso C2 L c implies the liveness cycle proviso C2 L .

Proof. This lemma is a direct consequence of propositions 1 and 2.

Anticipation of the backtrack phase

The red color appears in the graph when some partially expanded state s reaches an orange state. Indeed, once s is popped from the stack it becomes red and this color will be propagated to its predecessors in the stack. This way to proceed is very careful since we assume that the orange states reached by s will be later colored in red. However, there are situations in which we can directly color orange states in green by anticipating the backtrack phase. We will illustrate the principle of this optimization with the help of figure 4. The letters correspond to the colors of states. Without optimization when state s is processed it reaches the orange state s' and thus becomes red when popped. However, since all the outgoing arcs of s' have been visited and its only successor is green, we know that it will become green when leaving the stack. We can therefore immediately color s' in green. As a direct consequence, state s only reaches green states and can be marked as green.

No optimization

With anticipation

G R G O O G s' s' s' s s s G G

Fig. 4. Illustration of the optimization

The implementation of this optimization requires one extra boolean variable per state of the stack which specifies if all the outgoing arcs of the state have been visited. We also introduce an additional color: purple. States colored in purple are states of the stack that will be marked as red when popped. The only purpose of this new color is to ease the implementation of this optimization: purple states are treated as orange states when checking the proviso.

With the optimized proviso, denoted C2 L c⋆ , the algorithm proceeds as follows. When it assigns the green color to the current state or when it executes an action that leads to a green state, the stack is scanned from top to bottom until it meets a green or purple state or an orange state of which some outgoing arcs have not been visited. The green color is assigned to all the states scanned.

Alternatively, when an action leads to a purple or an orange state, the algorithm scans the stack until it meets a green or purple state and colors all the states scanned in purple.

We believe that this optimization has a strong potential insofar as the persistency condition C1 often leads to compute singletons, e.g., with a single transition that only operates on local variables, or to fully expand states. In such situations our optimization is very useful since it allows to assign the green color to most of the states of the stack: as soon as a fully expanded state is met, the green color propagates from top to bottom to all the states of the stack.

If it is clear that our safety proviso outperforms the in-stack check based one, we cannot draw such a conclusion for the color proviso. Proviso C2 L s and C2 L c are both based on the notion of dangerous and safe states. With the C2 L s proviso, dangerous states are all the states of the stack (or more generally, all the closed states [START_REF] Bosnacki | Partial-order reduction for general state exploring algorithms[END_REF]) while, on the contrary, with the color proviso, dangerous states do not belong to the stack anymore. It is therefore crucial to experiment these provisos in order to determine which one achieves the best reduction in practice.

Experiments

We implemented the algorithms proposed in our model checker Helena [START_REF] Evangelista | High level petri nets analysis with Helena[END_REF]. The tool takes as input a high-level Petri net and can verify reachability properties or the presence of dead states. In order to assess the quality of our provisos we also implemented the in-stack and in-queue check based provisos for DFS and BFS which are part of the Spin model checker.

We considered several families of models. Some are simple "toy" examples. Others are communication protocols or mutual exclusion algorithms of which some can be found on the BEEM web portal [START_REF] Pelánek | BEEM: Benchmarks for explicit model checkers[END_REF]. We also translated some concurrent Ada software to high-level nets with the help of the Quasar tool (http://quasar.cnam.fr). Some of these models can be found in Helena distribution (http://helena.cnam.fr).

We observed, as it was the case in [START_REF] Bosnacki | Improving Spin's partial-order reduction for breadth-first search[END_REF], that BFS based provisos tend to be less efficient that those based on a DFS. Indeed, on the ten models considered we only found one model (the slotted ring protocol) for which they achieved a better reduction. In addition the difference was pretty insignificant. On other models there were sometimes huge differences. Therefore, we decided not to report the results obtained with BFS based provisos to focus on a comparison between the in-stack check based provisos and our algorithms.

The result of the experimentations are reported in table 1. We performed several searches: without partial order reduction at all (column No POR); without action ignoring resolution (column PS); with a safety cycle proviso (columns C2 S s and C2 S e ); with a liveness proviso (columns C2 L s , C2 L c and C2 L c⋆ ). The numbers reported in columns No POR and PS must therefore be seen as upper and lower bounds when comparing the different provisos.

For each run we report the number of states of the reduced graph and the amount of memory consumed to store the state space. In some cases, we ran out of memory and could not complete the search. This is indicated by a "oom".

For safety properties, a comparison of columns PS and C2 S e shows that our proviso performs an excellent reduction. On eight models it did not introduce states that were not visited by an algorithm without action ignoring prevention. For Lamport's algorithm, it caused the exploration of a few thousands states which is quite low with respect to the size of the state space of this model. It also doubled the graph size of the resource allocation system. In this model, a process may potentially diverge and perform an infinite sequence that does not include any synchronization. So there actually is some risk of ignoring problem and it is thus obvious that any proviso will necessarily cause the visit of additional states. Nevertheless C2 S e behaves much better than C2 S s and on this model. These results confirm our initial expectations: a DFS seldom closes a cycle that does not contain any fully expanded state. In any concurrent system, there are usually some points of synchronization, e.g., an access to a global variable, the acquisition of a lock. When the processes reach these points it is likely that the algorithm fully expand the state. It seems to us that a weak point of the C2 S s proviso is that it does not exploit such information on the past of the search that the stack can provide us. Our proviso should therefore be nearly optimal in the sense that it will only disallow the algorithm to close a cycle when this one does not actually contain a fully expanded state.

We also observe that C2 S s and C2 L s sometimes brutally increase the graph size. This confirm our initial intuition that these provisos are not adapted to some systems. We can find several models for which these provisos cause the algorithm to visit much more states than really needed. For some examples, e.g., the slotted ring protocol, the resource allocation system, a look at column No POR shows that they even almost cancel the reduction. By comparing columns PS and C2 L c⋆ we can evaluate our proviso in term of number of states it introduces. The results are rather convincing. On seven models out of ten the reductions achieved are very close. For the peer-to-peer protocol and the resource allocation system, the introduction of this additional condition involves an important increase of the graph size. As we mentioned it earlier this fact is not very surprising for the resource allocation system. For the peer-to-peer protocol we will see that our proviso is not adapted to its graph structure.

On the whole, C2 L c⋆ seems to achieve better reductions than C2 L s . For some models the difference is quite impressive. We can cite the load balancing system or to a lesser extent the production cell. There also are some examples, e.g., Lamport's mutual exclusion algorithm, for which the difference is slighter. We only found two models out of ten for which C2 L s behaves better: the client-server program and the peer-to-peer communication protocol. For the first one the difference is hardly perceptible. A closer look at the graph structure of the peer-topeer protocol explains the bad results obtained by C2 L c⋆ with respect to the C2 L s ... ...

C2 L c⋆ C2 L s s s ′ s s ′
s ′′ s 1 s ′′ s 1 s n s n proviso. We found out that the situation depicted by the opposite figure often occurred. With the C2 L c⋆ proviso, when s is processed it may be partially expanded since the fully expanded s ′′ is between s and s ′ in the stack. Later, when states s 1 , . . . , s n are reached, the algorithm expands them fully since s has become red. On the other hand, with the C2 L s proviso state s may not reach s ′ without being fully expanded. States s 1 , . . . , s n can then be partially expanded since they lead to s that has left the stack. This can explain why, on this example, C2 L c⋆ fully expands much more states than C2 L s .

Let us conclude this section with some observations about memory usage. We notice that despite the additional memory it requires per state, C2 L c⋆ generally outperforms C2 L s . There is only one model -Lamport's algorithm -for which C2 L c⋆ achieves a better reduction than C2 L s but consumes more memory. Even in this case, the difference is insignificant. Moreover, as we already pointed it out, memory usage could be optimized by suppressing the expanded attribute of the states that leave the stack.

Conclusion

The contribution of this paper is the two new versions of the cycle proviso that resolves the ignoring phenomenon that may arise when applying partial order reduction. The algorithms introduced are simple, easy to implement and can be integrated in any explicit state model checker since they do not rely on any specification language. As a counterpart they assume a DFS exploration of the state space and require the storage of some additional informations. Nevertheless, we have seen that this extra memory consumption is usually compensated by the reduction achieved. A set of experiments revealed that our proviso outperforms state of the art algorithms, like those implemented by the Spin model checker, on many models.

We still plan to perform a more thorough experimentation in order to identify graph structures or classes of models for which our proviso outperforms the others or, on the contrary, is not adapted.

It should also be instructive to compare it with the two-phase algorithm [14] that also seems to outperform the standard proviso on many models -mainly those in which process act in a deterministic way.

At last we have the intuition that the color proviso could be optimized further by weakening the acceptance conditions of a persistent set. When the execution of an action a leads from an orange state o to a red state r the basic question we have to answer is the following one: is there a path leading from r to o or, otherwise stated, is there a path leading from r to a state of the stack? If not, then no cycle of partially expanded states may include the transition o a → r, and a may be executed without risking of closing an invalid cycle. Such a question can be answered by performing Tarjan's algorithm to detect strongly connected components or one of its variations for LTL model checking [START_REF] Couvreur | On-the-fly verification of linear temporal logic[END_REF][START_REF] Geldenhuys | Tarjan's algorithm makes on-the-fly LTL verification more efficient[END_REF]. However, a comparison of columns PS and C2 L c⋆ of table 1 shows that it is not obvious if this further reduction will compensate the extra memory consumed by Tarjan's algorithm (an additional stack plus at least one integer per state). On several models proviso C2 L c⋆ introduces a very little number of states and it is likely that this will not be the case for these.

Fig. 3 .

 3 Fig.3. A depth first search algorithm that implements our liveness proviso

  1. States s 1 , . . . , s i are on top of the stack. 2. s 1 .color = • • • = s i .color = orange. 3. There is a ∈ r(s i ) such that s i

	dfs (s)	push state (s)
	1 H ← H ∪ {s}	1 s.inStack ← true
	2 push state(s)	2 s.color ← orange
	3 let P be a persistent set that	3 s.expanded ← expanded
	4 5 6 if P = en(s) then satisfies C2 L c (s, P ) or en(s) if there is no such set 7 expanded ← expanded + 1 8 s.color ← green 9 search_loop: 10 for a ∈ P do 11 let s a → s ′ 12 if s ′ / ∈ H then dfs(s ′ ) 13 elsif s.color = orange 14 and s ′ .color = red 15 then 16 s.color ← green 17 P ← en(s) 18 goto search_loop 19 if P = en(s) then 20 expanded ← expanded -1 21 pop state(s) search () 1 H ← ∅ ; ; expanded ← 0 ; ; dfs(s0)	pop state (s) 1 s.inStack ← f alse 2 if s.color = orange then 3 if ∀a ∈ r(s), s a → s ′ , 4 s ′ .color = green 5 then 6 s.color ← green 7 else 8 s.color ← red C2 L c (s, P ) 1 for a ∈ P do 2 let s a → s ′ 3 if 4 s ′ ∈ H and 5 (s 8 then 9 return f alse 10 return true

a → s j and s j ∈ H.

From now on, we observe this configuration. By assumption, s j .color = green, hence, s j .color ∈ {orange, red}. Let us look at these two possibilities. ′ .color = red or 6 (s ′ .color = orange and 7 s ′ .expanded = s.expanded))

Table 1 .

 1 Comparison of the different provisos implemented in Helena.

	No POR	PS	PS + Safety proviso	PS + Liveness proviso
			C2 S s	C2 S e	C2 L s	C2 L c	C2 L c⋆
			Simple models
		Load-balancing system (7 clients, 3 servers)
	1 574 530	72 093	631 056	72 093	630 997	211 012	72 194
	26.4 MB	1.2 MB	10.7 MB	1.5 MB	10.7 MB	4 MB	1.3 MB
		A peer-to-peer communication protocol (8 processes)
	743 580	163	72 852	163	72 852	884 830	252 315
	12.1 MB	0.1 MB	1.2 MB	0.1 MB	1.2 MB	15.6 MB	5.2 MB
		Resource allocation system (4 processes)
	2 550 759	72 637 1 449 206	151 531 1 783 881	754 878	607 004
	49.9 MB	1.5 MB	28.7 MB	3.6 MB	35.2 MB	23.2 MB	15.6 MB
		Protocols and mutual exclusion algorithms
		Lamport's mutual exclusion algorithm (4 processes)
	1 914 784 1 052 518 1 282 950 1 055 985 1 455 606 1 304 311 1 304 310
	41.02 MB	22.5 MB	27.4 MB	26.7 MB	31.3 MB	31.6 MB	31.6 MB
		Peterson's mutual exclusion algorithm (4 processes)
	3 407 946	259 942	356 068	259 942	356 698	292 622	260 608
	49.3 MB	3.7 MB	5.1 MB	4.7 MB	5.1 MB	4.8 MB	4.3 MB
			Production cell (8 plates)
	oom	396 931 1 024 422 18.2 MB 46.3 MB	396 931 1 138 954 19.1 MB 51.4 MB	495 543 24.2 MB	451 355 21.9 MB
			Slotted ring protocol (7 processes)
	439 296	287 508	413 321	287 508	437 579	401 803	304 417
	6.1 MB	4 MB	5.8 MB	5.1 MB	6.1 MB	6.5 MB	4.9 MB
			Models extracted from programs
			The chameneos (4 tasks)
	oom	415 361 4.7 MB	899 295 10.4 MB	415 361 6.4 MB	899 295 10.4 MB	733 654 10.2 MB	494 123 6.9 MB
			The dining philosophers (6 tasks)
	10 888 070	109 222	174 354	109 222	174 354	115 333	110 190
	136 MB	1.3 MB	2.1 MB	1.7 MB	2.1 MB	1.7 MB	1.6 MB
		A client-server program (4 clients, 2 servers)
	oom	87 129 1.4 MB	99 430 1.6 MB	87 129 1.7 MB	99 430 1.6 MB	159 202 2.8 MB	108 659 1.9 MB

Acknowledgements. The authors thank Jean-François Pradat-Peyre for his comments on early drafts of this paper.


Émilie Bouyer

Éphane St

Damien Caro
email: damien.chablat@irccyn.ec-nantes.fr

Chablat

Jorge Angeles
email: angeles@cim.mcgill.ca

DETC2007/XXX THE MULTIOBJECTIVE OPTIMIZATION OF A PRISMATIC DRIVE

The multiobjective optimization of Slide-o-Cam is reported in this paper. Slide-o-Cam is a cam mechanism with multiple rollers mounted on a common translating follower. This transmission provides pure-rolling motion, thereby reducing the friction of rack-and-pinions and linear drives. A Pareto frontier is obtained by means of multiobjective optimization. This optimization is based on three objective functions: (i) the pressure angle, which is a suitable performance index for the transmission because it determines the amount of force transmitted to the load vs. that transmitted to the machine frame; (ii) the Hertz pressure used to evaluate the stresses produced on the contact surface between cam and roller; and (iii) the size of the mechanism, characterized by the number of cams and their width.

NOMENCLATURE p: pitch of the transmission;

e: distance between the axis of the cam and the line of centers of the rollers; r: radius of the roller; d cs : diameter of the camshaft (d cs = 2(er)); L: the width of the contact between the cams and the rollers; ψ: input of the mechanism, i.e., the angle of rotation of the cam; s: output of the mechanism, i.e., the displacement of the follower; µ: pressure angle; f: force transmitted from the cam to the roller; κ c and κ p : curvature of the cam profile and the pitch curve, respectively; ρ c and ρ p : radii of curvature of the cam profile and the pitch curve, respectively; m: number of cams mounted on the camshaft; n: number of lobes per cam; P: Hertz pressure; S M : size of the mechanism.

INTRODUCTION

In robotic and mechatronic applications, whereby motion is controlled using a piece of software, the conversion from rotational to translational motion is usually realized by means of ball-screws or linear actuators. While both are gaining popularity, they present some drawbacks. On the one hand, ball-screws comprise a high number of moving parts, their performance depending on the number of balls rolling in the shaft groove. Moreover, they have a low load-carrying capacity due to the punctual contact between balls and groove. On the other hand, linear bearings are composed of roller-bearings to figure out the previous issue, but these devices rely on a form of direct-drive motor, which makes them expensive to produce and maintain.

A novel transmission, called Slide-o-Cam, is depicted in Fig. 1 as introduced in [1] to transform a rotational motion into a translational one. Slide-o-Cam is composed of four main elements: (i) the frame; (ii) the cam; (iii) the follower; and (iv) the rollers. The input axis on which the cams are mounted, named camshaft, is driven at a constant angular velocity by means of an actuator under computer-control. Power is transmitted to the output, the translating follower, which is the roller-carrying slider, by means of pure-rolling contact between the cams and the rollers. The roller comprises two components, the pin and the bearing. The bearing is mounted to one end of the pin, while the other end is press-fit into the roller-carrying slider. Consequently, the contact between the cams and rollers occurs at the outer surface of the bearing. The mechanism uses two conjugate cam-follower pairs, which alternately take over the motion transmission to ensure a positive action; the rollers are thus driven by the cams throughout a complete cycle. Therefore, the main advantages of cam-follower mechanisms with respect to the other transmissions, which transform rotation into translation are: (i) lower friction; (ii) higher stiffness; (iii) low backlash; and (iv) reduction of wear. The multiobjective optimization of Roller Follower Conjugate cams Slide-o-Cam is reported in this paper. This optimization is based on three criteria: (i) the pressure angle, a suitable performance index for the transmission because it determines the amount of force transmitted to the load vs. that transmitted to the machine frame; (ii) the Hertz pressure, a measure of the stresses produced in the contact surface between the cams and the rollers; and (iii) the size of the mechanism, characterized by the number of cams and their width.

SYNTHESIS OF PLANAR CAM MECHANISMS

Let the x-y frame be fixed to the machine frame and the u-v frame be attached to the cam, as depicted in Fig. 2. O 1 is the origin of both frames, O 2 is the center of the roller, and C is the contact point between cam and roller. The geometric parameters are illustrated in the same figure. The notation used in this figure is based on the general notation introduced in [2-4], namely, (i) the pitch p, i.e., the distance between the center of two rollers on the same side of the follower; (ii) the distance e between the axis of the cam and the line of centers of the rollers; (iii) the radius r of The above parameters as well as the surface of contact on the cam are determined by the geometric relations derived from the Aronhold-Kennedy Theorem [2]. As a matter of fact, when the cam makes a complete turn, i.e., ∆ψ = 2π, the displacement of the roller is equal to the pitch, i.e., ∆s = p. Furthermore, if we consider that Fig. 3 illustrates the home configuration of the roller, the latter is below the x-axis when ψ = 0. Therefore, s(0) = -p/2 and the input-output function s is defined as:

s(ψ) = p 2π ψ - p 2 (1)
The cam profile is determined by the displacement of the contact point C around the cam. The Cartesian coordinates of C in the u-v frame take the form [5]

u c (ψ) = b 1 cosψ + (b 2 -r) cos(δ -ψ) (2a) v c (ψ) = -b 1 sin ψ + (b 2 -r) sin(δ -ψ) (2b)
The expressions of coefficients b 2 , b 3 and δ, as obtained in [6-10], are:

b 1 = p 2π (3a) b 2 = p 2π (2πη -1) 2 + (ψ -π) 2 (3b) δ = arctan ψ -π 2πη -1 (3c)
where η = e/p, a nondimensional design parameter. From Eq.(3c), we can notice that η cannot be equal to 1/(2π). Moreover, an extended angle ∆ was introduced in [6] As far as Slide-o-Cam is concerned, ∆ is negative, as shown in Fig. 4. Consequently, to close the cam profile, ψ must vary within ∆ ≤ ψ ≤ 2π -∆.

O 1 x y u v C ψ (a) O 1 x y C ψ -u -v (b) O 1 x y C ψ u v (c)

Pitch-Curve Determination

The pitch curve is the trajectory of O 2 , the center of the roller, distinct from the trajectory of the contact point C, which produces the cam profile. The Cartesian coordinates (e, s) of point O 2 in the x-y frame are depicted in Fig. 2. Hence, the Cartesian coordinates of the pitch-curve in the u-v frame are

u p (ψ) = e cos ψ + s(ψ) sin ψ (4a) v p (ψ) = -e sin ψ + s(ψ) cos ψ (4b)

Curvature of the Cam Profile

The curvature κ p of the pitch curve is given in [10] as

κ p = 2π p [(ψ -π) 2 + 2(2πη -1)(πη -1)] [(ψ -π) 2 + (2πη -1) 2 ] 3/2 (5)
provided that the denominator does not vanish at any value of ψ within ∆ ≤ ψ ≤ 2π -∆, i.e., η = 1/(2π). Let ρ c and ρ p be the radii of curvature of the cam profile and the pitch curve, respectively, and κ c the curvature of the cam profile. Since the curvature is the reciprocal of the radius of curvature, we have ρ c = 1/κ c and ρ p = 1/κ p . Furthermore, due to the definition of the pitch curve, it is apparent that

ρ p = ρ c + r (6)
From Eq. ( 6), the curvature of the cam profile can be written as

κ c = κ p 1 -rκ p (7)
In [9], the authors claimed that the cam profile has to be fully convex for machining accuracy. Such a profile can be obtained if and only if η > 1/π. In order to increase the range of design parameters, we include non-convex cams within the scope of this paper. Nevertheless, the sign of the local radius ρ c has to remain positive as long as the cam pushes the roller. In this vein, the cam is convex when

η ∈]1/(2π), 1/π] and ψ ∈]∆, π] [11].
ψ = ψ min = π - √ 4 n 2 π h -n 2 -4 n 2 π 2 h 2 n ( 8
)
where n is the number of lobes per cam. Therefore, the cam profile is not feasible when ρ c (ψ min ) < 0. If this inequality becomes an equality, the roller will block the cam, as depicted in Fig. 5.

MULTIOBJECTIVE OPTIMIZATION PROBLEM

We introduce in this section the multiobjective optimization of Slide-o-Cam. Indeed, such an optimization is needed to prop-erly dimension the mechanism. First, the objective functions are defined. Then, a sensitivity analysis of the mechanism is reported in order to choose shrewdly the design variables of the optimization problem. Finally, the results of the latter are illustrated by means of a Pareto frontier as the objective functions are antagonistic.

The Objective Functions

The optimization of the mechanism is based on three objective functions: (i) the maximum pressure angle µ max ; (ii) the maximum Hertz pressure P max related to the contact between the cams and the rollers; and (iii) the size of the mechanism S M . As a matter of fact, we want to simultaneously minimize these three functions.

The Pressure Angle

The pressure angle µ of a cam-roller-follower mechanism is defined as the angle between the normal to the contact point C between the cam and the roller and the velocity of C as a point of the follower [3]. As illustrated in Fig. 2, µ is a significant parameter in cam design. In fact, the smaller µ1 , the better the transmission. The expression for µ is given in [3]; in terms of η, we have illustrates the active parts of a two-and a threeconjugate-cam mechanisms. It turns out that the pressure angle is a maximum at the ends of the active parts for the two mechanisms. In this paper, µ max denotes the maximum pressure angle along the active part of the cam profile; it is an objective function in this optimization problem.

tan µ = n -2nπη nψ -π (9)

The Hertz Pressure

When two bodies with curved surfaces, for example, a cam and a roller, are pressed together, contact takes place not along a line but along a surface, due to the inherent material compliance. Moreover, the stresses developed in the two bodies are three-dimensional. Those contact stresses may generate failures as cracks, pits, or flaking in the surface material. To quantify these stresses, Heinrich Rudolf Hertz (1857-1894) proposed some formulas to evaluate the width of the band of contact between two cylinders and the maximum pressure of contact, called Hertz pressure. In Slide-o-Cam, the rollers and the cams are the bodies in contact. Unlike the roller, the cam is not a cylinder, but can be approximated by a cylinder with radius identical to the radius of curvature of the cam at the contact point. The width B of the band of contact is illustrated in Fig. 7, and given by Hertz as

B = 16F(K 1 + K 2 )R equ L (10a) R equ = r ρ c r + ρ c (10b)
F being the magnitude of the axial load f while R equ is the equivalent radius of contact, L the width of the contact between the cams and the rollers, and K 1 and K 2 the coefficients that characterize the materials of the cams and the rollers, respectively, i.e.,

K 1 = 1 -ν 2 1 πE 1 , K 2 = 1 -ν 2 2 πE 2 (11)
where ν 1 and ν 2 are the Poisson ratios of the materials of the cam and the roller, respectively, while E 1 , E 2 their corresponding Young moduli. Accordingly, the Hertz pressure P of the contact between the cams and the rollers takes the form:

P = 4F LπB (12)
Let us notice that P depends on ψ, as F is a function of this variable and B is a function of F.

Let us assume that F is constant. As L and r are constant and R equ is monotonic with respect to (w.r.t) ρ c as long as ρ c > -r, from Eq.( 10a), the lower ρ c , the lower B. From Eq.( 12), the lower B, the higher P. According to [11], ρ c is a minimum when ψ = π/n -∆ for a two-conjugate cam mechanism. Therefore, P is a maximum when ψ = π/n -∆ for such a mechanism.

Figure 6 illustrates the active parts of a two-and a threeconjugate-cam mechanisms. It turns out that the Hertz pressure is a maximum at the ends of the active parts for the two mechanisms as ρ c is a minimum at those ends. In this paper, P max denotes the maximum Hertz pressure along the active part of the cam profile; it is an objective function in this optimization problem.

The maximum Hertz pressures allowed for some materials are obtained from [12] and recorded in Table 1. The second column gives the allowable pressure P stat for a static load. As a matter of fact, it is recommended not to apply more than 40% of P stat in order to secure an infinite fatigue life. The corresponding values P max are given in the third column of Table 1. Obviously, the maximum allowable pressure depends also on the shape of the different parts in contact. A thick part will be stiffer than a thin one. Nevertheless, we only take into account the material of the cams and rollers for the determination of the allowable pressures within the scope of this research work. Finally, let us notice that only improved steel is appropriate for a Slide-o-Cam transmission in case of high Hertz-pressure values.

Size

The size of the mechanisms S M is defined as

S M = m L (13)
where m is the number of cams. From [9], a Slide-o-Cam with only one cam, i.e., m = 1, is not feasible. Besides, the smaller S M , the less bulky the mechanism.

The Design Variables

The design variables of the optimization problem are: (i) the diameter d cs of the camshaft (d cs = er); (ii) the radius r of the rollers; (iii) the width L of the contact between cam and roller; and (iv) the number of cams m.

Sensitivity Analysis

We conduct here the analysis of the sensitivity of the performance of Slide-o-Cam to the variations in its design parameters. Such an analysis is needed to both determine the tolerance of the design variables and obtain a robust design. illustrates the pressure-angle distribution for two conjugate-and three conjugate-cams with one lobe. We can notice that the pressure angle decreases with the number of cams. Consequently, we can use conjugate cams, namely, several cams mounted on the camshaft, to reduce the pressure angle. Below is a list of the effects of some design parameters on the pressure angle:

1. The lower η, the lower the pressure angle, with η ≥ 1/π; 2. the lower r, the lower the pressure angle; 3. the lower n, the lower the pressure angle, [9]; 4. the higher m, the lower the pressure angle.

where m is the number of cam(s) mounted on the camshaft.

As the pressure angle increases with the number of lobes, we consider only mono-lobe cams, i.e. n = 1.

Sensitivity of the Hertz

Pressure P max depends on the geometry of the cam, the number of conjugate cams, the material of the parts in contact and the load applied. Therefore, we have different ways to minimize the Hertz pressure, namely, 1. The higher m, the lower P max ; 2. the lower the axial load, the lower P max ; 3. the more compliant the material, the lower P max ; 4. the higher L, the lower P max .

In order to analyze the sensitivity of P to r, η, p and L, we use a first derivative model of P w.r.t. the corresponding parameters, i.e., -300

ψ = π/n -∆ ψ = 2π/n -∆ Figure 9
. Influence of the variations in r, η, p and L on P be compared. In this vein, we divide each of them by its nominal value. Now, we can plot each partial derivative with respect to the angle of rotation of the cam ψ, as illustrated in Fig. 9. The most influential variables are those with the highest absolute value of their corresponding partial derivative for a given value of ψ. As the maximum value of the Hertz pressure is obtained for ψ = π/n -∆ and ∆ = -1.2943 rad, the partial derivatives can be evaluated for ψ = π/n -∆. The sensitivity of P max to δq is recorded in Table 2. The plots in Fig. 9 show the sensitivity Table 3 provide the same results in terms of order of importance of the variations in r, η, p and L. Finally, in order to minimize the variations in the Hertz pressure, we had better minimize the variations in p, L r and η in descending order.

Sensitivity of the Size of the Mechanism

The sensitivity analysis of S M is trivial. Indeed, from eq. ( 13), the higher m, the higher S M . Likewise, the higher L, the higher S M .

Problem Formulation

A motivation of this research work is to implement a Slideo-Cam transmission in the Orthoglide, a low-power machine tool introduced in [8]. To that end, the transmission has to transmit a torque C t of 1.2 Nm with a pitch of 20 mm. In case of high-speed operations, i.e., when the velocity of the cams is higher than 50 rpm, the pressure-angle is recommended to be smaller than 30 • . Table 1 shows that the maximum value of the Hertz pressure has to be smaller than 800 MPa as the cams and the rollers are made up of steel. Moreover S M is supposed to be smaller than 90 mm with a view to limiting the size of the mechanism. Besides, the Slide-o-Cam transmissions under study are composed of two-or three-conjugate cams as a Slide-o-Cam with only one cam is not feasible and such a mechanism with more than three conjugate cams would be too bulky, i.e., m = {2, 3}. Consequently, the optimization problem can be formulated min

x (µ max , P max , S M ) s.t. µ max ≤ 30 • P max ≤ 800 MPa S M ≤ 90 mm x l ≤ x ≤ x u
where x = [d cs , r, L, m] T , while x l and x u denote the lower and upper bounds of the design variables, respectively. Here, x l = [0 mm, 4 mm, 0 mm, 2] and x u = [0 mm, 10.5 mm, L max , 3], L max being equal to S Max /m knowing that S Max = 90 mm . The optimization problem defined in Section 3.4 is multiobjective with objective functions of a different nature. For this reason, the optimum solutions of the problem can be illustrated As we want to minimize the three objective functions concurrently, the closer the Pareto frontier to the origin, the better the design. In Fig. 10, we notice that the optimum solutions obtained with a three-conjugate cam mechanism are slightly better when µ max is smaller than 24 • . Otherwise, a two-conjugate cam mechanism turns out to be more interesting.

Results

Nevertheless, the difference between the optimum solutions obtained with a two-and a three-conjugate cam mechanisms remains low. Figure 11 Figures 15 and 16 illustrate the contours of µ max and P max w.r.t d cs and r for a two-and a three-conjugate cam mechanisms with S M = 0.06 m. On the one hand, the continuous lines depict the iso-contours of µ max . On the other hand, the broken lines depict the iso-contours of P max . Besides, Figs. 15 and 16 highlight the location of the optimum solutions for a two-and a threeconjugate cam mechanisms with S M = 0.06 m. We can notice that the line of optimum solutions in the space of design variables d cs and r is longer in Fig. 16 than in Fig. 15. This means that a three-conjugate cam mechanism allows more optimal solutions than its two-conjugate cam counterpart. In this vein, it is more interesting to design a three-conjugate cam mechanism.

Figure 17 depicts the mechanisms corresponding to points M 1 and M 2 that are plotted in Fig. 15. For M 1 , d cs = 2.6 mm, r = 4.24 mm, µ max = 3 • and P max = 653.83 MPa. For M 2 , d cs = 4.16 mm, r = 6.4 mm, µ max = 30 • and P max = 562.12 MPa.

Figure 18 depicts the mechanisms corresponding to points M 3 and M 4 that are plotted in Fig. 16. For M 3 , d cs = 2.2 mm, According to Figs. 15 and 16, we can notice that the higher r, the smaller P max . Indeed, the maximum Hertz pressure values corresponding to M 2 and M 4 are smaller than the ones corresponding to M 1 and M 3 . However, the size of the mechanism along the x-axis is higher for M 2 and M 4 . Moreover, this induces a better transmission of the torque as d cs is higher. Finally, we can notice that the profiles of M 2 and M 4 are easier to machine as they are fully convex.

CONCLUSIONS

The multiobjective optimization of Slide-o-Cam was reported in this paper. Slide-o-Cam is a cam mechanism with multiple rollers mounted on a common translating follower. This transmission provides pure-rolling motion, thereby reducing the friction of rack-and-pinions and linear drives. A Pareto frontier was obtained by means of a multiobjective optimization. This optimization is based on three objective functions: (i) the pressure angle, which is a suitable performance index for the transmission because it determines the amount of force transmitted to the load vs. that transmitted to the machine frame; (ii) the Hertz pressure used to evaluate the stresses produced in the contact surface between the cams and the rollers; and (iii) the size of the mechanism characterized by the number of cams and their width. It turns out that three-conjugate cam mechanisms have globally better performance that their two-conjugate cam counterparts. However, the difference is small.

Figure 1 .

 1 Figure 1. Layout of Slide-o-Cam

Figure 3 .

 3 Figure 2. Parameterization of Slide-o-Cam

Figure 4 .

 4 Figure 4. Orientations of the cam found when v c = 0: (a) ψ = ∆; (b) ψ = π; and (c) ψ = 2π -∆ to obtain a closed cam profile. ∆ is defined as a root of Eq.(2b). As far as Slide-o-Cam is concerned, ∆ is negative, as shown in Fig. 4. Consequently, to close the cam profile, ψ must vary within ∆ ≤ ψ ≤ 2π -∆.

Figure 5 .

 5 Figure 5. Cam profile and local curvature of the cam

Figure 6 .

 6 Figure 6. Active parts of: (a) a two-and (b) three-conjugate cam mechanisms

Figure 7 .

 7 Figure 7. The width B of the contact between a cam and a roller

Figure 8 .

 8 Figure 8. Pressure-angle distribution for (a) two conjugate-cam and (b) three conjugate-cam mechanisms with one lobe, p = 50, r = 10 and e = 9

  of the parameters are known, we will be able to evaluate c. Let us assume that r = 4 mm, η = 0.18, p = 50 mm and L = 10 mm. The partial derivatives have to be normalized to

Figure 10 .

 10 Figure 10. Pareto frontier of a two-and a three-conjugate cam mechanisms

Figure 11 .

 11 Figure 11. Pareto frontier of Slide-o-Cam mechanisms

Figure 12 .Figure 13 .Figure 14 .

 121314 Figure 12. Pareto frontier w.r.t. µ max and S M

Figure 15 .Figure 16 .

 1516 Figure 15. Contours of µ and P w.r.t d cs and r and the location of the optimal solutions for a two conjugate-cam mechanism with S M = 0.06 m

  Figure 17. Optimal two conjugate-cam mechanisms

Table 1 .

 1 Allowable pressures

	Material	P stat [MPa]	P max [MPa]
	Stainless steel	650	260
	Improved steel 1600 to 2000 640 to 800
	Grey cast iron	400 to 700	160 to 280
	Aluminum	62.5	25 to 150
	Polyamide	25	10

Table 2 .

 2 Influence of the variations in r, η, p and L on P max Hertz pressure w.r.t the different parameters for different values of ψ and for the active part of the cam profile. However, it is more relevant to calculate the rms value of each partial derivative, as recorded in Table3. As a matter of fact, Table2 and Table 3. Global influence of the variations in r, η, p and L on P

		q i		r	η	p	L
	q init ∂P max ∂q i (q init )	4 mm 103.32 83.25 362.03 232.67 0.18 50 mm 10 mm
	Order of importance	3	4	1	2
	of the q i		r	η	p	L
	q init		4	0.18	50	10
	n π ψ	(	∂P ∂q i	) 2 dψ	156.59 20.21 261.85 207.79
	Order of importance	3	4	1	2

µ is a real number and can be either positive or negative. However, within the scope of this paper, µ remains positive. Therefore, µ = |µ |, | • | denoting the absolute value.


come

Introduction 1

The Open Access movement generates plenty of sympathy among archaeologists. Academia.edu has grown to one of the biggest repositories for 'freely' available archaeological papers, cross-cutting the boundaries of traditional reading circles 2 . Everyone can understand the benefits of this ready availability of papers. On the other hand, the Free Software movement, where the origin of the Open Access movement is to be situated, is mostly ignored since it is not considered as relevant. However, on-going and growing debates about benefits of data release available through new information technologies challenge this position. Why, though, should archaeologists become more aware of the philosophy of Free Software?

Even if Free Software is well established inside and outside academia, the advantages of Free software (that is "the 'free' as in 'free speech', and not the 'free' as in 'free beer' ") are rarely acknowledged 3 . Free software is in many cases (in the imaginary) assumed to be complicated, untrustable or not as effective as 'industry-standard' software. More generally software is treated as a neutral tool to answer research questions, and emphasis is placed on the results with little time devoted to the reuse of either work-flows or of the collected data.

The aim of this paper is to give a brief overview of the intersection of Free Software with Archaeology. This closer look draws our attention to changes in information technologies that question orthodox models of knowledge dissemination. Open Access is important not only to enable access for a much wider audience to research outcomes, but it falls on us to make the access to the data and the analysis in both transparent and reproducible ways, ideals which are closer to the ethics of scientific research. This will create a stronger research environment into the future.

Earlier Work

Papers discussing Free Software in archaeology have been published from the end of the 1990s onwards, presenting showcases, new software, or dedicated environments4 . Benjamin Ducke recently published articles discussing the relation of Free (and Open Source) Software and archaeological software [START_REF] Ducke | Natives of a connected world: Free and open source software in archaeology[END_REF][START_REF] Ducke | Reproducible data analysis and the open source paradigm in archaeology[END_REF]). He focusses attention on the problem of 'black boxes' [START_REF] Morin | Shining light into black boxes[END_REF]) and of sustainability for the development of archaeological software. Proprietary software restricts the review of methods and control over the processes, it and hinders the dissemination of the analysis. All those without a license to use specific proprietary software are de facto excluded from the understanding and reproduction of the analysis. In this sense, proprietary software acts like 'black boxes', where, at best, only inputs and outputs are (partially) released. As he acknowledges, Ducke does not examine the philosophical or social aspects of Free Software. In the analysis here, I would like to focus more narrowly on these aspects and how these paradigms question methods established in archaeological research without narrowing the questionnment on software.

Scientific community

science is cumulative even though it is often obscure how exactly knowledge accumulates. In any case it is a community endeavour. In this process, members of the scientific community contribute different points of views, different questions, and different methods to resolve same problems. The community is a pool of inspiration: interactions encourage innovation and spark ideas about new lines of evidence, new applications, new questions, and alternate explanations. Lively interactions of the community allow knowledge to accumulate and become 'stable' faster5 .

The scientific community also creates a motivating force for recognition, respect from peers or academic prestige, and institutes controls over the quality of research by scrutinising the work of others (e.g. peer-review in journals or books review). Both represent a system of checks and balances that assures that claims are not fraudulent. The communication and the open process inside the community make claims more robust, or, contrarily, it allows the rejection of weak claims. Indeed it is not the work of a lone researcher that makes science strong and reliable, it is rather the true scrutiny and critics of peers [START_REF] Fanelli | Redefine misconduct as distorted reporting[END_REF].

Free Software and Science

Free Software shares a lot of characteristics with science. Both have scrutiny and cumulative knowledge, which can be seen in process like peer review, where open data is subject to validation and replication. There is a strong culture of credit, civility, reputation, and communication.

The motivations to do science or develop Free Software are in many aspects similar: it's based on the reputation earned with published work, and there is in both cases an ethic to attribute the work [START_REF] Kelty | Free software/free science[END_REF]. Researchers make their work available to others and citations accredit reuse of ideas, concepts, or code. In Free Software or in science, differences are made according to the status of the contribution (author, contributor, maintainer, etc.). Contributions are based on same principles of cumulative knowledge, its reuse, mixing, and modulation.

But similarities between Free Software and science should not hide differences. Dissimilarities, specifically Free Software's assets, challenge what is taken for granted in the process of accumulating knowledge.

Modifiability

Modifiability is without any doubt the most fascinating concept among the dissimilarities between science and Free Software (Kelty 2008: 12). Books and articles have bolstered science by making stable knowledge. Yet the impression often given by books or articles is that of a final or definitive version of expertise. Free Software questions this concept with practices like forking, new versioning, cloning, and the constant evolution of source code. Every 'newly available' operating system, even proprietary, contains older pieces of software.

Free Software challenges the Power of Knowledge

New practices of publication associated with the appearance of new information technologies render knowledge more dynamic [START_REF] Vinck | Les humanités délivrées. savoir et culture réinventés hors du livre[END_REF]. Wikipedia is the most famous example: its content can be updated, changed, deleted, copied, or forked at any time by anyone. The last 10 years have seen a complete revaluation of Wikipedia across the academy. Ten years ago, as I saw it in France, it was mostly rejected as 'untrustable source'. Now academics explain to their students how to use it in scholarly context [START_REF] Garrison | Getting a 'quick fix': First-year college students' use of wikipedia[END_REF].

Even if there is a growing discussion on publication of dynamic content there are still few examples of work-flows in academia. The model proposed by Kansa and others -Push and Publish -will certainly have a bright future [START_REF] Kansa | Publishing and pushing: Mixing models for communicating research data in archaeology[END_REF]. In this model, data are published on-line and may be updated, completed, corrected, cloned after the first online release. Repositories and digital archiving enable new dissemination methods.

By looking at the practice of Free Software, it is easier to ask how authority is established and question the finality of publication. Free Software focuses not only on the results (the software) but unifies operations and the possibility of control, improvement, and reuse. Free Software allows computational archaeology not only to concentrate on the results but broaden the attention consequently on how results are reached. This is the only way to reconcile the ethic of science and the establishment of (computational) facts. It is with this sense in mind that I will turn to the problem of reproducibility for computational archaeology.

Reproducibility

Reproducibility allows anyone to start from the same data and check all the processes undertaken, in order to verify the results. The complete process, from ideas and data to the publication has been termed as a 'research pipeline' [figure 2]. In archaeology there has been no culture of creating code for reproducibility until very recently7 . If we turn back to the definition of science, however, reproducibility and sharing of code are even sine qua non for scholarly communication, permitting the community to scrutinise the work. It is the only way to stick with a robust exposition of facts. "We often forget that scientific knowledge is reliable not because scientists are more clever, objective or honest than other people, but because their claims are exposed to criticism and replication." [START_REF] Fanelli | Redefine misconduct as distorted reporting[END_REF] [Figure2] Research Pipeline (after ideas from Roger Peng and Kieran Healy) | N. Strupler CC BY-NC 4.0 It is unrealistic to describe all the steps of an archaeological project by means of programming language. But several sub-steps -where computer plays a central role -can be made more explicit with scripts. A script is a plain text file of code composed in programming languages that instruct a computer to accomplish a set of tasks. Scripts may be augmented by comments that work like annotations. They help readers to understand the logic of the tasks. Scripts are firstly meaningful for creators to remember themselves how they obtained the results, and they record workflows that can be inspected, reused, or modified by others. Making scripts public allows reader to fully understand how results have been obtained.

For archaeological analysis, best practices permit the combination of data, code, and results through scripting and shared computational environments [START_REF] Marwick | Doing quantitative archaeology with open source software[END_REF]). This chain must be attained to adhere to the ethic of science. Moreover reproducibility has a huge potential for empirical research, like archaeology. Reproducibility is important to reuse and maintain data up to date. If, as shown in the Published and Push model, data are updated, then the analysis can be quickly updated, and therefore results do not need to remain fossilised in the (outdated) state they were published.

Reproducibility helps to cast research into modules. Bits of research based on code can be transformed and reused for similar projects or built upon for new projects. The modularity of code impacts on two levels. Firstly, open and reproducible archaeology makes resources easy available as paradigmatic pedagogical object. Hands-on workshops, modulations of research, testing of new hypothesis can be done in teaching environments with a direct, do it yourself approach. Secondly, the modularity of Free Software eases the blurring of academic borders in unpredictable ways. By providing a common language, Free Software creates new transversal communities that make science stronger.

Discussion

There are undoubtly barriers inhibiting the spreading of this paradigm. Modern archaeology is largely a low-tech field and archaeologists acquire minimal computer training at the university which is not refreshed. Analysis methods and presentation of data did not dramaticaly improve for over a century. This situation, where computers are mainly used as a 'writing machine,' does not favor debates about the limitations and advantages of software or strategies to develop a research program that uses Free Software and open format as standard.

Debates about licensing, black boxes, and reproducibitliy have emerged and are primarily questioned in the computational sciences before occuring in archaeology. Furthermore, an intense advocacy for data publication and reproducibility emerged from multiple scandals about the falsification of results and after the retraction of publications. As far as I know, there is no such (known) case in archaeology and consequently these questions are not widely discussed among archaeologist. The structure of archaeological research does not favor the challenging of the current paradigm because there is only a vague distinction between the acteurs producing, analysing, publishing, and using a specific archaeological data set. More critical evaluation of the careers of individual researchers are focussed on, in particular their papers published in prestious journals, rather than also taking in account the data sets that are easily reusable by others.

Yet archaeology is increasingly dependant on software to generate results, and funding bodies and journals increasingly request publication of data. Current and future projects based on the reuse of data from other projects have to develop a workflow to aggregate, clean, analyse, and visualise a growing body of data, always gaining in resolution. By creating different modules of (reusable) scripts, the use of Free Software appears to be the best solution in the long term. Starting and maintaining a project with Free Software does not cost more time compared to proprietary software; however, the transition for propietary software to Free Software is time consuming. Therefore, it seems now critical to adopt Free Software and develop a transparent research pipeline, otherwise the current aspiration to do 'big data analysis' may turn from dream to nightmare.

Conclusion

Free Software challenges the authority of science and provides a means to transform computational archaeology and, indeed, the practice of archaeological research as a whole by questioning transmission and reuse of research. Free Software coupled with reproducibility by means of scripting makes the entire research pipeline available to the scrutiny of the community and reconciles data, processes, and results. Making the complete research available for free online has the potential to change archaeology into a research environment more robust and open to everyone.

[

  Figure1] [Open and wide communication of negative as well as positive findings. From Bartling et al. 2014, Opening Science (fig. 3, 10)](http://dx.doi.org/10.1007/978-3-319-00026-8_1) | CC BY-NC 3.0The top of this diagram [Figure1], shows a representation of the current way of doing research with stable knowledge: results are only used when they are stable. The bottom part represents how software development works and how science could be made to work. The process of sharing and reusing readily available knowledge becomes more dynamic. However this poses a question. If the content does not need any more to be stable and it is used like Free Software, "how should the authority, stability and reliability of knowledge be assessed"(Kelty 2008: 300)? In this sense Free Software can be said to challenge the 'Power of Knowledge' 6 .

This paper is a revised version of a talk given during the session 10A "ArcheoFOSS: free/open source software and archaeological research, ten years later" at the CAA

conference "KEEP THE REVOLUTION GOING". I am grateful to the organisers and to the participants for the comments in a nice and motivating atmosphere. The original paper, the slide-show and extra material are accessible online. DOI: 10.5281/zenodo.16596. A video of that lecture was recorded by Doug Rocks-Macqueen and has been published under his project Recording Archaeology. I would like to thank Mathias Strupler, Vera Egbers, Toby C. Wilkinson and Joseph Lehner for discussions, contributions, useful comments and suggestions on the language and structure of the manuscript. I also am grateful to two anonymous reviewer for their close reading and perceptive comments.2 academia.edu is 'free to use' but it is not free. There is no API, which would have enabled a query of the growth of papers tagged with #Archaeology during the last years and consequently asserts the affirmation from the main text. For now, it is just a guess . . .3 See the definition of the Free Software Foundation [Accessed: 30th June 2015]

It is not the purpose to review earlier literature in this paper but the proccedings of ArcheoFOSS[START_REF] Serlorenzi | ARCHEOFOSS free, libre and open source software e open format nei processi di ricerca archeologica[END_REF] for the latest published) and papers published in the proceedings of the CAA are a good starting point to gain an overview about Free Software and Archaeology.

"Stable knowledge" refers to the process of establishing a fact, among others[START_REF] Latour | Laboratory life: The social construction of scientific facts[END_REF].

I refer to the expression of C.Kelty in his book, Two Bits (2008)

For example, see the meeting during the SAA 2015 in San Francisco, "Electronic Symposium Open Methods in Archaeology: How to Encourage Reproducible Research as the Default Practice?" organised by Ben Marwick, Mark Lake and Andrew Bevan.