Nicolai Praestholm

Ann-Louise Andersen
email: annlou.andersen@gmail.com

Kjeld Nielsen

Thomas D Brunoe

Planning Nervousness in Product Segmentation: Empirical Analysis of Decision Parameters

Keywords: Planning, Nervousness, Product Segmentation 1

Previous research presents a theoretical relation between planning nervousness and product segmentation and indicates that the concept should be subject to further research. This paper seeks to empirically confirm this relation, by developing hypotheses and testing these on a specific case. Three hypotheses related to historical planning data, planning frequency, and demand variability are developed and tested using data from three-echelons in a case company. A key finding is a confirmation of the relationship, providing operational tools that can assist organizations in battling planning nervousness.

Introduction

In response to increased need for variety in products, supply chains need diverse operating strategies that can provide these responsively and cost-efficiently [START_REF] Fisher | What is the right supply chain for your product?[END_REF]. The variety of products is controlled through differentiated planning, where items are planned and controlled according to their characteristics. The segmentation of items is the core in differentiated planning, and thus the foundation for securing stable and effective planning processes. The objective of this paper is to investigate planning nervousness in relation to item segmentation, which is treated only to a limited extent in current research [START_REF] Andersen | Planning Nervousness in Product Segmentation: Literature Review and Research Agenda[END_REF]. Existing research on planning nervousness relate to specific planning contexts, primarily MRP and inventory systems, where nervousness is evaluated in connection to determining planning policy [START_REF] Carlson | Less nervous MRP systems a dynamic economic lot-sizing approach[END_REF]. However, as nervousness is a property of planning systems in general, this paper seeks to quantify a relationship between segmentation parameters and nervousness. This constitutes an improved foundation for decision-making, rather than merely relying on subjective intuition when handling nervousness problems in companies.

Planning Nervousness in Product Segmentation

Planning nervousness was introduced in the late 70's in order to describe instability and rescheduling of MRP plans in terms of quantity and timing [START_REF] Ho | Evaluating the impact of operating environments on MRP system nervousness[END_REF] [START_REF] Blackburn | A comparison of strategies to dampen nervousness in MRP systems[END_REF]. Later, the discussion of nervousness has broadened to cover multiple planning levels and enti-ties, highlighting that nervousness propagates horizontally within supply chains and vertically within planning systems [START_REF] Kaipia | Planning nervousness in a demand supply network: an empirical study[END_REF] [7] [START_REF] Genin | Improving the robustness of a supply chain tactical plan[END_REF]. As a result, nervousness can be defined as the counterpart to planning stability, which is defined as the situation where plans do not change and equal the actual requirements imposed on the planning system [START_REF] Pujawan | Schedule nervousness in a manufacturing system: a case study[END_REF]. A trade-off between responsiveness and nervousness exists, where frequent replanning results in more updated parameters and ability to respond to changing customer needs, while nervousness increases in relation to the transition from the original plan to the updated plan [START_REF] Schönberger | Schedule Nervousness Reduction in Transport Re-Planning[END_REF].

As nervousness propagates throughout planning levels, it is important to assess how product segmentation affects planning stability and provides a solid foundation for differentiated planning. In recent research, a tentative relationship between the two areas is proposed, based on the nervousness-responsiveness trade-off, where nervousness is defined as shifts in the assigned groups for specific products between two successive versions of the segmentation [START_REF] Andersen | Planning Nervousness in Product Segmentation: Literature Review and Research Agenda[END_REF]. In contrary, responsiveness relates to immediately and continuously updating segmentations based on changes in segmentation criteria e.g. demand variability or demand volume. The aim of this paper is to further investigate this relation and develop an assessable connection between three key segmentation criteria and nervousness. More specifically, historical planning data, planning frequency, and demand variability in relation to threshold values in the segmentation will be tested, as all three parameters were recognized as main influencers of nervousness in previous research [START_REF] Andersen | Planning Nervousness in Product Segmentation: Literature Review and Research Agenda[END_REF].

Hypotheses

Three hypotheses are developed to test the relationship between nervousness and segmentation. In all hypotheses, nervousness is defined in the context of segmentation, referring to the number of shifts in the assigned segments.

The first hypothesis is built on planning horizons, which is recognized as a key influencer on nervousness [START_REF] Pujawan | Schedule nervousness in a manufacturing system: a case study[END_REF]. However, as existing research focuses on MRP, MPS, and inventory contexts, planning horizon refers to the number of future time periods determined in the plan. The key notion is that when the planning horizon is prolonged, nervousness is mitigated [START_REF] Blackburn | A comparison of strategies to dampen nervousness in MRP systems[END_REF]. In a segmentation context, this concept of planning horizon do not apply, as it is merely a foundation for planning rather than an actual time-phased plan. Nevertheless, the planning horizon has a direct link with the length of historical data periods included, as longer planning horizons require more historical data as the planning foundation [START_REF] Silver | Inventory Management and Production Planning and Scheduling 3rd edn[END_REF]. This means that if the objective is to forecast or plan only on a short horizon, less data should be included than for longer horizons [START_REF] Vollmann | Manufacturing Planning & Control 6th edn[END_REF]. In a segmentation context, planning horizon can thus be compared to the number of periods in the segmentation data foundation. Therefore, the first hypothesis focuses specifically on the data foundation and its relationship to nervousness. The data foundation can be selected based on various reasons, but a relationship where the planning period constitutes a larger period when rolling the plan forward is expected to be more vulnerable to nervousness. This means that the more data that is included, the more nervousness is mitigated. This notion is encapsulated in the first hypothesis.

Hypothesis 1: As the number of historical data periods included in the segmentation is increased, nervousness is decreased.

The second hypothesis relates to the frequency of continuous segmentations. How often the segmentation is run, is expected to have a direct effect on nervousness in terms of segmentation changes. The notion of planning frequency impacting planning nervousness is already established and acknowledged in research on nervousness [START_REF] Sahin | Master production scheduling policy and rolling schedules in a two-stage make-to-order supply chain[END_REF] [14], but as in the former hypothesis, not in relation to segmentation. In this context, planning frequency refers to how often products are segmented and planning parameters re-calculated. A relationship is expected, as the possibility of excessive rescheduling is anticipated to increase with planning frequency.

Hypothesis 2: As the time between re-planning is increased, planning nervousness decreases.

The third hypothesis focuses on demand variability, often measured by the coefficient of variance. This is one of the most commonly used segmentation criteria and is expected to have an effect on nervousness in relation to the selected threshold values set through the segmentation. These values are the limits that separate segments from one another. Demand variability have been frequently mentioned in relation to nervousness [START_REF] Ho | Evaluating the impact of operating environments on MRP system nervousness[END_REF], but not considered in relation to the chosen threshold values. However, a relationship with low nervousness for both low and high values of demand variation and high for medium values is expected. This is based on the reasoning that low values of demand variability are stable enough to produce stable planning results with few shifts. Likewise, unstable products will also have few shifts, as they will always be treated as make-to-order. Hypothesis 3: Nervousness peaks if demand variability corresponds to the threshold values selected in the segmentation method.

Methodology

In order to test the hypotheses, demand data from a case company is applied. The case company is a Danish utility company with global reach that serves a variety of market segments ranging from domestic use to industrial application. Currently, the case company is introducing new supply chain planning processes, including a new process for item segmentation and assignment of control methods. The aim of this process is to balance inventories and secure product availability in response to pressure of reducing cost and increasing customer service.

The segmentation process at the case company consists of a classification of products to three different groups, two make-to-stock groups and one make-to-order group. More specifically, the three groups are denoted plan-based (P), consumptionbased (C), and order-based (O) and are named in accordance with their planning method. The segmentation is based on the number of order lines and the monthly demand coefficient of variance (CoV) of products, where P products have a CoV less than 0.3, C products have a CoV between 0.3 and 0.6, and O products have a CoV above 0.6. For simplicity, only the CoV's as a determinant for the segmentation is considered here.

In order to be able to empirically test the hypothesis, a specific supply chain at the case company is selected as the unit of analysis. This supply chain consists of three echelons: two supplying factories producing parts and assembly-ready-components, and one assembly site. All of the echelons are internally owned companies, but are separated in terms of management and planning activities.

In each of the three sites, 3-years of historic sales data is extracted for three part numbers belonging to different part types. The selection of part numbers is based on a combination of their initial segmentation and ranking on share of total sales volume. For instance, in the collection of a specific component type, the part number representing the median of the sorted sales volume data in both the P, C, and O group is selected, in order to increase how representative the tested part numbers are. For the finished products, part numbers are selected based solely on sales volume being high, medium, or low, due to lack of data foundation in regards to segmentation of finished products, but medians were likewise chosen. Median sampling is chosen to increase the generalizability of the results despite a relative small number of data points. In total, 24 part numbers representing different levels and types of sales is selected for the quantitative testing.

In order to test the three hypotheses, different assumptions are made. First of all, in all hypotheses nervousness needs to be quantified. As mentioned, nervousness is in this context defined as the number of shifts in overall segmentation, that is when a products shifts from being a plan-based (P) product to consumption-based (C) and order-based (O) product and vice versa.

In order to determine the category of each product, the CoV's are calculated on monthly buckets, with a specific number of months of historic sales included in the calculation and a varying planning frequency. Initially, hypothesis 1 and 2 regarding historical data periods and planning frequency are tested, as they represent a foundation for testing hypothesis 3. In each hypothesis, all part numbers are tested individually, but only the average results are presented and discussed in the following.

Results

Hypothesis 1

In order to test the relationship between the number of historical data periods and nervousness, varying amounts of historical data periods are tested with a constant replanning frequency of 1 month. In Figure 1, the average result for all part numbers is depicted. The expected relationship is a decreased number of shifts with an increased amount historical data periods.

As seen in Fig. 1., this hypothesis has strong empirical support. Moreover, there are indications that the relationship is exponentially decreasing, which mean that the benefits from increasing the amount of included historical data periods are considerable in the beginning and then decreases as more periods are included.

Hypothesis 2

In order to test the relationship between planning frequency and nervousness, varying planning frequencies are tested with a constant number of 6 months historical data points. In Figure 2, the average result of the testing is depicted. Again, there is empirical support for the hypothesis concerning a decrease in nervousness when planning frequency decreases. It may seem that planning frequency do not impact nervousness as strongly as the included historical data. However, the absolute number of planning shifts would have been considerably higher, if less than 6 months of historical data was applied. In other words, the absolute number of shifts is not as interesting as the relationship between the two tested parameters, which indicates an approximate decreasing exponential relation.

Hypothesis 3

In order to test the impact of the chosen threshold values in the segmentation, all the tested part numbers and their respective number of shifts and monthly CoV's are 3. The shifts are computed, as the average results for each part number that were used in Fig. 1 and Fig. 2.

In the segmentation approach applied in the testing of the hypothesis, the limits for the three different segments are CoV´s of 0.3 and 0.6. In the empirical test, it is seen that nervousness peaks for products that has demand variability similar to these threshold values. In particular, a peak in nervousness is indicated around a CoV of 0.6, which is the limit between consumption-based and order-based segments. In other words, products that have a natural demand variability close to the chosen threshold values is expected to have the highest number of shifts between segments. A natural consequence of this is that in order to reduce nervousness, threshold values that secure that the main part of products stays in between limits and not across and around the limits should be selected. This idea corresponds to the idea of clustering, where maximum between-segments variability and minimum within-segment variability is the goal, in order to make the segmentation as effective as possible [START_REF] Everitt | Clyster Analysis 4th edn[END_REF].

Discussion & Managerial Implications

With the data foundation from the case company, it is concluded that the three hypotheses can be accepted for this specific case. However, when considering the sparse data foundation and the fact that only one specific case supply chain is tested, the need for further testing is stressed. For instance, only 24 different part numbers have been tested, which even though they are selected as median representatives, only make up less than a 1 ‰ of the total number of part numbers in the tested supply chain. Therefore, it is suggested that future research should focus on empirically validating these hypotheses on a broader data foundation cutting across both organizations and industries.

Another point that should receive more attention is the criticality of shifts. In this paper, the number of shifts in the segmentation quantifies nervousness, where the criticality of shifts is overlooked. This criticality is perceived to have larger consequences if a product changes directly from being a P product to an O product, without transitioning through the C group. Therefore, it could be argued that some shifts are more intense than others, thereby causing increased nervousness. This should be ad- Validation of the three hypotheses implies that some degree of planning nervousness can be mitigated through changes in the product segmentation processes. As a result, it is expected that for this specific case, nervousness can be battled through changes in the segmentation setup. However, the objective of reducing nervousness by all means should be questioned, as this may create an inflexible setup with little emphasis on responsiveness. Therefore, nervousness reductions should always be considered in relation to the desired level of operational responsiveness. In this paper, only the mitigation of nervousness is considered, without measurable connections to responsiveness. However, nervousness should not be approached in a vacuum but must be addressed with emphasis both to the desired goals and the environment of the organization.

The confirmation of the hypotheses examined in this paper has led to findings on how the relationship between the amount of historical planning periods and planning frequency affects nervousness, and how it can be accelerated or alleviated through changes in the segmentation process. Additionally, the selection of threshold values poses a direct consequence on nervousness. A negative consequence is experienced if these threshold values are improperly chosen around the values. This outcome is seen as an initial step in operationalizing the measures causing and possibly mitigating planning nervousness within the process of segmentation. Nevertheless, no generalizable conclusions can be derived from this analysis, as the empirical evidence should be broadened, but indications strongly suggest a direct and controllable relationship between segmentation and planning nervousness.

Conclusion

The contribution of this paper should be seen as an initial step in the direction of explaining the relationship between nervousness and planning processes on a general level. Three hypotheses concerning key decision parameters within product segmentation have been established and tested for a specific case. The hypotheses are indented to operationalize the concept of nervousness, by allowing for quantitative evaluation of the amount of data periods included in the segmentation, the frequency of the segmentation, and the segmentation limits. In conclusion, it can be stated that for the case tested here, a relation between these segmentation parameters and planning nervousness exists. Evidence suggests that planning nervousness can be minimized through changes in the segmentation process. In other words, the degree of nervousness and planning instability experienced in companies can be controlled and is not solely determined by the incontrollable environmental factors. Though, it should be emphasized that in order to generalize the findings, these hypotheses should be tested on different cases in alternate environments. This paper therefore strengthens the field of knowledge-based production planning by operationalizing the concept of nervousness through establishing a direct relation between nervousness and product segmentation.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Test Results For Historical Data Periods

Fig. 3 .

 3 Fig. 3. Test Results for Threshold Values


Anubis G De

M Rossetto
email: anubisrossetto@gmail.com

Cláudio F R Geyer
email: geyer@inf.ufrgs.br

Luciana Arantes
email: luciana.arantes@lip6.fr

Pierre Sens
email: pierre.sens@lip6.fr

Implementing a flexible failure detector

Traditional unreliable failure detectors are per process oracles that provide a list of nodes suspected of having failed.

, we introduced the Impact failure detector that outputs a trust level value which is the degree of confidence in the system. An impact factor is assigned to each node and the trust level is equal to the sum of the impact factors of the nodes not suspected to have failed. An input threshold parameter defines an impact factor limit value, over which the confidence degree on the system is ensured. The impact factor indicates the relative importance of the process in the set S, while the threshold offers a degree of flexibility for failures and false suspicions. We propose in this article two different algorithms, based on query-response message rounds, that implement the Impact FD whose conceptions were tailored to satisfy the Impact FD's flexibility. The first one exploits the time-free message pattern approach while the second one considers a set of bounded timely responses. We also introduced the concept that a process can be P S-accessible (or ♦P S-accessible) which guarantees that the system S will always (or eventually always) be trusted to this process as well as two properties, P R(IT ) and P R(♦IT ), that characterize the minimum necessary stability condition of S that ensures confidence (or eventual confidence) on it. In both implementations, if the process that monitors S is P S-accessible or ♦P S-accessible, at every query round, it only waits (or eventually only waits) for a set of response that satisfy the threshold. A crucial facet of this set of processes is that it is not fixed, i.e., the set of processes can change at each round, which is in accordance with the flexibility capacity of the Impact FD.

Introduction

There are several important works in the literature concerning unreliable fault detectors (FDs). A FD can informally be seen as a per process oracle which, when invoked, provide information about processes liveness [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF].

In [START_REF] Rossetto | A failure detector that gives information on the degree of confidence in the system[END_REF], we introduced the Impact failure detector. In contrast with traditional unreliable failure detectors [START_REF] Chen | On the quality of service of failure detectors[END_REF] [START_REF] Bertier | Performance analysis of a hierarchical failure detector[END_REF] that output the set of nodes suspected of having failed, the Impact FD outputs a trust level concerning a given system S. The output can be considered as the degree of confidence in the system. To this end, an impact factor, that is defined by the user, is assigned to each node and the trust level is equal to the sum of the impact factors of the trusted nodes, i.e., those nodes not suspected of failure. Furthermore, an input threshold parameter defines an impact factor limit value, over which the confidence degree on S is ensured. Hence, by comparing the trust level with the threshold, a process p that monitors S knows whether the system is trusted or not.

We consider "trusted" the expectation that a system will behave in a particular manner for a specific purpose even in the face of failures, i.e., the system is able to maintain the normal functionality. The impact factor indicates the relative importance of the process in the set S, while the threshold offers a degree of flexibility for failures and false suspicions, thus allowing a higher tolerance of instability in the system. For instance, in an unstable network, although there might be many false suspicions, depending on the value assigned to the threshold, the system can remain trustworthy. [START_REF] Aguilera | Communication-efficient leader election and consensus with limited link synchrony[END_REF] Having the above characteristics, the Impact FD can be applied for systems that have the following features: [START_REF] Rossetto | A failure detector that gives information on the degree of confidence in the system[END_REF] applications that execute on them are interested on information about the reliability of the system as a whole and can tolerate a certain margin of failures. The latter may vary depending on the environment, situation, or context, such as systems that provide redundancy of software/hardware; [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF] systems that organize nodes with some common characteristic into groups; (3) systems where the nodes can have different importance (relevance) or roles and, thus, their failures may have distinct impact on the system. Among many, (1) wireless sensor networks (WSNs) that monitor environment conditions or (2) replicated servers that offer some quality of service (QoS) such as bandwidth or response time are two examples of systems where the Impact FD could be applied. In WSN used to collect environmental data, the monitored area can be divided into management zones in accordance with different characteristics. Each zone comprises sensors of different types (e.g., humidity control, temperature control, etc.) and the density of the sensors depends on the characteristics of each zone. That is, the number of sensors can be different for each type of sensor within a given zone. Furthermore, the redundancy of the sensors ensures both area coverage and connectivity in case of failure. Each management zone can thus be viewed as a single set which has sensors of the same type grouped into subsets. This grouping approach allows a threshold to be defined as being equal to the minimum number of sensors that each subset must have to keep the connectivity and application functioning all the time. In the second example, if the primary server that offers some quality of server fails, n backup servers could replace it, provided that this set of servers, together, offer the same (or higher) quality of service than the primary one. In such a scenario, the impact factor value of the main server or the sum of the impact factors of the backup servers must be greater or equal than the threshold value. If this holds, the system will always be trusted, offering the expected QoS.

We denote flexibility property the capacity of the Impact FD to tolerate a certain margin of failures or false suspicions, i.e., its capacity of accepting different set of responses that lead to a trusted state of S. Thus, this article presents two different implementations for the Impact FD tailored to satisfy the flexibility property. Both of them use query-response message rounds. The first one is based on the time-free message pattern approach [START_REF] Mostefaoui | Asynchronous implementation of failure detectors[END_REF] which does not assume bounds on process and communication delays but the relative speed among messages. A process p broadcasts a query message to the nodes of S that it monitors and then waits for responses from α processes or from a set Q of processes whose response satisfy the trust level. In the second approach, p can receive responses to its broadcast query from a set of processes within a bounded delay (timely responses).

We also defined two properties, P R(IT ) and P R(♦IT ), that characterize the minimum necessary stability condition of S that ensures confidence (or eventual confidence) on it. In other words, if P R(IT ) (resp., P R(♦IT )) holds, the system S is always (resp., eventually always) trusted for the monitor process p.

Inspired in [START_REF] Malkhi | meets paxos: Leader election and stability without eventual timely links[END_REF], we have introduced the concept that a process can be P S-accessible or ♦P S-accessible: a correct process p is P S-accessible (resp., ♦P S-accessible) if every query broadcast by p obtains from the beginning (resp., eventually) a set Q of responses that satisfy the degree of confidence in S, i.e., the trust level of S is greater or equal the threshold S value. In the case of the message pattern approach, this property implies that a query broadcast by p receives responses from a set of process Q which satisfy threshold S and these responses are always (resp., eventually always) winning responses, i.e., arrive before the other responses. In the case of the timer-based approach, there exists a set Q of processes that satisfy the threshold S and a query broadcast by p always (or eventually always) receives timely (i.e., within a known bounded delay) responses from each process of Q. Interestingly that, in both implementations the set Q of processes is not fixed, i.e., can be different at each query, which is in accordance with the flexibility property of the Impact FD.

This paper is structured as follows. Section 2 outlines some basic concepts of unreliable failure detectors while Section 3 describes the system model. Section 4 describes the Impact Failure Detector and its properties. Section 5 presents two algorithms for the implementation of the Im-pact FD as well as their proofs of correctness. In Section 6 we discuss some existing related work. Finally, Section 7 concludes the paper and outlines some of our planned future research work.

Unreliable Failure Detectors

An important abstraction for the development of fault tolerant distributed systems is the unreliable failure detector [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. The aim of the latter is to encapsulate the uncertainty of the communication delay between two distributed entities.

An unreliable FD can be seen as an oracle that gives (not always correct) information about process failures (either trusted or suspected). It usually provides a list of processes suspected of having crashed. In addition, a failure detection system consists of local modules in which each machine may monitor a group or subgroup of system processes, or even be monitored by other detectors.

According to [START_REF] Hayashibara | Two-ways adaptive failure detection with the φ-failure detector[END_REF], unreliable FDs are so named because they can make mistakes (1) by erroneously suspecting a correct process (false suspicion), or (2) by not suspecting a process that has actually crashed. If the FD detects its mistake later, it corrects it. For instance, a FD can stop suspecting at time t + 1, a process that it suspected at time t. Although the unreliable FDs can not accurately determine the real state of processes, using them increases knowledge about the processes of the system [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. This means that the aim of an unreliable FD is to encapsulate the uncertainty of the communication delay between two distributed entities.

Unreliable failure detectors are characterized by two properties, completeness and accuracy, as defined in [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. Completeness characterizes the failure detector's capability of suspecting faulty processes, while accuracy characterizes the failure detector's capability of not suspecting correct processes, i.e., restricts the mistakes that the failure detector can make. FDs are then classified according to two completeness properties and four accuracy properties [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF].

Notice that the type of accuracy depends on the synchronism or stability of the network. For instance, a strong accuracy requires a synchronous system while an eventual strong one relies on a partially synchronous system which eventually ensures a bound for message transmission delays and processes' speed.

Implementation of Failure Detectors

The literature has several proposals for implementing unreliable failure detectors which usually exploit either a timer-based or a message-pattern approach.

In the timer-based strategy, FD implementations make use of timers to detect failures in processes. Every process q periodically sends a control message (heartbeat) to process p that is responsible for monitoring q. If p does not receive such a message from q after the expiration of a timer, it adds q to its list of suspected processes.

The message-pattern strategy does not use any mechanism of timeout. In [START_REF] Mostefaoui | Asynchronous implementation of failure detectors[END_REF], the authors propose an implementation that uses a request-response mechanism. A process p sends a QU ERY message to n nodes that it monitors and then waits for responses (RESP ON SE message) from α processes (α ≤ n, traditionally α = n -f , where f is the maximum number of failures). A query issued by p ends when it has received α responses. The other responses, if any, are discarded and the respective processes are suspected of having failed. A process sends QU ERY messages repeatedly if it has not failed. If, on the next request-response, p receives a response from a suspected process q, then p removes q from its list of suspects. This approach considers the relative order for the receiving messages and that one (or a set of nodes) always (or after a time) answers faster to the QU ERY than the other nodes.

System Model

In this work, we consider that there is one process by node (site) or sensor. Thus, the word process can mean either a node, a sensor, or a site. We consider a distributed system which consists of a finite set1 of processes S = {q 1 , . . . , q n } with |S| = n.

Processes communicate by sending and receiving messages over bi-directional reliable links, i.e., they do not lose, duplicate or corrupt messages and they never generate spurious messages.The network is assumed to be fully connected, i.e., Λ = (p, q)|p, q ∈ S.

The system model is asynchronous. It is important to point out that an asynchronous system is characterized by the absence of bounds on process speed and message delay. As result, it is impossible for a process to distinguish a crashed process from a process that is slow or a process which communication is slow. Thus, for the two proposed implementations, the asynchronous system is enriched with new assumptions about synchrony of the links or the relative speed among.

Processes fail by crashing and do not recover. We define a correct process the one which never fails during the whole execution; otherwise it is faulty. We assume the existence of some global time denoted T . A failure pattern is a function F : T → 2 S , where F (t) is the set of processes that have failed before or at time t. The function correct(F ) denotes the set of correct processes, i.e., those that have never belonged to a failure pattern (F ), while f aulty(F ) denotes the set of faulty processes, i.e., the complement of correct(F ) with respect to S.

Besides S, we consider a correct process p (p ∈ correct(F )) that monitors S.

Impact Failure Detector

The Impact FD can be defined as an unreliable failure detector that provides an output related to the trust level with regard to a set of processes. If the trust level provided by the detector, is equal to, or greater than, a given threshold value, defined by the user, the confidence in the set of processes is ensured. We can thus say that the system is trusted. We denote FD (I p S ) the Impact failure detector module of process p that monitors system S. When invoked in p, the Impact FD (I p S ) returns the trust level p S value which expresses the confidence that p has in the set S.

Each process q ∈ S has an impact factor ( I q |I q > 0 : I q ∈ R ). Furthermore, set S can be partitioned into m disjoint subsets. Notice that the grouping feature of the Impact FD allows the processes of S to be partitioned into disjoint subsets, in accordance with a particular criterion. For instance, in a scenario where there are different types of sensors, those of the same type can be gathered in the same subset. Let then S * = {S * 1 , S * 2 , ...S * m } be set S partitioned into m disjoint subsets where each S * i is a set composed of the tuple id, impact , where id is a process identifier and impact is the value of the impact factor of the process in question.

S * = {S * 1 , S * 2 , ...S * m } is a set of processes of such that ∀i, j, i = j, S * i ∩ S * j = ∅ and {q| q, ∈ S * i ; 1 ≤ i ≤ m} = S We denote trusted p S (t) = {trusted 1 (t), . . . , trusted m (t)}, where each trusted i (1 ≤ i ≤ m) contains the processes of S * i that are not considered faulty by p at t ∈ T . Similarly to S * i , each trusted i is composed of the tuple id, impact .
The

trust level at t ∈ T of processes p / ∈ F (t) of S is the denoted trust level p S such that trust level p S (t) = {trust level i |trust level i = sum(trusted i (t)); 1 ≤ i ≤ m}
where the function sum(subset) returns the sum of the impact factor of all the elements of subset. In other words, the trust level p S is a set that contains the trust level of each subset of S * expressing the confidence that p has in S.

An acceptable margin of failures, denoted as the threshold S , characterizes the acceptable degree of failure flexibility in relation to set S. The threshold S is adjusted to the minimum trust level required for each subset. i.e., it is defined as threshold S = {threshold 1 , . . . , threshold m }

The threshold S is used by the application to check the confidence on the processes of S. If, there is s subsets of S * such that the trust level i (t) ≥ threshold i (1 ≤ i ≤ m), S is considered to be trusted at t by p, i.e., the confidence of p in S has not been compromised; otherwise S is considered not trusted by p at t.

Two points should be highlighted: (1) both the impact factor and threshold S render the estimation of the confidence in S flexible. For instance, it is possible that some processes in S might be faulty or suspected of being faulty but S can still be trusted; (2) the Impact FD can be easily configured to adapt to the needs of the environment. The threshold S can be tuned to provide a more restricted or softer monitoring.

In Table 1, we consider a set S, where S * is composed by three subsets: S 1 , S 2 , and S 3 (S * = {{ q 1 , 1 , q 2 , 1 , q 3 , 1 }, { q 4 , 2 , q 5 , 2 , q 6 , 2 }, { q 7 , 3 , q 8 , 3 , q 9 , 3 }}). The values of threshold S define that the subsets S 1 , S 2 and S 3 must have at least two correct processes. The table shows several possible outputs for FD (I p S ): the set S is considered trusted whenever, for each subset S * i , trust level i (t) ≥ threshold i .

1 {q2} {{ q1, 1 , q3, 1 }, { q4, 2 , q5, 2 , q6, 2 }, { q7, 3 , q8, 3 , q9, 3 }} {2, 6, 9} Trusted 2 {q2, q5} {{ q1, 1 , q3, 1 }, { q4, 2 , q6, 2 }, { q7, 3 , q8, 3 , q9, 3 }} {2, 4, 9} Trusted 3 {q2, q5, q6} {{ q1, 1 , q3, 1 }, { q4, 2 }, { q7, 3 , q8, 3 , q9, 3 }} {2, 2, 9} Not Trusted S * = {{ q 1 , 1 , q 2 , 1 , q 3 , 1 }, { q 4 , 2 , q 5 , 2 , q 6 , 2 }, { q 7 , 3 , q 8 , 3 , q 9 , 3 }} threshold S = {{2, 4, 6}}

Flexibility of the Impact FD

The flexibility of the Impact FD characterizes its capacity of accepting different set of responses that lead to a trusted state of S. Let P S be the set that contains all possible subsets which satisfy a defined threshold:

P S = T P owerSet(S, threshold)|T P owerSet(S, threshold) = × P owerSet(S i , threshold i )
Initially, the TPowerSet function generates the power set 2 for each subset (S i ) of S. Then, only the subsets of S i whose sum of their parts is greater than, or equal to, threshold i are selected. Following this, the Cartesian product is applied to generate all possible combinations 3 , i.e., all the subsets generated satisfy the threshold S .

Let's consider the following example:

S * = {{ q 1 , 1 , q 2 , 1 }, q 3 , 1 , q 4 , 1 }, { q 5 , 1 , q 6 , 1 }} threshold S = {1, 1, 1} P S = T P owerset(S * , threshold S ) PowerSet(S * 1 , threshold 1 ) = {{ q 1 , 1 }, { q 2 , 1 }, { q 1 , 1 , q 2 , 1 }} PowerSet(S * 2 , threshold 2 ) = {{ q 3 , 1 }, { q 4 , 1 }, { q 3 , 1 , q 4 , 1 }} PowerSet(S * 3 , threshold 3 ) = {{ q 5 , 1 }, { q 6 , 1 }, { q 5 , 1 , q 6 , 1 }} PS = PowerSet(S * 1 , threshold 1 ) × PowerSet(S * 2 , threshold 2 ) × PowerSet(S * 3 , threshold 3 ) PS = PowerSet(S * 1 , threshold 1 ) × PowerSet(S * 2 , threshold 2 ) × PowerSet(S * 3 , threshold 3 ) PS = {{{ q 1 , 1 }, { q 3 , 1 }, { q 5 , 1 }}, {{ q 1 , 1 }, { q 3 , 1 }, { q 6 , 1 }}, {{ q 1 , 1 }, { q 3 , 1 }, { q 5 , 1 , q 6 , 1 }}, {{ q 1 , 1 }, { q 4 , 1 }, { q 5 , 1 }}, {{ q 1 , 1 }, { q 4 , 1 }, { q 6 , 1 }}, {{ q 1 , 1 }, { q 4 , 1 }, { q 5 , 1 , q 6 , 1 }}, {{ q 1 , 1 }, { q 3 , 1 , q 4 , 1 }, { q 5 , 1 }}, {{ q 1 , 1 }, { q 3 , 1 , q 4 , 1 }, { q 6 , 1 }}, {{ q 1 , 1 }, { q 3 , 1 , q 4 , 1 }, { q 5 , 1 , q 6 , 1 }},. . . }
2 the power set of any set S is the set of all subsets of S, including the empty set and S itself 3 The ×S i is a means of abbreviating the Cartesian Product when there are several sets, e.g.

S * 1 , S * 2 , S * 3 (X = (S * 1 ) × (S * 2 ) × (S * 3 ) )
For instance, if trusted p S (t 1 ) = {{ q 1 , 1 }, { q 3 , 1 }, { q 5 , 1 }} and trusted p S (t 2 ) = {{ q 1 , 1 }, { q 3 , 1 , q 4 , 1 }, { q 6 , 1 }}, p considers that the system S is trusted at both t 1 and t 2 .

Some properties

Similarly to many existing works (see Section 6), we define some properties and process/link behaviors in order to introduce some synchrony on the asynchronous system.

Considering the set P S, which characterizes the flexibility of the Impact FD, we define the following properties:

Impact Threshold Property -PR(IT): For a failure detector of a correct process p, the set trusted p S is always a subset of P S.

P R(IT

) ≡ p ∈ correct(F ), ∀t ≥ 0, trusted p S (t) ⊂ P S
Eventual Impact Threshold Property -PR(♦IT ): For a failure detector of a correct process p, there is a time after which the set trusted p S is always a subset of P S.

P R(♦IT ) ≡ ∃t ∈ T, p ∈ correct(F ), ∀t ≥ t, trusted p S (t ) ⊂ P S

If P R(IT ) (resp., P R(♦IT ) ) holds, the system S is always (resp., eventually always) trusted by p.

Inspired by the concept that a process is ♦f -accessible proposed in [START_REF] Malkhi | meets paxos: Leader election and stability without eventual timely links[END_REF] (see Section 6), we also define the concept of a P S-accessible and a ♦P S-accessible process:

A process p ∈ correct(F ) is P S-accessible (resp., ♦P S-accessible) if every QU ERY message broadcast by p obtains from the beginning (resp., eventually) a set Q of responses that satisfy the threshold S . Thus, if p is P S-accessible (resp., ♦P S-accessible), P R(IT ) (resp., P R(♦IT ) ) holds for p.

We have then the following definitions for the message pattern and timer-based approaches:

Message-pattern approach: Given a query issued by p, the set of first RESP messages received by p to this query are denoted winning responses [START_REF] Mostefaoui | Asynchronous implementation of failure detectors[END_REF], [START_REF]Eventual leader service in unreliable asynchronous systems: Why? how?[END_REF].

A process p is P S-accessible (resp., ♦P S-accessible) if for τ 0 ≥ 0 (resp., ∃τ 0 , ∀τ ≥ τ 0 ) there exists a set Q of processes such that Q ∈ P S and p / ∈ Q(τ ) and a QU ERY message broadcast by p at τ receives RESP messages from processes of Q(τ ) and these responses are always (resp., eventually always) winning responses.

Timer-based approach: A process p ∈ correct(F ) is P S-accessible (resp., ♦P S-accessible) if for τ 0 ≥ 0 (resp., ∃τ 0 , ∀τ ≥ τ 0 ) there exists a set Q of processes such that Q ∈ P S and p / ∈ Q(τ ) and a QU ERY message broadcast by p at τ receives a RESP message from each process of Q(τ ) by time τ + δ.

We should point out that in both definitions of P S-accessible and ♦P S-accessible, the set Q(τ ) is not fixed and can be different at distinct times which is in accordance with the flexibility property of the Impact FD.

Implementations of Impact FD

In this section we present two different implementations of the Impact FD: the first one is based on the messagepattern approach and the second one on the timer-based approach. Both of them use query-response message rounds and were conceived to exploit the flexibility capacity of the Impact FD.

We consider that the monitor process p ∈ correct(F ) and p / ∈ S. It repeatedly issues queries by calling the primitive broadcast(m) which sends a copy of the QU ERY message over every link from p to q, ∀q ∈ S. At each new round, p broadcasts a QUERY message. The time interval between two consecutive rounds is finite and arbitrary (resp., bounded) for the message pattern (resp., timer-based) implementation. When process q receives a QUERY message from p, q confirms its reception with a RESP message.

The following local variables are used in both algorithms:

• r p : round counter of process p;

• trusted: it is the set formed by {trusted 1 , . . . , trusted m } (m the number of subsets of S), where each trusted i (1 ≤ i ≤ m) contains the processes of S i that are not considered faulty by p. Each trusted i is a set composed of the tuple id, impact , where id is the process identifier and impact is the value of the impact factor of the process that belongs to the subset trusted i . • trust level: the set that contains the trust level of each subset of processes; • PS: the set comprising all possible subsets formed by processes of S, where the sum of its elements is greater than, or equal to, the threshold S .

We also defined the function Add() which is used in both algorithms:

• Add(set, subset, q, impact ): function that adds the process q, with impact factor impact to the subset subset of the set set provided that q is not already in subset.

Message-pattern Implementation

Algorithm 1 presents the message pattern approach implementation of the Impact FD of process p with respect to S.

Process p receives as input the set of process of the system S, the number of subsets of S * (m), the threshold value of each subset of S * (the set threshold S * ) and the maximum number of messages to wait (α). The latter is a set α = {α 1 , . . . , α m }, where each α i corresponds to a threshold value for the number of messages to wait from the processes of subset S * i . For instance, if f i denotes the maximum number of failures of processes of subset S * i ,

α i ≤ |S * i | -f i (for i = 1 to m).
Algorithm 1 Message pattern implementation for i = 1 to m do for each subset 5:

trusted i ← S i 6:
tmp trusted i ← ∅ 7:

trust level i ← ∅ 8:
end for 9:

P S ← T P owerSet(S, threshold S * ) Task T1 Upon reception of (RESP, r, I q , subset q ) from q do 20:

if r = r p then 21:

Add(tmp trusted, subset q , q, I q ) Upon reception of (QU ERY, r p ) from p do 31:

send(RESP, r p , I q , subset q ) to p 32: end 33: End

The algorithm has four tasks. Tasks T1, T2, and T3 are executed by p, while T4 is executes by q ∈ S.

At the initialization, trusted is initialized with the nodes of S. Then, the function T P owerSet is carried out to generate the set P S which contains all possible subsets formed by processes of S that satisfy the threshold S * . The variable tmp trusted, at every query round, gathers the identification of processes that answered to the current query.

Task T1 of p has an infinite loop. Firstly it sends the message (QUERY, r p ) to all processes of S (line 11). Then, at each round (r p ), p waits for at least α i responses (1 ≤ i ≤ m) or until tmp trusted is a subset of P S (i.e., contains processes that satisfy the threshold S * ) (line 12). Finally, the round counter (r p ) is incremented (line 17).

Task T2 handles the reception of messages (RESP, r, I q subset q ) sent by q. The message contains the round, the impact factor and the subset to which q belongs. If round r is equal to r p , then q is added to the trusted q set. Task T3 handles the invocation of the Impact() function (line 24), which computes the trust level of each subset and returns the trust level of the trusted processes (line 28).

Task T4 is responsible for the reception of messages QUERY by process q ∈ S. When q receives a (QUERY, r) message from the monitor process p (line 30), q must respond with a RESP message containing the round, its impact factor, and the number of its subset (line 31).

Sketch of Proof

Lemma 1. Process p never blocks forever in a queryresponse round.

Proof. The only point that p could block forever would be in the wait statement of Task T1 (line 12).

Let's consider round r p and that the system is blocked in the wait statement. Let's also suppose that the system is trusted in round r and that the set of nodes included in tmp trusted by Task T2 within round r p are also included in P S. In this case, the second condition of the wait becomes true and T 1 will not block. Let's now suppose that p is blocked on thewait statement and that the second condition does not hold, i.e., p will not be unblocked because of it. However, for every subset S * i , p waits for α i messages (1 ≤ i ≤ m), where f i is the maximum number of processes of S * i that can fail and α i ≤ |S * i | -f i . Therefore, as the channels are reliable and, even if f i nodes of each S * i have failed, p will receive α i responses which will render the first condition true, and p will be unblocked. In other words, since α i is bounded by n and f i and no query or response messages are lost, such a condition always ensures the progress of the failure detector.

Lemma 2. At every query r p issued by p, trusted p is updated.

Proof. From Lemma 1, Task 1 never blocks and, thus, line 13 is always executed. This line is the only point where trusted is updated after initialization (line ??). Hence, at every query round, trusted p is updated.

Lemma

3. If p is P S-accessible (resp., ♦P S-accessible), Algorithm 1 ensures that P R(IT ) (resp., P R(♦IT )) holds for p.

Proof. For t = 0, trusted p = S. Let Q(r) be the set of winning responses and r 0 be the first round where Q(r 0 ) ∈ P S. Thus, for r 0 , trusted = tmp trusted ⊆ P S. Let then consider that ∀r ≥ r 0 , Q(r) ∈ P S which characterize the P S -accessibility of p. In this case, since from Lemma 2, trusted is updated at every query round, trusted = tmp trusted ⊆ P S. Let t be the time when trusted is updated in round r 0 (line ?? or line 13). Therefore, ∀t ≥ t, when the impact FD is invoked, P R(IT ) (resp., P R(♦IT )) holds.

Theorem

1. If p is P S-accessible (resp., ♦P S-accessible), ∀t ≥ 0 (resp. ∃t ∈ T, ∀t ≥ t), trust level(t) p ≥ threshold.

Proof. The proof follows directly from Lemma 3.

Timer-based Implementation

Algorithm 2 shows a timer-based implementation of the Impact FD of process p with respect to S.

For this implementation we added the assumption that there exists a known upper bound δ on the round-trip delay of messages, but it might not hold on all pairs of processes at all times. If p ∈ correct(F ) is P S-accessible (resp., ♦P S-accessible) it always (resp. eventually always) receives RESP messages from a set Q of processes Q ∈ P S, in a delay of time smaller than δ.

Process p monitors the processes of S and receives as input the set S, the number of subsets m, the threshold S * , the interval time (∆ > δ) to send the broadcast message and the upper bound on the round-trip delay of messages (δ) for timely links.

The algorithm has five tasks. Tasks T1, T2, T3, and T5 are executed by p, while T4 is executes by q ∈ S.

At the initialization, each subset of trusted and trust level is initialized as empty (lines 3 -4). Then, the function T P owerSet is carried out to generate the set P S which contains all possible subsets formed by processes of S that satisfy the threshold S * (line 7). The variables r p , and timer timeout are also initialized.

At every round r p , Task T1 of p reset tmp trusted and increments the round counter (lines 10-13). Periodically (interval of ∆ time units), process p sends to the processes in S a QU ERY message (line 14) and starts the timer timeout (line 15).

In Task T2, when process p receives a RESP message sent by q, if round r is equal to r p and q is not in tmp trusted, q is added to tmp trusted (lines [START_REF] Anta | From an asynchronous intermittent rotating star to an eventual leader[END_REF][START_REF] Arantes | Eventual leader election in evolving mobile networks[END_REF]. At this point, if tmp trusted is a subset of P S (i.e., contains processes that satisfy the threshold S * ) (line 20), then the variable tmp trusted is assigned to trusted and the timeout is stopped.

Task T3 and T4 are the same of Algorithm 1 : task T3 handles the invocation of the Impact() function by p, which returns the sum of impact factor of the trusted processes (line 25); in Task T4, process q ∈ S receives a (QUERY, r) message from p (line 31), q answers with a RESP message containing the the round, its impact factor, and the number of its subset (line 32). for i = 1 to m do for each subset 4:

trusted i ← ∅ 5:
trust level i ← ∅ 6:

end for 7:

P S ← T P owerSet(S, threshold S * ) 8:

r p ← -1 9:
timeout ← δ Task T1 -Repeat forever every ∆ time unit 10:

for i = 1 to m do for each subset 11:

tmp trusted i ← ∅ 12:
end for 13:

r p ← r p + 1 14:
broadcast(QU ERY, r p )

15:

start timeout Task T2

16:

Upon reception of (RESP, r, I q , subset q ) from q do 17:

if r = r p then 18:
Add(tmp trusted, subset q , q, I q ) Upon reception of (QU ERY, r p ) from p do 32:

send(RESP, r p , I q , subset q ) to p end 37: End Upon expiration of the timer timeout (Task T4), p assigns its current knowledge about trusted processes (in tmp trusted) to trusted.

Sketch of Proof

Lemma 4. At every query r p issued by p, trusted p is updated.

Proof. At every new query rp in task T1, p starts a timer (line 15). As ∆ > δ, a new query will not be issued before the timer expires or is stopped. If the set of Q messages received for this query are such that Q ∈ P S, the timer is stopped and trusted p = Q by Task T2 (lines 21 -22). Otherwise, the timer will expires (Task T5) and trusted p will be updated with the set of processes that sent RESP messages to p (line 35) within a delay of δ .

Lemma

5. If p is P S-accessible (resp., ♦P S-accessible), Algorithm 2 ensures that P R(IT ) (resp., P R(♦IT )) holds for p.

Proof. From Lemma 4, trusted p is updated at every query. Let t 0 ∈ T be the time where for every query issued by p at t ≥ t 0 , a QU ERY message broadcast by p at t receives a RESP message from processes of a Q(t) ∈ P S within t+δ. In this case, the timer started in every query at line 15 will never expire and, therefore, line 21 will be never executed ∀t ≥ t. On the other hand, since Q(t) ∈ P S, the test of line 20 is always true. Hence ∀t ≥ t,, when the impact FD is invoked P R(IT ) (resp., P R(♦IT )) holds for p.

Theorem

2. If p is P S-accessible (resp., ♦P S-accessible), ∀t ≥ 0 (resp. ∃t ∈ T, ∀t ≥ t), trust level(t) p ≥ threshold.

Proof. The proof follows directly from Lemma 5.

Related Work

We can divide related studies of the literature into two groups: (1) unreliable failures detectors and (2) works which consider additional assumptions for asynchronous systems.

Unreliable failure detectors: Most of the unreliable fault detectors in the literature are based on a binary model and provide as output a set of process identifiers, which usually informs the set of processes currently suspected of having failed ( [2] [4]). However, in some detectors, such as class Σ (resp., Ω) [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF], the output is the set of processes (resp., one process) which are (resp., is) not suspected of being faulty, i.e., trusted.

The φ Accrual failure detector [START_REF] Hayashibara | The ϕ accrual failure detector[END_REF] proposes an approach where the output is a suspicion level on a continuous scale, rather than providing information of a binary nature (trusted or suspected). It is based on an estimation of inter-arrival times which assuming that the latter follow a normal distribution. The suspicion level captures the degree of confidence with which a given process is believed to have crashed. If the process actually crashes, the value is guaranteed to accrue over time and tends toward infinity. In [START_REF] Satzger | A new adaptive accrual failure detector for dependable distributed systems[END_REF], the authors extended the Accrual FD by exploiting histogram density estimation. Taking into account a sampled inter-arrival time and the time of the last received heartbeat, the algorithm estimates the probability that no further heartbeat messages arrive from a given process, i.e., it has failed. The aim of Accrual failure detectors is to decouple monitoring from interpretation.

Starting from the premise that applications should have information about failures to take specific and suitable recovery actions, the work in [START_REF] Leners | Improving availability in distributed systems with failure informers[END_REF] proposes a service to report faults to applications. The latter also encapsulates uncertainty which allows applications to proceed safely in the presence of doubt. The service provides status reports related to fault detection with an abstraction that describes the degree of uncertainty.

Considering that each node has a probability of being byzantine, a voting node redundancy approach is presented in [START_REF] Brun | Smart redundancy for distributed computation[END_REF] in order to improve reliability of distributed systems. Based on such probability values, the authors estimate the minimum number of machines that the system should have in order to provide a degree of reliability which is equal to or greater than a threshold value.

In [START_REF] Véron | Repfd-using reputation systems to detect failures in large dynamic networks[END_REF], the authors propose the use of a reputation mechanism to implement failure detectors for large and dynamic networks. The reputation mechanism allows node cooperation through the sharing of views about other nodes. The proposed approach exploits information about the behavior of nodes to increase its quality in terms of detection. When classifying the behavior of the nodes, it includes a reputation service where the nodes periodically exchange heartbeat messages.

Additional assumptions for asynchronous systems: Several works have tried to circumvent the impossibility of the consensus in pure asynchronous systems in the presence of failures [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]. Therefore, the challenge is to identify properties that can be satisfied "nearly always" by the underlying asynchronous system enriched by some assumptions which allow an algorithm, for instance Ω (which can then be used to solve consensus in a system with a majority of correct processes) to be implemented during the "periods" in which the properties are satisfied [START_REF] Anta | From an asynchronous intermittent rotating star to an eventual leader[END_REF].

The Message Pattern approach does not assume eventual bounds on process and communication delays. In [START_REF] Mostefaoui | Asynchronous implementation of failure detectors[END_REF], the authors consider that there is a correct process p and a set Q of f processes (with p / ∈ Q, moreover, Q can contain crashed processes) such that, each time a process q ∈ Q broadcasts a query, it receives a response from p among the first (n -f ) corresponding responses (such a response is called a winning response). Note that this assumption does not prevent message delays from always increasing without bound. This approach has been applied to the construction of a leader protocol.

Aguilera et al. introduced the ♦f -source assumption in [START_REF] Aguilera | Communication-efficient leader election and consensus with limited link synchrony[END_REF] aiming at providing communication-efficient leader and consensus protocol implementations. In a system with n nodes and up to f process can crash, a ♦f -source node p is a correct node with f outgoing links that are eventually timely, i.e., there exist t 0 and a bound δ, such that any message sent by p after t 0 on one of these links is received at most δ units of time after it has been sent.

In [START_REF] Malkhi | meets paxos: Leader election and stability without eventual timely links[END_REF], the authors introduce the notion of eventual ♦f -accessible. A process p is eventual f -accessible if there is a time τ 0 such that, at any time τ ≥ τ 0 , there is a set Q(τ ) of f processes such that p / ∈ Q(τ ) and a message broadcast by p at τ receives a response from each process of Q(τ ) by time τ + δ (where δ is a bound known by the processes). This approach requires a majority of correct processes. Its interest lies in the fact that the set Q of processes whose responses have to be received in a timely manner is not fixed and can be different at distinct times. The paper also presents a protocol building Ω when there is a process that is ♦f -accessible forever, and all other links are fair-lossy.

In [START_REF] Arantes | Eventual leader election in evolving mobile networks[END_REF] and [START_REF] Greve | Eventually strong failure detector with unknown membership[END_REF], the authors propose a model to implement unreliable FDs in dynamic networks with suitable assumptions for such a scenario. The message pattern model establishes conditions on the logical time the messages are delivered by processes. They present a stabilized responsiveness property (SRP ). The property states that there exists a time t after which all nodes of p i 's neighborhood receive, to every of their queries, a response from p i which is always among the α j responses to the query. That is, it denotes the ability of a node to reply to a query among the first nodes. Similarly to the winning channel approach, the response of p i is always a winning response.

Conclusion and Future Work

In this paper we have shown the flexibility capacity of our Impact FD provided by the impact factor and the threshold which enables the user to define the importance (e.g., degree of reliability) of each node and an acceptable margin of failures respectively.

We have defined two properties, P R(IT ) and P R(♦IT ), which denote the capacity of the Impact FD for accepting different set of responses that lead to a trusted state of the system S as well as the concept of a P S-accessible (resp., ♦P S-accessible) process such that every QU ERY message sent by this process obtains from the beginning (resp., eventually) a set Q of responses that satisfy the degree of confidence in S (threshold S ). Interestingly, that in both definitions of P S-accessible and ♦P S-accessible, the set Q is not fixed and can be different at distinct times which is in accordance with the flexibility property of the Impact FD.

Then, we have presented two algorithms that implement the Impact FD tailored to exploit its flexibility feature. The first algorithm is based on a time-free message pattern approach which waits for responses from α processes or from a set Q of processes whose responses satisfy the threshold S . The second algorithm assumes that for every query issued by p, the latter can receive timely responses. We have proved that, for both algorithms, if the monitoring process p is P S-accessible (resp., ♦P S-accessible) the system S is always (eventually always) trusted by p.

As future work, we intend to extend the Impact FD so that it could be able to address dynamic impact factor values, i.e., they can vary during execution, which express the degree of reliability of the node (or reputation). We are also working on the reduction and equivalence of Impact FD in regard with other detectors (e.g., Sigma and Omega [START_REF] Leners | Improving availability in distributed systems with failure informers[END_REF]), which will require some new assumptions and/or new definitions. In [START_REF] Rossetto | A failure detector that gives information on the degree of confidence in the system[END_REF], we presented some performance evaluation results with a timer-based implementation of the Impact FD and traces collected from execution that we conducted on the PlanetLab platform [START_REF] Planetlab | Planetlab[END_REF] that include messages losses and failures of nodes. However, we still aim to conduct further performance experiments on different networks such as WiFi or LAN and, thus, comparing the Impact FD with other well-known failure detectors.

  Upon invocation of Impact() do 25:for i = 1 to m dofor each subset 26:trust level i ← sum(trusted i )

  , threshold S * , ∆, δ Init 3:

TABLE 1 .

 1 EXAMPLE OF FD (Ip S ) OUTPUT: S * HAS THREE SUBSETS

	t	F(t)	trustedp S (t)	trust levelp S Status

In this work, 'set' and 'multiset' are used interchangeably. Unlike a set, an element of a multiset can appear more than once. This allows different processes to have the same identity.


Ngoc Anh

Dung Do

Peter Nielsen

Zbigniew Michna
email: zbigniew.michna@ue.wroc.pl

Izabela Ewa Nielsen
email: izabela@m-tech.aau.dk

Quantifying the Bullwhip Effect of Multi-echelon System with Stochastic Dependent Lead Time

Keywords: bullwhip effect, multi-echelon supply chain, dependent lead time, reorder point, inventory management

Considering a multi-echelon system, the bullwhip effect is recognized as a significant factor with regards to the inventory management. This paper focuses on the effect of stochastic dependent lead time on the bullwhip effect. Simulation based approach is used to quantify the bullwhip effect with different demand and lead time distributions. The experiment results show that the dependent lead time has much effect on the 2 nd echelon (from the downstream to the upstream) and bullwhip effect decrease significantly if the variance of this echelon decreases.

Introduction

The bullwhip effect occurs when the demand variance in the supply chain is amplified as demand prorogates up the supply chain (Lee et al., 1997). The variance of demand increases upstream in the supply chain. In general, to deal with the variance of demand, safety stock is used. The level of safety stock is proportional to the demand variance and the service level. This means that the safety stock increases toward the upstream of supply chain due to the amplification of demand variance. Higher level of safety stock has to be carried with consequently more investment, extra production capacity, and increased storage space [START_REF] Chatfield | The Bullwhip Effect-Impact of Stochastic Lead Time, Information Quality, and Information Sharing: A simulation Study[END_REF]. Therefore, bullwhip effect reduction can bring benefit to the supply chain.

Several studies have been focused on the variation of demand. Nielsen et al. (2010b) considered the time dependent demand and the interdependent of demands of multiple products and developed a method to model the time dependent demand rate profiles by using the estimations of multivariate density distributions, and then to evaluate the interdependence of demand rates of products. Many studies have been investigated on the bullwhip effect and a number of these studies identify the causes of bullwhip effect, for example Lee et al. (1997). Some studies analyze the bullwhip effect by using simulation and show the causes of variance amplification [START_REF] Forrester | Industrial dynamics-A major breakthrough for decision makers[END_REF][START_REF] Bhaskaran | Simulation analysis of a manufacturing supply chain[END_REF]. [START_REF] Croson | Impact of POS data sharing on supply chain management: An experimental study[END_REF] concluded that the bullwhip effect can be decreased by information sharing. Several papers focus on quantifying the bullwhip effect in a more analytical framework. [START_REF] Chen | Quantifying the Bullwhip Effect in a simple supply chain: The impact of forecasting, lead times, and information[END_REF] quantified the bullwhip effect of a multi-stage supply chain with constant lead time and stochastic demand and concluded that the variance of orders of a retailer will be greater than variance of demand when that retailer updates the mean and variance of demand based on observed customer demand data. Moreover, they also pointed out that the customer demand information sharing can significantly reduce the bullwhip effect. The impact of lead time is considered in some studies. Wickner et al. (1991) noted that a twenty percent reduction in peak amplification can be achieved if lead time is reduced. Metters (1997) identified the magnitude of the bullwhip effect by establishing an empirical lower bound on the profitability impact of the bullwhip effect and found that eliminating the bullwhip effect can increase product profitability by 10-30% and significantly save inventories and other costs. [START_REF] Chen | Quantifying the Bullwhip Effect in a simple supply chain: The impact of forecasting, lead times, and information[END_REF] showed that the increase in lead time will increase the variability of orders from retailer to manufacturer.

Nielsen et al. (2010a

) offers an approach to improve supply chain planning through the use of RFID technology to track and thus be able to provide higher quality information, while Sitek and Wikarek (2013) offers approaches for improving planning through optimization. The main issue in applying optimization methods for supply chain management is the quality of the information available for the methods.

Most research to date has considered deterministic lead time and two echelons systems. A few papers have been investigated on stochastic lead time and multi-echelon system, for example [START_REF] Chatfield | The Bullwhip Effect-Impact of Stochastic Lead Time, Information Quality, and Information Sharing: A simulation Study[END_REF]. [START_REF] Nielsen | A Design of Experiments Approach to Investigating the Sensitivity of the Re-Order Point Method[END_REF] considered the reorder point inventory management models sensitivity to demand distributions, demand dependencies and lead time distribution with four different versions of service level and concluded that the skew of demand distribution is the most significant with regards to the service level. However, no paper has been focused on the effect of stochastic lead time of the upstream echelon to that of the downstream one. All papers assumed that the lead times of echelons are independent. This is not practical because the variance of lead time of a downstream echelon can be longer due to the variance of lead time of an upstream echelon. Moreover, the variance of lead time affects the amount of safety stock of an echelon. Therefore, the reorder point (ROP) of an echelon is adjusted based on the historical data of lead time.

In this paper, the impact of stochastic lead time on the bullwhip effect of a multiechelon system using an inventory policy is investigated. This paper differs from the previous studies that the dependence of lead times of echelons is considered. The problem description is presented in Section 2. Numerical experiment is shown in Section 3 and Section 4 points out the conclusions.

2

Problem description and methodology

Problem description

A multi-echelon system is considered as in Figure 1. Li denotes the lead time of the echelon of order i. The variance of lead time is assumed unchanged. The lower echelon will place an order to the next upper echelon when the inventory level lower than or equal the ROP. The ROP is computed as the sum of expected demand during expected lead time and the safety stock. The safety stock is calculated based on the variance of lead time and service level. It is assumed that the continuous review policy is applied for the inventory system of each echelon. The ROP is updated when a new lead time is recorded. Order-up-to is used to determine the order quantity. This means that when the inventory level downs to the ROP, the order quantity can full fill the inventory level up to a desired value. The incoming replenishment and total demand which is not satisfied are considered when review the inventory level. In details, an order will be made when current inventory level + total incoming replenishment -total unsatisfied demand < ROP To decide when an order should be placed, the manager of a lower echelon needs to know the ROP. However, the ROP is calculated based on the expected lead time. If the expected lead time is higher, the ROP is higher. Unfortunately, in practice, the manager cannot know exactly the expected lead time of the next order. Therefore, the manager estimates the expected lead time based on historical data of lead times of previous orders. In our experiment the expected lead time is estimated using a moving average with n = 3. This means that the expected lead time is the average of actual lead time of three consecutive orders which is closest to the time point to estimate the expected lead time. For example, at a certain time in planning horizon, an echelon placed N orders to the next upper echelon. The actual lead time of order i is denoted as LA i . The expected lead time is estimated by using the following formula

expected lead time = (LA N + LA N -1 + LA N -2 ) / 3 (2) Echelon 1 Demand Echelon 2 Echelon k …… L 1 L 2 L k-1 L k
Because the expected lead time is changed when a new order is made, the ROP of an echelon is also changed. As a result, the order quantity also changes in each order of an echelon. Due to the variance of order quantity, bullwhip effect will be expected to occur. The aim of this paper is to answer two questions. First, is there a bullwhip effect when the lead time of a lower echelon depends of that of the next upper echelon? In this paper, the bullwhip effect is defined as the ratio between the variance of order of the upper echelon and that of the next lower echelon. If all ratios are greater than 1, meaning that the variance of order of the upper echelon is higher than that of the next lower echelon, then the bullwhip effect exits. Secondly, if the bullwhip effect exists what is its size? Furthermore, through quantifying the bullwhip effect, we can see the effect of variance of lead time on the bullwhip effects of each echelon and the supply chain as a whole.

Methodology

To answer the two mentioned questions, Monte Carlo simulation is implemented on this multi-echelon system. Firstly, the possible events for each echelon are analyzed. The events at an echelon include:

• Order placing: when the relative inventory level is lower than or equal the ROP, an order is placed at the next upper echelon. The order quantity is calculated by equation [START_REF] Bhaskaran | Simulation analysis of a manufacturing supply chain[END_REF]. The information sent to the next upper echelon includes order ID and order quantity. Following this, information about the lead time of this order is sent back from the next upper echelon. The information about this order is recorded including order ID, release date, lead time, and order quantity. • Order receipt: when the echelon receives an order from the next lower echelon.

The lead time for this order is generated and sent back to the next lower echelon. Information about this order is recorded including order ID, order quantity, and delivery date. • Order delivering: an order is considered to be delivered when its delivery date comes or is over and the current inventory level is higher than the quantity of this order. The upper echelon will sent information about order ID and actual delivery date. Current inventory level is updated and the order is removed out of the list of order receipt. • Order replenishment: when the lower echelon receives the information about order delivery from the next upper echelon, the replenishment quantity is added to the current inventory. The lead time of this order is updated (in case it is different from the estimated lead time). Following this, the expected lead time is updated. • Inventory review: investigates whether the relative inventory level is less than or equal to the ROP or not.

• Delivery check: to check whether an order in the list of order receipt is delivered or not. The condition for an order to be delivered includes delivery date of this order comes or is over and the current inventory level is higher than the quantity of this order.

For practical purposes there are some differences for the first and last echelon.

• Order receipt at the first echelon (echelon 1 in Figure 1): when the demand is received, the information is recorded to the list of order receipt following which the order delivery happens instantaneously.

• Order placement at the last echelon (echelon k in Figure 1): the lead time is generated when placing the order. • Order replenishment at the last echelon: the order is replenished at the delivery date. This means that the order is replenished at the time which equals release date plus lead time

The simulation is terminated after the last day of planning horizon has been considered. After that, the variance of order of each echelon is calculated. Finally, the bullwhip effect of each echelon is computed.

Numerical experiment

Some scenarios are conducted in the numerical experiment. Four echelons are considered. The scenarios are the combination of the different cases of demand and lead time shown in Table 1. It is assumed that all echelons have the same lead time. The target service level is 90%. All echelon will order up to 1000 units. The initial inventory level follows a uniform distribution U(0,500). The planning horizon is 365 days. There are 30 runs for each scenario. The result of the experiment is shown in Tables 2a,2b, and 2c. It can be seen from the experiment result that the bullwhip effect exists when lead time is stochastic and dependent. The different cases of demand do not affect the decrement in bullwhip effect when moving to the upstream (upper echelon) of the multiechelon system. It shows that the second echelon has big bullwhip effect. The bullwhip effect becomes smaller when moving to the upper echelon. This shows that the bullwhip effect tends to have the value of 1 when more echelons are considered.

Variance

Figure 2 shows an interesting result. In echelon 1, the echelon closest to the demand and hence the natural demand, variance is very low. This seems reasonable as at this echelon the demand should be easy to observe and thus estimate. However, the orders sent to echelon 2 has an effect on the variance of order of echelon 2. Due to the amplification of demand variance, the upper echelon will have higher variance on demand. Figure 3 shows the direction of the increase of demand variance for a 4-echelon system where echelons 1 and 2 are considered as retailer and manufacturer and other echelons are the subsequent material suppliers. On the other hand, the cumulative effect of the lead time variance seems to directly impact the upper echelons, specifically the manufacturer. This is shown as the increase of lead time variability in Figure 3. The result is that the manufacturer experiences a very large bullwhip effect, much more so than any other echelon to echelon combination. The conclusion must be that the manufacturer especially absorbs the variance effect due to both the variance of lead time and demand. This underlines that the bullwhip effect of this system can be significantly reduced if the inventory policy of the manufacturer is carefully investigated. Furthermore, it can be concluded that the effect of lead time variation dominate that of demand variance in a multi-echelon system with dependent lead time. This means that decision making relate to inventory management is much different when lead time is uncertain and dependent. The study on inventory management with dependent lead time is very promising and can be put in future research.

Conclusion

In this paper, the stochastic and dependent lead time is considered in a multi-echelon system. The lead time of downstream (lower) echelon is assumed to be affected by that of upstream (upper) echelons. A simulation based experiment is run to determine and quantify the bullwhip effect in this type of system. Some scenarios are proposed for numerical experiments. The result of experiments shows that there is bullwhip effect in the system and the bullwhip effect is significantly decreased if the bullwhip effect of the 2nd echelon decreases. Several issues can be investigated for further Retailer Demand Manufacturer Supplier 2

L 1 L 2 L 3 L 4 O 1 O 2 O 3 O 4 D
Increase in lead time variation Increase in demand variation Supplier 1 study. Studying an optimal inventory policy for the 2 nd echelon with considering stochastic and dependent lead time is very promising to decrease bullwhip effect of the whole system. Information sharing in the system is another issue which can show how much bullwhip effect can be reduced. The study also underlines that lead times and their variations are in fact critical for supply chains, especially if the lead times to some extend are dependent on each other.

Fig. 1 .

 1 Fig. 1. the description of considered systemIf the left hand side of the above inequality is denoted as the relative inventory level, then the order quantity will be order quantity = desired up-to-value -relative inventory level[START_REF] Bhaskaran | Simulation analysis of a manufacturing supply chain[END_REF]

Fig- ure 2

 2 shows the variance of order of each echelon Demand Echelon 1 Echelon 2 Echelon 3 Echelon 4

Fig. 3 .

 3 Fig. 3. Effect of the variances of lead time and demand on a 4-echelon system

Table 1 .

 1 The cases of demand and lead time

		Constant	Normal	Exponential	Uniform
	Demand	D = 50	N(50, 10 2 )	-	U(40,60)
	Lead time	L = 2	N(2,1)	Expo(2)	U(1,3)

Table 2 .

 2 a. Average and std. deviation of bullwhip affect when demand is constant

		L = 2 days	L ~ N(2,1)	L ~ Expo(2)	L ~U(1,3)
		Avg	Std	Avg	Std	Avg	Std	Avg	Std
	Echelon 2 219.1721 0.8834 141.1904 120.0914 4.1726 0.9078 161.6278 127.3034
	Echelon 3	4.4194 0.0011	1.9649	0.4869 1.8175 0.3010	2.4348	1.2051
	Echelon 4	2.1398 0.0001	1.7096	0.6015 1.4620 0.2013	1.7175	0.4353

Acknowledgement the presented research is partly supported by the Polish National Centre of Science under the grant UMO-2012/07/B/HS4/00702.