Delegating effectively across cultures

Keywords: Cross-cultural leadership, Empowerment, Delegation, Madagascar, NGO

This article builds on the contingency approach to global leadership to examine empowerment in a cross-cultural context. Drawing upon ethnographic research on employees of a French NGO in Madagascar, our study demonstrates that effective empowerment is not dependent on the amount of delegation, but rather it is dependent on how delegation is performed. Understanding the cultural representations of formalization, skill development, collective work, and decision-making appeared to be crucial to effective delegation in Madagascar. This result suggests that managers should adapt the way that they empower their teams based on the conditions and forms of delegation prevailing in local cultures.

Introduction

Delegation is widely acknowledged to be a crucial aspect of effective leadership that often proves particularly challenging in a cross-cultural context. Research that examines the use of delegation across cultures remains scarce and, as Pellegrini and Scandura noted, "still, research has yet to examine delegation in a cross-cultural context" (2006, p. 264). In addition, much of the literature discusses the presence or absence of managerial delegation, although delegation is a complex and multi-faceted process [START_REF] Yukl | Determinants of delegation and consultation by managers[END_REF]. The "how" of delegation across cultures remains under investigated. This paper addresses this theoretical gap and examines its practical implications. Its purpose is to examine the extent to which culture determines the conditions under which delegation is deemed acceptable. This paper builds on the contingency approach to global leadership (Steers, Sanchez-Runde, & Nardon, in press). For the past several decades, research efforts have increasingly been directed at understanding the role of leadership across cultures. Many cross-cultural leadership studies have attempted to define a global leadership style [START_REF] Javidan | Conceptualizing and measuring global mindset[END_REF][START_REF] Mendenhall | Global leadership : research, practice, development[END_REF]. The contingency approach instead analyzes leadership-style variations across cultures while highlighting cultural contingencies and questioning the transferability of practices from one culture to another. The Global Leadership and Organizational Behavior Effectiveness (GLOBE) research program (Dorfman, Javidan, Hanges, Dastmalchian, & House, in press;[START_REF] House | Culture, Leadership, and Organizations: The GLOBE Study of 62 Societies[END_REF]) is one of the most influential studies in this area of research. Although most leadership attributes and behaviors were found to vary significantly across cultures, this study also identified some key characteristics of an efficient leadership style that are universally endorsed.

Our research is based on a study of relationships between French expatriates and Malagasy employees of a French non-governmental organization (NGO).

Contrasting expectations with regard to delegation were observed across the two samples. This discrepancy is interpreted in light of Malagasy and French national cultures. This research enhances our understanding of cross-cultural leadership in two ways. First, it provides insight into leadership processes in a country with a very different culture than Western countries, where most of the research on leadership and delegation has been conducted. Madagascar has not been included in the sample population of most cross-cultural research [START_REF] Hofstede | Culture's consequences comparing values, behaviors, institutions and organizations across nations[END_REF][START_REF] House | Culture, Leadership, and Organizations: The GLOBE Study of 62 Societies[END_REF]. Second, it demonstrates that the effectiveness of delegation is contingent on national culture. Although this is in line with extant research (e.g., [START_REF] Pellegrini | Leader-member exchange (LMX), paternalism, and delegation in the Turkish business culture: An empirical investigation[END_REF], it shows that this cultural contingency might be better understood in terms of how delegation is implemented, rather than whether it should be implemented or not. Overall, the results of this study have both practical and theoretical implications.

The remainder of the paper is structured as follows. First, we briefly review existing research on leadership with a focus on delegation issues and introduce our conceptualization of culture. Next, we introduce the empirical background of this study and the methodology. Then, we analyze and compare the views about delegation across French and Malagasy culture. Finally, the implications of this study are discussed.

Theoretical framework

Leadership and delegation: a contingency approach

The cross-cultural leadership literature can be divided into two categories: (1) studies that consider culture to be a moderator of the relationship between leadership and employees' outcomes, (2) studies that focus on variations in leadership styles, practices and preferences across countries. Culture is therefore expected to account for a significant variance in leadership [START_REF] Van Emmerik | Leadership Behaviors around the World: The Relative Importance of Gender versus Cultural Background[END_REF][START_REF] Zander | When Nationality Matters: A Study of Departmental, Hierarchical, Professional, Gender and Age-based Employee Groupings' Leadership Preferences across 15 Countries[END_REF]. We now briefly review these two categories, with a focus on delegation issues.

Delegation occurs when a manager gives subordinates the authority and responsibility for making and implementing decisions [START_REF] Bass | The Bass handbook of leadership : theory, research, and application[END_REF][START_REF] Yukl | Determinants of delegation and consultation by managers[END_REF]. As such, delegation is central to participative leadership. Different studies in the first of the two aforementioned categories have shown that the outcomes of participative leadership depend on employees' cultural values [START_REF] Lam | Participative decision making and employee performance in different cultures: the moderating effects of allocentrism/idiocentrism and efficacy[END_REF][START_REF] Zhang | Effects of participative leadership: the moderating role of cultural values[END_REF]. The rationale for this moderating effect of culture is that people will respond differently to various leadership styles according to their culturally contingent prototype of an effective leader. For instance, [START_REF] Robert | Empowerment and Continuous Improvement in the United States, Mexico, Poland, and India: Predicting Fit on the Basis of the Dimensions of Power Distance and Individualism[END_REF] found that empowerment was negatively associated with satisfaction in India, a high power distance cultural setting.

Similarly, [START_REF] Hui | Empowerment effects across cultures[END_REF] demonstrated that employees' willingness to accept and exercise discretionary power depends on the cultural value of power distance, which, in turn, moderates the effect of empowerment on job satisfaction. More recently, [START_REF] Pellegrini | Leader-member exchange (LMX), paternalism, and delegation in the Turkish business culture: An empirical investigation[END_REF] suggested that delegation might not be an effective management practice in the Turkish business context, with respect to job satisfaction. Given that Turkey ranks high on measures of uncertainty avoidance, employees may be reluctant to deal with the ambiguity of being delegated a challenging task and prefer to be told what to do.

In the same vein, different studies in the second category have shown that participative leadership is far from being universally endorsed. For instance, GLOBE research suggests that high power distance and uncertainty avoidance cultures are less inclined to endorse participative leadership [START_REF] House | Culture, Leadership, and Organizations: The GLOBE Study of 62 Societies[END_REF]. Similarly, [START_REF] Wendt | Leadership and team cohesiveness across cultures[END_REF] found cultural individualism to be negatively related to supportive leadership. In the second category, different studies have also focused on leadership prototypes across cultures. These studies show that delegation is not universally acknowledged as an ideal leader's behavior. For instance, [START_REF] Romero | Latin American leadership: El Patrón & El Líder Moderno[END_REF] demonstrates that traditionally, in a Latin-American context, delegation is not commonly expected from a leader (a similar result can be found in [START_REF] Dorfman | Managerial leadership in the United States and Mexico: Distant neighbors or close cousins?[END_REF]. Conversely, [START_REF] Hoppe | Leadership in the United States of America: The leader as cultural hero[END_REF], as part of the GLOBE project, suggest that the ideal leader in the United States is someone who encourages participation through delegation. Beyond these few examples of studies that develop knowledge on leadership prototype variation across cultures, some other studies have researched the influence of different cultural dimensions on the inclination to delegate or expect delegation [START_REF] Hofstede | Culture's consequences comparing values, behaviors, institutions and organizations across nations[END_REF]. Looking at actual managers' behavior, [START_REF] Offermann | Culture's Consequences for Leadership Behavior: National Values in Action[END_REF] found that managers from high uncertainty avoidance countries tended to delegate less than those from low uncertainty avoidance countries. The rationale for this result is that leaders from high uncertainty avoidance cultures are more likely to find ways to keep their units under control in an attempt to make their working environment more certain. Their findings also indicate that power distance influences the inclination to delegate because this cultural dimension is associated with a tendency for leaders to autocratically retain power (similar results can be found in [START_REF] Van De Vliert | Leader reliance on subordinates across nations that differ in development and climate[END_REF].

Traditionally, delegation was conceptualized by characteristics of the subordinates and the manager-subordinate relationship [START_REF] Schriesheim | Delegation and leader-member exchange: main effects, moderators, and measurement issues[END_REF][START_REF] Yukl | Determinants of delegation and consultation by managers[END_REF]. Our succinct review also suggests that the use of delegation is far from being a universal leadership behavior.

However, in the literature reviewed above, the question is primarily addressed in terms of the presence or absence of managerial delegation. However, delegation is a complex and multi-faceted process [START_REF] Yukl | Determinants of delegation and consultation by managers[END_REF]. The forms of delegation across cultures remain underinvestigated. The remainder of the paper addresses this question.

National cultures

To date, most cross-cultural leadership researchers have considered culture drawing upon the comparative work of [START_REF] Hofstede | Culture's consequences comparing values, behaviors, institutions and organizations across nations[END_REF]. Using this perspective, culture is a shared system of values that determines individual preferences and attitudes. In this paper, we adopt an interpretative approach to culture (d'Iribarne, 2009;[START_REF] Primecz | Cross-Cultural Management in Practice: Culture and Negotiated Meanings[END_REF]. In this approach, culture is the shared context of meaning (i.e., a set of references with which actors give meaning to their experiences). Thus, sharing a culture means using the same symbolic categories to make sense of reality and not attaching value to the same reality. Although such sense-making patterns are a strong constraining force, especially regarding legitimate ways of coping with social interactions within organizations, they do not affect attitudes in a deterministic manner. For instance, in the United States, social relations are mainly conceived as contracts. However, individuals can still disagree on whether a given action respects their contract while sharing the same definition for the concept of a contract [START_REF] Chevrier | Is National Culture Still Relevant to Management in a Global Context?: The Case of Switzerland[END_REF].

Thus defined, culture is relatively stable due to its deep structure. Indeed, it appears that in any society, an opposition was formed between a dominant peril (i.e., a basic concern that makes people uneasy or even anxious) and paths to salvation that enable people to avert this fear (d'Iribarne, 2009). This fear marks all social existence and, particularly, the life of an organization because many events taking place in organizations are likely to revive these fears. This opposition between situations that inspire fear and paths to salvation is based upon idiosyncratic references, which are implicit and unconscious. However, in a given society, this opposition is highlighted by a network of real or mythical figures and narratives. The vocabulary in use in a society also reflects the categories at work in this opposition.

The French cultural example, which we borrow from d'Iribarne (2009, p. 314-315), illustrates this definition of culture. In French society, the basic fear is servility (i.e., the experience of being bent by fear or by interest). A specific vocabulary is associated with this experience: "to yield", "to submit", "to lower oneself", "to crawl", "to reveal oneself to be spineless". The path to salvation is resistance, in the name of something great, over fear and petty interests; this path is associated with expressions such as "to face" and to "stand up to". Courage is opposed to cowardice, an idea that is well expressed in expressions such as "all is lost except honor" or "honor is safe". Thus, many French myths glorify resistance, from Vercingétorix to Jean Moulin, via Jeanne d'Arc. This opposition between the unworthiness of servility and the nobleness of resistance is far from being universal. For example, some other societies are much more concerned with chaos (China) or impurity (India).

Thus defined, culture represents a framework for individual and collective action. Management practices are culturally rooted. Hierarchical relations will be interpreted in the light of cultural dominant peril. For instance, in the French context, one can intuitively understand how the implicit reference to servility will help individuals to determine whether a relationship is acceptable. This does not mean that French leaders systematically avoid placing followers in a servile and degrading situation. Actual behaviors are widely dispersed. However, both leaders and followers will refer to the same basic opposition to make sense of their relationships. At a cross-cultural level, this implies that delegating and symmetrically taking responsibility refer to culturally contingent sense-making patterns. These differences might explain some difficulties associated with delegation across cultures.

Background of the case study and methodology

This research has been undertaken at the request of a French NGO named GRET 1 . Founded in 1976, GRET is an association of professionals for fair development. GRET designs and implements field projects, provides expertise in a wide range of areas and conducts applied research and studies. Its headquarters are located in Paris, France. GRET is active in more than thirty countries, and it has thirteen permanent branch offices in Asia, Africa and Latin America. This study was almost entirely conducted in the office in Antananarivo, Madagascar. In headquarters, as well as in the Malagasy branch office, French managers regularly complained of the difficulties in transferring some of their tasks to Malagasy teams. Because it was suspected to be a cross-1 GRET stands for "Groupe de recherche et d'échange technologique", which can be translated as the "Technological Research and Exchange Group" cultural issue, the GRET headquarters and the head of its permanent branch office in Antananarivo jointly initiated this study with the authors. The purpose was to identify the conditions for effective delegation for both Malagasy and French partners.

Table 1 presents our interviewee sample. As this table illustrates, our sample covers the whole range of positions in the local GRET office, including the head of the office, his assistant, administrative personnel and members of project teams. To avoid a possible organizational bias and to reinforce the robustness of our analysis, we included Malagasy interviewees from other NGOs. In this way, we could reasonably assume that the shared representations that we identified were specific to the Malagasy culture and not only the GRET organizational culture. Table 1 also reveals an imbalance between the number of French and Malagasy interviewees in our sample. To control for this bias, this work takes advantage of previously completed interpretative research on French culture [START_REF] D'iribarne | La logique de l'honneur : gestion des entreprises et traditions nationales[END_REF][START_REF] Segal | Efficaces, ensemble : un défi français[END_REF].

Our data were collected in 2009 and 2010 and consist of recorded semidirected interviews, for an approximate total length of forty hours. These interviews were based on a guide that was structured around broad themes: professional aspirations, decision making and expectations toward superiors' attitude. However, respondents were invited to answer very freely, and digressions were allowed. We tried not to influence respondents with our own cultural conceptions, and we expected them to describe working situations and events with their own words and through their own mental categories. We favored spontaneous expression to understand individuals' representations as closely as possible.

The interviews have been typed out word for word. The data were analyzed afterwards using the inductive coding method [START_REF] Miles | Qualitative data analysis : an expanded sourcebook[END_REF].

From an interpretative perspective, this method allows the researcher to progressively disentangle the respondents' implicit mental categories [START_REF] D'iribarne | How to Use Ethnographic Case Studies to Decipher National Cultures[END_REF]. Our emerging coding categories are presented in Appendix 1. Concretely, on the basis of a careful analysis of the interviews, we identified recurrent words and ideas in the discourse of interviewees and how different words and ideas could be associated or opposed. By cross-checking the interviews, we identified shared representations among the French, on the one hand, and the Malagasy, on the other hand. Furthermore, in this study, the interpretive process was performed by both authors in parallel. This protocol limits possible bias by ensuring that results are convergent among researchers. For interviewees with a leader position, the interview addressed both upward and downward relationships (c):

Appendix 2 provides a brief overview of these projects

Results

French managers mentioned that they were urging Malagasy teams to take on initiatives. However, most of them complained of still being consulted on decisions or actions that Malagasies were expected to make by themselves.

The French interpreted this attitude as a reluctance to take responsibility or even a lack of courage. At first sight, some accounts given by Malagasies tended to confirm this interpretation. Some of them mentioned their fear of making bad decisions or their tendency to expect approval from their superior.

However, we also observed that delegation was sometimes successful. Above all, the analysis of the Malagasies' professional aspirations revealed a strong and shared desire to take on greater responsibility. However, for Malagasies, several conditions had to be met to make delegation effective. In particular, delegation should be accompanied by (1) a detailed formalization of roles and structures, (2) skill development, (3) collective work and (4) a clarification of decision procedures and processes. Although it could be argued that these conditions are universal, our analysis revealed that these conditions did not refer to the same sense-making framework on the French and Malagasy side, even if convergence points also emerged.

Role and structure formalization

Both the Malagasies and the French perceived role and task formalization as a means of understanding their place in the organization by clarifying everyone's prerogatives and duties. Role and task formalization was also mentioned as a necessary objective basis for performance appraisal. Beyond this convergence point, our analysis revealed that the two communities made sense of formalization very differently (figure 1). Indeed, it avoids them by limiting possible overlaps, and it regulates them by providing a benchmark to refer to in case of dispute.

I had two people under my responsibility, so I distinguish well what everyone does so that there is not this overlap of activities where everyone does the same thing and where some activities are left aside. (M)

Formalization expectations did not only concern tasks but also structures and hierarchical relationships. Detailed individual reporting relationships are expected as a means to specify everyone's legitimate scope of decision making. To conclude, in the Malagasy perspective, formalization is a way of escaping from an ambiguous and blurred organization that inhibits action and creates conflicts.

On the French side, although formalization is acknowledged to have many virtues, it is also perceived as having strong paralyzing effects. On the one hand, formalization is expected as a means to clarify relationships and to define everyone's space of autonomy. On the other hand, there is a strong fear of an excessive formalization, which is associated with an image of bureaucracy and paralyzing rigidity. Although both Malagasy leaders and followers overwhelmingly advocated for a thorough formalization of roles and tasks, French leaders were wary of getting locked in such formalization. In the French context, formalization rather refers to a broadly defined mission or role in the organization or a project. Such a definition leaves room for maneuvering and is conceived as "a score that still has to be interpreted" (F).

The development of skills

On both the French and Malagasy sides, skills are at the heart of taking on increased responsibilities and delegation. Skills refer to know-how that can either result from education or on-the-job training and are perceived as a source of legitimacy. Nevertheless, beyond this shared ground, quite different patterns emerged from our analysis (figure 2). From the Malagasy perspective, skills were associated with control over one's function or "domain" (M). The word "domain", which was used by many Malagasy interviewees, clearly evoked ownership over one's field. Skills also emerged as the key resource to "keep control" (M) over work situations and not to be "overtaken by events" (M). This conception is consistent with high formalization expectations (see above). A thorough definition of everyone's remits both determines the boundaries of the domain according to which skills will be valued and provides securing benchmarks that will help to keep control over this domain. Accordingly, it appeared that skills were prerequisites for delegation endorsement. Skills clearly determined the acceptable scope of responsibilities of Malagasy employees. Being assigned responsibilities outside one's skill-set is a cause for legitimate refusal in the Malagasy context.

Conversely, if such a situation is accepted, it will be perceived as a strong "challenge" that requires intensive learning efforts to gain control over the domain that one is entering.

It is a challenge. Sometimes I enter a domain that I don't know, so I'm obliged to go into this domain in depth, to research this domain, to improve on just a

little, to try to see what this subject really is. (M)

On the French side, skills emerged as the key to professional autonomy. They allow people to appropriate their mission and to know what to do within a very loosely defined general frame. Skills refer not only to know-how, but also to knowing what to do. In other words, skills refer to the knowledge of the rights and duties of one's "métier"2 . Skills allow people to take initiatives. Such initiatives will only be limited by people's implicit professional rules. For instance, skills entitle employees to free themselves from some administrative constraints. They allow them to decide whether procedures should be followed scrupulously, or if an operational emergency prevails over administrative rules and the situation will be regularized afterwards.

Collective work

Collective work was perceived by Malagasy and French interviewees as the means to complete complex projects through synergies between various areas of expertise. It was also mentioned that collective work creates strong interdependencies between individuals because everyone's work is then dependent on the other's contribution. However, it was commonly acknowledged that such interactions are a source of mutual learning (figure 3). French interviewees acknowledged that collective work creates conviviality.

I
However, from their perspective, collective work was conceived as a place of debate and a means to confront various points of view. Thus, priority is not given to avoiding offense, but to defending opinions with thorough and logical reasoning. Therefore, individuals express themselves very frankly and frequently interrupt one another to vigorously assert conflicting arguments. In other words, ideas prevail over relationships. Collective work is perceived as very time-consuming because it may result in endless discussions, unlike the autonomous decision making process, which fosters quicker decisions. From the French perspective, collective work is used in case of uncertainty regarding the right way of managing projects, but it may be sacrificed in the case of operational emergencies.

Decision making

Employees' willingness to make decisions by themselves clearly reflects delegation acceptance in a given cultural context. However, our analysis revealed strong discrepancies between French and Malagasy conceptions of decision making (figure 4). In the Malagasy context, decisions are considered more efficient when they are collective. Although Malagasies thought that they could ultimately make decisions within their "domain", it appeared that collective decision making was perceived as providing security because it reduces the risk of error and its potential negative consequences for oneself, others, the project or even the entire organization.

I did not take too many risks because if I ever make the [wrong] decision it may have an impact on the project ... (M)

Malagasy interviewees expected to be consulted about what falls within their "domain". They also expected their opinion to be taken into account in the final decision. Repeatedly, Malagasies used the term "primary responsible for" [a department, a project…]. This clearly expressed that individual responsibilities are not weakened by collective work. Thus, someone is always clearly identified as responsible for a decision. However, the word "primary" suggests that some other people were also considered as jointly responsible.

This word clearly suggested that other members of the group felt jointly liable.

At the same time, it appeared that from the followers' point of view, hierarchy played a crucial role in decision-making. Leaders' decisions are naturally imposed on followers, with the exception of those fields that have been delegated explicitly and formally to followers. Such formalization, along with skill development, is necessary to help followers legitimately make and take responsibility for decisions personally.

In the French context, decision-making is considered a matter of personal choice for which individuals should take responsibility. Some say that several responsible parties make as many irresponsible people. In other words, from the French perspective, responsibility should not be dispersed. Decision making is, above all, related to personal autonomy within a field of liability.

This field results from a subjective perception of one's "métier". Within this field, anyone should be able to make a decision by himself in the light of one's personal interpretation of professional references. A good professional whether leader or team member, is expected to take reasonable risks. When decision-making exceeds one's subjectively defined prerogatives, a consultation might be held to consider various options and arouse support for the one that seems the most favorable. Because ideas prevail over relationships, individuals are expected to stand up for their opinions, even if those opinions are different from the leader's point of view. In this context, decisions are made and implemented because they are considered relevant, not simply because they were explicitly requested by leaders. Accordingly, once a decision has been made, it may be easily changed if another alternative is perceived to be better. This situation is perfectly acceptable in the French context.

Discussion

In this study, our starting point was twofold. At the theoretical level, consistent with the contingency approach of global leadership, we intended to investigate the "how" of delegation across cultures. At the empirical level, we tried to explain discrepancies with regard to delegation expectations between two culturally distinct subsamples. We now return to these two dimensions and discuss the implications of our research.

In the case of hierarchical relationships between French expatriates and Additionally, the definite nature of decisions in the Malagasy decision-making process might have been perceived as a reluctance to take initiative and a lack of reaction to operational imperatives from the French viewpoint.

Figure 1 :

 1 Figure 1: French and Malagasy representations of formalization

Figure 2 :

 2 Figure 2: French and Malagasy representations of skills development

Figure 3 :

 3 Figure 3: French and Malagasy representations of collective work

Figure 4 :

 4 Figure 4: French and Malagasy representations of decision-making

  Malagasy employees in GRET's Antananarivo branch office, delegation was the most important issue. It seemed that there was a deep misunderstanding regarding what French leaders and local personnel expected from each other.We further explored the situation and identified distinct cultural representations along four dimensions, namely, role and structure formalization, the development of skills, collective work and decision making.Differences in sense-making patterns with regard to these four dimensions, and the resulting reciprocal interpretations, help explain the initial situation.The French interpreted the Malagasy cultural representation as cowardice or reluctance to take responsibility for decisions and actions. For instance, French leaders probably did not perceive that the Malagasy followers' tendency to consult them was only the expression of their cultural representation of collective work, which is based on mutual aid. Similarly, although role and structure formalization plays a crucial role in both avoidance and settlement of conflict in the Malagasy context, this practice is perceived negatively in the French context because it is considered to have paralyzing effects.

Table 1 : Overview of interviewee sample Total sample= 41 interviewees GRET sample= 33 interviewees French a sub sample= 8 interviewees Position Leader/Follower b Project c

 1

	1 Project team member (knowledge capitalization)	Follower	Nutrimad
	2 Project manager	Leader	Médéa
	3 Project team member (beneficiaries communication and
	education)	Leader	Médéa
	4 Project manager	Leader	Nutrimad
	5 Project manager	Leader	Rhyvière
	6 Head of the permanent branch office	Leader	Transversal
	7 Program manager	Leader	Headquarter
	8 Program manager	Leader	Headquarter
	Malagasy a sub sample= 25 interviewees
	Position	Leader/Follower b Project c
	9 Project team member	Follower	Médéa
	Project team member (engineering)	Follower	Médéa
	Project team member (assistant)	Follower	Nutrimad
	Project team member (beneficiaries communication and	Follower
	education)		Nutrimad
	Project team member (engineering)	Follower	Nutrimad
	Project team member (institutional partnerships)	Follower	Nutrimad
	Project team member (project monitoring keyboard	Follower
	operator)		Nutrimad
	Project team member (risk management and	Follower
	infrastructures)		Nutrimad
	Project team member (statistical studies)	Follower	Nutrimad
	Project team member (engineering)	Follower	Rhyvière
	Project team member (engineering)	Follower	Rhyvière
	Project team member (engineering)	Follower	Rhyvière
	Project team member (engineering)	Follower	Rhyvière
	Administrative team member (accounting)	Follower	Transversal
	Administrative team member (assistant)	Follower	Transversal
	Administrative team member (logistics)	Follower	Transversal
	Administrative team member (management accounting)	Follower	Transversal
	Assistant of head of the permanent branch office	Leader	Transversal
	Project manager	Leader	Drynet
	Project team member (opportunity studies)	Leader	Médéa
	Project team member	Leader	Nutrimad
	Project team member (project management in rural areas) Leader	Nutrimad
	Project team member (project monitoring and evaluation) Leader	Nutrimad
	Project team member (engineering)	Leader	Rhyvière
	Chief administrative officer and human resource manager Leader	Transversal
	Additional non GRET sample= 8 interviewees
	7 Malagasy a NGO employees
	1 French a NGO employee

(a):

Quotations from the interviews are identified as follows: (M) for Malagasy interviewees, (F) for French interviewees (b):

  believe this is not normal to work really on my own and I think it is always

	by one interviewee: "Once shared, a burden becomes a feather". The group
	contributes to a pleasant atmosphere that some Malagasy interviewees
	compared to that of "a family". This reference to family clearly evoked
	"fraternal" relationships (i.e., close and egalitarian relationships).
	Maintaining this fraternal atmosphere implies the need to weigh one's words,
	to avoid conflicts, and to keep to oneself what might hurt others.
	necessary to have support from a person or another [...] if I have a project
	and I found myself alone, it could still work in terms of project management,
	you can always reach the goals, but it would not be very exciting, teamwork is
	always better. (M)
	It appeared that for Malagasies, collective work means a shared objective that
	creates mutual involvement and a strong feeling of belonging. It also emerged
	that collective work is an opportunity to help each other and to find solutions
	together. It is worth noting that for Malagasy interviewees, collective work
	referred to both lateral relationships and hierarchical relationships. Everyone is
	expected to bring help as much as his (or her) skills allow. Such help takes
	place in various contexts, including mutual aid between team members,
	support from leaders to followers, and vice versa. The group also makes a
	heavy workload more bearable, as summarized in a Malagasy proverb recalled

The French word "métier" is difficult to translate. It refers to one's professional role or field of expertise, and it is a key reference in French culture(d'Iribarne, 2009).

Reciprocally, some practices of the French leaders might have been perceived negatively from the Malagasy viewpoint. For instance, in the French context, delegating a very loosely defined mission shows the trust that a leader places in his followers. Such delegation practices may be very disturbing from the Malagasy viewpoint. It may be that French leaders do not meet Malagasy followers' expectations with regard to formalization. This analysis is consistent with previous research that sheds light on the difficulties that French expatriates have when exercising leadership abroad (d'Iribarne, 2009a;[START_REF] Frank | Acquisitions américaines : le management français en question[END_REF][START_REF] Segal | Efficaces, ensemble : un défi français[END_REF].

At the theoretical level, we believe that our research contributes to a better understanding of leadership across cultures with regard to delegation. Existing research suggests that culture influences both followers' expectations and leaders' inclination to delegate [START_REF] Hoppe | Leadership in the United States of America: The leader as cultural hero[END_REF][START_REF] House | Culture, Leadership, and Organizations: The GLOBE Study of 62 Societies[END_REF][START_REF] Hui | Empowerment effects across cultures[END_REF][START_REF] Offermann | Culture's Consequences for Leadership Behavior: National Values in Action[END_REF][START_REF] Pellegrini | Leader-member exchange (LMX), paternalism, and delegation in the Turkish business culture: An empirical investigation[END_REF][START_REF] Romero | Latin American leadership: El Patrón & El Líder Moderno[END_REF]. Our results confirm that the use of delegation is subjected to cultural relativism. However, this research suggests that the relationship between culture and the use of delegation as an effective leadership practice may be less deterministic than it is usually regarded. We observed that both French and Malagasy leaders could delegate more or less depending on circumstances and their personal profile. This suggests that culture does not represent in itself a definite constraint on delegation. However, this also does not imply that the cultural dimension of delegation could be neglected.

Delegation practices only make sense in the light of cultural systems of meaning. Our empirical study demonstrated that French and Malagasy cultural representations of delegation were significantly different.

Managerial relevance and conclusion

At the practical level, ignoring differences in cultural representations seriously impairs the effectiveness of delegation as a leadership practice. Therefore, the issue is not to know to what extent leaders should delegate, but to understand the specific conditions of effective delegation in various countries.

Additionally, we believe that this understanding should not be limited to the followers' cultural representations. Leaders should also understand that their own delegation practices are subject to cultural relativism. For instance, although they easily recognized themselves in our description, very few French leaders were conscious of their manner of advancing their "métier", professional autonomy and associated skills. These cultural representations are far from being shared around the world. The desire to respect skillful followers by giving them broad autonomy and being careful not to interfere in their area of responsibility creates deep misunderstandings. Although these practices may just be driven by the desire to help followers, they may be interpreted as indifference, ambiguity, or even arrogance. Hence, in a crosscultural context, it seems crucial to increase leaders' awareness of their own basic concerns and to make them reflect upon the meaning of their practices.

While we advocate for a better understanding of the cultural representations of delegation, we must acknowledge that this does not automatically lead to appropriate leadership practices. In a cross-cultural context, the following question remains unanswered: who should adapt their practices? Should expatriate leaders adapt to local followers' expectations? Or should local followers compromise with expatriate leaders' "exotic" practices? There is probably no single answer, but we believe that a thorough explanation of cultural contexts can open the path to negotiations for appropriate practices.

Acknowledging that there is no single way to delegate is the first step toward effective delegation practices across cultures. This recognition becomes particularly crucial in a time when expatriates are expected to increase host country nationals' autonomy and often play a key role in the transfer of knowhow from headquarters to subsidiaries [START_REF] Bonache | Knowledge Transfer and the Management of Expatriation[END_REF].

Our research also has a number of limitations that should be acknowledged. In terms of data collection, the main limitation of our research is related to the relative imbalance between French and Malagasy interviewees in our sample.

We tried to control for this bias by taking advantage of previous interpretative research on French culture [START_REF] D'iribarne | La logique de l'honneur : gestion des entreprises et traditions nationales[END_REF](d'Iribarne, , 2009;;[START_REF] Segal | Efficaces, ensemble : un défi français[END_REF]. Additionally, one of the two authors was involved in many cross-cultural research projects concerning the French culture. Previous research results helped validate our interpretations of French cultural representations. We are also careful to acknowledge that the scope of this research is limited. Our study was based on an ethnographic approach. Although this provides a thorough understanding of cultural representations, this involves relatively small samples and a limited number of countries. It would therefore be necessary to enlarge the study to other countries with bigger samples to get a broader understanding of delegation across cultures. Finally, our study was conducted in a specific organizational context, namely, NGOs in the field of fair development. Further research is therefore needed to study delegation in other contexts.

Role of the funding source

Data collection was funded by GRET. With the exception of the identification of the initial managerial problem, GRET had no particular role in study design, in data collection, analysis, and interpretation of data, in the writing of the report and in the decision to submit the paper for publication.

Meddea

Project that aims to promote access to safe drinking water by installing sewage systems and water distribution systems.

Rhyviere

Program for the development of small hydropower in rural areas.

Drynet

A recent project concerned with the fight against desertification.


Mario Bravetti

Saverio Giallorenzo
email: saverio@imada.sdu.dk

Jacopo Mauro

Iacopo Talevi

Gianluigi Zavattaro

Optimal and Automated Deployment for Microservices

Keywords: Node1_large -CPU: 2, RAM: 4, cost: 100 2 RAM: 3 Attachment Analyzer Cost: CPU: 2 RAM: 3 Node2_xlarge -CPU: 4, RAM: 8, cost: 199 3 2 CPU: 2 RAM: 3 Node4_large -CPU: 2, RAM: 4, cost: 100 2 RAM: 3 Attachment Analyzer Cost: CPU: 2 RAM: 3 Node3_xlarge -CPU: 4, RAM: 8, cost: 199

Microservices are highly modular and scalable Service Oriented Architectures. They underpin automated deployment practices like Continuous Deployment and Autoscaling. In this paper we formalize these practices and show that automated deployment -proven undecidable in the general case -is algorithmically treatable for microservices.

Our key assumption is that the configuration life-cycle of a microservice is split into two phases: (i) creation, which entails establishing initial connections with already available microservices, and (ii) subsequent binding/unbinding with other microservices. To illustrate the applicability of our approach, we implement an automatic optimal deployment tool and compute deployment plans for a realistic microservice architecture, modeled in the Abstract Behavioral Specification (ABS) language.

Introduction

Inspired by service-oriented computing, Microservices structure software applications as highly modular and scalable compositions of fine-grained and looselycoupled services [START_REF] Dragoni | Microservices: yesterday, today, and tomorrow[END_REF]. These features support modern software engineering practices, like continuous delivery/deployment [START_REF] Humble | Continuous Delivery: Reliable Software Releases Through Build, Test, and Deployment Automation[END_REF] and application autoscaling [START_REF]AWS auto scaling[END_REF]. Currently, these practices focus on single microservices and do not take advantage of the information on the interdependencies within an architecture. On the contrary, architecture-level deployment supports the global optimization of resource usage and avoids "domino" effects due to unstructured scaling actions that may cause cascading slowdowns or outages [START_REF] Hellerstein | Serverless computing: one step forward, two steps back[END_REF][START_REF] Mccombs | Outages? Downtime?[END_REF][START_REF] Woods | On infrastructure at scale: a cascading failure of distributed systems[END_REF].

In this paper, we formalize the problem of automatic deployment and reconfiguration (at the architectural level) of microservice systems, proving formal properties and presenting an implemented solution.

In our work, we follow the approach taken by the Aeolus component model [START_REF] Di Cosmo | Automatic application deployment in the cloud: from practice to theory and back[END_REF][START_REF] Di Cosmo | Aeolus: a component model for the cloud[END_REF][START_REF] Di Cosmo | Towards a formal component model for the cloud[END_REF], which was used to formally define the problem of deploying component-based software systems and to prove that, in the general case, such problem is undecidable [START_REF] Di Cosmo | Towards a formal component model for the cloud[END_REF]. The basic idea of Aeolus is to enrich the specification of components with a finite state automaton that describes their deployment life cycle. Previous work identified decidable fragments of the Aeolus model: e.g., removing from Aeolus replication constraints (e.g., used to specify a minimal amount of services connected to a load balancer) makes the deployment problem decidable, but non-primitive recursive [START_REF] Di Cosmo | Aeolus: a component model for the cloud[END_REF]; removing also conflicts (e.g., used to express the impossibility to deploy in the same system two types of components) makes the problem PSpace-complete [START_REF] Mauro | On the complexity of reconfiguration in systems with legacy components[END_REF] or even poly-time [START_REF] Di Cosmo | Towards a formal component model for the cloud[END_REF], but under the assumption that every required component can be (re)deployed from scratch.

Our intuition is that the Aeolus model can be adapted to formally reason on the deployment of microservices. To achieve our goal, we significantly revisit the formalization of the deployment problem, replacing Aeolus components with a model of microservices. The main difference between our model of microservices and Aeolus components lies in the specification of their deployment life cycle. Here, instead of using the full power of finite state automata (like in Aeolus and other TOSCA-compliant deployment models [10]), we assume microservices to have two states: (i) creation and (ii) binding/unbinding. Concerning creation, we use strong dependencies to express which microservices must be immediately connected to newly created ones. After creation, we use weak dependencies to indicate additional microservices that can be bound/unbound. The principle that guided this modification comes from state-of-the-art microservice deployment technologies like Docker [START_REF] Merkel | Docker: lightweight Linux containers for consistent development and deployment[END_REF] and Kubernetes [START_REF] Hightower | Kubernetes: Up and Running Dive into the Future of Infrastructure, 1st edn[END_REF]. In particular, the weak and strong dependencies have been inspired by Docker Compose [START_REF] Docker | Docker compose documentation[END_REF] (a language for defining multi-container Docker applications) where it is possible to specify different relationships among microservices using, e.g., the depends on (resp. external links) modalities that force (resp. do not force) a specific startup order similarly to our strong (resp. weak) dependencies. Weak dependencies are also useful to model horizontal scaling, e.g., a load balancer that is bound to/unbound from many microservice instances during its life cycle.

In addition, w.r.t. the Aeolus model, we also consider resource/cost-aware deployments, taking inspiration from the memory and CPU resources found in Kubernetes. Microservice specifications are enriched with the amount of resources they need to run. In a deployment, a system of microservices runs within a set of computation nodes. Nodes represent computational units (e.g., virtual machines in an Infrastructure-as-a-Service Cloud deployment). Each node has a cost and a set of resources available to the microservices it hosts.

On the model above, we define the optimal deployment problem as follows: given an initial microservice system, a set of available nodes, and a new target microservice to be deployed, find a sequence of reconfiguration actions that, once applied to the initial system, leads to a new deployment that includes the target microservice. Such a deployment is expected to be optimal, meaning that the total cost (i.e., the sum of the costs) of the nodes used is minimal. We show that this problem is decidable by presenting an algorithm working in three phases:

(1) generate a set of constraints whose solution indicates the microservices to be deployed and their distribution over the nodes; (2) generate another set of constraints whose solution indicates the connections to be established; (3) synthesize the corresponding deployment plan. The set of constraints includes optimization metrics that minimize the overall cost of the computed deployment. The algorithm has NEXPTIME complexity because, in the worst-case, the length of the deployment plan could be exponential in the size of the input. However, we consider this worst-case unfeasible in practice, as the number of microservices deployable on one node is limited by the available resources. Under the assumption that each node can host at most a polynomial amount of microservices, the deployment problem is NP-complete and the problem of deploying a system minimizing its total cost is an NP-optimization problem. Moreover, having reduced the deployment problem in terms of constraints, we can exploit state-of-the-art constraint solvers [START_REF]The CP solver[END_REF][START_REF]GECODE: an open, free, efficient constraint solving toolkit[END_REF][START_REF]Google: Optimization tools[END_REF] that are frequently used in practice to cope with NP-hard problems.

To concretely evaluate our approach, we consider a real-world microservice architecture, inspired by the reference email processing pipeline from Iron.io [START_REF] Fromm | Thinking Serverless! How New Approaches Address Modern Data Processing Needs[END_REF]. We model that architecture in the Abstract Behavioral Specification (ABS) language, a high-level object-oriented language that supports deployment modeling [START_REF] Johnsen | ABS: a core language for abstract behavioral specification[END_REF]. We use our technique to compute two types of deployments: an initial one, with one instance for each microservice, and a set of deployments to horizontally scale the system depending on small, medium or large increments in the number of emails to be processed. The experimental results are encouraging in that we were able to compute deployment plans that add more than 30 new microservice instances, assuming availability of hundreds of machines of three different types, and guaranteeing optimality.

The Microservice Optimal Deployment Problem

We model microservice systems as aggregations of components with ports. Each port exposes provided and required interfaces. Interfaces describe offered and required functionalities. Microservices are connected by means of bindings indicating which port provides the functionality required by another port. As discussed in the Introduction, we consider two kinds of requirements: strong required interfaces, that need to be already fulfilled when the microservice is created, and weak required interfaces, that must be fulfilled at the end of a deployment (or reconfiguration) plan. Microservices are enriched with the specification of the resources they need to properly run; such resources are provided to the microservices by nodes. Nodes can be seen as the unit of computation executing the tasks associated to each microservice.

As an example, in Fig. 1 we have reported the representation of the deployment of a microservice system inspired by the email processing pipeline that we will discuss in Sect. 3. Here, we consider a simplified pipeline. A Message Receiver microservice handles inbound requests, passing them to a Message Analyzer that checks the email content and sends the attachments for inspection to an Attachment Analyzer. The Message Receiver has a port with a weak required interface that can be fulfilled by Message Analyzer instances. This requirement is weak, meaning that the Message Receiver can be initially deployed without any connection to instances of Message Analyzer. These connections can be established afterwards and reflect the possibility to horizontally scale the application by adding/removing instances of Message Analyzer. This last microservice has instead a port with a strong required interface that can be fulfilled by Attachment Analyzer instances. This requirement is strong to reflect the need to immediately connect a Message Analyzer to its Attachment Analyzer.

Figure 1 presents a reconfiguration that, starting from the initial deployment depicted in continuous lines, adds the elements depicted with dashed lines. Namely, a couple of new instances of Message Analyzer and a new instance of Attachment Analyzer are deployed. This is done in order to satisfy numerical constraints associated to both required and provided interfaces. For required interfaces, the numerical constraints indicate lower bounds to the outgoing bindings, while for provided interfaces they specify upper bounds to the incoming connections. Notice that the constraint ≥ 3 associated to the weak required interface of Message Receiver is not initially satisfied; this is not problematic because constraints on weak interfaces are relevant only at the end of a reconfiguration. In the final deployment, such a constraint is satisfied thanks to the two new instances of Message Analyzer. These two instances need to be immediately connected to an Attachment Analyzer: only one of them can use the initially available Attachment Analyzer, because of the constraint ≤ 2 associated to the corresponding provided interface. Hence, a new instance of Attachment Analyzer is added.

We also model resources: each microservice has associated resources that it consumes (see the CPU and RAM quantities associated to the microservices in Fig. 1). Resources are provided by nodes, that we represent as containers for the microservice instances, providing them the resources they require. Notice that nodes have also costs: the total cost of a deployment is the sum of the costs of the used nodes (e.g., in the example the total cost is 598 cents per hour, corresponding to the cost of 4 nodes: 2 C4 large and 2 C4 xlarge virtual machine instances of the Amazon public Cloud).

We now move to the formal definitions. We assume the following disjoint sets: I for interfaces, Z for microservices, and a finite set R for kinds of resources. We use N to denote natural numbers, N + for N \ {0}, and N + ∞ for N + ∪ {∞}.

Definition 1 (Microservice type).

The set Γ of microservice types, ranged over by T 1 , T 2 , . . ., contains 5-ples P, D s , D w , C, R where:

-P = (I → N + ∞ ) are the provided interfaces, defined as a partial function from interfaces to corresponding numerical constraints (indicating the maximum number of connected microservices); -D s = (I → N + ) are the strong required interfaces, defined as a partial function from interfaces to corresponding numerical constraints (indicating the minimum number of connected microservices); -D w = (I → N) are the weak required interfaces (defined as the strong ones, with the difference that also the constraint 0 can be used indicating that it is not strictly necessary to connect microservices); -C ⊆ I are the conflicting interfaces; -R = (R → N) specifies resource consumption, defined as a total function from resources to corresponding quantities indicating the amount of required resources.

We assume sets dom(D s ), dom(D w ) and C to be pairwise disjoint. 1Notation: given a microservice type T = P, D s , D w , C, R , we use the following postfix projections .prov, .reqs, .reqw, .conf and .res to decompose it; e.g., T .reqw returns the partial function associating arities to weak required interfaces. In our example, for instance, the Message Receiver microservice type is such that Message Receiver.reqw(MA) = 3 and Message Receiver.res(RAM) = 4. When the numerical constraints are not explicitly indicated, we assume as default value ∞ for provided interfaces (i.e., they can satisfy an unlimited amount of ports requiring the same interface) and 1 for required interfaces (i.e., one connection with a port providing the same interface is sufficient).

Inspired by [START_REF] Di Cosmo | Aeolus: a component model for the cloud[END_REF], we allow a microservice to specify a conflicting interface that, intuitively, forbids the deployment of other microservices providing the same interface. Conflicting interfaces can be used to express conflicts among microservices, preventing both of them to be present at the same time, or cases in which only one microservice instance can be deployed (e.g., a consistent and available microservice that can not be replicated).

Since the requirements associated with strong interfaces must be immediately satisfied, it is possible to deploy a configuration with circular dependencies only if at least one weak required interface is involved in the cycle. In fact, having a cycle with only strong required interfaces would mean to deploy all the microservices involved in the cycle simultaneously. We now formalize a well-formedness condition on microservice types to guarantee the absence of such configurations.

Definition 2 (Well-formed Universe). Given a finite set of microservice types U (that we also call universe), the strong dependency graph of U is as follows:

G(U ) = (U, V ) with V = {(T , T )|T , T ∈ U ∧ ∃p ∈ I.p ∈ dom(T .reqs) ∩ dom(T .prov)}. The universe U is well-formed if G(U ) is acyclic.
In the following, we always assume universes to be well-formed. Well-formedness does not prevent the specification of microservice systems with circular dependencies, which are captured by cycles with at least one weak required interface.

Definition 3 (Nodes).

The set N of nodes is ranged over by o 1 , o 2 , . . . We assume the following information to be associated to each node o in N .

-A function R = (R → N) that specifies node resource availability: we use o.res to denote such a function. -A value in N that specifies node cost: we use o.cost to denote such a value.

As example, in Fig. 1, the node Node1 large is such that Node1 large.res(RAM) = 4 and Node1 large.cost = 100.

We now define configurations that describe systems composed of microservice instances and bindings that interconnect them. A configuration, ranged over by C 1 , C 2 , . . ., is given by a set of microservice types, a set of deployed microservices (with their associated type), and a set of bindings. Formally:

Definition 4 (Configuration). A configuration C is a 4-ple Z, T, N, B where:

-Z ⊆ Z is the set of the currently deployed microservices; -T = (Z → T ) are the microservice types, defined as a function from deployed microservices to microservice types; -N = (Z → N ) are the microservice nodes, defined as a function from deployed microservices to nodes that host them; -B ⊆ I × Z × Z is the set of bindings, namely 3-ples composed of an interface, the microservice that requires that interface, and the microservice that provides it; we assume that, for (p, z 1 , z 2 ) ∈ B, the two microservices z 1 and z 2 are distinct and p ∈ (dom(T (z 1 ).reqs) ∪ dom(T (z 1 ).reqw)) ∩ dom(T (z 2 ).prov).

In our example, if we use mr to refer to the instance of Message Receiver, and ma for the initially available Message Analyzer, we will have the binding (MA, mr, ma). Moreover, concerning the microservice placement function N , we have N (mr) = Node1 large and N (ma) = Node2 xlarge.

We are now ready to formalize the notion of correctness of configuration. We first define a provisional correctness, considering only constraints on strong required and provided interfaces, and then we define a general notion of configuration correctness, considering also weak required interfaces and conflicts. The former is intended for transient configurations traversed during the execution of a reconfiguration, while the latter for the final configuration.

Definition 5 (Provisionally correct configuration). A configuration

C = Z, T, N, B is provisionally correct if, for each node o ∈ ran(N ), it holds 2 ∀ r ∈R. o.res(r) ≥ z∈Z,N (z)=o T (z).res(r)
and, for each microservice z ∈ Z, both following conditions hold: Notice that, in the example in Fig. 1, the initial configuration (in continuous lines) is only provisionally correct in that the weak required interface MA (with arity 3) of the Message Receiver is not satisfied (because there is only one outgoing binding). The full configuration -including also the elements in dotted linesis instead correct: all the constraints associated to the interfaces are satisfied.

-(p → n) ∈ T (z).
We now formalize how configurations evolve by means of atomic actions.

Definition 7 (Actions). The set A contains the following actions:

-bind(p, z 1 , z 2 ) where z 1 , z 2 ∈ Z, with z 1 = z 2 , and p ∈I: add a binding between z 1 and z 2 on port p (which is supposed to be a weak-require port of z 1 and a provide port of z 2 ); -unbind(p, z 1 , z 2 ) where z 1 , z 2 ∈Z, with z 1 = z 2 , and p ∈I: remove the specified binding on p (which is supposed to be a weak required interface of z 1 and a provide port of z 2 ); -new(z, T , o, B s ) where z ∈ Z, T ∈Γ, o ∈ N and B s = (dom(T .reqs) → 2 Z-{z} );

with B s (representing bindings from strong required interfaces in T to sets of microservices) being such that, for each p ∈ dom(T .reqs), it holds |B s (p)| ≥ T .reqs(p): add a new microservice z of type T hosted in o and bind each of its strong required interfaces to a set of microservices as described by B s ;3 -del(z) where z ∈Z: remove the microservice z from the configuration and all bindings involving it.

In our example, assuming that the initially available Attachment Analyzer is named aa, we have that the action to create the initial instance of Message Analyzer is new (ma, MessageAnalyzer, Node2 xlarge, (AA → {aa})). Notice that it is necessary to establish the binding with the Attachment Analyzer because of the corresponding strong required interface.

The execution of actions can now be formalized using a labeled transition system on configurations, which uses actions as labels.

Definition 8 (Reconfigurations). Reconfigurations are denoted by transitions C

α -→ C meaning that the execution of α ∈ A on the configuration C produces a new configuration C . The transitions from a configuration C = Z, T, N, B are defined as follows:

C bind(p,z 1 ,z 2 ) --------→ Z, T, N, B ∪ p, z1, z2
if p, z1, z2 ∈ B and p ∈ dom(T (z1).reqw) ∩ dom(T (z2).prov)

C unbind(p,z 1 ,z 2 )
----------→ Z, T, N, B \ p, z1, z2 if p, z1, z2 ∈ B and p ∈ dom(T (z1).reqw) ∩ dom(T (z2).prov)

C new (z,T ,o,Bs) ---------→ Z ∪ {z}, T , N , B if z ∈ Z and ∀ p ∈ dom(T .

reqs). ∀z ∈ Bs(p). p ∈ dom(T (z ).prov) and

T = T ∪ {(z → T )} and N = N ∪ {(z → o)} and B = B ∪ { p, z, z | z ∈ Bs(p)} C del(z) ----→ Z \{z}, T , N , B if T = {(z → T ) ∈ T | z = z } and N = {(z → o) ∈ N | z = z } and B = { p, z1, z2 ∈ B | z ∈ {z1, z2}}
A deployment plan is simply a sequence of actions that transform a provisionally correct configuration (without violating provisional correctness along the way) and, finally, reach a correct configuration.

Definition 9 (Deployment plan).

A deployment plan P from a provisionally correct configuration C 0 is a sequence of actions α 1 , . . . , α m such that:

-there exist C 1 , . . . , C m provisionally correct configurations, with C i-1 αi -→ C i for 1 ≤ i ≤ m, and -C m is a correct configuration.
Deployment plans are also denoted with

C 0 α1 -→ C 1 α2 -→ • • • αm --→ C m .
In our example, a deployment plan that reconfigures the initial provisionally correct configuration into the final correct one is as follows: a new action to create the new instance of Attachment Analyzer, followed by two new actions for the new Message Analyzers (as commented above, the connection with the Attachment Analyzer is part of these new actions), and finally two bind actions to connect the Message Receiver to the two new instances of Message Analyzer.

We now have all the ingredients to define the optimal deployment problem, that is our main concern: given a universe of microservice types, a set of available nodes and an initial configuration, we want to know whether and how it is possible to deploy at least one microservice of a given microservice type T by optimizing the overall cost of nodes hosting the deployed microservices.

Definition 10 (Optimal deployment problem).

The optimal deployment problem has, as input, a finite well-formed universe U of microservice types, a finite set of available nodes O, an initial provisionally correct configuration C 0 and a microservice type T t ∈ U . The output is:

-A deployment plan P = C 0 α1 -→ C 1 α2 -→ • • • αm --→ C m such that • for all C i = Z i , T i , N i , B i , with 1 ≤ i ≤ m, it holds ∀z ∈ Z i . T i (z) ∈ U ∧ N i (z) ∈ O, and • C m = Z m , T m , N m , B m satisfies ∃z ∈ Z m : T i (z) = T t ;
if there exists one. In particular, among all deployment plans satisfying the constraints above, one that minimizes o∈O.(∃z.Nm(z)=o) o.cost (i.e., the overall cost of nodes in the last configuration C m ), is outputted.

no (stating that no such plan exists); otherwise.

We are finally ready to state our main result on the decidability of the optimal deployment problem. To prove the result we describe an approach that splits the problem in three incremental phases: (1) the first phase checks if there is a possible solution and assigns microservices to deployment nodes, (2) the intermediate phase computes how the microservices need to be connected to each other, and (3) the final phase synthesizes the corresponding deployment plan.

Theorem 1. The optimal deployment problem is decidable.

Proof. The proof is in the form of an algorithm that solves the optimal deployment problem. We assume that the input to the problem to be solved is given by U (the microservice types), O (the set of available nodes), C 0 (the initial provisionally correct configuration), and T t ∈ U (the target microservice type). We use I(U ) to denote the set of interfaces used in the considered microservice types, namely I(U ) = T ∈U dom(T .reqs) ∪ dom(T .reqw) ∪ dom(T .prov) ∪ T .conf. The algorithm is based on three phases.

Phase 1 The first phase consists of the generation of a set of constraints that, once solved, indicates how many instances should be created for each microservice type T (denoted with inst(T )), how many of them should be deployed on node o (denoted with inst(T , o)), and how many bindings should be established for each interface p from instances of type T -considering both weak and strong required interfaces -and instances of type T (denoted with bind(p, T , T )). We also generate an optimization function that guarantees that the generated configuration is minimal w.r.t. its total cost.

We now incrementally report the generated constraints. The first group of constraints deals with the number of bindings:

p∈I(U )
T ∈U, p∈dom(T .reqs)

T .reqs(p) • inst(T ) ≤ T ∈U bind(p, T , T ) (1a) p∈I(U ) T ∈U, p∈dom(T .reqw) T .reqw(p) • inst(T ) ≤ T ∈U bind(p, T , T ) (1b) p∈I(U ) T ∈U, T .prov(p)<∞ T .prov(p) • inst(T ) ≥ T ∈U bind(p, T , T ) (1c) p∈I(U ) T ∈U, T .prov(p)=∞ inst(T ) = 0 ⇒ T ∈U bind(p, T , T ) = 0 (1d) p∈I(U ) T ∈U, p / ∈dom(T .prov) T ∈U bind(p, T , T ) = 0 (1e)
Constraint 1a and 1b guarantee that there are enough bindings to satisfy all the required interfaces, considering both strong and weak requirements. Symmetrically, constraint 1c guarantees that the number of bindings is not greater than the total available capacity, computed as the sum of the single capacities of each provided interface. In case the capacity is unbounded (i.e., ∞), it is sufficient to have at least one instance that activates such port to support any possible requirement (see constraint 1d). Finally, constraint 1e guarantees that no binding is established connected to provided interfaces of microservice types that are not deployed.

The second group of constraints deals with the number of instances of microservices to be deployed.

inst(Tt) ≥ 1 (2a) p∈I(U ) T ∈U, p∈T .conf T ∈U -{T }, p∈dom(T .prov) inst(T ) > 0 ⇒ inst(T ) = 0 (2b) p∈I(U ) T ∈U, p∈T .conf ∧ p∈dom(T .prov) inst(T ) ≤ 1 (2c) p∈I(U ) T ∈U T ∈U -{T } bind(p, T , T ) ≤ inst(T ) • inst(T ) (2d) p∈I(U ) T ∈U bind(p, T , T ) ≤ inst(T ) • (inst(T ) -1) (2e)
The first constraint 2a guarantees the presence of at least one instance of the target microservice. Constraint 2b guarantees that no two instances of different types will be created if one activates a conflict on an interface provided by the other one. Constraint 2c, consider the other case in which a type activates the same interface both in conflicting and provided modality: in this case, at most one instance of such type can be created. Finally, the constraints 2d and 2e guarantee that there are enough pairs of distinct instances to establish all the necessary bindings. Two distinct constraints are used: the first one deals with bindings between microservices of two different types, the second one with bindings between microservices of the same type.

The last group of constraints deals with the distribution of microservice instances over the available nodes O.

inst(T ) = o∈O inst(T , o) (3a) r∈R o∈O T ∈U inst(T , o) • T .res(r) ≤ o.res(r) (3b) o∈O T ∈U inst(T , o) > 0 ⇔ used(o) (3c) min o∈O, used(o) o.cost (3d)
Constraint 3a simply formalizes the relationship among the variables inst(T ) and inst(T , o) (the total amount of all instances of a microservice type, should correspond to the sum of the instances locally deployed on each node). Constraint 3b checks that each node has enough resources to satisfy the requirements of all the hosted microservices. The last two constraints define the optimization function used to minimize the total cost: constraint 3c introduces the boolean variable used(o) which is true if and only if node o contains at least one microservice instance; constraint 3d is the function to be minimized, i.e., the sum of the costs of the used nodes.

These constraints, and the optimization function, are expected to be given in input to a constraint/optimization solver. If a solution is not found it is not possible to deploy the required microservice system; otherwise, the next phases of the algorithm are executed to synthesize the optimal deployment plan.

Phase 2 The second phase consists of the generation of another set of constraints that, once solved, indicates the bindings to be established between any pair of microservices to be deployed. More precisely, for each type T such that inst(T ) > 0, we use s T i , with 1 ≤ i ≤ inst(T ), to identify the microservices of type T to be deployed. We also assume a function N that associates microservices to available nodes O, which is compliant with the values inst(T , o) already computed in Phase 1, i.e., given a type T and a node o, the number of s T i , with

1 ≤ i ≤ inst(T ), such that N (s T i ) = o coincides with inst(T , o).
In the constraints below we use the variables b(p, s T i , s T j ) (with i = j, if T = T ): its value is 1 if there is a connection between the required interface p of s T i and the provided interface p of s T j , 0 otherwise. We use n and m to denote inst(T ) and inst(T ), respectively, and an auxiliary total function limProv (T , p) that extends T .prov associating 0 to interfaces outside its domain.

T ∈U p∈I(U ) i∈1...n j∈(1...m)\{i|T =T } b(p, s T i , s T j ) ≤ limProv (T , p) (4a) T ∈U p∈dom(T .reqs) i∈1...n j∈(1...m)\{i|T =T } b(p, s T i , s T j ) ≥ T .reqs(p) (4b) T ∈U p∈dom(T .reqw) i∈1...n j∈(1...m)\{i|T =T } b(p, s T i , s T j ) ≥ T .reqw(p) (4c) T ∈U p / ∈dom(T .reqs)∪dom(T .reqw) i∈1...n j∈(1...m)\{i|T =T } b(p, s T i , s T j ) = 0 (4d)
Constraint 4a considers the provided interface capacities to fix upper bounds to the bindings to be established, while constraints 4b and 4c fix lower bounds based on the required interface capacities, considering both the weak (see 4b) and the strong (see 4c) ones. Finally, constraint 4d indicates that it is not possible to establish connections on interfaces that are not required.

A solution for these constraints exists because, as also shown in [START_REF] Di Cosmo | Automatic application deployment in the cloud: from practice to theory and back[END_REF], the constraints 1a . . . 2e (already solved during Phase 1) guarantee that the config-uration to be synthesized contains enough capacity on the provided interfaces to satisfy all the required interfaces.

Phase 3 In this last phase we synthesize the deployment plan that, when applied to the initial configuration C 0 , reaches a new configuration C t with nodes, microservices and bindings as computed in the first two phases of the algorithm. Without loss of generality, in this decidability proof we show the existence of a simple plan that first removes the elements in the initial configuration and then deploys the target configuration from scratch. However, as also discussed in Sect. 3, in practice it is possible to define more complex planning mechanisms that re-use microservices already deployed.

Reaching an empty configuration is a trivial task since it is always possible to perform in the initial configuration unbind actions for all the bindings connected to weak required interfaces. Then, the microservices can be safely deleted. Thanks to the well-formedness assumption (Definition 2) and using a topological sort, it is possible to order the microservices to be removed without violating any strong required interface (e.g., first remove the microservice not requiring anything and repeat until all the microservices have been deleted).

The deployment of the target configuration follows a similar pattern. Given the distribution of microservices over nodes (computed in the first phase) and the corresponding bindings (computed in the second phase), the microservices can be created by following a topological sort considering the microservices dependencies following from the strong required interfaces. When all the microservices are deployed on the corresponding nodes, the remaining bindings (on weak required ports) may be added in any possible order. Remark 1. The constraints generated during Phase 2 of the algorithm, in order to establish the microservice bindings, are expected to be given in input to a constraint/optimization solver. One can enrich such constraints with metrics to optimize, e.g., the number of local bindings (i.e., give a preference to the connections among microservices hosted in the same node): min T ,T ∈U,i∈1...inst(T ),j∈1...inst(T ),p∈I(U ),N (s

T i ) =N (s T j ) b(p, s T i , s T j )
Another example, used in the case study discussed in Sect. 3, is the following metric that maximizes the number of bindings4 : max

s T i ,s T j ,p∈I(U ) b(p, s T i , s T j )
From the complexity point of view, it is possible to show that the decision versions of the optimization problem solved in Phase 1 is NP-complete, in Phase 2 is in NP, while the planning in Phase 3 is synthesized in polynomial time.

Unfortunately, due to the fact that numeric constraints can be represented in log space, the output of Phase 2 requiring the enumeration of all the microservices to deploy can be exponential in the size of the output of Phase 1 (indicating only the total number of instances for each type). For this reason, the optimal deployment problem is in NEXPTIME. However, we consider unfeasible in practice the deployment of an exponential number of microservices on one node having limited resources. If at most a polynomial number of microservices can be deployed on each node, we have that the optimal deployment problem becomes an NP-optimization problem and its decision version is NP-complete. See the companion technical report [START_REF] Bravetti | Optimal and automated deployment for microservices[END_REF] for the formal proofs of complexity.

Application of the Technique to the Case-Study

Given the asymptotic complexity of our solution (NP under the assumption of polynomial size of the target configuration) we have decided to evaluate its applicability in practice by considering a real-world microservice architecture, namely the email processing pipeline described in [START_REF] Fromm | Thinking Serverless! How New Approaches Address Modern Data Processing Needs[END_REF]. The considered architecture separates and routes the components found in an email (headers, links, text, attachments) into distinct, parallel sub-pipelines with specific tasks (e.g., remove malicious attachments, tag the content of the mail). We report in Fig. 2 a depiction of the architecture. When an email reaches the Message Receiver it is forwarded to the Message Parser, which sends each component into a specific sub-pipeline. In the sub-pipelines, some microservices -e.g., Text Analyzer and Attachment Analyzer -coordinate with other microservices -e.g., Sentiment Analyzer and Virus Scanner -to process their inputs. Each microservice in the architecture has a given resource consumption (expressed in terms of CPU and memory). As expected, the processing of each email component entails a specific load. Some microservices can handle large inputs, e.g., in the range of 40K simultaneous requests (e.g., Header Analyzer that processes short and uniform inputs). Other microservices sustain heavier computations (e.g., Image Recognizer) and can handle smaller simultaneous inputs, e.g., in the range of 10K requests.

To model the system above, we use the Abstract Behavioral Specification (ABS) language, a high-level object-oriented language that supports deployment modeling [START_REF] Johnsen | ABS: a core language for abstract behavioral specification[END_REF]. ABS is agnostic w.r.t. deployment platforms (Amazon AWS, Microsoft Azure) and technologies (e.g., Docker or Kubernetes) and it offers high-level deployment primitives for the creation of new deployment components and the instantiation of objects inside them. Here, we use ABS deployment components as computation nodes, ABS objects as microservice instances, and ABS object references as bindings. Finally, to describe the requirements in our model, we use ABS with SmartDepl [START_REF] De Gouw | Declarative elasticity in ABS[END_REF], an extension that supports deployment annotations. Strong required interfaces are modeled as class annotations indicating mandatory parameters for the class constructor: such parameters contain the references to the objects corresponding to the microservices providing the strongly required interfaces. Weak required interfaces are expressed as annotations concerning specific methods used to pass, to an already instantiated object, the references to the objects providing the weakly required interfaces. We define a class for each microservice type, plus one load balancer class for each microservice type. A load balancer distributes requests over a set of instances that can scale horizontally. Finally, we model nodes corresponding to Amazon EC2 instances: c4 large, c4 xlarge, and c4 2xlarge (with the corresponding provided resources and costs).

Microservice (max computational load) Initial (10K) +20K +50K +80K MessageReceiver(∞)

1 ---

MessageParser(40K) 1 - +1 -
HeaderAnalyzer(40K) 1 - +1 - LinkAnalyzer(40K) 1 - +1 - TextAnalyzer(15K) 1 +1 +2 +2 SentimentAnalyzer(15K) 1 +3 +4 +6 AttachmentsManager(30K) 1 +1 +2 +2 VirusScanner(13K) 1 +3 +4 +6
ImageAnalyzer(30K) 1 +1 +2 +2 NSFWDetector(13K) 1 +3 +4 +6
ImageRecognizer(13K) 1 +3 +4 +6 MessageAnalyzer(70K) 1 +1 +2 +2
In the table above, we report the result of our algorithm w.r.t. four incremental deployments: the initial in column 2 and under incremental loads in 3-5. We also consider an availability of 40 nodes for each of the three node types. In the first column of the Table, next to a microservice type, we report its corresponding maximum computational load, i.e., the maximal number of simultaneous requests that it can manage. As visible in columns 2-5, different maximal computational loads imply different scaling factors w.r.t. a given number of simultaneous requests. In the initial configuration we consider 10K simultaneous requests and we have one instance of each microservice type (and of the corresponding load balancer). The other deployment configurations deal with three scenarios of horizontal scaling, assuming three increasing increments of inbound messages (20K, 50K, and 80K). In the three scaling scenarios, we do not implement the planning algorithm described in Phase 3 of the proof of Theorem 1. Contrarily, we take advantage of the presence of the load balancers and, as described in Remark 1, we achieve a similar result with an optimization function that maximizes the number of bindings of the load balancers. For every scenario, we use SmartDepl [START_REF] Mauro | Smartdepl[END_REF] to generate the ABS code for the plan that deploys an optimal configuration, setting a timeout of 30 min for the computation of every deployment scenario. 5 The ABS code modeling the system and the generated code are publicly available at [START_REF] Bravetti | Code repository for the email processing example[END_REF]. A graphical representation of the initial configuration is available in the companion technical report [START_REF] Bravetti | Optimal and automated deployment for microservices[END_REF].

Related Work and Conclusion

In this work, we consider a fundamental building block of modern Cloud systems, microservices, and prove that the generation of a deployment plan for an architecture of microservices is decidable and fully automatable; spanning from the synthesis of the optimal configuration to the generation of the deployment actions. To illustrate our technique, we model a real-world microservice architecture in the ABS [START_REF] Johnsen | ABS: a core language for abstract behavioral specification[END_REF] language and we compute a set of deployment plans.

The context of our work regards automating Cloud application deployment, for which there exist many specification languages [START_REF] Bergmayr | A systematic review of cloud modeling languages[END_REF][START_REF] Chardet | Madeus: a formal deployment model[END_REF], reconfiguration protocols [START_REF] Boyer | Robust reconfigurations of component assemblies[END_REF][START_REF] Durán | Robust and reliable reconfiguration of cloud applications[END_REF], and system management tools [START_REF]Red Hat Ansible[END_REF][START_REF] Kanies | Puppet: next-generation configuration management[END_REF]37,[START_REF]Puppet Labs: Marionette collective[END_REF]. Those tools support the specification of deployment plans but they do not support the automatic distribution of software instances over the available machines. The proposals closest to ours are those by Feinerer [START_REF] Feinerer | Efficient large-scale configuration via integer linear programming[END_REF] and by Fischer et al. [START_REF] Fischer | Engage: a deployment management system[END_REF]. Both proposals rely on a solver to plan deployments. The first is based on the UML component model, which includes conflicts and dependencies, but lacks the modeling of nodes. The second does not support conflicts in the specification language. Neither proposals support the computation of optimal deployments. Three projects inspire our proposal: Aeolus [START_REF] Di Cosmo | Automatic application deployment in the cloud: from practice to theory and back[END_REF][START_REF] Di Cosmo | Aeolus: a component model for the cloud[END_REF], Zephyrus [START_REF] Ábrahám | Zephyrus2: on the fly deployment optimization using SMT and CP technologies[END_REF], and Conf-Solve [START_REF] Hewson | A declarative approach to automated configuration[END_REF]. The Aeolus model paved the way to reason on deployment and reconfiguration, proving some decidability results. Zephyrus is a configuration tool based on Aeolus and it constitutes the first phase of our approach. ConfSolve is a tool for the optimal allocation of virtual machines to servers and of applications to virtual machines. Both tools do not synthesize deployment plans.

Regarding autoscaling, existing solutions [START_REF]Amazon CloudWatch[END_REF][START_REF]Apache: Apache Mesos[END_REF][START_REF] Docker | Docker swarm[END_REF][START_REF] Hightower | Kubernetes: Up and Running Dive into the Future of Infrastructure, 1st edn[END_REF] support the automatic increase or decrease of the number of instances of a service/container, when some conditions (e.g., CPU average load greater than 80%) are met. Our work is an example of how we can go beyond single-component horizontal scaling policies (as analyzed, e.g., in [START_REF] Bravetti | Replicating web services for scalability[END_REF]).

As future work, we want to investigate local search approaches to speed-up the solution of the optimization problems behind the computation of a deployment plan. Shorter computation times would open our approach to contexts where it is unfeasible to compute plans ahead of time, e.g., due to unpredictable loads.

Fig. 1 .

 1 Fig. 1. Example of microservice deployment (blue boxes: nodes; green boxes: microservices; continuous lines: the initial configuration; dashed lines: full configuration). (Color figure online)

  reqs implies that there exist n distinct microservices z 1 , . . . , z n ∈ Z \{z} such that, for every 1 ≤ i ≤ n, we have p, z, z i ∈ B; -(p → n) ∈ T (z).prov implies that there exist no m distinct microservices z 1 , . . . , z (z).reqw implies that there exist n distinct microservices z 1 , . . . , z n ∈ Z \{z} such that, for every 1 ≤ i ≤ n, we have p, z, z i ∈ B; -p ∈ T (z).conf implies that, for each z ∈ Z\{z}, we have p / ∈ dom(T (z ).prov).

m ∈ Z \{z}, with m > n, such that, for every 1 ≤ i ≤ m, we have p, z i , z ∈ B.

Definition 6 (Correct configuration).

A configuration C = Z, T, N, B is correct if C is provisionally correct and, for each microservice z ∈ Z, both following conditions hold:

-(p → n) ∈ T

Given a partial function f , we use dom(f ) to denote the domain of f , i.e., the set {e | ∃e : (e, e ) ∈ f }.

Given a (partial) function f , we use ran(f ) to denote the range of f , i.e., the function image set {f (e) | e ∈ dom(f )}.

Given sets S and S we use: 2 S to denote the power set of S, i.e., the set {S | S ⊆ S}; S -S to denote set difference; and |S| to denote the cardinality of S.

We model a load balancer as a microservice having a weak required interface, with arity 0, that can be provided by its back-end service. By adopting the above maximization metric, the synthesized configuration connects all possible services to such required interface, thus allowing the load balancer to forward requests to all of them.

Here, 30 min are a reasonable timeout since we predict different system loads and we compute in advance a different deployment plan for each of them. An interesting future work would aim at shortening the computation to a few minutes (e.g., around the average start-up time of a virtual machine in a public Cloud) to obtain on-the-fly deployment plans tailored to unpredictable system loads.