George Bosilca

Aurelien Bouteiller

Amina Guermouche

Thomas Herault

Yves Robert

Pierre Sens

Jack Dongarra

Failure Detection and Propagation in HPC systems

Keywords: MPI, Failure Detection, Fault-Tolerance

Building an infrastructure for Exascale applications requires, in addition to many other key components, a stable and efficient failure detector. This paper describes the design and evaluation of a robust failure detector, able to maintain and distribute the correct list of alive resources within proven and scalable bounds. The detection and distribution of the fault information follow different overlay topologies that together guarantee minimal disturbance to the applications. A virtual observation ring minimizes the overhead by allowing each node to be observed by another single node, providing an unobtrusive behavior. The propagation stage is using a non-uniform variant of a reliable broadcast over a circulant graph overlay network, and guarantees a logarithmic fault propagation. Extensive simulations, together with experiments on the Titan ORNL supercomputer, show that the algorithm performs extremely well, and exhibits all the desired properties of an Exascale-ready algorithm.

I. INTRODUCTION

Failure detection is a prerequisite to failure mitigation and a key component to any infrastructure requiring resilience. This paper is devoted to the design and evaluation of a reliable algorithm that will maintain, and distribute the updated list of alive resources with a guaranteed maximum delay. We consider a typical High-Performance Computing (HPC) platform in steady-state operation mode. Because in such environments the transmission time can be considered as bounded (although that bound is unknown), it becomes possible to provide a perfect failure detector according to the classical definition of [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. A failure detector is a distributed service able to return the state of any node, alive or dead (subject to a crash) 1 . A failure detector is perfect if any node crash is eventually suspected by all surviving nodes, and if no surviving node ever suspects a node that is still alive. Critical fault-tolerant algorithms for HPC, and implementations of communication middleware for unreliable systems rely on the strong properties of perfect failure detectors (see e.g. [START_REF] Egwutuoha | A survey of fault tolerance mechanisms and checkpoint/restart implementations for high performance computing systems[END_REF], [START_REF] Herault | Practical scalable consensus for pseudosynchronous distributed systems[END_REF], [START_REF] Bland | An evaluation of user-level failure mitigation support in MPI[END_REF], [START_REF] Bland | Lessons Learned Implementing User-Level Failure Mitigation in MPICH[END_REF], [START_REF] Katti | Scalable and fault tolerant failure detection and consensus[END_REF]). Their cost, in terms of computation and communication overhead, as well as their properties in terms of latency to detect and notify failures and of reliability, have thus a significant impact on the overall performance of a fault-tolerant HPC solution.

While we focus primarily on of one the most widely used programming paradigms, the Message Passing Interface (MPI), the techniques and algorithms proposed have a larger scope, and are applicable in any resilient distributed programming environment. We consider the platform as being initially composed of N nodes, but with a high probability, some 1 We use the words failure, crash, or death indifferently.

Platform parameters N Initial number of nodes τ

Upper bound on the time to transfer a message Protocol parameters η Period for heartbeats δ Time-out for suspecting a failure of these resources will become unavailable throughout the execution. When exposed to the crash of one node, traditional applications would abort. However, the applications that we consider, are augmented with fault tolerant extensions that allow them to continue across failures (e.g. [START_REF] Bland | Postfailure recovery of MPI communication capability: Design and rationale[END_REF]), either using a generic or an application-specific fault tolerant model. The design of this model is outside the scope of this paper, but without loss of generality, we can safely assume that any fault tolerant recovery model requires a robust fault detection mechanism. Our goal is to design such a robust protocol that can detect all failures and enable the efficient repair of the execution platform. By repairing the platform, we mean that all surviving nodes will eventually be notified of all failures, and will therefore be able to compute the list of surviving nodes. The state of the platform where all failed nodes are known to all processes is called a stable configuration (note that nodes may not be aware that they are in a stable configuration).

By robust, we mean that regardless of the length of the execution, if a set of up to f failures disrupt the platform and precipitate it into an unstable configuration, the protocol will bring the platform back into a stable configuration within T (f ) time units (we will define T (f ) later in the paper). Note that the goal is not to tolerate up to f failures overall. On the contrary, the protocol will tolerate an arbitrary number of failures throughout an unbounded-length execution, provided that no more than f successive overlapping failures strike within the T (f ) time-window. Hence, f induces a constraint on the frequency of failures, and not on the total number of failures.

By efficiently, we aim at a low-overhead protocol that limits the number of messages exchanged to detect the faults and repair the platform. While we assume a fully-connected platform (any node may communicate with any other), we use a realistic one-port communication model [START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF], where a node can send and/or receive at most one message at any time-step. Independent communications, involving distinct sender/receiver pairs, can take place in parallel: however, two messages sent by the same node will be serialized.

These goals seem contradictory but they only call for a carefully designed trade-off: as shown in [START_REF] Ferreira | Characterizing application sensitivity to OS interference using kernel-level noise injection[END_REF], [START_REF] Hoefler | Characterizing the influence of system noise on large-scale applications by simulation[END_REF], [START_REF] Kharbas | Assessing HPC Failure Detectors for MPI Jobs[END_REF], system noise created by the messages and computations of the fault detection mechanism, can impose significant overheads in HPC applications, hence the efficiency of the approach must be carefully assessed. The overhead should be kept minimal in the absence of failures, while failure detection and propagation should execute quickly, which usually implies a robust broadcast operation that introduces many messages. The major contributions of this work are as follows:

• A proven algorithm for failure detection, based on a robust protocol that tolerates an arbitrary number of failures, provided that no more than f consecutive failures strike within a time window of duration T (f );

• The protocol has minimal overhead in failure-free operation, with a unique observer per node;

• The protocol achieves failure detection and propagation in logarithmic time for up to f max = log n -1 where n is the number of alive nodes. More precisely, the bound T (f max ) is deterministic, and logarithmic in n, even in the worst case;

• All performance guarantees are expressed within a realistic one-port communication model;

• Extensive simulations and experiments with ULFM [START_REF] Bland | Postfailure recovery of MPI communication capability: Design and rationale[END_REF] show very good performance of the algorithm. The rest of the paper is organized as follows. We start with an informal description of the algorithm in Section II. We detail the model, the proof of correctness and the timeperformance analysis in Section III. Then we assess the efficiency of the algorithm in a practical setting, first by reporting on a comprehensive set of simulations in Section IV, and then by discussing experimental results on the ORNL Titan supercomputer in Section V. Section VI provides an overview of related work. Finally, we outline conclusions and directions for future work in Section VII.

II. ALGORITHM

This section provides an informal description of the algorithm. We refer to Section III for a detailed presentation of the model, a proof of correctness and a time-performance analysis. We maintain two main invariants in the algorithm:

1) Each alive node maintains its own list of known dead resources; 2) Alive nodes are arranged along a ring and each node observes its predecessor in the ring. In other words, the successor/observer receives heartbeats from its predecessor/emitter (see below). When a node crashes, its observer broadcasts the information and reconnects the ring: from now on, the observer will observe the last known predecessor (accounting for locally known failures) of its former predecessor. The rationale for using a ring for detection is to reduce the overhead in the failure free case: with only one observer, a minimal number of heartbeat messages have to be sent. We use the protocol suggested in [START_REF] Chen | On the quality of service of failure detectors[END_REF] for fault detection. Consider a node q observing a node p. The observed node p is also called the emitter, because it emits periodic heartbeat messages m 1 , m 2 , . . . at time σ 1 , σ 2 , . . . to its observer q, every η time units. Now let

σ i = σ i + δ. At any time t ∈ [σ i , σ i+1 ), q trusts p if it has
Algorithm 1 Sketch of the failure detector for node i. emitter i ← (i -1) mod N 3:

observer i ← (i + 1) mod N 4:
HB-TIMEOUT ← η Send HEARTBEAT(i) to observer i 12: end task

D i ← D i ∪ emitter i 21:
dead ← emitter i 22:

emitter i ← FindEmitter(D i ) 23:
Send NEWOBSERVER(i) to emitter i

24:

Send BCASTMSG(dead, i, D i ) to Neighbors(i, D i ) 25: end task return k 42: end function received heartbeat m i or higher. Here, δ is the time-out after which q suspects the failure of p. Assume there are initially N alive nodes numbered from 0 to N -1, and node i+1 mod N observes node i according to the previous protocol, for all 0 ≤ i ≤ N -1. Tasks T 1 and T 2 in Algorithm 1 execute this basic observation node, with the time-out delay being reset upon reception of a heartbeat. Note that [START_REF] Chen | On the quality of service of failure detectors[END_REF] shows that this protocol, where the emitter spontaneously sends heartbeats to its observer, exhibits better performance than the variant where observers reply to heartbeat requests.

What happens when an observer (node i) suspects the crash of its predecessor in the ring? Task T 3 in Algorithm 1 implements two actions. First, it updates the local list D i of dead nodes with the identity of its emitter and then reconnects the ring (lines 19 to 23); and second, it initiates a reliable broadcast informing all nodes in its current list of alive nodes about the crash of its predecessor (line 24).

The first action, namely the reconnection of the ring, is taken care of by the procedure FindEmitter(D i ): node i searches its list of dead resources D i and finds the first (believed) alive node, j, preceding it in the ring. It assigns j as its new emitter and sends a message NEWOBSERVER informing j that i has become its observer. Node i also sets a timeout to 2δ time units, a period after which it will suspect its new emitter, j, if it has not received any heartbeat. Task T 4 implements the corresponding action at the emitter side.

The second action for node i is the broadcast of the crash to all alive nodes (according to its current list). A message BCASTMSG(dead, i, D i ) containing the identity of the crashed node dead, the source of the broadcast i, and the locally known list of dead nodes D i is broadcast to all alive nodes (according to the current knowledge of node i). We now detail how this procedure works. Let A be the complement of D i in {0, 1, . . . , N -1}, and let n = |A|. The elements of A are labeled from 0 to n -1, where the source i of the broadcast is labeled 0. The broadcast is tagged with a unique identifier and involves only nodes of the labeled list A (this list is computable at each participant as D i is part of the message). Because n is not necessarily a power of two, we have a complication 2 . Letting k = log n (all logarithms are in base 2), we have 2 k ≤ n < 2 k+1 . We use twice the reliable hypercube broadcast algorithm (HBA) of [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF]. The first HBA call is from the source (label 0) to the sub-cube of nodes j, where 0 ≤ j ≤ 2 k , and the second HBA call is from the same source (label 0) to the sub-cube of nodes n -j mod n, where 0 ≤ j ≤ 2 k . Each HBA call thus involves a complete hypercube of 2 k nodes, and their union covers all n nodes (with some overlap). The HBA algorithm delivers multiple copies of the broadcast message through disjoint paths to all the nodes in the system. Each node executes a recursive doubling algorithm and propagates the received information to up to k participants ahead of it, located at distance 2 k for 0 ≤ j ≤ 2 k . For simplicity we refer to both HBA calls as a single broadcast in our algorithm.

Upon reception of a broadcast message including a source s and a list of dead nodes D, any alive node i can reconnect the complement list A of nodes involved in the broadcast operation and their labels, and then compute the ordered set of neighbors Neighbors(s, D) to which it will then forward the message. We stress that the same list D, or equivalently the same set of participating nodes, is used throughout the broadcast operation, even though some intermediate nodes might have a different knowledge of dead and alive nodes. This feature is essential to preserving fault-tolerance in the algorithm of [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF]. Indeed, we know from [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF] that each subhypercube broadcast is guaranteed to complete provided that there are no more than k -1 dead nodes within participating nodes (set A) while the broadcast executes.

III. MODEL & PERFORMANCE ANALYSIS

This section provides a detailed presentation of the model, and a proof of correctness of the algorithm, together with a worst-case time-performance analysis.

A. Model 1) General Framework: Nodes can communicate by sending messages in communication channels, expected to be lossless and not ordered. Any node can send a message to any other node. Messages in the communication channel (p, q) take a random time T p,q to be delivered, which has an upper bound τ . We consider executions where nodes can crash permanently at any time. If a node p crashes, then all communication channels to p are emptied, p does not send any message nor execute any local assignment.

Note that τ is a property of the platform, that represents the maximal time that separates a process entering a send operation, and the destination process having the corresponding message ready to read in its memory. While the exact value for τ is generally unknown, it can be bounded in our case, using the techniques described in Section V-A. The algorithm uses δ > τ as a bound to define the limit after which a node is suspected dead. Tuning the value of δ as close as possible to τ , without underestimating τ to guarantee that false positives are not detected, is an operation that must be fitted for each target platform. Thus, in the theoretical analysis, we use τ to evaluate the worst case of a communication that succeeds, while the algorithm must rely on δ to detect a failure.

2) Using the One-Port Model: While we assume a fullyconnected platform (any node may communicate with any other), we use a realistic one-port communication model [START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF] where a node can send and/or receive at most one message at any time-step. Independent communications, involving distinct sender/receiver pairs, can take place in parallel: however, two messages involving the same node will be serialized. Using the one-port model while aiming at a low-overhead protocol is a key motivation to this work. It is not realistic to assume that each node would observe any other node, or even a large subset of nodes: while this would greatly facilitate the diffusion of knowledge about a new crash, and speed-up the transition back to a stable configuration, it would also incur a tremendous overhead in terms of heartbeat messages, and in the end dramatically impact the throughput of the platform.

Because all messages within our algorithm have a smallsize, we model our communications using a constant time τ to send a message from one node to another. We could have used a traditional model such as LogP, or used a start-up overhead plus a time proportional to the message size, but since we use this only as an upper bound, this would complicate the analysis unnecessary. Under the one-port model, the HBA algorithm [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF] with 2 k nodes executes in 2kτ , provided that no more than k -1 crashes strike during its execution. The time for one complete broadcast algorithm in Algorithm 1 would then be (upper bounded by) 4τ log n in the absence of any other messages, since we use two HBA calls in sequence. But our algorithm also requires heartbeats to be sent along the ring, as well as NEWOBSERVER messages when ring reconnection is needed. Assuming that η ≥ 3τ (where η is the heartbeat period), we can always insert broadcast and NEWOBSERVER messages in between two successive heartbeats, thereby guaranteeing that a broadcast in Algorithm 1 will always execute within B(n) = 8τ log n, assuming no new failure interrupts the broadcast operation.

3) Stable Configuration and Stabilization Time: Here we consider executions that, from the initial configuration, reached a steady state before a failure hit the system and made it leave that steady state. To prove the correctness of our algorithm, we show that in a given time, the system returns to a steady state, assuming that no more than a bounded number of failures strike during this time.

Connected Node A node p is connected with its successor in a configuration, if p is alive and emitter p is the closest predecessor of p that is alive (on the ring). It is connected with its predecessor if it is alive, and observer p is the closest successor of p that is alive in that configuration. It is reconnected if it is connected with both its successor and predecessor. If all processors are reconnected, we say the ring is reconnected.

Stable Configuration A configuration C is the global state of all processes plus the status of the network. A configuration is declared as stable, if any alive node p is reconnected in C and for any node q, q ∈ D p ⇐⇒ q is dead in C.

Stabilization Time T (f ), with f being the number of overlapping failures, is the duration of the longest sequence of non stable configurations during any execution, assuming at most f failures during the sequence.

B. Correctness and Performance Analysis

The main result is the following proof of correctness, that provides a deterministic upper bound on the Stabilization Time T (f ) of the algorithm with at most f overlapping faults: Theorem 1. With n ≤ N alive nodes, and for any f ≤ log n -1, we have

T (f ) ≤ f (f + 1)δ + f τ + f (f + 1) 2 B(n) (1)
where

B(n) = 8τ log n.
This upper bound is pessimistic for many reasons, which are discussed after the proof. But the key point is that the algorithm tolerates up to log n -1 overlapping failures in logarithmic time O((log n) 3 ).

Proof. Starting from a non stable configuration, the next stable configuration will be reached when (i) all nodes are informed of the different failures via the broadcast, and (ii) processes of the ring are reconnected. Recall that every time a node has detected a failure, it initiates a broadcast that executes within B = B(n) = 8τ log n time units, and which is guaranteed to reach all alive nodes as long as f ≤ log n -1. Because we interleave reconnection messages within the broadcast, B encompasses both the broadcast and the reconnection. However, due to the one-port model, we cannot assume anything about the pipelining of several consecutive broadcast operations. In this proof, we make a first simplification by overapproximating T (f ) as the maximum time R(f ) to reconnect the ring after f overlapping failures, plus the time to execute all the broadcasts that were initiated, in sequence (assuming no overlap at all). We prove an upper bound on R(f ) by induction, letting R(0) = 0:

Lemma 1. For 1 ≤ f ≤ log n -1, we have R(f ) ≤ R(f -1) + 2f δ + τ (2)
Proof. We first prove Equation ( 2) when f = 1. Assume that node p, observed by node q, fails. After receiving the last heartbeat, q needs δ time units to detect the failure (line 15 of Algorithm 1). Thus, the worst possible scenario is when p fails right after sending a heartbeat, which will take τ time units to reach q. Thus q detects the failure after τ + δ time units. Finally, q sends the reconnection message to the predecessor of p, which will take τ , hence R(1) ≤ 2τ + δ. We keep the over-approximation R(1) ≤ τ + 2δ to simplify the formula in the general case. Assume now that Equation (2) holds for all f ≤ log n -2. Now consider an execution with f +1 overlapping failures, the first of them striking at time 0 (see Figure 2). The (f + 1)-th failure strikes at time t. Necessarily t ≤ R(f ), otherwise the ring would have been reconnected after f failures, and the last one would not be overlapping. There are f dead nodes just before time t among the original n alive nodes, which define k ≤ f segments I i , 1 ≤ i ≤ k. Here, segment I i is an interval of d i ≥ 1 consecutive dead nodes (see Figure 1). Of course k i=1 d i = f , and there remain n -f alive nodes. There are multiple cases depending upon which node is struck by the (f + 1)-th failure at time t:

(a) The new failure strikes a node that is neither a predecessor nor a successor of a segment (e.g., the failure strikes node 7 in Figure 1). In that case, a new segment of length 1 is created, and the ring is reconnected at time t + R(1).

(b) The new failure strikes a node p that precedes a segment I i . Let q be the successor of the last dead node in I i . By definition, q = p. There are two sub-cases: (i) The predecessor p of p is still alive (e.g., the failure strikes node 1 preceding segment I 1 in Figure 1, q = 4 and p = 0 is alive). Then the size of segment I i is increased by one. In the worst case, q is not aware of the death of any node in I i at time t, and needs to probe all these nodes one after the other before reconnecting with p (in the example, q = 4 needs to try to reconnect with 2 and 1 since it is not aware of their death). This costs at most

(d i + 1)(2δ) + τ ≤ 2(f + 1)δ + τ , because d i + 1 ≤ f + 1, hence the ring is reconnected at time t + 2(f + 1)δ + τ . (ii)
The predecessor p of p is dead (e.g., the failure strikes node 4 preceding segment I 2 in Figure 1, q = 6 and p = 3 is dead). Then p is the last node of another segment I j . In that case, segments I i and I j are merged into a new segment of size d i + d j + 1 ≤ f + 1. Just as before, in the worst case, q is not aware of the death of any node in that new segment, and the reconnection costs at most (d i +d j +1)(2δ)+τ ≤ 2(f +1)δ+τ (see Figure 2 for an illustration). Hence the ring is reconnected at time t + 2(f + 1)δ + τ .

(c) The new failure strikes a node p that follows a segment I i . Let q be the successor of p. If q is alive, it now follows a segment of size d i + 1. If q is the first dead node of segment I j , let r be the node that follows I j . Now r follows a segment of size d i + d j + 1. In both cases, we conclude just as before. This completes the proof of Lemma 1.

From Lemma 1, we easily derive by induction that

R(f ) ≤ f (f + 1)δ + f τ
for all values of f ≤ log n -1. During the ring reconnection, processes that discover a dead process initiate a broadcast of that information. We need to count, in the worst case, how many broadcasts are initiated to compute how long it takes for the information to be delivered to all nodes. Lemma 2. Let p i , 1 ≤ i ≤ f ≤ log n -1 be the i -th process subject of a failure. In the worst case, at most f -i+1 processes can detect the death of p i .

Proof. A process p is discovered dead by process q in Task T3, if emitter q = p. In that case, p is added to D q , and emitter q is re-computed using FindEmitter. That function cannot return any process in D q , and p is never removed from D q . Thus, q will never discover the death of p again. As long as q lives, no other process q will execute the task T3 with emitter q = p, because q is an alive process between q and p in the ring. Thus, q must fail after p, for p to be discovered once more. Since there are at most f faults, p i , the i -th failed process can thus be discovered dead by at most f -i+1 processes.

We derive from Lemma 2 that at most

f i=1 (f -i + 1) = f (f +1) 2
broadcasts are initiated. Finally, the information on the f dead nodes must reach all alive nodes. For each segment I i , there is a last failure after which the broadcast initiated by the observing process is not interrupted by new failures. That broadcast operation thus succeeds in delivering the list of newly discovered dead processes to all others (d i ≤ log n -1). In the worst case, that broadcast operation is the last to complete. As already mentioned, we conservatively consider that all the broadcast operations execute in sequence. Since there are at most f (f +1) 2 broadcast operations initiated , we obtain T (f ) ≤ R(f ) + f (f +1) 2 B(n), which leads to the upper bound in Equation ( 1) and concludes the proof of Theorem 1. The bound on T (f ) given by Equation ( 1) is quite pessimistic. We can identify three levels of complexity with their corresponding bounds on T (f ). In the most likely scenario, where the time between two consecutive faults is larger than T (1), the system has time to return to a stable configuration before the second fault, in which case all faults can be considered as independent, and the average stabilization time is

T (1) = R(1) + B(n) = O(log n).
If the system suffers quickly overlapping faults, the location of impacted nodes becomes important. However, the larger the platform, the smaller the probability that successive faults strike consecutive nodes (2/n, where n is the number of alive nodes). Thus, on large platforms, overlapping failures are more likely to strike non consecutive nodes in the ring. If overlapping faults hit non consecutive nodes rapidly, i.e., faster than the time needed by the system to reach the next stable configuration, each error is detected once, but due to the one-port model, the upper bound on T (f ) becomes R(1) + f B(n) = O(log 2 n). Finally, in the unlikely scenario where f quickly overlapping faults hit f consecutive nodes in the ring, the Theorem 1 provides the upper bound for

T (f ) ≤ R(f ) + f (f +1) 2 B(n) = O(log 3 n).

C. Non Stabilization Risk Control

To guarantee convergence within T (f ) time units, Algorithm 1 assumes that f ≤ log(n) -1. In order to evaluate the risk behind this assumption, consider that failures strike following an Exponential distribution of parameter λ. Let P T (f ) be the probability of the event "more than f failures strike within time T ".

Then P T (f ) = 1 -Σ f k=0 (λT ) k k! e -λT .
Consider a platform of n nodes: if µ ind is the MTBF of a single node, then λ = n µind [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]. Let M = log(n) -1, the assumption that there will not be more than M failures before stabilization is then true with probability P T (M ) (M ). In Figure 3, we represent this relation by showing the upper bound of δ to enforce P T (M ) (M ) < 10 -9 , at variable machines scale (n), and for different values of µ ind , with a message time bound of τ = 1µs. Figure 3 illustrates that for all values of δ lower than the bound shown for a given system size and individual

�� � �� � �� � �� � �� � �� ��� ���� ���� ���� ���� ������������� ������������������� � ��� ��������� � ��� ��������� � ��� ����������
Fig. 3: Maximal value for δ to ensure that P T (M ) (M ) < 10 -9 with τ = 1µs and M = log 2 (n) .

node reliability, the probability that failures strike fast enough to prevent Algorithm 1 from converging in T (f ) is negligible (less than 0.000000001). As already mentioned, this bound on δ is a loose upper bound, because the bound on T (f ) in Equation ( 1) is loose itself. Furthermore, it captures the risk that enough failures would strike during stabilization time to make the appearance of the worst case scenario possible, even though this worst case scenario has itself a very low probability to happen (as shown in Sections IV and V). Still, for the largest platforms with n = 256, 000 nodes, we find that δ ≤ 22s for the most pessimistic µ ind = 20 years, and δ ≤ 60s if µ ind = 45 years results in timely convergence. With such large values, the detector generates negligible noise to the applications, as shown in Section V-C.

IV. SIMULATIONS

We conduct simulations and experiments to evaluate the performance of the algorithm under different execution scenarios and parameter settings. We instantiate the model parameters with realistic values taken from the literature. The code for all algorithms and simulations is publicly available [START_REF]Hidden for double-blind review[END_REF], so that interested readers can build relevant scenarios of their choice. In this section, we report simulation results. See Section V for experiments.

A. Simulation Settings

The discrete-event simulator imitates how the protocol of Algorithm 1 would behave on a distributed machine of size n. Messages between a pair of alive nodes in this machine take a uniformly distributed time in the interval (0, τ ]. Failures are injected following an exponential law of parameter λ = n/µ ind (see Section III-C). In order to generate a manageable amount of events, each heartbeat message and the corresponding timeouts are not simulated, but the simulator asserts that a timeout should have expired on the observer after the death of its emitter, if the observer is alive at that time (otherwise, the observer's observer is going to react, following the protocol).

The simulator computes (i) the average time to reach a stable configuration (all processes know all faults) starting from a configuration with a single failure injected at time 0, (ii) the average time to reach a configuration where all processes know about the initial failure, and (iii) the average number of failures striking during the time it takes to reach a stable configuration, over a set of 10,000 independent runs. We consider two main scenarios for the simulations. In both scenarios, we target a large scale machine (up to 256,000 computing nodes) with a low latency interconnect (τ = 1µs). In the scenario LOWNOISE, we set the failure detector so as to minimize the overhead in the failure free case: η is set to 10 seconds, and δ to 1 minute. We consider this case significant for platforms where nodes are expected to be reliable, or where alternative methods to detect most failures exist; the heartbeat mechanism is then used as a last resort solution, e.g. when special hardware providing a Baseboard Management Controller and controlled through a protocol like IPMI [START_REF] Wung | Intelligent platform management interface[END_REF] is connected to the application notification system. We also considered a scenario LOWLAT, with the opposite assumptions, where active check through heartbeats is the primary method to detect failures, and a low latency of detection is required for the application: η = 0.1s, and δ = 1s.

B. Simulation Results

In Figure 4, we force the simulator to inject the maximum number of failures tolerated by the algorithm for a given platform size ( log 2 (n) -1) in a very short time, inferior to δ, in order to evaluate the average stabilization time in the most volatile environment. Varying the system size (n), and the number of injected failures simultaneously, we evaluate the time taken for the first failure to be notified to all processes, and for all the processes to be notified of all the failures that struck since the last stable configuration.

The figure considers scenario LOWNOISE. Points on the graph show times reported by the simulator, while lines represent functions fitted to these points, O( 1 n + log 2 (n) ) for all know all failures (orange lines), and O( 1n ) for all know the first failure (green lines).

In average, the first failure, striking at time 0, is detected δ -η 2 seconds later, and this is the observed base line for detecting the first failure at all nodes. The reliable broadcast overhead in this case is negligible, because τ << δ and η. There are a few executions in which, within the first δ seconds, another failure hits the observer of the first failure, introducing another δ delay to actually detect the first failure and broadcast it. As the size of the machine increases, this probability decreases. Such overlapping failure cases contribute to a longer detection and notification time that can be fitted with a function inversely proportional to the platform size, but have a low probability to happen, introducing a measurable but small overhead at small scale. For general stabilization, where all processes need to know all failures, the reliable broadcast remains as fast as for the initial failure. However, if any failure strikes before that broadcast phase is complete, this delays reaching stabilization by another δ followed by a logarithmic phase. As we observe in both figures, this shows at large scale, where failures have a high probability to strike successively, each introducing a constant overhead. The fitting function thus shows the same inversely proportional property in the beginning, then the logarithmic behavior starts to dominate at large scale. We conducted the same set of simulations on the LOWLAT scenario, but cannot include them for lack of space. The evaluation presents the exact same characteristics, shifted by the ratio between the two values for δ.

We then consider the average case, when failures are not forced to strike quasi-simultaneously. We set the MTBF of independent components to a very pessimistic value (µ ind = 1year), making the MTBF of the platform decrease to a couple of minutes at 256,000 nodes. Although we do not expect such a pessimistic value in real platforms, we evaluate this case in order to ensure that failures may occur before the initial one is detected and broadcast (or stabilization would be reached immediately after). Figure 5 presents the average number of failures observed at different scales, the average time for all nodes to know about the first failure, and the average time for all nodes to know about all failures. Points represent values given by the simulator, while lines represent fitting functions:

for the time for all to know the first failure, O(n) for the average number of failures and the average time for all to know all failures. We present here the scenario LOWNOISE, although the result also holds for scenario LOWLAT, at a different scale.

This figure shows that, on average, and even with extremely low MTBFs, the probability that two independent failures hit the system in an overlapping manner (before the first failure is known by all nodes) is very low. This happens when the MTBF of the system becomes comparable to δ. In that case, the first failure still takes close to a constant time to be notified to all. This is because τ log 2 (n) remains very small compared to δ, and once the broadcast is initiated, it completes in τ log 2 (n). The successive failures may strike anytime between [0, δ], delaying the time to reach the stable configuration by another δ + τ log 2 (n). On average, at 256,000 nodes, this happens in the middle of the initial failure detection interval, delaying the completion by δ/2. Each failure, however, is independent in that case, and each is detected almost δ time units after it strikes.

V. EXPERIMENTAL EVALUATION

This section presents an experimental evaluation of an operational implementation of the proposed failure detector on the Titan ORNL supercomputer. We have implemented the failure detection and propagation service in the reference implementation of the User-Level Failure Mitigation (ULFM) draft MPI standard [START_REF] Bland | An evaluation of user-level failure mitigation support in MPI[END_REF], provided by OPEN MPI. ULFM is an extension of the MPI standard that empowers MPI users (that is, applications, library developers, or parallel programming languages) to provide their own fault tolerant strategy. The general design of ULFM relies on local semantics: failures are notified to the user only in MPI calls that involve a failed process, and a correct ULFM implementation will try to make all operations succeed, if it can complete locally. Although this relaxed design eases the implementation requirements and delivers higher failure-free performance, the fact that a failure is guaranteed to be detected only after an active reception from the dead process can lead to an increase of latency during failure recovery operations, because the same process failures may be detected sequentially by multiple processes, possibly at a much later time than when they were first reported. Moreover, several routines imply necessarily a communicator-wide knowledge on failures: operations like MPI_COMM_AGREE and MPI_COMM_SHRINK need to build consistent knowledge on (sub)sets of acknowledged failures; a pending point-to-point reception from any source must eventually raise an error, if it cannot complete because of the death of a processor. Therefore, the addition of the failure detection and propagation service provides an acceleration to such scenarios, by eliminating delayed local observation of the failure, which can then be immediately reported to the upper-level, which can then act upon it quickly.

A. Implementation

The failure detector is composed of two components: the observation ring, and the propagation overlay. The components operate on a group of processes, which must be MPI consistent (that is, identical at all ranks). The propagation topology is implemented at the Byte Transport Layer (BTL) level, which provides the portable low-level transport abstraction in OPEN MPI.

The propagation overlay takes advantage of the Active Message behavior of the OPEN MPI BTL's. Each message, with a size lesser than the "eager" protocol switch point, contains the index of the callback function to be analyzed by upon reception. This approach provides independence from the MPI semantic (including matching). Upon the reception of a propagation message, the message is forwarded according to two possible algorithms. In the case where the overlay is not corrected to incorporate the knowledge about failed processes, thus the group can be considered as an invariant during the entire execution, the message is forwarded as is through the propagation topology which is constructed every time a broadcast is initiated, according to the algorithm presented in Section II, in order to guarantee the logarithmic propagation delay. When the upper level declares, through a runtime parameter, that it repairs its communicators after every stabilization phase, the reliable propagation overlay can reduce the size of the messages to include only the latest detected failures, and the overlay is then built considering all processes of the group. The observation ring is also built at the BTL level. The emission of the heartbeats poses a particular challenge in practice. The timely activation and delivery of heartbeats is of critical importance to enforce the perfection of the detector, and the bound on τ . Missing its η emission period deadlines puts the emitter process at risk of becoming suspected by its observer, even though it is still alive. If the heartbeats are emitted from the application context, they can only be sent when the application enters MPI routines, and consequently, a compute intensive MPI application would often miss the η period. In our implementation, the heartbeats are emitted from within a separate, library internal thread, in order to render their emission independent from the application's communication pattern. For ease of implementation, the MPI_THREAD_MULTIPLE support is enabled by default when the detector thread is enabled; however, future software releases will drop this requirement. An intricate issue also arises from a negative interaction between the emission and the reception of heartbeat messages. In order to check the liveliness of the emitter process (after the δ timeout), the observer has to check if it has received heartbeats. From an implementation perspective, if the heartbeats are sent through the "eager" channel, the detector thread, which is the receive thread in this case, has to be active and poll the BTL engine for progress. However, if the application has posted operations on large messages, the poll operation may start progressing these (long) operations before returning control to the detector thread, leading to an unsafe delay in the emission of heartbeats from that same thread. To circumvent that difficulty, the detector thread emits heartbeats using the "RDMA put" channel. Heartbeats are thus directly deposited by raising a flag in the registered memory at the receiver, using hardware accelerated put operations that do not require active polling. The observer can then simply check that the flag has been raised during the last δ period with a local load operation, and reset the flag with a local store, which are mostly impervious to noise and do not delay the η period. This approach also allows the observer to miss δ periods without endangering the correctness of the protocol (only increasing the time to detect and notify the failure, but no triggering a false positive).

B. Experimental Conditions

The experiments are carried out on the Titan ORNL Supercomputer [START_REF] Titan | Oak Ridge National Laboratory[END_REF], a Cray XK7 machine with 16-core AMD Opteron processors and the Cray Gemini interconnect. The ULFM MPI implementation is based on a pre-release of OPEN MPI 2.x (r#6e6bbfd), which supports the optimized uGNI and shared-memory transports (without XPmem), and uses the Tuned collective module. The MPI implementation is compiled with the MPI_THREAD_MULTIPLE support. Every experiment is repeated 30 times and we present the average. The benchmarks are deployed with one MPI rank per core, and all threads of an MPI process are bound to that same core (application, detector, and driver threads when applicable, i.e., the detector thread does not require exclusive compute resources).

C. Noise and Accuracy

The first set of experiments investigate the noise generated by the detector and its accuracy for different workloads when η and δ vary, in a method similar to [START_REF] Kharbas | Assessing HPC Failure Detectors for MPI Jobs[END_REF] that focused exclusively on measuring the noise generated by different failure detection strategies. The η and δ periods are set so that δ = 10 × η. If the test is successful (that is, no failure was detected, since none was injected in this experiment), then η is reduced, and the experiment is repeated, until a false positive is reported. We also collect the number of times an η deadline was missed, even when the δ timeout is still respected. We first considered a non-communicative, compute-only MPI application where each rank calls LAPACK DGEMM operations on local matrices, without calling MPI routines for extended periods of time. Without the detector thread, the non-communicative benchmark reports false detections for all considered values of η.

With the detector thread, this non-communicative benchmark succeeds until η is set to one millisecond. However, starting from η < 5 milliseconds, messages indicating a missed η deadline are occasionally issued (although the δ timeout is still respected). These observations are consistent with the scheduling time quantums (sched_min_granularity is set to 3ms), and indicate that the thread scheduling latency is an absolute for the minimum η period. Smaller periods could be achieved with a real time scheduler, but such capabilities require administrative privileges, which is undesirable. Next, in Figure 6 we present the noise incurred on a variety of communication, and computation workloads, provided by the Intel MPI Benchmark (version 4.1), and HPL (version 2.2), respectively. Accuracy results are similar overall in the communicative benchmarks. All tests of the IMB-MPI1 suite can run without false detection for η ≥ 10ms. Notably, point-to-point only benchmarks can succeed with η value as low as 2.5ms but occasionally report false suspicions. Collective communication benchmarks are more sensitive and report occasional heartbeat emission deadline misses until η ≥ 25ms, due to contentions on the access to hardware network resources.

The latency performance (left graph) and bandwidth performance (center graph) are barely affected by low frequencies of heartbeat emissions. For higher frequencies, the overhead generated by the noise can reach approximately 10%. The bandwidth performance is less impacted overall than the latency, especially for point-to-point bandwidth, which remains unchanged for all but the most extreme values of η. The application performance (Linpack, right graph) exhibits no observable performance degradation for η ≥ 100ms. For higher frequencies, the performance degradation remains contained under 2%.

D. Failure Detection Time

Figure 7 presents the behavior observed when injecting failures. The first graph (left) presents the time to reach a stable state when injecting 1 to 8 failures for a varying number of nodes. After synchronizing, the desired number of MPI processes (whose ranks are chosen at random) simulate a failure. All other processes post an any-source reception. When the reception raises a process failure exception (the only possible outcome for this non-matched any-source reception), the process counts the number of locally known failed processes, and if it does not contain all injected failures, repeats the reception. The time at which all failures have been locally observed is reported at each rank. We observe that for small scales, the reported delay is consistently close to δ. If emitters were sending heartbeats to their observer at random starting time, we would expect the detection time to be closer to δ -η/2; however, as all processes start to sending heartbeats to their observer at the end of the MPI_Init function, they are almost synchronized, and for all runs we observe a consistent delay at small scale. At larger scale, processes leave MPI_Init at a more variable date, and the average starts to converge toward the theoretical bound. This observation matches the model, considering that in this scenario all failures are "simultaneous", and that the random allocation of failures has a low probability of hurting observer/emitter pairs. Consequently, the detection and propagation of each of these failures progresses concurrently and do not suffer from the cumulative effect of detecting multiple predecessors' failures on the ring.

The second experiment (center in Figure 7) investigates the effect of collisions on the reliable broadcast propagation delay. The benchmark is similar to the previous experiment, except that before a process simulates a failure, it sends its observer a special "trigger heartbeat", which initiates an immediate propagation reporting it dead, without waiting for the δ timeout. The rest of the observation protocol remains unchanged (i.e., heartbeats are exchanged between live processes with an η period, and the observer of the injection process switches to observing the predecessor). We then present the increase in the average duration of the reliable broadcast when multiple broadcasts are progressing concurrently. To simplify the proof of the upper bound on stabilization time (Theorem 1), we have considered that successive broadcasts are totally sequential. This is an admittedly pessimistic hypothesis, and indeed, performing two concurrent propagations does not significantly increase the delay, as the two reliable broadcasts can actually overlap almost completely. However, starting from 4, and, more prominently, for 8 concurrent broadcasts, the average completion time is significantly increased. Considering the small size of the messages, the bandwidth requirements are small, and contention on port access is indeed the major cause of the imperfect overlap between these concurrent broadcasts, therefore vindicating the importance of considering a portlimited model during the design of the failure detector and propagation algorithms.

The last experiment (right in Figure 7) presents the performance of the agreement algorithm after failures have been injected. The authors of [START_REF] Herault | Practical scalable consensus for pseudosynchronous distributed systems[END_REF] presented a similar performance result for their agreement algorithm. In their results, the agreement performance was severely impacted when failure were discovered during the agreement (with the failure free performance of 80µs increasing to approximatively 80ms), an effect the authors claim is due to failure detection overhead. In their work, failure detection was delegated to an ORTE based RAS service, responsible for detecting and propagating failures. In this experiment, we strive to recreate as closely as possible this setup, except that we deploy our failure detector in lieu of the ORTE RAS service. We consider the same implementation of the agreement, on 6,000 Titan cores (the same number of cores they deployed on the generally similar Cray XC30 Darter system). Some in-band detection capabilities are active, in particular, failure of shared-memory sibling ranks are reported by the node's local operating system. With the replacement of the ORTE RAS service by our failure detector algorithm, the time to completion of the agreement algorithm decreases to below 1.5ms (a 50x improvement). This is due to the faster propagation of failure knowledge among the agreement participants: instead of waiting for (long) inband timeouts or ORTE RAS notification, a process whose parent or children have failed can observe the condition much earlier, and start the on-line mending of the fan-in/fan-out tree topology at an earlier date. Interestingly, previously hidden performance issues become visible, as failure detection is not the dominant cost anymore: we observe that the performance of the agreement decreases linearly with the number of detected failures, a behavior that can be attributed to the agreement algorithm performing a linear scanning of the group when a failure is reported.

VI. RELATED WORK

In this section, we survey related work on failure detectors and then on fault-tolerant broadcast algorithms.

A. Failure detectors

A number of failure detection (FD) algorithms have been proposed in the literature. Most current implementations of FDs are based on an all-to-all communication approach where each node periodically sends heartbeat messages to all nodes. Because they consider a fully connected set of known nodes that communicate in an all-to-all manner, these implementations are not appropriate for platforms equipped with a large number of nodes. Several efforts have been made towards scaling up failure detectors implementations [START_REF] Bertier | Performance analysis of a hierarchical failure detector[END_REF], [START_REF] Larrea | Optimal implementation of the weakest failure detector for solving consensus[END_REF]. An alternative approach for implementing scalable failure detectors is to use gossip-like protocols where nodes randomly choose a few other nodes with whom they exchange their failure information [START_REF] Van Renesse | A gossip-style failure detection service[END_REF], [START_REF] Gupta | On scalable and efficient distributed failure detectors[END_REF], [START_REF] Hayashibara | Failure detectors for largescale distributed systems[END_REF], [START_REF] Horita | A scalable and efficient selforganizing failure detector for grid applications[END_REF], [START_REF] Tock | Design and implementation of a scalable membership service for supercomputer resiliency-aware runtime[END_REF]. Targeting HPC computations at scale, a scalable failure detector is propsoed in [START_REF] Katti | Scalable and fault tolerant failure detection and consensus[END_REF], based on observing random nodes and gossiping information. In their protocol, each ping message transmits information on all currently known failures, either via a liveness matrix or in compressed form.

Practically, gossip approaches bring along redundant failure information which degrades their scalability. Furthermore, the randomization used by gossip protocols makes the definition of timeout values difficult, since the monitoring sets change often over time. In order to eventually avoid false detections, these techniques tend to oversize their timeouts, which results in longer detection times. Theoretically, gossip approaches introduce random detection and propagation times, whose worst-case with a prescribed risk factor are hard to bound 3 . In contrast, our algorithm follows a deterministic detection and propagation topology with (i) constant-size heartbeats and well-defined delays, (ii) a single observer, (iii) a logarithmictime propagation, and (iv) a guaranteed worst-time to stabilization, thereby achieving all the goals of randomized methods with a deterministic implementation.

B. Fault-Tolerant Broadcast

Fault-tolerant broadcasting algorithms have been extensively studied, and we refer the reader to the surveys in [START_REF] Pelc | Fault-tolerant broadcasting and gossiping in communication networks[END_REF], [START_REF] Heydemann | Cayley graphs and interconnection networks[END_REF]. A key-concept is the fault-tolerant diameter of the interconnection graph, which is defined as the maximum length of the longest path in the graph when a given number of (arbitrarily chosen) nodes have failed [START_REF] Krishnamoorthy | Fault diameter of interconnection networks[END_REF]. The main objective in this context is to identify classes of overlay networks whose fault-tolerant diameter is close to their initial (faultfree) diameter, even when allowing a number of failures close to their minimal degree (allowing more failures than the minimal degree could disconnect the graph). Furthermore, these overlay networks should provide enough vertex-disjoint paths for broadcast algorithms to resist that many failures.

Research has concentrated on regular graphs (where all vertices have the same degree): hypercubes [START_REF] Krishnamoorthy | Fault diameter of interconnection networks[END_REF], [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF], [START_REF] Fraigniaud | Asymptotically optimal broadcasting and gossiping in faulty hypercube multicomputers[END_REF], binomial graphs [START_REF] Angskun | Binomial graph: A scalable and fault-tolerant logical network topology[END_REF] or circulant networks [START_REF] Liaw | Fault-tolerant routing in circulant networks and cycle prefix networks[END_REF]. For all these graphs, efficient broadcast algorithms have been proposed. These algorithms tolerate a number of failures up to their degree minus one, and execute within a number of steps (in the one-port model) that does not exceed twice their original diameter. However, to the best of our knowledge, such algorithms require the number of nodes in the graph to be a power of two, or a constant times a power of two, while we need an algorithm for an arbitrary number of nodes. This motivates our solution based upon a double diffusion (see Section II).

VII. CONCLUSION

Failure detection is a critical service for resilience. The failure detector presented in this work relies on heartbeats, timeouts, and communication bounds to provide a reliable solution that works at scale, independently of the type of faults that create permanent node failures. Our study reveals a complicated tradeoff between system noise, detection time, and risks: a low detection time would demand a low latency in the detection of failures, thus a tight approximation of the communication bound, increasing the risk of a false positive, and a frequent emission of heartbeat messages, increasing the system noise generated by the failure detector. We proposed a scalable algorithm capable of tolerating high frequency failures, and proved a theoretical upper bound to the time required to reconfigure the system in a state that allows new failures to strike; therefore the algorithm can tolerate an arbitrary number of failures, provided that they do not strike with higher frequency. The algorithm was implemented in a resilient MPI distribution, which we used to assess its performance and impact on applications at large scale. The performance evaluation shows that for reasonable values of detection time, the ring strategy for detection introduces a negligible or non-measurable amount of additional noise in the system, while the high performance reliable broadcast strategy for notification allows for quickly disseminating the fault information, once detected by the observing process.

Implementation considerations lead us to advocate that the detection part of the service should be provided at a lower levels of the software stack, either inside the operating system, or inside the interconnect hardware: active heartbeats to probe the activity of remote nodes could be handled by these lower levels without measurable noise, and with tighter bounds, since the other levels of the software stack would not introduce additional components to the noise. Future work should focus on providing this capability, and on evaluating the approach to address the tradeoff between detection time and risk.

  task T5: upon reception of BCASTMSG(dead, s, D) 33: D i ← D i ∪ {dead} 34: Send BCASTMSG(dead, s, D) to Neighbors(s, D) 35: end task 36: 37: function FindEmitter(D i ) 38: k ← emitter i 39: while k ∈ D i do 40: k ← (k -1) mod N 41:

Fig. 1 :

 1 Fig. 1: Segments of dead nodes after f = 3 failures: n = 9, k = 2, I 1 = {2, 3}, I 2 = {5}, d 1 = 2 and d 2 = 1.

τ + δ ≤ 2δ to detect the failure of 3 NO 4 Fig. 2 :

 342 Fig.2: From stable configuration C, growing segment I 1 of Figure1: first failure on node 3, next two failures striking its ring predecessors.

Fig. 4 :

 4 Fig. 4: Average Stabilization Time, when the maximal number of failures strike a platform of varying size in the scenario LOWNOISE (δ = 1min, τ = 1µs, η = 10s).

Fig. 5 :

 5 Fig. 5: Average Stabilization Time, with random overlapping failures in scenario LOWNOISE (δ = 1min, τ = 1µs, η = 10s), with µ ind = 1year.

Fig. 6 :

 6 Fig. 6: Sensitivity to noise resulting from the failure detector activity for varied workloads.

Fig. 7 :

 7 Fig. 7: Detection and propagation delay, and impact on completion time of fault-tolerant agreement operation.

TABLE I :

 I List of Notations.

Delay-bounded fault-tolerant broadcasts are not easily obtained for arbitrary values of n, see the discussion in Section VI-B.

Absolute worst-case times are infinite, as some nodes could be observed only after an unbounded delay. To give a simple example, after an observation round with n nodes randomly selecting their targets, in expectation, n/e nodes will not be observed (where e = 2.718 is Euler's number).


Cynthia Lavoie
email: lavoic@uqtr.ca

Georges Abdulnour
email: georges.abdulnour@uqtr.ca

How to recognize a creative SME?

Keywords: Creative enterprise, Creativity, SME, Small and Medium Size enterprise

In the actual knowledge-based economy, intangible assets are crucial. Those assets cannot be created without the creativity of the employees. Despite the phenomenal amount of works published on creativity, only a few are related to Small and Medium Enterprises (SME). Furthermore, a literature review made evident that a proper definition of what is a creative SME does not exist, even though it is important for practitioners, researchers and professionals in this domain. A definition of a creative SME needs to include external characteristics, ones that are easy to recognize from an observer's point of view. This research is thus trying to answer the following question: "How can we recognize a creative SME?" By using a Delphi with a group of experts, the researchers obtained a list of characteristics to recognize a creative SME. A case-study based research on internal factors that affect creative SME characteristics will follow.

Introduction

The human capital is a transforming driver of enterprises and is an integral part of their competitive advantage to build on. This capital must be created based on the creativity of the members of an organization.

Despite the incredible amount of literature written about creativity1 by professionals and academics, the researchers in the domain of creativity concentrated their work on large organizations. However, Small and Medium Enterprises (SME), like large organizations, are looking for more assets to be successful in building a competitive advantage based more and more on knowledge and obviously on creativity and innovation [START_REF] Raymond | L'entreprise-réseau : Dix ans d'expérience de la Chaire Bombardier Produits récréatifs[END_REF].

Some authors have addressed the issue of creativity in SME, but a clear distinction between a creative and a non-creative SME does not exist. Following this statement, the question that is addressed in the present research is: "What is a creative SME and how can we recognize it?" The answer to this question is important for researchers and practitioners in the field because researchers need dependant variables to study creativity, either in SMEs or in large organizations. For practitioners, it will be useful to know what to aim for as they put in place practices to increase creativity in their enterprises.

A literature review done by the authors on the subject revealed that, even for large organizations, researchers do not agree on a way to distinguish a creative enterprise from a non-creative one. Furthermore, according to what we know, of the few researchers that have tried to define a creative enterprise, none of them addressed the case of the SME. The term, "creative enterprise" is often used to distinguish cultural, high-tech or marketing firms and enterprises, but without presenting a concrete definition or specific characteristics.

The main objective of this paper is to get a list of external characteristics that will be used to recognize a creative SME. To fill up this objective, the collaboration of experts was requested. Following this, the results obtained will serve as an input for the next step, which consists in selecting a sample of creative SME to be included in a case study. The case study will allow to study different factors of the SME creativity.

In the following sections a literature review, the methodology, the results obtained, a discussion and a conclusion will be presented.

2

Literature review

2.1 Definitions of Creativity Definition of creativity has evolved in many areas: psychology, sociology, education, management, etc. In this particular research, the concept of creativity is studied in the context of organizations. [START_REF] Batey | Creativity, intelligence, and personality: A critical review of the scattered literature[END_REF] classified the definitions of creativity in four categories [START_REF] Batey | Creativity, intelligence, and personality: A critical review of the scattered literature[END_REF] : 1) New and useful. The definitions in this category include two characteristics: the product must be new and useful or adapted to reality; 2) Observable product. Here, the emphasis is put on the product obtained with creativity, which must be of quality and creative according to the evaluation of external observers; 3) Part of a process. Here, the creativity is seen as a part of a process, a problem resolution, an innovation or a mental process; 4) A set of components. In this last category, creativity is seen as a set of interrelated components. According to [START_REF] Mumford | Where Have We Been, Where Are We Going? Taking Stock in Creativity Research[END_REF], it seems that it exists a certain agreement around the following definition in the context of organization [START_REF] Mumford | Where Have We Been, Where Are We Going? Taking Stock in Creativity Research[END_REF]: Creativity consists of the production of new and useful ideas in a domain. Those ideas has to be qualified as such by observers who are familiar with the domain (T. [START_REF] Amabile | Assessing the work environment for creativity[END_REF].

Since the present work tries to study SME and their organizational context, a definition of a creative SME enterprise is required. In this context, definitions of organiza-tional creativity have to be taken into account. Organizational creativity is defined as the creation of a new, valuable and useful product, service, idea, procedure or process, by individuals who work together in a complex social system [START_REF] Moneta | Multirater assessment of creative contributions to team projects in organizations[END_REF][START_REF] Woodman | Toward a theory of organizational creativity[END_REF]. Creativity can also refer to the employees that use a diversified spectra of competencies, abilities, knowledge, views and experiments to generate new ideas for decision making, problem resolution and effective execution of tasks [START_REF] Cheung | Transformational leadership, leader support, and employee creativity[END_REF].

Those definitions are clear and useful for some kind of researches, but as the present research seeks to answer the question "How to recognize a creative enterprise?" it is difficult to do so without some precisions on the external characteristics of a creative enterprise.

2.2

Impacts of Creativity A creative enterprise will be influenced by organizational creativity, even though real impacts of creativity are not well documented. A review of impacts of creativity is therefore useful.

According to [START_REF] Amabile | Social psychology of creativity: A consensual assessment technique[END_REF], the creative performance of an enterprise can be measured in an external manner by the products or the accomplishments that can be observed as: "A product or response is creative to the extent that appropriate observers independently agree it is creative. Appropriate observers are those familiar with the domain in which the product was created or the response articulated. Thus, creativity can be regarded as the quality of products or responses judged to be creative by appropriate observers, and it can also be regarded as the process by which something so judged is produced" (T. M. [START_REF] Amabile | Social psychology of creativity: A consensual assessment technique[END_REF]. Furthermore, [START_REF] Pitta | Creating a culture of innovation at Portugal Telecom[END_REF] underlines that "The enterprises that cannot bring creativity and innovation in their daily tasks find that their failures are related to their weakness in establishing an appropriate culture and climate which value new ideas and this will decrease profits" [START_REF] Pitta | Creating a culture of innovation at Portugal Telecom[END_REF]. It means that an increase of creativity plays a role in the financial success of enterprises. For [START_REF] Heunks | Innovation, Creativity and Success[END_REF], this financial success is related to creativity only if innovation is present [START_REF] Heunks | Innovation, Creativity and Success[END_REF].

Actually, creativity is, for some researchers, considered as a component of innovation [START_REF] Wright | Creativity and innovation: A comparative analysis of definitions and assessment measures[END_REF] or as part of the innovation process [START_REF] Westwood | The multicultural muse: Culture, creativity and innovation[END_REF]. Innovation comes from creativity and then creativity is considered as "pre-innovation." Consequently, creativity leads to innovation [START_REF] Burbiel | Creativity in research and development environments: A practical review[END_REF].Considering that, a brief review of the impacts and measures of innovation can be taken into account to measure or recognize a creative enterprise.

2.3

Impacts and Measures of Innovation Aas and Pedersen (2010) suggest that management literature on innovation measures is a heterogeneous set of knowledge. Particularly, they highlight the work of [START_REF] Tidd | Innovation management in context: environment, organization and performance[END_REF], who suggests two classes of performance measurements: "(1) accounting and financial performance measures, and (2) market performance measures." [START_REF] Tidd | Innovation management in context: environment, organization and performance[END_REF] suggest that the impact of innovation is threefold, resulting in: (1) financial benefits, (2) increased customer value, and (3) strategic success [START_REF] Tidd | Innovation management in context: environment, organization and performance[END_REF].

On the other hand, [START_REF] Milway | Canada's innovation imperative: REPORT ON CANADA[END_REF], propose to measure innovation and the value it creates with the gross domestic product (GDP) per capita [START_REF] Milway | Canada's innovation imperative: REPORT ON CANADA[END_REF]. According to the Organization for Economic Co-operation and Development (OECD), innovation is a permanent process in continuous movement, which makes it difficult to measure. The OECD suggests some measurements that can be used such as: the impacts on the net sales, the impacts of the innovation process on costs and employment and the impacts of innovations on productivity (OCDE, 2005).

It is true that this offers some avenues on how to measure the impacts of creativity, however exploring the measures used in the literature on creativity is crucial in order to build a list of characteristics that allows to recognize a creative organization.

2.4

Creativity organizational measurements In the literature, the measurement of creativity on the organizational level is conducted by measuring some aspects of the organizational climate that are known to have an impact on creativity. KEYS, a tool conceived by Professor Amabile, is a tool commonly used to measure the stimulants and the obstacles of creativity in a work environment based on empirical researches and theories related to the creativity in organizations. It uses 78 items; 66 describing the work environment and 12 validating the performance at work evaluated according to creativity and productivity (T. [START_REF] Amabile | Assessing the work environment for creativity[END_REF].

The performance criteria presented in the KEYS can be used to measure organizational creativity in an "organization or a creative unit where a high creativity is needed and where people think they produce creative work." This measurement is a selfevaluation and consists of the following items: 1-My department is innovator; 2-My department is creative; 3-Globally, my actual work environment helps me to develop my own creativity; 4-A lot of creativity is needed in my day-to-day work; 5-Globally, my actual work environment helps me to develop my work group creativity; 6-I think I am really creative in my work. This tool can be used in a department, a division or a small organization, as long as the individuals in the group perceive the same work environment, because the perceived work environment makes a difference on the creativity level of the organization (T. [START_REF] Amabile | Assessing the work environment for creativity[END_REF].

To conclude, the characteristics provided in the literature are not specific and concrete to recognize creative SMEs among the other SMEs. In the following section, the methodology used to close the gap of the researches regarding SME creativity is presented.

Methodology and discussion

Following the literature review, the Delphi Method was used to elaborate a list of external characteristics of a creative SME. Then, the results obtained will serve as an input for the next step, which consists in selecting a sample of creative SME to be included in a case study. The case study will allow to test the effects of some factors on SME creativity.

The Delphi method was invented by [START_REF] Dalkey | The Delphi Method: An Experimental Study of Group Opinion[END_REF] of the RAND Corporation, in the 1960s. This method aims at refining the judgment of group members using questionnaires. Three elements are important in the Delphi Method: anonymous responses, iteration and controlled feedbacks, and statistical group responses. "These features are designed to minimize the biasing effects of the dominant individuals, irrelevant communications and of group pressure toward conformity" [START_REF] Dalkey | The Delphi Method: An Experimental Study of Group Opinion[END_REF]. In this study, all three features were respected. To ensure that, open questions were asked to make sure every expert had a chance to express his/her opinion. Two iterations were done in order to obtain a consensus among the experts.

Emails and web-based software (SurveyMonkey.com) were used to collect the data. On the first round, an email, including a brief introduction, a presentation of the researchers and the project and a link to the survey, was sent. On the second round, only a brief introduction and the link to the survey were sent. The details about the survey are presented in a following section, while a description of the respondents is presented in the next section.

The respondents

Criteria. The experts were chosen according to a list of criteria, developed by the researchers and evaluated in the first part of the survey. The different criteria included: expertise in defining creativity, knowledge on tools, techniques and success factors related to creativity, SME field experience and finally researcher on SME. The expert group had to include at least: 1 researcher in SME, 1 practitioner in SME, 1 researcher in creativity and 1 practitioner in creativity.

Evaluation. Seventeen experts were asked to answer the survey. Ten of them accepted to fill up the survey. Among this group of experts, nine out of ten who answered were kept according to the conformity of the answers. From those nine people, three were creativity experts, three were experts in creativity tools and techniques, two were experts in success factors of creativity, three were field SME practitioners and five were SME researchers. As for the group composition, three were researchers in SME, two were practitioners in SME, one was practitioner in creativity and three were researchers in creativity.

In the second round, ten people answered the revised and updated questionnaire.

From those ten respondents, nine were the same that answered in the first round and one was a new respondent.

Experts' qualification. According to their evaluation, eight out of nine people had at least one criteria evaluated as "expert in this domain" or "high knowledge of this domain". Furthermore, some of them had more than one criteria evaluated as "expert in this domain". The global results show that, in average, 22% of the participants consider having a high knowledge of the domain, and 34% think they are experts in these domains, for a total of 56%.

External Characteristics

First round. In the first round of the Delphi, the question asked on the external characteristics to the experts has to be answered on a 6-point scale basis.

Twenty external characteristics, based on the literature review, were given and the experts had to answer whether they believed those characteristics were appropriate to differentiate a creative enterprise from a non-creative one or not. For example, points like the "number of ideas implemented or commercialized in a time period" and the "originality of the ideas, according to a group of experts" were included.

Seven characteristics were chosen by the experts as characteristics being impacted by creativity in a SME:

• Turnover rate of ways to do things Second round. The purpose of the second round was to prioritize the list of external characteristics. The experts were then asked to prioritize the seven external characteristics that obtained the best score in the first iteration. The results show that the top characteristics to consider in recognizing a creative enterprise are: 1) Offer of distinctive products or services (not available at competitors); 2) Turnover rate of ways to do things, 3) Impact of the innovations on the targeted market.

Implications and Conclusion

Furthermore, the external characteristics will be useful for researchers in this research. Following this results, a case-study research will be conducted in order to study the detailed internal success factors or characteristics that will create a creative SME, recognized and measured with the external characteristics obtained in this part of the research. To select those cases to study, those external characteristics have to be detailed in an objective way to concretely qualify the enterprises. The following table show how each external characteristic has been transcribed in concrete measures by the authors to select the SMEs.

External characteristic

Objective measure 1) Offer of distinctive products or services (not available at competitors)

The products or processes of the enterprise must include at least one characteristic not available in their competitive market.

2) Turnover rate of ways to do things

The enterprise must have a process to improve its way to do things as a R&D department, suggestion system or continuous improvement system. The enterprise must have review at least a process or product in the last year.

3) Impact of the innovations on the targeted market The increase of market share related to an innovation has to be positive.

Even if creativity is a subject well studied in the literature, describing the external characteristics is an emerging, if not a new, research area to be investigated. Knowing the external characteristics of a creative enterprise, especially a SME, will lead enterprises to aim for those results as implementing practices to create a creative enterprise and will facilitate the work of researchers as they will know which dependant variables to use for their research.

Table 1 .

 1 Objective measures of external characteristics

More than 30 000 publications found in Scopus Database, on July

nd , 2014.