Pascale Trompette

POMPES FUNÈBRES AND THE OVERFLOWING OF OSTENTATIOUS FUNERALS

The 19th century saw the formation of the funeral market in France. Within the context of constant interference by Church and State, the first pompes funèbres (funeral companies or undertakers) gradually spread from Paris into the major provincial cities and their outskirts to assume the role of supplier of funeral goods and services. How did the trade of funeral goods, under the clergy's rule over previous centuries, become the source of private business prosperity through a process of increasing commodification of the funeral goods on offer? In this chapter, I suggest that the case of the funeral market offers a privileged insight into the way public utilities lead to specific forms of market, in which "market devices" closely link politics and markets, both in their framework and in their "overflowing" of the framework.

, all describing the entanglement of market and non-market forces. In her famous study on the history of life insurance -a subject close to the death market discussed in this chapter -Vivianne Zelizer (1978) suggested that the historical process of the changing social value of death and the transformation of cultural meaning be followed.

. The point of these market devices is to incorporate this institutional complexity into the other essential problems of coordination that must be resolved: value formation, regulation of competition, and the organization of 1 This Napoleonic law was directly inspired by the tried and tested organizational funeral régime that had been negotiated with the parish councils and undertakers, and introduced in Paris by the prefect, N. Frochot, in the preceding years.

cooperation (Beckert, 2007).

The funeral economy of 19th century France was the subject of conflicting political and moral appropriations, notably in the confrontation between Church and State. The following analysis demonstrates how market devices integrated "calculation formulae," which conveyed a substantial political dimension, in an attempt to balance the divergent values and interests of the stakeholders. I suggest that this form of political calculation, as an institutional compromise slotted into a price-setting mechanism, was decisive for the merging of private business interests with the public management of death. To understand how funeral merchants fit into this complex and conflicting institutional context, one must follow them in the way they interceded in this institutional interplay and succeeded in managing the dissonance among the stakeholders [START_REF] Stark | The sense of dissonance. Accounts of worth in economic life[END_REF]. Only then it is possible to see how the formation of the market proceeded from the continual reinvention of this "frame-setting" as an attempt to manage overflow. This movement spread on two levels: the entrepreneur's ability to fructify the trade of funeral goods beyond the redistribution of its benefits; and the intrusion of peripheral actors, attracted by this flourishing trade, to develop competition at the margins.

The pragmatic approach to market formation is notably inspired by the work of Michel Callon, through his focus on socio-technical arrangements (STA) in shaping calculation activities and formatting economic interactions [START_REF] Callon | The laws of the markets[END_REF][START_REF] Caliskan | Economization, part 2: a research program for the study of markets[END_REF]. I follow complementary approaches by considering these founding market devices as "dynamic configurations" of material and narrative elements, inevitably including market infrastructure and political aims [START_REF] Fourcade | Moral views of market society[END_REF][START_REF] Kjelberg | Political Marketing: multiple values, performativies and modes of engaging[END_REF][START_REF] Mcfall | Pragmatics and politics: The case of industrial branch assurance in the UK 1880-1990[END_REF]. The further objective is to show how the continuous movement of framing/overflowing around the panel of supplies generated its constant expansion in line with the growth of entrepreneurship and competition.

Formal sharing among the Church, the State, and the pompes funèbres The property rights agreement

The story begins with the legislation of 1804, when property rights and rules for sharing among the various protagonists were formally established, along with a formal institutional framework. The Year XII Prairial Decree, introduced in June 1804 under Napoleon, 1 established a political framework to settle divergences between the State and the Church. The aim of the law was to end the burial crisis in Paris and other French cities -a result of Revolutionary absolutism and its attempt to make a clean sweep of the past. In re-establishing the alliance of State and Church, Napoleon reinstated exclusive rights to the ceremonial side of the funerals to the fabriques (vestries),2 in order to compensate the Church for its losses. At the same time, it confirmed the municipalities as the coregulatory authority for the part of funeral ceremonies that occurred outside the Church building -the transporting of the body to the cemetery. It also permitted the pompes funèbres to develop their trade both as the contract holder of the monopoly and as a competitor for peripheral supplies (graves and ornaments). These new pompes funèbres were often the direct heirs of the corporations (town criers3 , candle makers, coffin makers) that had continued to supply funeral material during the revolutionary period4 (du [START_REF] Camp | Les cimetières de Paris et le danger des nécropoles urbaines[END_REF].

This "political exchange" [START_REF] Pizzorno | Political exchange and collective identity in industrial conflict[END_REF] was established through a division of the service into three areas: the "internal service," covering the offer of goods and services associated with the religious ceremony (e.g. candles, wall hangings, and priests), and for which the authority in charge was the clergy; the "external service," covering the organization of the funeral cortège (procession) through the town and as far as the cemetery; and the "extra service," which designated such supplies and accessories as wreaths and flowers that were sold by companies outside the monopoly at freely set prices.

The 1804 law had thus constituted the key distributive partition of tasks among the Church, the State, and the emerging private industry, by splitting up the supply side of funeral goods and services. At the same time, it provided the base of a vast enterprise of competing "qualifying" and valuing goods [START_REF] Callon | The economy of qualities[END_REF], a subject that turned out to be extremely conflictual. The coffin, the draperies, the medallions and insignia, the carriage (later the "hearse") -but also the prayers and other participants in the procession-all these things, and many more, became part of the long list of "ancillary" services and goods provided by the three purveyors (religious, public, and "extra").

Their valuation (the determination of tariffs) was to be kept under close control by public authorities (municipal council, prefect, and emperor). The entire distribution of services was, in fact, eminently political. The public or "external service" covered the minimum service (coffin, porters, and the individual grave 5 ), which demonstrated the equality of all citizens outside the church. The religious ceremonial or "internal service" (the religious service and all decorations for the church and the home of the deceased) provided parish revenues from the embellishment of the procession with levels of decorum and pomp as befitted the wealth of the deceased. The area of "extra goods" was initially seen as supporting the undertaker's investments to provide the public service. In time, however, this profitable sphere gave rise to constant controversies concerning its boundaries and the benefits accruing therefrom.

Established in 1804, this mapping of property rights over the production of material and symbolic goods evolved continuously over the following centuries: first, through the way in which the participants profited from their prerogatives, extending the catalogue of goods on offer in each category and falling out over the issue of who had the right to what; then, through the major institutional changes brought about by the separation of Church and State in 1905, which modified the distributive balance among the three protagonists. In this chapter, I examine the way in which this political frame was taken over, reconstructed, and indeed overflowed by local participants, particularly in urban centers, where there was a greater concentration of mortality.

Coordination and arrangements between participants at the local level

The Prairial Decree set out the framework for negotiations between civil and religious administrations, by distributing attributions and powers with respect to the administration of tariffs. But it left it free to local actors to implement the law and to invent their own arrangements. In fact, in most of the country, which was semi-rural and rural, the fabriques conceded their monopoly, which tended not to be profitable in areas where the proportion of upper classes -and expensive funerals -was low. As in previous centuries, the organization of burials in the countryside relied on community solidarity in the form of neighbors, family and next of kin, the parish priest, or charity brotherhoods. In major French cities, on the other hand, the fabriques negotiated with public authorities to set up a local organization for funerals. The testimonies provided by historians [START_REF] Kselman | Death and the Afterlife in Modern France[END_REF][START_REF] Bellanger | La mort, une affaire publique[END_REF][START_REF] Bertherat | Paris dernier voyage. Histoire des pompes funèbres (XIX e -XX e siècles)[END_REF] and jurists [START_REF] Gaubert | Traité théorique et pratique de législation, de doctrine et de jurisprudence sur le monopole des inhumations et des pompes funèbres[END_REF][START_REF] Rubat Du Merac | Le nouveau régime des pompes funèbres[END_REF] describe this progressive construction as punctuated by various failures and changes, organizational schemes and forms of regulation, as well as the appearance of private companies.

It is within this institutional context that recourse to a private company began to emerge as a solution that was especially favored by the various protagonists, because it allowed for economic balance as part of a political tradeoff [START_REF] Trompette | Political Exchanges in the French Funeral Market. Management and Organizational History[END_REF]. Thus the concessionaire, the pompes funèbre chosen by the municipal government, now held the monopoly for funeral services conducted in the area. Within major cities -Paris and its suburbs, Angers, Tours, and others -historical analyses of the negotiations between institutional stakeholders and pompes funèbres at both the local and national levels 6 demonstrate that the pompes funèbres managed to establish themselves as efficient trade mediators. Given the context of uncertainty and the possible legislative changes, 7 private businesses could guarantee a profit, whereas the parish or municipal councils could not. By granting them substantial commissions on the sale of funeral goods, they were able to provide significant revenues to the parish councils. Referring to the first discussions among the episcopal officials; the town hall officials; and Mr. Jeramec, representing the company Pompes Funèbres Générales (PFG), Kselman reports that "[Mr. Jeramec] demonstrated to episcopal officials that the fabriques of Angers would suffer serious losses in revenue after the new decree was implemented. (…) He proposed that the undertaker add a list of options beyond the items agreed to by the fabriques and the city council, on the sale of which he would remit 25 percent to the parishes" (Kselman, 1993: 266). The profit mechanism established by the private operators to increase profitability was simple: they added superfluous accessories (at freely set prices) to the classified offer of goods, awarding the parish councils a commission on these supplies, albeit much lower than the commissions offered for the main categories of services that they administered. Cushions, drapes, flowers, and various accessories enhanced the pomp of funerals, and the profits were redistributed between the entrepreneur and the fabriques. To forestall the city's opposition to such profitable activities being in private hands, these new "entrepreneurs"8 made provision for what was basically the municipality's responsibility: transporting the body to the cemetery.

Thus the official concessionaire applied a delegated calculation or rather, in this case, a "delegated profit." "(…) [T]he lay undertakers saved the clergy the embarrassing task of collecting fees for services, while providing the parishes with sufficient funds for maintaining the cult; (…) cities profited from the system by freeing themselves of the charge of burying the poor. (…) By increasing the revenues for the parishes, city governments would free themselves of potential expenses, because the law controlling municipalities made them liable for any deficits run up by the fabriques" (Kselman, 2003: 272). By adapting the goods on offer, the concessionaire guaranteed profits that were redistributed in the direction of both religious and public interests (setting up a win-win situation). Given their opposing interests, the institutional stakeholders were thereby freed from any direct confrontation in the management of funerals and the attendant goods trade. The concession model (leasing solution) would therefore become the most widely used model, in which the fabriques and the municipal authorities would delegate, "under their tutelary supervision," the running of funeral services as a monopoly to the concessionaire, including a free service offered to the destitute.

The system of categories (classes of funerals) :Framing the sharing of profits

The control exercised by the authorities among themselves and over the pompes funèbres was exerted principally through the administration of tariffs; within each category of service (religious, public, extra goods), lists of items with corresponding prices were to be defined and approved by the clergy and public officials (city council, prefect), under state supervision (the Minister of the Interior). This tutelary controlling function covered the official undertaker business, on the basis of the cahiers des charges (contract conditions) that fixed the product tariffs and the percentage commission to be paid to the fabriques. The device that was invented to support this activity of co-regulation is especially noteworthy. The administration of tariffs was "mediated" [START_REF] Latour | Reassembling the social. An introduction to actor-networktheory[END_REF] by packaging the listed range of goods and services to be supplied by each protagonist into a series of categories or classes of funerals 9 ranging in number from three to ten, depending on the town being provided. The system of classes has the essential virtue of "attaching" the goods among them, while ordering them into a valuation scale [START_REF] Guyer | The Eruption of tradition. On ordinality and calculation[END_REF], a calculation infrastructure that framed and performed in several ways the interplay among the actors. First, it allowed those running the trade to fix the sharing of the spoils in advance, in order to balance the profits among the clergy, the fabriques, and the entrepreneurs: "the degree of luxury must be carefully graded, in such a way that the correlation between the two services 10 be as clear and complete as possible" 11 (Gaubert, 1890: 198). Then, the officials justified this carefully graded offer of classes of service as a means of simplifying the task for grieving families. "In a moment when the distress takes away the necessary presence for mind" (Gaubert, 1875: 129), the classes of funerals prevented the families from making a long series of choices through an interminable list of individual items. It also limited the freedom of the entrepreneur to compose his own "basket of merchandises," which, it was feared, could have lead to all kinds of "abuses." While framing the social craving for distinction and social distinctiveness, however, the system of classes described a value scale. Thus the degree of funeral pomp could readily reflect the social rank: "the number of class categories should be increased depending of the variety of wealth," prescribed the Minister of the Interior to the prefects in his 1852 decree. The system of classes can therefore be seen as a market device framing the interplays among all the stakeholders, but also as a first attempt to manage the potential overflow of consumption habits 9 Translation of the French term classes d'enterrement. 10 B. Gaubert (a lawyer) is talking here about the correlation between the religious service within the church on the one hand; and the public service, including the funeral procession throughout the town, on the other hand -both of which are part of the classes of service. 11 Kselman reports that the system of classes, initially established for the religious service in Paris in 1803, was, extended by law in 1806 to include the entire funeral ceremony. Then, various regulations expressed the attempt to set the correlation between the categories linking the religious and the (public) ceremonial procession: "The law also required that families be presented with only one bill and assumed that they would choose the same class for both the religious services and the funeral procession" (Kselman, 1993: 236; see also Gaubert, 1875: 200, italics added).

and the luxury business applied to funerals.

Beyond the regulation of profit sharing, this formal frame carried a positive and moral intention, directly incorporated in the categories and price design. One should also note that price differences between the classes of funerals were considerable: "From six thousand francs, the price of a first-class funeral, one drops to one thousand eight hundred francs for the second class, to seven hundred for the third, to two hundred and fifty francs for the fourth, and to one hundred for the fifth. And this fifth class is subdivided, to lower amounts of forty or even thirty-six" (Fievée, 1811). Even if it is clear that this is far from the egalitarian absolutism of the Revolution, this range of tariffs -or prices for the packages -nonetheless serves the general interest, namely guaranteeing a minimal standard of service for every citizen. Thus the price range was constructed such that the ostentatious satisfaction of the richest and the middle class would serve to benefit the poorest, and particularly the destitute, that represented a sizeable proportion of burials 12 .

In its report on the Paris Official Company of pompes funèbres, under the heading of General Observations, following the classes and tariff specifications, M. Fiévée, counselor to Napoleon, exclaimed:

In this respect, the needs of society were at the root of the calculations. The funeral service cannot possibly be organized in ways other than through a private company, and it should be unjust if this company, performing fourteen thousand six hundred funerals annually, without taking into account the disposal of those dying in hospital, didn't make profits according to its business and to the funds it has been required to invest (…) these invested founds are covered by around three thousand burials with more or less "pomp." Nine thousand funerals of the non-indigent fall under the common and uniform pattern of transport to the grave without ceremony; and two thousand four hundred of the totally destitute are buried freely. We see that, while the business applies to a great number of people, only a quarter generates profits. (M. Fievée, 1811: 25-26, italics added) 13

Managing dissonance, managing overflow

One can analyze this framework of regulations (the segmentation into three parts and the various classes of funerals) as a market device that regulates the 12 In his study of the Parisian bourgeoisie in the 19th century A. [START_REF] Daumard | La bourgeoisie parisienne de 1815 à 1848[END_REF], provides the data issued by the Journal de la Société Statistique on the details of the funeral arrangements covered by the main Paris pompes funèbres company. Between 1821 and 1830, 83% of all burials (out of 261,360 deaths) were those of indigents. Between 1839 and 1848, the percentage dropped from 73% and 76.9%. According to du Camp, the rate of burials of the poor and indigents still reached 74% of all the funerals in 1873 (Camp (du) 1874). PASCALE: WHY IS (DU) IN PARENTHESES? Within major cities in the provinces, the percentage is closer to 30 to 40%, which nevertheless represents a significant expense and a regular subject of conflict between the fabriques and the town hall [START_REF] Lassère | Les pauvres et la mort en milieu urbain[END_REF]. 13 All translations in this chapter are by the author.

articulation of economic and political interests and supports the coordination of the various actors in the funeral economy. But one can also observe that the framework organizes an axiological combination, allowing the cohabitation of value systems and legitimacies that were initially opposed to each other [START_REF] Zelizer | Human values and the market: The case of life insurance and death in 19th-century America[END_REF].

Funerals are, in effect, one of the privileged arenas in which one finds focused the political and value conflicts that animated the relationships among State, Church, and civil and political society in the 19th century. On one side is the revolutionary project, which was forged in a fight against the clericalization of funerals and against the continuation of social inequalities, epitomized in the sumptuous pomp of the grandiose funeral cortège. One must remember the degree to which the institution of civic funerals was animated by a superior principle during the Revolution (under the Convention) -the principle that "of imposing funereal dignity through the sole majesty of the law, without pomp, without splendor and to the absolute exclusion of all religious thought" (Gaubert, 1875: 151). But this revolutionary absolutism would finally be abandoned once it became clear that the organization of funerals could not be dissociated from the social and religious attributes that surrounded the cult of the dead [START_REF] Fureix | De l'hommage funèbre à la prise de parole. L'enterrement du général Foy (novembre 1825)[END_REF][START_REF] Lalouette | Mourir contre les siens. La famille, la religion et la mort au XIX et XXème siècles[END_REF]. Even with its secularist pretensions attenuated, the political power maintained an egalitarian mission, if only through the institution of a civil funeral service and the free burial of the destitute. On the other side, through the Concordat, the Church had been rehabilitated as a legitimate actor in the production of symbolic goods, and burials remained linked to the cult of the dead. This situation reflected the spirit of what was still a profoundly religious society [START_REF] Isambert | Enterrements civils et classe sociale[END_REF]Laouette, 2001).

Furthermore, the reinstatement of pomp in the funeral echoes the taste of 19th century high society for an imposing ceremonial, a craving for the public display of splendor, which experienced an increasing popularity through the century and across the country [START_REF] Segalen | Rituels funéraires en Normandie et attitudes vis-à-vis de la mort[END_REF][START_REF] Kselman | Death and the Afterlife in Modern France[END_REF]. It was through the purchase of distinctive furnishings and other trappings that an economy of homage in bourgeois society could be displayed -the proper way of signifying the rank of deceased persons in society and the respect due to them. Following the example of historians, one can discover in the literary descriptions of funerals (in the works of Balzac and Zola, for example) the degree to which appearances in public and the "exchange of looks" in measuring ostentation had gained a hold in the middle classes.

At the end of the funeral procession there are twelve coaches of mourners; they are counted and commented on as the cortège passes through the neighborhood. (...) Agatha, who was seated in the front pew of the church seemed to be counting the number of lit candles. (Zola, 1902(Zola, /2002: 14, 22) : 14, 22) It was to these bourgeois people and to the middle classes in general that the pompes funèbres targeted their product. The endless lists of items enumerating in detail a multitude of ornaments and accessories echoed and simultaneously promoted the overflowing manifestation of sumptuousness as an expression of honor rendered to the deceased person.

An analysis of the negotiations of the two main institutional stakeholders and the pompes funèbres shows that, although all three principles/value systems were legitimate, they were far from being easily compatible. The sumptuous funerals of the great of this world, where the treatment of the dead was a reflection of their nobility and social distinction, were greatly frowned upon by the republicans, but fabriques could reap substantial profits. Conversely, the defense of the civic funeral service and the right of free burials for the poorest placed a heavy burden on municipalities, owing to the high rate of urban and industrial migrations. The solution they invented through the composition of classes of funeral services, which the individual entrepreneur could embellish by adding supplementary ornamental "special offers," was a way of solving a basic economic and political equation. The sumptuousness of bourgeois pomp was converted into a form of death tax to serve the poorest, whereas the symbolic emphasis on degrees of distinction at least provided substantial income for the fabriques and the entrepreneurs. The system reconciled the two regulation principles opposing the clergy and the elected officials: "the freedom of individuals to choose a service commensurate with their wealth with the right of all citizens to equal treatment" (Kselman, 2003: 266).

Analyzing classes of funerals as a central device of the co-regulation system demonstrates how it functioned as a mechanism of both "value ordering" (managing dissonance; [START_REF] Stark | The sense of dissonance. Accounts of worth in economic life[END_REF] and "value distribution" (managing overflow) between the stakeholders. Through this profit/distribution mechanism, the overflow of funeral goods was converted to a moral value that was geared both to profit sharing and to the defense of the common interest.

The art of filling the basket and sharing the value

The Prairial Decree provided the foundation for traditional actors and new market stakeholders (pompes funèbres) to build their own business arrangements. The analysis in this section offers a closer examination of the way these arrangements were transformed, reinterpreted, and rebuilt through their business activity and how they could be transformed by competitive business practices at a local level. The following sections demonstrate the extent to which the ever-increasing speculation on the offer of goods and the ability of entrepreneurs to manage this overflow accompanied market formation.

The development of competition

In comparison with parish unions or companies run by municipal governments, the private business concession model became widely popular as a means of reconciling public service requirements with the parish fabriques' need for income. Throughout the 19th century, the funeral businesses developed in town and city centers as part of this highly administered funeral management system, with the intention of increasing their share of funeral profits. As this space opened up to business, competition between funeral parlors grew fiercer [START_REF] Chaillot | Le droit funéraire français[END_REF]. The awarding of contracts within cities became an arena of heated battles among pompes funèbres. In Paris, six funeral parlors (Bobée, Labalte, Baudoin, Lesmaistre, Pector, Vafflard) sprang up one after the other between 1811 and 1871. Given the fierce competition for the awarding of contracts, the commissions granted to the fabriques led to ferocious overbidding that reached as much as 83.5% in 1852. 14This state of affairs drove the pompes funèbres to seek a way of increasing their profit margins. Kselman (1997) described the tough negotiations between the pompes funèbres and the fabriques over the definition of the categories of service. The concessionaire sought to reduce the share of the religious service proportionally to that of the extra service, for which commissions were much lower. To achieve this goal, the concessionaire curried favor with the elected authorities (prefects and mayors) by stressing the financial burden incurred by burying the destitute. But the speculative commercial sense of the pompes funèbres went much further. It related particularly to the contents of the basket of merchandise that was produced by the concessionaires (or their representatives in the various municipal authorities) in consultation with the bereaved families. The commercial process consisted of adding a supply of supplementary accessories to the basket that the families were going to buy -often products for which the town halls or the fabriques would not be taking a commission.

The mutual denunciation of pompes funèbres one against the other, reveals them as highly skilled "managers of overflow." Here are extracts from a brochure by L. Vafflard, Director-General of the Burial Company, for the attention of the inhabitants of the City of Paris:

Not wishing that the rules and regulations of the pompes funèbres become the object of trafficking and haggling, whereby the inexperience and momentarily disturbed state of families will render them defenseless victims of the company's agents, the legislator had fixed the prices of the various classes of funerals, leaving the families with only the choice among these classes and the possibility of reducing their cost by eliminating a few details. But in practice the positive effects of this precautionary measure have been nullified by the right accorded to the company, to add to these fixed offers other decorative objects or fancy ornaments, which are paid for as an extra and for which the fabriques receive hardly any commission either. It is natural that the pompes funèbres and his agents seek to multiply the use of these additional ornaments as much as possible, and that they do all in their power to exploit to this end the vanity or the piety of the families. Hence, considerable payments are made every single day to funeral pomp, which profit hardly anyone except the company (…).

If one objects that certain of these so-called additional objects are now of common use, and that no cortège can be considered complete without them, we would reply: what is the point for a family that has paid 100 francs to put draperies on the door of the deceased person's home, that you should add to this 247 francs worth of further accessories? That on top of this 100-franc drapery, which is supposed to be clean, you should place a band of drapery that costs 3 francs a meter; and that by the side of this band you add another one, which you call an antique drapery, and that on top of these piled-up draperies you place other decorations and a medallion in velvet, with the deceased person's age embroidered on it? Are these objects really necessary? (...) Moreover one should note that the prices of these objects do not follow the price hierarchy of the tariffs for the classes, so that you pay as much for these objects in a lower class as you do for a higher class. (Balard, 1856: 24, 32) Funeral drums, funeral crepe, military emblems, trophies, wreaths of artificial flowers, medallions, extra carriages, tablecloths -all of these brought something special to the cortège, while simultaneously lining the pockets of the concessionaire. Under the influence of the pompes funèbres, the growth of the pomp of funerals accompanied the broader commodification of funerals with an increasingly vast range of products. This outburst of quibbling and haggling about the accessories called into question the careful political and economic balancing act that the 23 Prairial Decree of Year XII (1804) had achieved. Conflicts among the municipalities, the fabriques, and the pompes funèbres led to legal judgments (lower-court and appealcourt rulings, recommendations and judgments up to the level of the Conseil d'Etat) for arbitration and interpretations of the law. "Over a seventy-year period, the operation of the pompes funèbres monopoly led to so many procedural wranglings that it is impossible to put even an approximate number on the disputes" [START_REF] Corbeaux | Discours de la promotion funéraire[END_REF]. The legal judgments generally came down in favor of the fabriques; thus, the law pertaining to the profit-sharing arrangements reintegrated many of the accessories for which they had received no payment. "Legal rulings, even when their wording was general and not specific, declared that the monopoly was applicable to flowers, wreaths, announcement cards, gloves, crepe furnishings, and even the decoration of drums and horses...." (Rubat du Merac, 1905: 35). This constant redefinition of territorial boundaries between the classes of funerals and the extra services characterizes a vain attempt to frame an overflowing of the basket of merchandise. It led instead to a further complex table of goods, tariffs, and percentage pay-offs that only the pompes funèbres could understand. It is evident, however, that this quest of control did not succeed in stabilizing the competitive game, but simply reshuffled the cards, with the pompes funèbres keeping an essential margin for maneuvering in the way they played their game.

Competition at the outer margins of the monopoly

The art of optimizing income from luxury goods, however, depended primarily on the relationships cultivated with the family of the deceased. This strategic place was soon challenged by a new stakeholder: the "funeral agency." Like the concessionaires, funeral agencies were private companies, but private companies developing their businesses at the outer limits of the monopoly, by selling extra funeral ornaments. The strategy of these private agencies was to offer families their services as "brokers" of the funeral organization. Representing the funeral agency, the broker came forward as the monopoly's right-hand man, arguing the necessity of protecting the customer from spending on ... objects that had no real meaning and were overpriced… One day, the Prefect of the Seine could comment: "A particular agency, if it is well directed, can be a useful way of controlling the activities of the Undertaker of the pompes funèbres, acting as a necessary Moderator against the undertaker's cupidity and that of his assistants." (Girault, 1910: 30) Thus concessionaires and agencies were in direct competition with each other in the area of extra supplies. Rather than moderating the game of multiplying accessories and profits, the burgeoning of funeral agencies revolving around the official undertaker intensified its growth. The agencies strove to take every advantage laid open by the concessionaire's reluctant acceptance of outside competition -that is the optimization of the basket profits with the aim of enhancing their own businesses. A fervent denouncer of the "commercial abuses" associated with funerals, Girault noted sarcastically:

The deceased, the poor deceased! For him, nothing is too much.... nothing should be spared... and it is therefore in his honor, in his fond memory that the agent lays out his bag of tricks, of useless and expensive objects. And not without a certain cunning, for, if he feigns to advise against buying a particular object, which would earn him little, it is often in order to recommend another one, with a suitable tone of compunction, which will bring him between 50% and 300% profit. (Girault, 1910: 12) The art of organizing the funeral (or assembling the set of luxury objects) was no longer a profitless game, but was used to optimize the distributed interests, reinforcing the interdependent links between the multiple actors involved in the funeral economy and the general economy. The funeral agency was generally much less visible than the official undertaker, who was acting on behalf of the municipal authorities with whom deaths were registered and the funeral arrangements finalized. To conquer their place in the market, the funeral agencies therefore developed commercial alliances with the other principal market participants, beginning with the fabriques, to which they awarded substantial commissions on all accessories sold. "They were welcomed by the church fabriques, who saw them as gifted businessmen able to increase the prices that the living were willing to pay out of the savings of the deceased in order to ensure their name would live on as expected and in an appropriate manner" (Théodore-Vibert, 1905: 13). This competition also served the interests of other town hall employees -the ordonnateur (the town's funeral official) 15 , the pallbearers, and gravediggers -all those involved in the cortèges, who systematically received gratuities for serving the interests of the rival companies. Many historical documents -letters of complaint, public protest signs, and lawyers' documents -attest to the unseemly infighting that existed between the funeral agencies and the officially delegated pompes funèbres, and reveal the underside of the funeral business. Unsavory stories abounded about the extraordinary lengths to which all sorts of people would go in order to influence vulnerable families and fill up their basket. Thus such titles as Les Vampires [START_REF] Girault | Autour des funérailles. Les vampires[END_REF] or Les Mystères des Pompes Funèbres de la Ville de Paris [START_REF] Balard | Les mystères des pompes funèbres de la ville de Paris dévoilés par les entrepreneurs eux-mêmes[END_REF].

For both market actors -the concessionaires as well as the funeral agencies -the main target was the composition of the "basket of merchandise" and the distribution of commissions between complicit partners at the expense of the mourners. There was even a name in the profession for this sort of underhanded dealing: régler les funérailles (fixing the funeral). This system of sharing funeral income between rival actors fostered a trend of constantly adding to the range of products in the basket of goods available.

Driving away the competition

This development of further competition around funerals led not only to an overflow of offerings of accessories at the heart of the pompes funèbres' business. It also threatened the economic formula that provided moral justification for conspicuous consumption, contributing to a positive construction of overflow. By reducing to a minimum the part of the basket of goods allocated to the monopoly and by augmenting the proportion of accessories for which they took all the profits, the agencies put a strain on the profits to be utilized for the benefit of burying the destitute. As Girault exclaimed: "Pity the poor monopolist! He is meant to safeguard the interests of the collectivity, yet he has difficulty in making two ends meet. Nay! He is sacrificed to the ambition and the egoism of a good number of the Agencies which are suffocating him and are hovering ready to divide up his spoils" (Girault, 1910: 31). In this way, the agencies undermined the ability of the town's funeral official to reconvert profit to cover the cost of burying the destitute.

To parry the threat constituted by this competition, the municipalities adopted a hands-on approach and established alliances with the concessionaires to act as barriers to the development of the private market. This alliance between municipalities and concessionaires against the development of the private market was going to be reinforced and would gain considerable strength at the end of the 19th century, in an institutional context that underwent major changes. As of 1879, legislation on funerals was regularly discussed within the context of reforms on secularization and the separation of Church and State. After long debates accompanying the successive reform projects, the law of 1905 led to the transfer of the funeral service monopoly from the fabriques to the municipal authorities, with the aim of providing a neutral, public service.

Compared with the previous system, the boundaries of the three areas (internal/religious service, external/municipal service, extra supplies) had been considerably modified, with the scope of the monopoly being significantly downsized. At the end of some fierce bargaining, in which liberals were opposed by a lobby upholding powerful public system, the funeral was finally entrusted to a public monopoly; but the public lost many accessories to the benefit of private businesses. This new distribution of property rights was to provoke an even more intense competition between the town's funeral official and city agencies. The threat constituted by the development of private competition reinforced the institutional stakeholders' interest in working closely with the official concessionaires; in comparison with a public company that would be run directly by municipal government, the concessionaire exhibited a greater ability to face up to the competition from traders on the outer margins of the monopoly.

The continuation of the story after 1905 reveals continuous attempts to reframe activities in order to manage the overflow around funerals and to maintain their functioning in the service of the common good. As it had in the preceding period, the new legislative framework ratified an institutional compromise between the commercial actors and the noncommercial actors of Church and State, while simultaneously fixing the accord-cadre (outline agreement), on the basis of which local actors would make their own arrangements and organize their own coordination. But here again, the agreement tended to be negotiated, twisted, and reinvented by the protagonists in the field. Even for the original agreement, twenty years of negotiations and jurisprudence were to be necessary before a new dividing line was drawn between the goods and services of the monopolized service -including the funeral cortège, the carriage, and the coffin -and those that could be freely sold. Taking the trimmings on the coffin for example, if they were on the outside (e.g. screws, trims, rings, handles, draperies, and moldings), they were considered part of the monopolized service; but if on the inside of the coffin (e.g. cushions, padding, mattress, and powders), they were open to market forces. The monopoly applied to the funeral hangings used on the exterior of the deceased's home (defined as public space) but not on the interior of the entrance porch (private space). The same ambiguity occurred in the treatment of the deceased: placing the body in the coffin was not the job of the official undertaker, but closing the lid, yes! In short, it can be said that in this second century of the funeral market, there was a fierce competition between the municipal funeral officer and the agencies. Both the funeral agencies and the concessionaires fought over their dealings with the bereaved families and used their commercial skills to fill the merchandise basket, so as to maximize their profits.

Conclusion

The study of the dealings between the institutional actors and the commercial interest surrounding funerals in the 19th century offers a new perspective on the modalities of market formation. It is true that the workings of the funeral market in the 19th century cannot be dissociated from the prevalent system of values that made ostentatious funerals more attractive, and increasingly so for the bourgeoisie, if not the middle classes in general (Veblen, 1899(Veblen, /1994)). The same applies to the desire to "keep up appearances" and the general consciousness of social rank, which must be viewed in the context of the evolution of forms of social segmentation [START_REF] Daumard | La bourgeoisie parisienne de 1815 à 1848[END_REF]. But, contrary to Veblen's thesis, it is suggested here that this social aspect cannot be understood without considering the central mediating role of pompes funèbres in the commodification of funerals, and the attendant overflow activity of the supply of accessories.

The first central development concerns the insertion of pompes funèbres into a commercial activity, which was closely embedded in the political and religious institutions of the period. It reveals the political skills of the pompes funèbres, in particular in the construction of a system of production and sharing of profits that simultaneously guaranteed the distribution of an assured economic income through the reconciliation of political differences and the satisfaction of one common 19th-century value -caring for the destitute. But it also reveals the skill of the pompes funèbres in upholding the moral justification for conspicuous consumption and any attendant overflow. On the one hand, the device of coregulation -the system of offering prepackaged and standardized classes of funeral services -framed the public craving for social differentiation and distinctiveness in the social hierarchy. On the other hand, by adding the category of "extra goods" onto the standardized classes of funerals, the pompes funèbres invented an economic formula that supported the reconversion of profits for the destitute. This arrangement contributed to the diffusion of the model, whereby public funeral service management was delegated to private businesses.

To understand the second stage of market formation -the growth of competition -one needs to observe how this framework was constantly renegotiated in the inventive practices of business. Thus, the pompes funèbres manipulated the classes of funerals by bringing in more and more tactics and commercial tricks to their advantage. Further, a sub-structure of increasing speculation around the range of available goods has been constructed, encouraged by the variety of alliances and the competition between actors. The competition over the sphere of extra goods threatened the delicate sharing equilibrium, which promoted a positive conception of overflowing (involving caring for the burial of the destitute) and substituted for it a negative conception, which served only private interests. Funerals became a commercial matter entirely, at the heart of which a growing number of actors shamelessly fought over income, benefits, and commissions, making their petty arrangements and alliances in order to ensnare bereaved families.

The struggles among the various actors in the market can now be seen in many places: in the doorways of the town halls where agents were lurking to win over families and keep them away from the concessionaire; over the coffins, with their special fittings of rings, handles, draperies, cushions and padding, and powders; with the employees squabbling over the sharing of the profits; in the courts of justice, where concessionaires and agents were battling it out over the dividing lines between categories of basic service or extra goods; and finally on the political scene, the theater for rival arguments on the virtues of a monopoly, or of the market as the economic organization serving the public interest. But whatever or wherever the scene, the battle over the commercial organization of funerals was played out over the ability of the one or the other participant to manage, to canalize, or to channel off the overflow and its multiple ramifications, either in the service of private interests, or in the service of the common good.

More exactly to the fabriques (vestries) and the consistoires (consistory councils), the latter being the administrative local councils of the Protestant churches.

The town criers publicly announced deaths, along with anything to be advertised publicly. In France, this function led them to be the first corporation to provide funeral supplies.

According to historical documents, their role during the revolutionary period was controversial. On the one hand, they had worked alongside the municipalities to cope with the critical burial crisis in Paris and other French cities; on the other hand, testimonies from republicans condemned their "obsessional mercantilism" (Rubat du Merac, 1905) and their "sordid speculations" (Report relating to burials by Comte Ségur, 1803), favored by the absence of regulation.

Prior to the 1804, it was common practice for ordinary people to be buried in communal graves. The 1804 decree established the individual grave as a right and a common good for all citizens.

The establishment of a municipal undertaking service had to be approved by the Ministry of the Interior following a presentation of the organization's system and the tariffs applied.

The vestry monopoly was the result of political bartering, and remained highly controversial within the context of the debate on secularism -notably between 1879 and 1905. The leasing solution meant that the parish fabriques or municipalities were freed from the heavy investments needed to guarantee a dignified and lasting public service during such periods of crisis as epidemics and political crises. Horses, hearses, wall hangings, and personnel represented some of the biggest investments.

It is significant that the English word "undertaker" is a literal translation of the French word entrepreneur, but that it applies solely to the occupation of funeral management.

Sources: Maison Balard tract, dated around 1860 (Paris Archives).

It was the role of this official to plan and guide the processions across the town; this was a relatively high office.


Ludovic Henrio
email: ludovic.henrio@cnrs.fr

Fabrice Huet
email: fabrice.huet@inria.fr

Zsolt István
email: zistvan@ethz.ch

Multi-threaded Active Objects

Keywords: Concurrency and distribution, active-objects, multicore architectures

Active objects offer a paradigm which simplifies writing distributed applications. Since each active object has a single thread of control, data races are prevented. However, this programming model has its limitations: it is deadlockprone, and it is not efficient on multicore machines. To overcome these limitations, we present an extension of the active object model, called multi-active objects, that allows each activity to be multi-threaded. The new model is implemented as a Java library; it relies on method annotations to decide which requests can be run in parallel. It provides implicit parallelism, sparing the programmer from low-level concurrency mechanisms. We define the operational semantics of the multi-active objects and study the basic properties of this model. Finally, we show with two applications that our approach is easy to program and efficient.

Introduction

Writing distributed applications is a difficult task because the programmer has to face both concurrency and location-related issues. The active object [START_REF] Lavender | Active object: an object behavioral pattern for concurrent programming[END_REF][START_REF] Yonezawa | Object-oriented concurrent programming ABCL/1[END_REF][START_REF] Caromel | Asynchronous sequential processes[END_REF] paradigm provides a solution by abstracting away the notions of concurrency and of object location. An object is said to be active if it has its own thread of control. As a consequence, every call to such an object will be some form of remote method invocation -a request -that is handled by the object's thread of control. Active objects are partly inspired by Actors [START_REF] Agha | Actors: a model of concurrent computation in distributed systems[END_REF][START_REF] Agha | A foundation for actor computation[END_REF]: they share the same asynchronous treatment of messages, and ensure the absence of data race-conditions. They do differ however in how the internal state of the object is represented. Active objects are mono-threaded, which prevents data races without the use of synchronized blocks. Distributed computations rely on the absence of sharing between processes, allowing them to be placed on different machines.

In classical remote method invocation, the invoker is blocked waiting for the result of the remote call. Active objects, on the other hand, return futures [START_REF] Halstead | Multilisp: A language for concurrent symbolic computation[END_REF] as placeholders for the result, allowing the invoker to continue its execution. Futures can be created and accessed either explicitly, like in Creol [START_REF] Johnsen | Creol: A type-safe object-oriented model for distributed concurrent systems[END_REF] and JCoBox [START_REF] Schafer | JCoBox: Generalizing active objects to concurrent components[END_REF], or implicitly as in ASP [START_REF] Caromel | Asynchronous sequential processes[END_REF] (Asynchronous Sequential Processes) and AmbientTalk [START_REF] Dedecker | Ambient-oriented programming in ambienttalk[END_REF]. A key benefit of the implicit creation is that no distinction is made between synchronous (i.e., local) and asynchronous (i.e., remote) operations in the program. Hence, when the accessed object is remote, a future is immediately obtained. Similarly to their creation, the access to futures can happen either explicitly using operations like claim and get, or implicitly, in which case operations that need the real value of an object (blocking operations) automatically trigger synchronisation with the future update operation. In most active object languages, future references can be transmitted between remote entities without requiring the future to be resolved.

There are different models related to active objects. The ASP calculus [START_REF] Caromel | Asynchronous sequential processes[END_REF] is a distributed active object calculus with futures; the ProActive library is its reference implementation. ASP has strong properties and is easy to program, but the strict sequential service of requests creates deadlocks. A different approach is provided by active objects languages with cooperative multithreading (Creol [START_REF] Johnsen | Creol: A type-safe object-oriented model for distributed concurrent systems[END_REF][START_REF] Boer | A complete guide to the future[END_REF], Jcobox [START_REF] Schafer | JCoBox: Generalizing active objects to concurrent components[END_REF]). In this model a thread serving a request can stop in order to let the service of another request progress. While no data race condition is possible, interleaving of the different request services triggered by the different release points makes the behaviour more difficult to predict; in particular Creol does not feature the determinism properties of ASP. Explicit future access, explicit release points, and explicit asynchronous calls make JCobox and Creol richer, but also more difficult to program.

This paper provides a new extension of the active object model with a different trade-off between expressiveness and ease of programming compared to the existing approaches. Our approach replaces the strict mono-threading that avoids data-races in active-objects, by an expressive and simple mechanism of request annotation that controls parallelism. Our approach also achieves better performance than classical activeobjects on multi-core machines. Our contribution can be summarised as follows:

-A new programming model called multi-active objects is proposed (Section 2). It extends active objects with local multi-threading; this both enhances efficiency on multicore machines, and prevents most of the deadlocks of active objects. -We rely on declarative annotations for expressing potential concurrency between requests, allowing easy and high-level expression of concurrency. However, the expert programmer can still use lower level concurrency constructs, like locks. -We define the operational semantics of multi-active objects in Section 3. This semantics allows us to prove properties of the programming model. -We experimentally show that multi-active objects make writing of parallel and distributed applications easier, but also that the execution of programs based on multi-active objects is efficient (Section 4). The programming model has been implemented as an extensions to a Java middleware 3 . Additionally, Section 5 compares our contribution with the closest languages, and finally Section 6 concludes the paper. Details on the semantics, the implementation, and the experiments are available in a research report [START_REF] Henrio | A language for multi-threaded active objects[END_REF].

Multi-active Object Programming Model

Illustrating example We will illustrate our proposal with an example inspired by a simple peer-to-peer network based on the CAN [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF] routing protocol. In a CAN, data are stored in peers as key-value pairs inside a local datastore. Keys are mapped through a bijective function to the coordinates of a N-dimensional space, called the key-space.

The key-space is partitioned so that each key is owned by a single peer. A peer knows its immediate neighbours, and when an action concerns a key that does not belong to this particular peer, it routes the request towards the responsible peer according to the coordinates of the key. Our CAN example provides three operations: join, add, and lookup. When a new peer joins the network, it always joins an existing peer. This joined peer splits its partition of the key-space in two; it keeps one half and gives the other to the new peer. The add operation stores a key-value pair, and lookup retrieves it.

Active objects are a natural choice to implement this application by representing each peer with an active object. Locally, requests will be served one-by-one. This limits the performance of the application, and also possibly leads to deadlocks if re-entrant requests are issued. With multi-active objects, a peer will be able to handle several operations in parallel. We will illustrate multi-active objects by showing how to simply program a safe parallelisation of the CAN peers.

Assumptions and Design Choices

To allow active objects to serve several requests in parallel, we introduce multi-active objects that enable local parallelism inside active objects in a safe manner. For this, the programmer can annotate the code with information about concurrency by defining a compatibility relationship between concerns. This notion of annotation for concurrency share some common ideas with JAC [START_REF] Haustein | Jac: declarative Java concurrency[END_REF]. For instance, in our CAN example we distinguish two non-overlapping concerns: one is network management (join) and another is routing (add, lookup). For two concerns that deal with completely disjoint resources it is possible to execute them in parallel, but for others that could conflict on resources (e.g. joining nodes and routing at the same time in the same peer) this must not happen. Some of the concerns enable parallel execution of their operations (looking up values in parallel in the system will not lead to conflicts), and others do not (a peer can split its zone only with one other peer at a time).

In the RMI style of programming, every remote invocation to an object will be run in parallel, as a result, data-races can happen on concurrently accessed data. A classic approach to solve this problem in Java is to protect concurrent executions by making all methods synchronized. This coarse-grain approach is inefficient when some of the methods could be run in parallel. Alternatively, the programmer can protect the data accesses by using low-level locking mechanisms, but this approach is too fine-grained and possibly error-prone.

By nature, active objects materialise a much safer model where no inner concurrency is possible. In this work, we look for a concurrency model that is more flexible than the single threaded active-objects, but more constrained and less error-prone than Java concurrency. We extend active-objects by assigning methods to groups (concerns). Then, methods belonging to compatible groups can be executed in parallel, and methods belonging to conflicting groups will be guaranteed not to be run concurrently. This way the application logic does not need to be mixed with low-level synchronisations. The idea is that two groups should be made compatible if their methods do not access the same data, or if concurrent accesses are protected by the programmer, and the two methods can be executed in any order. The programmer should declare as compatible both the non-conflicting groups, and the groups where the conflicting code has been protected by means of locks or synchronised blocks. We chose annotations to express compatibility rules because we think that this notion is strongly dependent on the application logic, and should be attached to the source code.

We start from active objects à la ASP, featuring transparent creation, synchronisation, and transmission of futures. We think that the transparency featured by ASP and ProActive helps writing simple programs, and is not an issue when writing complex distributed applications. We also think that the non-uniform active objects of ASP, and JCoBox, reflect better the way efficient distributed applications are designed: some objects are co-allocated and only some of them are remotely accessible. In our model, only one object is active in a given activity but this work can easily be extended to multiple active-object per activity (i.e. cobox). An active object can be transformed into a multi-active object by applying the following design methodology:

-Without annotations, a multi-active object behaves identically to an active object, no race condition is possible, but no local parallelism is possible either. -If some parallelism is desired, e.g. for efficiency reasons or because dead-locks appeared, each remotely invocable method can be assigned to a group. Then compatibility between the groups can be defined based on, for example, the variables accessed by each method. Methods belonging to compatible groups can be executed in parallel and out of the original order. This implies that two groups should only be declared compatible if the order of execution of methods of one group relatively to the other is not significant. -If even more parallelism is required, the programmer has two non-exclusive options: either he protects the access to some of the variables by a locking mechanism which will allow him to declare more groups as compatible, or he realises that, depending on runtime conditions, such as invocation parameters or the object's state, some groups might become compatible and he defines a compatibility function allowing him to decide at runtime which request executions are compatible. We assume that the programmer defines groups and their compatibility relations inside a class correctly. Dynamic checks or static analysis should be added to ensure, for example, that no race condition appear at runtime. Verifying that annotations written by the programmer are correct or even inferring them, e.g. [START_REF] Shanneb | Exclusion requirements and potential concurrency for composite objects[END_REF], is out of scope here.

Defining Groups

The programmer can use an annotation, Group, to define a group and can specify whether the group is selfCompatible, i.e., two requests on methods of the group can run in parallel. The syntax for defining groups in the class header is shown on lines 1-5 of Figure 1.

Compatibilities between groups can be expressed as Compatible annotations. Each such annotation receives a set of groups that are pairwise compatible, as illustrated on lines 6-9 of Figure 1. A method's membership to a group is expressed by annotating the method's declaration with MemberOf. Each method belongs to only one group. In case no membership annotation is specified, the method belongs to an anonymous group that is neither compatible with other groups, nor self-compatible. This way, if no method of a class is annotated, the multi-active object behaves like an ordinary active object. The MemberOf annotation is shown on lines 11, 13, 15, and 17 of Figure 1.

@DefineGroups({ @Group(name="join", selfCompatible=false) @Group(name="routing", selfCompatible=true) @Group(name="monitoring", selfCompatible=true) }) @DefineRules({ @Compatible({"join", "monitoring"}) @Compatible({"routing", "monitoring"}) }) public class Peer { @MemberOf("join") public JoinResponse join(Peer other) { ... } @MemberOf("routing") public void add(Key k, Serializable value) { ... } @MemberOf("routing") public Serializable lookup(Key k) { ... } @MemberOf("monitoring") public void monitor() { ... } } Fig. 1: The CAN Peer annotated for parallelism Figure 1 illustrates the annotations in the context of a CAN peer active object in which adds and lookups can be performed in parallel -they belong to the same selfcompatible group routing. Since there is no compatibility rule defined between them, methods of join and routing will not be served in parallel. To fully illustrate our annotations, we added monitoring as a third concern independent from the others.

Dynamic Compatibility

Sometimes the compatibility of requests can be more precisely decided at run-time. For example, two methods writing in the same array can be compatible if they don't access the same cells. For this reason, we first introduce an optional group-parameter which indicates the type of a a parameter which will be used to decide compatibility. This parameter must appear in all methods of the group and in case a method has several parameters of this type, the leftmost one is chosen. In Figure 2, we add parameter=" can.Key" to the routing group to indicate that the parameter of type Key will be used. Overall, at runtime, compatibility between two requests can be decided as a function depending on three parameters: the group-parameter of the two requests, and the status of the active-object. We describe below how we integrated this idea into our framework and allowed the programmer to define compatibility functions inside his/her objects.

To actually decide the compatibility, we add a condition in the form of a compatibility function which takes as input the common parameters of the two compared groups and returns true if the methods are compatible. The general syntax for this rule is: @compatible{value={"group1","group1"}, condition="SomeCondition"}

The compatibility function can be defined as follows:

when SomeCondition is in the form someFunc, the compatibility will be decided by executing param1.someFunc(param2) where param1 is the parameter of one request and param2 is the parameter of the other.

@DefineGroups({ @Group(name="routing",selfCompatible=true,parameter="can.Key",condition="!equals") @Group(name="join", selfCompatible=false) }) @DefineRules({@Compatible(value={"routing", "join"},condition="!this.isLocal") }) public class Peer { private boolean isLocal(Key k){ synchronized (lock) { return myZone.containsKey(k); } } } Fig. 2: The CAN Peer annotated for parallelism with dynamic compatibility when SomeCondition is in the form [REF].someFunc, the compatibility will depend on the results of someFunc(param1, param2) with the group parameters as arguments.

[REF] can be either this if the method belongs to the multi-active object itself, or a class name if it is a static method. Additionally the result of the comparator function can be negated using "!", e.g. condition="!this.isLocal". Since the compatibility method can run concurrently with executing threads, the programmer should ensure mutual exclusion, if necessary. One can define dynamic compatibility even when only one of the two groups has a parameter, in that case the compatibility function should accept one less input parameter. It is even possible to dynamically decide compatibility when none of the two groups has a parameter (e.g. based on the state of the active object); in that case the compatibility function should be a static method or a method of the active object, with no parameter.

As an example, we show how to better parallelise the execution of joins and routing operations in our CAN. During a join operation, the peer which is already in the network splits its key-space and transfers some of the key-value pairs to the peer which is joining the network. During this operation, ownership is hard to define. Thus a lookup (or add) of a key belonging to one of the two peers cannot be answered during the transition period. Operations that target "external" keys, on the other hand, could be safely executed in parallel with a join. Figure 2 shows a modified version of the Peer class which supports dynamic compatibility checks. For the sake of clarity, we omit unmodified code. The modifications are as follows. 1) a group parameter, can.Key has been added to the routing group; 2) a compatibility rule has been defined for groups routing and join with condition "!this.isLocal"; 3) a method boolean isLocal(Key k) has been created, which checks whether a key falls in the zone of a peer At runtime, the method isLocal(Key k) will be executed when checking the compatibility of groups routing and join. This method is selected because it is the only one matching the name of the condition and the group parameter type. We also defined a condition for self-compatibility in the routing group: to guarantee that there is no overtaking between requests on the same key, we configure the group to be selfCompatible only when the key parameter of the two invocations is not equal, see Figure 2, line 2.

A Calculus of Multi-active Objects

This section describes MultiASP, the multi-active object calculus. We present its small step operational semantics and its properties. In MultiASP, there is no explicit notion of place of execution, but the calculus is particularly adapted to distribution because, first, inter-activity communication behaves like remote method invocation, and second, each object belongs to a single activity. Overall, each active object can be considered as a unit of distribution. The operational semantics is parametrised by a function deciding whether a request should be served concurrently on a new thread or sequentially by the thread that triggered the service.

Syntax and Runtime Structures

While x, y range over variable names, we let l i range over field names, and m i over method names (m 0 is a reserved method name; it is called upon the activation of an object and encodes the service policy). :: denotes the concatenation of lists; we also use it to append an element to a list. H denotes an empty list or an empty set. The syntax of MultiASP is identical to ASP [START_REF] Caromel | Asynchronous sequential processes[END_REF] (except for the clone operator that is of no interest here). Active objects and futures can be created at runtime. New objects can be allocated in a local store (there is one local store for each active object). Thus, we let ι i range over references to the local store (ι 0 is a reserved location for the active object), α, β, γ range over active object identifiers, and f i range over future identifiers. Among the terms above, static terms are the ones that contain no references to futures, active objects, or store location. Note that every term is an object and rs is an empty object: a ::" x variable (y also ranges over variables), | rli " ai; mj " ςpxj, yjqa A reduced object is either a future, an activity reference, or an object with all fields reduced to a location. A store maps locations to reduced objects; it stores the local state of the active object:

o ::" rl i " ι i ; m j " ςpx j , y j qa j s iP1..n jP1..m | f | α σ ::" tι i Þ Ñ o i u iP1..k
To ensure absence of sharing, the operation Copy&Mergepσ, ι ; σ 1 , ι 1 q performs a deep copy of the object at location ι in σ into the location ι 1 of σ 1 , and ensures that communicated values are "self-contained". This is achieved by copying the entry for ι at location ι 1 of σ 1 (if this location already contains an object it will be erased). All locations ι 2 referenced (recursively) by the object σpιq are also copied in σ 1 at fresh locations (See [START_REF] Henrio | A language for multi-threaded active objects[END_REF][START_REF] Caromel | Asynchronous sequential processes[END_REF] for the formal definition). F ranges over future value association lists; such a list stores computed results where ι i is the location of the value associated with the future f i : F ::" tf i Þ Ñ ι i u iP1..k . The list of pending requests is denoted by R ::" rm i ; ι i ; f i s iP1..N , where each request consists of: the name of the target method m i , the location of the argument passed to the request ι i , the future identifier which will be associated to the result f i . pf Þ Ñ ιq P F means pf Þ Ñ ιq is one of the entries of the list F and similarly rm; ι; f s P R means rm; ι; f s is one of the requests of the queue R.

There are two parallel composition operators: } expresses local parallelism, it separates threads residing in the same activity, and ~expresses distributed parallelism, it separates different activities. A request being evaluated is a term together with the future to which it corresponds (a i Þ Ñ f i ). An activity has several parallel threads each consisting of a list of requests being treated: the leftmost request of each thread is in fact currently being treated, the others are in a waiting state. C is a current request structure: it is a parallel composition of threads where each thread is a list of requests. By nature, } is symmetric, and current requests are identified modulo reordering of threads:

C ::" H | ra i Þ Ñ f i s iP1..n }C
Finally, an activity is composed of a name α, a store σ, a list of pending requests R, a set of computed futures F , and a current request structure C. A configuration Q is made of activities. Configurations are identified modulo the reordering of activities.

Q ::" H | αrF ; C; R; σs~Q An initial configuration consists of a single activity treating a request that evaluates a static term a 0 : b 0 " α 0 rH; a 0 Þ Ñ f H ; H; Hs. Contexts. Reduction contexts are terms with a hole indicating where the reduction should happen. For each context R, the operation (Rrcs) replaces the hole by a given term c. Contrarily to substitution, filling a hole is not capture avoiding: the term filling the hole is substituted as it is.

Sequential reduction contexts indicate where reduction occurs in a current request:

R ::" ' | R.li | R.mjpbq | ι.mjpRq | R.li :" b | ι.li :" R | rli " ιi, l k " R, l k 1 " b k 1 ; mj " ςpxj,yjqajs iP1..k´1,k 1 Pk`1..n jP1..m | ActivepRq
A parallel reduction context extracts one thread of the current request structure (remember that current requests are identified modulo thread reordering):

R c ::" rR Þ Ñ f 1 s::ra j Þ Ñ f j s jP2..n }C

Operational Semantics

Our semantics is built in two layers, a local reduction Ñ loc defined in [START_REF] Caromel | Asynchronous sequential processes[END_REF] and in [START_REF] Henrio | A language for multi-threaded active objects[END_REF] that corresponds to a classical object calculus, and a parallel semantics that encodes distribution and communications. Activities communicate by remote method invocations and handle several local threads; each thread can evolve and modify the local store according to the local reduction rules. Thanks to the parallel reduction contexts R c , multiple threads are handled almost transparently in the semantics. The main novelty in MultiASP is the request service that can either serve the new request in the current thread or in a concurrent one; for this we rely on two functions: SeqSchedule and ParSchedule. Given a set of method names to be served (the parameter of the Serve primitive), the set of futures calculated by the current thread, and the set of futures calculated by the other threads of the activity, these functions decide whether it is possible to serve a request sequentially or in parallel. The last parameter is the request queue that will be LOCAL pa, σq Ñloc pa LOCAL triggers a local reduction Ñ loc described in [START_REF] Caromel | Asynchronous sequential processes[END_REF] and in [START_REF] Henrio | A language for multi-threaded active objects[END_REF]. ACTIVE creates a new activity: from an object and all its dependencies, this rule creates a new activity at a fresh location γ. The method m 0 is called at creation, the initial request is associated with f H , a future that is never referenced and never used. REQUEST invokes a request on a remote active object: when an activity α performs an invocation on another activity β this creates a fresh future f , and enqueues a new request in β. The parameter is deep copied to the destination's store. ENDSERVICE finishes the service of a request: it adds an entry corresponding to the newly calculated result in the future value association list. The result object is copied to prevent further mutations. REPLY sends a future value: if an activity α has a reference to a future f , and another activity β has a value associated to this future, the reference is replaced by the calculated value 3 . SERVE serves a new request sequentially: it relies on a call to SeqSchedule that returns a request rm, f, ιs and the remaining of the request queue R 1 . The request rm, f, ιs is served by the current thread. The Serve instruction is replaced by an empty object that will be stored, so that execution of the request can continue with the next instruction. SeqSchedule receives, the set of method names M , the set of futures of the current thread, the set of futures of the other threads, and the request queue. PARSERVE serves a new request in parallel: it is similar to the preceding rule except that it relies on a call to ParSchedule, and that a new thread is created that will handle the new request to be served rm, f, ιs. The particular case where the source and destination are the same require an adaptation of the rules REQUEST and REPLY [START_REF] Henrio | A language for multi-threaded active objects[END_REF].

σαpιq " β ι 2 R dompσ β q f fresh future σ 1 β " Copy&Mergepσα, ι 1 ; σ β , ι 2 q α " F ; Rcrι.mjpι 1 qs; R; σα ‰ ~β" F 1 ; C 1 ; R 1 ; σ β ‰ ~Q ÝÑ α " F ; Rcrf s; R; σα ‰ ~β" F 1 ; C 1 ; R 1 ::rmj; ι 2 ; f s; σ 1 β ‰ ~Q ENDSERVICE ι 1 R dompσq σ 1 " Copy&Mergepσ, ι ; σ, ι 1 q α " F ; ι Þ Ñ f ::rai Þ Ñ fis iP1..n }C; R; σ ‰ ~Q ÝÑ α " F ::f Þ Ñ ι 1 ; rai Þ Ñ fis iP1..n }C; R; σ 1 ‰ ~Q REPLY σαpιq " f σ 1 α " Copy&Mergepσ β , ι f ; σα, ιq pf Þ Ñ ι f q P F 1 α " F ;C;R;σα ‰ ~β" F 1 ;C 1 ;R 1 ;σ β ‰ ~Q ÝÑ α " F ;C;R;σ 1 α ‰ ~β" F 1 ;C 1 ;R 1 ;σ β ‰ ~Q SERVE C " rRrServepM qs Þ Ñ f0s::rai Þ Ñ fis iP1..n }C 1 SeqSchedulepM, tfiu iP0..n , FuturespC 1 q, Rq " prm, f, ιs, R 1 q α " F ; C; R; σ ‰ ~Q ÝÑ α " F ; rι0.mpιq Þ Ñ f s::rRrrss Þ Ñ f0s::rai Þ Ñ fis iP1..n }C 1 ; R 1 ; σ ‰ ~Q PARSERVE C " rRrServepM qs Þ Ñ f0s::rai Þ Ñ fis iP1..n }C 1 ParSchedulepM, tfiu iP0..n , FuturespC 1 q, Rq " prm, f, ιs, R 1 q α " F ; C; R; σ ‰ ~Q ÝÑ α " F ; rι0.mpιq Þ Ñ f s}Rrrss Þ Ñ f0s::rai Þ Ñ fis iP1..n }C 1 ; R 1 ; σ ‰ ~Q
We can show that ÝÑ does not create references to futures or activities that do not exist, and thus the parallel reduction is well-formed. Quite often an active-object will serve all the requests in a FIFO order: m 0 consists of a loop: while ptrueq ServepM A q where M A is the set of all method names 4 and the other methods never perform a Serve. m 0 is compatible with all the other methods and thus all services can be done in parallel, but the service of a request might have to wait until another request finishes. We call this particular case FIFO request service.

Scheduling Requests

Several strategies could be designed for scheduling parallel or sequential services. Future identifiers can be used to identify requests uniquely; also it is easy to associate some meta-information with them (e.g. the name or the parameters of the invoked method). Consequently, we rely on a compatibility relation between future identifiers: compatiblepf, f 1 q is true if requests corresponding to f and f 1 are compatible. We suppose this relation is symmetric.

Table 2 shows a suggested definition of functions SeqSchedule and ParSchedule which maximises parallelism while ensuring that no two incompatible methods can be run in parallel. The following of this section explains in what sense this definition is correct and optimal. The principle of the compatibility relation is that two requests served by two different threads should be compatible: Property 1 (Compatibility). If two requests are served by two different threads then they are compatible: suppose

Q 0 ÝÑ ˚α" F ; C; R; σ ‰ ~Q then: C " ra i Þ Ñ f i s iP1..n }ra 1 j Þ Ñ f 1 j s jP1.
.m }C 1 ñ @i P 1..n. @j P 1..m. compatiblepf i , f 1 j q We consider that parallelism is "maximised" if a new request is served whenever possible, and those services are performed by as many threads as possible. Thus, to maximise parallelism, a request should be served by the thread that performs the Serve operation only if there is an incompatible request served in that thread. The "maximal parallelism" property can then be formalised as an invariant:

@f P F 1 . compatiblepfj, f q Df P F. compatiblepfj, f q mj P M @k ă j. m k P M ñ `compatiblepfj, f k q ^Df P F 1 . compatiblepf k , f q SeqSchedulepM,
F, F 1 , rmi,fi,ιis iP1..N q " prmj,fj,ιjs, rmi,fi,ιis iP1..j´1 ::rmi,fi,ιis iPj`1..N q @f P F 1 . compatiblepfj, f q @f P F. compatiblepfj, f q mj P M @k ă j. m k P M ñ `compatiblepfj, f k q ^Df P F 1 . compatiblepf k , f q ParSchedulepM, F, F 1 , rmi,fi,ιis iP1..N q " prmj,fj,ιjs, rmi,fi,ιis iP1..j´1 ::rmi,fi,ιis iPj`1..N q

F ; C; R; σ ‰ ~Q then: `C " ra i Þ Ñ f i s iP1..n }C 1 ^k ą 1 ˘ñ Di 1 ă k. compatiblepf k , f i 1 q
The properties above justify the two first premises of the rules in Table 2. The last premise decides which request to serve. For this, we filter the request queue by the set M of method labels. Then we serve the first request that is compatible with all requests served by the other threads. These definitions ensure that any two requests served inside two different threads are always compatible, and also that requests are served in the order of the request queue filtered by the set of methods M , except that a request can always overtake requests with which it is compatible. We say that parallelism is maximised because we eagerly serve new requests on as many parallel threads as possible.

We conclude this section by explaining why it is reasonable to let a request overtake compatible ones. Indeed, whenever two compatible requests are served in parallel compatibility implies that the operations of these requests can be freely interleaved. Overtaking is just a special case of interleaving, namely when all operations of one request are executed before the operations of the other request. Thus, even if requests were served in the exact incoming order, a request may actually overtake a compatible one. More generally, if all requests are necessarily served at some point, then allowing a request to be overtaken by compatible ones is a safe decision.

Evaluation

In this section we show that our proposal provides an effective compromise between programming simplicity and execution efficiency of parallel and distributed applications: multi-active objects achieve the same performance as classical concurrent approaches while simplifying the programming of distributed applications. A detailed analysis of the results and the description of the multi-active API is provided in [START_REF] Henrio | A language for multi-threaded active objects[END_REF] Our proposal is implemented on top of ProActive, the reference implementation of ASP. No preprocessing or modified Java compiler are required, all decisions are made at runtime by reifying constructors and method invocation. The flexibility and portability we obtain using these techniques induce a slight overhead, but experience shows it has no significant impact at the application level. The implementation of multi-active objects comes with an API for customising the request service policy, the possibility to limit the number of threads inside a multi-active object, and an inheritance mechanism for compatibility annotations [START_REF] Henrio | A language for multi-threaded active objects[END_REF]. NAS Parallel Benchmarks We first compare multi-active objects with Java threads based on a well-known parallel benchmark suite: the NAS Parallel Benchmarks. To achieve a multi-active implementation, we modify the Java-based version of the benchmark [START_REF] Frumkin | Implementation of NAS parallel benchmarks in Java[END_REF] and create a multi-active object version from each kernel. A single multiactive object replaces all worker threads, and futures and wait-by-necessity replace wait() and notify(). This makes the code easier to understand and to maintain. Code related to parallelism in the multi-active version is much shorter than the original (between 35% and 70%), depending on the benchmark. Also, our annotations make synchronisation much more natural, and on a higher level of abstraction than the original program. The performance of the modified application is very close to the original.

CAN Experimental Results

We implemented the CAN illustrating example to show the efficiency brought by multi-active objects compared to active-objects in a distributed multicore environment. The purpose of these experiments is to evaluate the benefits of multi-active objects, not the performance of our CAN implementation. Therefore, our experiments were designed to provide an interesting workload for the active objects themselves, not necessarily for the CAN network. We created and populated a CAN using join and add operations, then we measured the benefits of lookup request parallelisation in the following situations:

-All from two: In this scenario, two corners send lookup requests to all other nodes, and then wait until all the results are returned. This experiment gives an insight about the overall throughput of the overlay. -Centre from all: In this test case, all the peers lookup concurrently a key located in a peer at the centre of the CAN. This experiment highlights the scalability of a peer under heavy load. We repeated each scenario 50 times and measured the overall execution time (the difference between successive runs was found to be negligible). The creation and population of the network was not measured as part of the execution time. We used up to 128 machines located at the Sophia-Antipolis site of the Grid50005 platform. All hosts are interconnected through Gigabit Ethernet, and are equipped with quad-core CPUs (Intel Xeon E5520, AMD Opteron 275 and AMD Opteron 2218), running Java 7 Hotspot 64-Bit Server VMs. Each requested value was 24KB in size.

Figure 3 shows the execution times and speedup (when turning active objects into multi-active ones) for several sizes for the two scenarios. Both scenarios achieve significant speedup thanks to the communication and request handling performed in parallel, however, the gain in the first scenario is smaller because the lookups are issued from the two corners in sequence; the sequential sending of the initial lookups limits the number of lookups present at the same time in the network. In the second case, the active object version has a bottleneck because the centre peer can only reply to one request at a time whereas those requests can be highly parallelised with our model. As shown before,

Comparison with Related Work

Parallel actor monitors [START_REF] Scholliers | Parallel actor monitors[END_REF] (PAM) provide multi-threading capacities to actors based on explicit scheduling functions. However, we believe that the compatibility annotations of multi-active objects provide a higher level of abstraction than PAM, and that this high-level of abstraction is what makes active-objects and actors easy to program. The main difference between our approach and active-objects with cooperative multi-threading like JCoBox [START_REF] Schafer | JCoBox: Generalizing active objects to concurrent components[END_REF] and Creol [START_REF] Johnsen | Creol: A type-safe object-oriented model for distributed concurrent systems[END_REF] is twofold. On one hand, Creol-like languages are not really multi-threaded (only one thread is active at a time [START_REF] Johnsen | Creol: A type-safe object-oriented model for distributed concurrent systems[END_REF]), thus they do not necessarily address the issue of efficiency on multicore architectures; JCoBox proposes a shared immutable state that can be used efficiently on multicore architectures but as the distributed implementation is still a prototype, it is difficult to study how an application mixing local concurrency and distribution like our CAN example would behave. On the other hand, concerning synchronisation, in cooperative multi-threaded solutions between explicit release points (awaits) the programs are executed sequentially. Adequately placing those release points is the main challenge in programming in Creol or JCoBox: too many release points leads to a complex interleaving between sequential code portions, whereas not enough of them will probably lead to a deadlock.

Multi-active objects provide an alternative approach by allowing local concurrency in active objects: with annotations, the programmer can reason on high-level compatibility rules, and parallelism can be expressed in a simple manner. Compatible methods are run concurrently, with potential race-conditions but also local multi-threading. Overall, in ASP and MultiASP distribution and concurrency are much more transparent than in JCoBox and Creol; this difference in point of view explains most of the differences between the two models: transparent vs. explicit futures and compatibility annotations vs. explicit thread release. However, the principles of multi-active objects could be applied to an active object language with explicit futures and explicit release points, but in this case thread activation (after an await statement) must take into account compatibility information.

Cunha and Sobral [START_REF] Cunha | An annotation-based framework for parallel computing[END_REF] use Java annotations to parallelise sequential objects in an OpenMP fashion. A method can be called asynchronously if it is flagged with the Future annotation, but the programmer must follow the flow of futures carefully and declare which methods can access them. There is also an ActiveObject annotation that creates a proxy and a scheduler, but its exact semantics is not well-defined in [START_REF] Cunha | An annotation-based framework for parallel computing[END_REF]. In our opinion, JAC's and our compatibility rules offer a greater control and a higher abstraction level than OpenMP style fork-join blocks, they are also better adapted to active-objects.

Our annotation system looks like JAC's proposal, and this paper could also be seen as an adaptation of a concurrency model à la JAC to the active object model. The inheritance model of JAC annotations is well designed [START_REF] Haustein | Jac: declarative Java concurrency[END_REF] and resembles the way our annotations are inherited from class to class. However, multi-active objects offer a simpler annotation system and a higher synchronisation logic encapsulation. Moreover, the dynamic compatibility rules of multi-active objects are not directly translatable into JAC annotations: JAC provides a precondition mechanism that can be used to express dynamic compatibility but it does not guarantee safe access to shared variables. Compared to JAC, we think multi-active objects are simpler to program, have stronger properties, and are better suited to distribution. In particular, the transparent inclusion of annotations leads in our opinion to a powerful and interesting programming model. Now that our active objects are equipped with multiple threads, strategies for optimizing the number and utilization of threads will have to be considered (e.g. [START_REF] Haller | Scala actors: Unifying thread-based and event-based programming[END_REF][START_REF] Henrio | A language for multi-threaded active objects[END_REF]).

Conclusion

In active object languages, programming efficiently on multicore architectures is not possible. Indeed, to have multiple threads on the same machine, all the other languages require to create multiple active objects (or coboxes). Then, the communication between those objects is either costly (it relies on a request invocation and heavy parameter passing), or restricted (JCoBoxes can share a state but it must be immutable). In our case, several threads inside an active objects can co-exist and we provide an annotation system to control their concurrent execution. The annotations can be written from a high-level point of view by declaring compatibility relations between the different concerns an active object manages. The operational semantics defined in Section 3 allowed us to prove that request services can be scheduled such that parallelism is somehow maximised while preventing two incompatible requests from being served in parallel.

The originality of our contribution lies in the interplay between the formal and precise study of the MultiASP language, and a middleware implementation efficient enough to compete with classical multi-threading benchmarks. The use of dynamic constraints for compatibility allows a fine-grain control over local concurrency and improves expressiveness. We implemented the proposed model in Java and ran experiments to ensure that our approach is efficient. The experiments showed that the performance of multi-active objects is similar to the manually multi-threaded version while code dedicated to parallelism is much simpler when using multi-active objects. We also illustrated the performance gain brought by multi-active objects compared to a classical active object version. Overall, multi-active objects outperform simple active objects, and are easier to program than classical multi-threading. Interleaved execution and race-conditions can of course appear due to multithreading, but, on one side, annotations provide a good way to control this non-determinism, and on the other side, we defined an operational semantics that will allow us to study the possible executions of a multi-active objects and extend properties that the authors proved in the past for ASP.

Fig. 3 :

 3 Fig. 3: CAN experimental results

Table 1 :

 1 Parallel reduction (used or modified values are non-gray) split into a request to be served and the remaining of the request queue. If no request can be served neither sequentially nor in parallel, both functions are undefined. We define F uturespCq as the set of futures being computed by the current requests C. Then, parallel reduction ÝÑ is described in Table1. We will denote by ÝÑ ˚the reflexive transitive closure of ÝÑ. Table1consists of seven rules:

Table 2 :

 2 A possible definition of SeqSchedule and ParSchedule Property 2 (Maximum parallelism). Except the leftmost request of a thread, each request is incompatible with one of the other requests served by the same thread (and that precede it). More formally, if Q 0 ÝÑ

	˚α"

available at: www-sop.inria.fr/oasis/Ludovic.Henrio/java/PA_ma.zip

http://www.grid5000.fr/