Wilfried Martens

National Memories at the Heart of Europe: Re-Framing the Local Past in Strasbourg since 1945. Kiryll Atamanchyk; Aliaksei Lastouski; Iryna Ramanava. Places of Memory: A European Perspective on Overcoming Past

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

This is the author version, pre-publication draft. Published version available here :

https://www.martenscentre.eu/wp-content/uploads/2022/12/Places-of-Memory-A-European-Perspective-on-Overcoming-Past-Trauma.pdf

NATIONAL MEMORIES AT THE HEART OF EUROPE: RE-FRAMING THE LOCAL PAST IN STRASBOURG SINCE 1945

Tom Williams

Senior Lecturer in British Studies, Université d'Angers, and researcher at the Centre Interdisciplinaire de Recherche sur les Patrimoines en Lettres et Langues (CIRPaLL,EA 7457).

On 12 April 2022, between the two rounds of voting in the French presidential elections, Emmanuel Macron gave a speech in the shadow of Strasbourg cathedral, in which he declared his love for the city: "Strasbourg, Alsatian city, French city, European city, city of my heart, is one of the capitals of Europe! And yes, here, we know the meaning of the wounds [literally "bite marks"] when history takes a wrong turn". i Such insistence on these three frameworks of identity -regional, national and European -as well as on Strasbourg's symbolic status as a victim of "history" are typical of the way in which the city and its past have been commemorated since 1945. After decades of French-German conflict over Alsace, in which Strasbourg's past had been mobilized in support of rival national claims and integrated into competing national narratives, the second half of the twentieth century saw Strasbourg forge a new role for itself as the symbolic site of post-war Franco-German reconciliation at the heart of an integrating Western Europe. In this context, the city's contested past has been reinvented in ways which have reinforced Strasbourg's status both as a cultural "crossroads" at the European centre and as a victim of modern conflicts on the national periphery.

Emmanuel Macron's claim that Strasbourg can be both a French city and a "capital of Europe" reflects the fact that the Europeanization of Strasbourg's past since 1945 has not fundamentally undermined French national claims to the city. Indeed, it has above all been those historical figures, sites and periods which had previously been central to German national and territorial claims which have been denationalized, either within the narrow framework of Alsatian regional heritage or within the expanded framework of the city's European cultural heritage. Meanwhile, the core symbols and narratives of French patriotic memory in Strasbourg have rarely been challenged. Moreover, even though modern periods of German rule in the city from 1870 to 1918 and from 1940 to 1944 have been remembered with greater nuance in recent decades, core narratives of local suffering and resistance during these years have remained prominent, thus further reinforcing French patriotic memory in the city. As such, even though Macron's reference to the city's status as a victim of "history" was expressed in typically neutral language, the public was expected to understand that the "bite marks" to which he referred have been left not only by national conflicts in general but, above all, by past German attempts to dominate Strasbourg.

The Politics of History and Memory in a Contested Borderland, 1870-1945

Strasbourg's history has been shaped by its central location in the Rhine valley as well as its peripheral position between regions of Latin/French and Germanic culture. Founded by the Romans as the military camp of Argentoratum, the city came under the control of Alemannic tribes in the fourth century. It flourished as a commercial and cultural centre during the medieval period, gaining the status of a Free Imperial City within the Holy Roman Empire from the 1260s, and became an important centre of the Reformation in the sixteenth century. In 1681, during the reign of Louis XIV, this largely German-speaking and Protestant city was annexed by France, and Catholicism was re-imposed. The city then remained part of France for nearly two centuries, experiencing the profound political transformations of the Revolutionary and Napoleonic eras, the Restoration, the Revolutions of 1830 and 1848 and the Second Empire of Napoleon III. In September 1870, after a six-week-long siege and heavy bombardment, the city fell to the combined military forces of Prussia, Baden and Württemberg and subsequently became the administrative capital of the Reichsland of Elsass-Lothringen (Alsace-Lorraine) within the newly founded German Empire.

During the period of the German Kaisserreich from 1871 to 1918, the Alemannic linguistic and cultural heritage of Strasbourg (renamed Straßburg) and its flowering as a centre of German-speaking culture during the medieval period and Reformation were used by the authorities as a means of reinforcing German national claims to the city. At the inauguration of the city's new university buildings in 1884, for example, the university's rector Rudolf Sohm insisted that the cultural links between Strasbourg and Germany had never been broken, even during two centuries of French rule: "Here, where German folk and chivalric poetry once flourished, where German art made the wonderful cathedral soar high into the air, where in the 16th century the German Reformation triumphed and at the same time produced a German university, the connection with German intellectual life has never been broken." ii As this example suggests, German historical claims to the city focussed on the medieval period and Reformation, underlining their cultural achievements in purely national terms. In such a narrative, the French annexation of the city in 1681 was presented as a rapacious conquest, and the subsequent centuries of French rule as an unnatural, foreign imposition on the city's German-speaking population.

In opposition to a German definition of nationality based on language and culture, French intellectuals during this period formulated an alternative definition of the nation based on voluntary citizenship, one which reinforced French national claims to the borderland by emphasizing, above all, the transformative experience of the French Revolution. iii In a famous response to Theodor Mommsen's claims regarding the German nationality of Alsace, the French historian Fustel de Coulanges argued in 1870 that nationality was not an objective category but something that "men feel in their hearts" insisting that "it may be that Alsace is German by race and by language, but by nationality and patriotic sentiment it is French. And do you know what made it French? It is not Louis XIV, but our Revolution of 1789". iv Similar arguments were put forward by Ernest Renan in his 1882 lecture "What is a Nation?" in which he argued that language and "race" were less important factors in creating national communities than "a heroic past, great men, glory, […] having suffered, rejoiced and hoped together". v Such arguments regarding the French "sentiments" of the population were crucial when it came to maintaining French territorial claims to the "lost provinces" of Alsace-Lorraine after 1871 and in justifying their reconquest by France during the First World War.

After the return of Alsace-Lorraine to France in November 1918, French claims to Strasbourg were reasserted through a selective presentation of the local past dominated by the local figures and events which had tied Alsace to France from the seventeenth century to 1870. vi The enduring popularity of local heroes of the French Revolution and Empire was put forward as evidence that the city's French past had never been forgotten despite half a century of German rule. Most prominent among such local heroes was the revolutionary general Jean-Baptiste Kléber whose statue had stood on one of the city's main squares since 1840. This monument, according to the French President Raymond Poincaré in a speech given in Strasbourg in December 1918, had "silently represented, during the German occupation, the indomitable resistance of the people of Strasbourg". In the same speech Poincaré also insisted that Strasbourg had remained essentially unchanged in its national identity since 1790, when the city's inhabitants had "planted on the banks of the Rhine, facing Germany, the first tricolor flag with this inscription: 'Here begins the land of liberty'". vii Indeed, in the pronouncements of French politicians after 1918, the "liberty" of the Revolution and the "liberation" of 1918 were often presented as one and the same. Even the wars of Louis XIV in Alsace and the annexation of the city in 1681 were presented as a "first liberation", a claim that infuriated Alsatian regionalists. viii Heavy-handed French policies of centralization in the 1920s, particularly over matters of language, education and religion, led to the rise of several Alsatian regionalist and autonomist movements, which challenged the French patriotic version of regional history and sought to preserve aspects of Alsace's German cultural heritage. ix While the entry of French troops into the city in 1918 was invariably presented in official celebrations as a "liberation", the wider commemoration of the First World War was a particularly problematic subject, given that the majority of the local male population had been mobilized in the armies of the German Empire during the First World War. Tense deliberations over the question of a municipal war memorial lasted for almost two decades before a monument was finally erected on the place de la République in 1936. This monument depicted three figures: a mother holding the naked bodies of her two dying sons in her arms, representing the two nations for which the city's sons had fought. The inscription, "To Our Dead", made no mention of nationality. x The memory of the war was therefore partially denationalized, and above all de-Germanized, through the presentation of the city as a victim of national conflicts.

The annexation of Alsace by the Third Reich after the fall of France in June 1940 led to a further reinvention of the city at the centre of a National Socialist "Upper Rhine" region. xi A campaign of Entwelschung (literally "de-Latinization") was undertaken in the city, which included the the renaming of streets and squares and the removal of the statue to General Kléber. xii During this period, Strasbourg's medieval heritage was once again celebrated, the cathedral becoming the most regularly used symbol for the region's German past. xiii Historical propaganda of various forms, including several exhibitions organized as part of a "year of historical education" in 1942, underlined the city's supposed millennia-long struggle against French influence and its role as a cultural bulwark of the German nation, particularly during the Reformation. xiv National Socialist propaganda rejected the idea of a city's dual cultural heritage, insisting instead that the French "hereditary enemy" (Erbfeind) had left only a thin veneer of superficial "civilization" on the surface of a profoundly German city.

French Patriotic Commemoration and the Contested Past since 1945

The military defeat and occupation of Germany in 1945, as well as the renunciation of any territorial claims to Alsace by the post-war Federal Republic, made it possible for Strasbourg to be reinvented after 1945 as a symbol of reconciliation between former "hereditary enemies". Crucially, this reinvention as the symbolic heart of post-war European integration did not call into question the French nationality of the city: French patriotic commemoration in fact continued after 1945 along similar lines to the interwar period, presenting France as the bringer both of political "liberty" in 1789 and of "liberation" from Germany in 1918 and 1944. While this historical narrative was occasionally challenged by Alsatian regionalists, German nationalist claims to the city all but disappeared since the experience of the Third Reich and Second World War. Despite tensions over the memory of this period, particularly concerning the military service of Alsatians in the Wehrmacht and Waffen SS during the Second World War, periods of German rule in Strasbourg from 1870Strasbourg from to 1918Strasbourg from and 1940Strasbourg from to 1944 have tended to be presented in ways that reinforce the idea of the border city as a victim, and therefore as a potent symbol of post-war rapprochement.

Following the return of Strasbourg to France in November 1944, the city's liberators were frequently celebrated as the modern-day equivalents of the local heroes of the Revolutionary and Napoleonic periods. As had been the case in 1790 and in 1918, signs bearing the phrase "Here begins the land of liberty" were erected on the banks of the Rhine in 1945. xv On the first anniversary of the city's liberation, the city's mayor Charles Frey equated General Kléber, "the citizen-soldier of the armies of liberty" with the liberator of 1944 General Leclerc, "the young and bold general of the army of liberation". xvi Taking such a historical comparison into even more problematic territory, at a ceremony in honour of General de Lattre de Tassigny in 1948, Charles Frey praised the modern-day liberator as the descendent of Marshall Turenne, whose victories in the period of Louis XIV had secured the French possession of Alsace: "in the footsteps of the great Turenne […] he, too, liberated Alsace from the oppression of a hereditary enemy". xvii Given that even Fustel de Coulanges in the 1870s had argued that it had been the French Revolution, rather than Louis XIV, that had made Alsace French, such references to seventeenth century "liberation" were highly problematic. While a programme of festivities in 1948 to mark the 300 th anniversary of Alsace's "union" with France passed without serious incident, the celebration, in 1981, of the 300 th anniversary of Strasbourg's annexation by France generated heated debate, in spite of a very cautious, nuanced presentation of the events of 1681 in an exhibition by Strasbourg's municipal museums. xviii Alongside much discussion in the regional press, the most striking challenge to the 1981 tercentenary celebrations was the destruction, by an extreme-right regionalist group calling itself the "Black Wolves" (Schwarze Wölfe), of concrete monument erected in Thann during the tercentenary celebrations of 1948. A note sent by this group to the regional press directly challenged the typical French patriotic narratives: '1681-1981: 300 years of French colonialism in Alsace are 300 too many! The conquest of Alsace-Lorraine at that time was not a LIBERATION but a ROBBERY [Raub] in violation of international law". xix A more moderate, recent challenge to the French narrative of "300 years of liberation" came during the commemoration of the centenary of the First World War, when a regionalist party called "Our Land" (Unser Land) engaged in various symbolic protests including the unveiling of a red and white regionalist flag from the spire of Strasbourg Cathedral on the morning of 11 November 2018, in order to protest against the presentation of November 1918 as a moment of "liberation" for Alsace. xx Thus, while the challenge to French patriotic narratives of local history is less vocal and less politically potent than the regionalist and autonomist movements of the interwar years, these narratives have not gone wholly unchallenged since 1945.

The memory of periods of German rule from 1870 to 1918 and from 1940 to 1944 has also been a topic of contestation and controversy since 1945, although the result of such controversy has usually been to reinforce the status of Strasbourg and Alsace as the victims of history: not only the victims of nationalism or of German rule but also, in certain cases, of French distrust and misunderstanding. Such was the case in 1953 during the Bordeaux trial, in which fourteen Alsatian recruits into the Waffen SS (only one of whom had been a volunteer) were put on trial alongside German Waffen SS members for their involvement in the massacre of French civilians at Oradour-sur-Glane. Although the Alsatian conscripts received lighter penalties than the Germans, the guilty verdict was met by wide-spread protest and consternation in Alsace. 6,000 people took to the streets in protest in Strasbourg, and the war memorial on the place de la République was draped in black cloth. Fearing a return of the autonomist crises of the interwar years, the French national assembly hastily drafted a bill of amnesty and the Alsatians were released from prison. According to a report by the French préfet in Strasbourg, the whole episode had been extremely regrettable because the experience of Nazi rule and wartime conscription had in fact made the local population feel more French than ever before: "the Alsatians never felt so French as when they remembered being the victims of Germany". xxi After 1953, many Alsatians thus felt a double sense of victimization, first as victims of German tyranny and subsequently as victims of French distrust and suspicion. Such a discourse of victimization has not only shaped the memory of 1940-1944 but has also been projected back onto the period 1870-1918: the construction of the Mémorial de l'Alsace-Moselle in 2005 at Schirmeck, near the site of the National Socialist re-education camp of Schirmeck-Vorbruck, has reinforced this narrative of Alsace as a victim of German rule during both historical periods, and of French misunderstanding ever since. While some recent events, such as the exhibition " Strasbourg 1940Strasbourg -1944" held at the municipal archives from May 2021 to January 2022 have been able to look at this period in a more nuanced, objective way, the period 1940-1944 is still a highly sensitive subject in Alsace, particularly when compared to the rest of France, where the history and memory of the Occupation and the Vichy regime have been the subject of greater critical scholarly attention xxii

The Europeanization of Strasbourg's architectural and cultural heritage

In such a context, the Europeanization of Strasbourg's past since 1945 has facilitated the process of reconciliation, making it possible for elements of local history that fit uneasily into French national narratives to be celebrated as evidence of the city's European heritage or "destiny" without undermining the city's French nationality in the present. The founding of the Council of Europe in the city in 1949, and later the choice of Strasbourg as the site for the first directly elected European Parliament in 1979 have reinforced this narrative of a European "destiny", an idea that was also particularly prominent during the celebration of the city's "2000 th anniversary" in 1988. In the same year, Strasbourg's historic centre was added to the UNESCO World Heritage list, and this protected area was expanded in 2017 to include the Neustadt constructed under German rule after 1871. Both the 1988 and 2017 UNESCO decisions underlined Strasbourg's unique dual heritage as a product of two cultures. xxiii The selective Europeanization of the local past was a recognizable feature of the opening session of the Council of Europe, held at Strasbourg University on 10 August 1949, when the council's acting president -Édouard Herriot, whose centralizing government had aggravated Alsatian regionalist tensions in the 1920s -spoke of two great moments in Strasbourg's glorious past: the writing of the Marseillaise in the city in 1792 and the experiences of Strasbourg university's most famous student, Goethe, in the 1770s. The former, Herriot implied, was a symbol of the universal claims of the French Revolution but he also insisted that it was proof of the undying loyalty of Strasbourg to France: "this dear city with a faithful heart whose body has been so often martyred but which has never let its soul be violated". xxiv While the Marseillaise was thus only partly Europeanized, the figure of Goethe was entirely denationalized in Herriot's speech as "the example of an intellect that transcends and overcomes national boundaries". xxv This statement stands in stark contrast to previous German nationalist claims regarding Goethe's experience in the city. In the same hall just six years previously, Goethe's experience in the borderland had been proclaimed as an almost religious conversion to German national consciousness. xxvi By denationalizing Goethe in this way Strasbourg's role as a European cultural crossroads was emphasized and, simultaneously, the German cultural claims to Goethe, and to Alsace as a German cultural heartland, were undermined.

In the decades which followed the foundation of the Council of Europe, the historical experience of Strasbourg would frequently be presented as that of a European "crossroads", which made it possible for events that had previously been portrayed in terms of French-German cultural conflicts on the Rhine to be re-invented as evidence of fruitful cultural crossfertilization and exchange. In a report on Strasbourg's municipal museums in 1950, the longserving director of museums Hans Haug noted that, after the foundation of the Council of Europe, Strasbourg appeared "destined for a new role in history" which the municipal museum's collections could support by providing evidence of the city's "essentially European civilization". xxvii The representation of local heritage as European heritage would characterise a number of commemorations and exhibitions during this period, including the 1959 exhibition entitled "Strasbourg et l'Europe à travers l'histoire" and the exhibition "Strasbourg et l'Europe" organized to mark the opening of the session of the newly elected European parliament in 1979. xxviii In the catalogue for the latter exhibition, the city's mayor Pierre Pflimlin, a key figure in the city's reinvention as a European "capital", made reference to the conflicts of the past, but only in order to underline Alsace's commitment to the task of constructing a united Europe. Alsace he claimed, was "faithful to its European mission, to which the inhabitants of all Alsace attach great importance because our region, more than any other, has been the victim of the fratricidal struggles that have torn our continent apart". xxix The idea of Strasbourg as a cultural crossroads was thus frequently combined with an image of the borderland as the suffering and innocent victim of modern conflicts.

The 'dual' cultural heritage of borderland, in the decades after 1949, has been transformed into a symbol of peaceful European co-existence, rather than conflict. Cultural developments which had previously been presented, particularly in National Socialist historical propaganda, as evidence of cultural conflict and national struggle could appear as peaceful and fruitful moments of cultural exchange when presented in a European context. Strasbourg's role as a centre of the Reformation was reinvented along these lines. In 1991, the 500 th anniversary of the birth of the Protestant reformer Martin Bucer, founder of the city's Protestant 'Gymnasium' with Johannes (Jean) Sturm, which would become the university, was celebrated with a European outlook in an exhibition entitled "Martin Bucer, Strasbourg et l'Europe" xxx The figure of Bucer, who had been presented during the 1942 'year of historical education' as proto-nationalist fighting for German cultural unity, was transformed into a figure of peaceful intellectual exchange rather than one of cultural struggle. The 450 th anniversary of the foundation of the "Gymnasium", portrayed under National Socialist rule as a bastion of German Protestantism and national struggle, was commemorated with an exhibition which made no reference to national implications, and barely even to Protestant-Catholic conflict, but which instead placed Strasbourg and the surrounding region at the cultural and intellectual heart of Europe. xxxi Similarly, the cultural life of medieval Strasbourg, which had previously been used to assert German nationalist claims, has been celebrated in recent years as a further example of the city's "European" heritage. xxxii In the period since the Second World War the commemoration of Strasbourg's "European" past has therefore predominantly involved the denationalization of those periods, figures and events in local history -such as medieval architecture, the Reformation, or Goethe -that had previously been central to German nationalist claims. Historical events tying the city to France -such as its annexation in 1681, its contributions to the history of the French Revolution and Empire, or its two twentieth-century "liberations" -have tended to be remembered within a more narrowly national framework that (at its least subtle) identifies France as the bringer of both liberty and liberation to the Rhine borderlands, a discourse that has not always been well received by Alsatian regionalists. Nevertheless, the position of Strasbourg at the heart of the European project and as the symbolic site of post-war French-German reconciliation has made it possible, in contrast to the periods of national conflict from 1870 to 1945, to present a more nuanced, complex and objective vision of local history to the public. Even if the promotion of Strasbourg's role as a seat of European institutions has given an obvious political incentive for emphasizing Strasbourg's history as a cultural crossroads and as a victim of modern national conflicts, it goes without saying that the process of French-German reconciliation (and simply the passage of time since the Second World War) has created the conditions for a much more open and critical discussion of the local past than would have been possible during the successive German and French nation-building campaigns of the late nineteenth and early twentieth centuries.


Paul Gastin

LSV Nathalie Sznajder
email: nathalie.sznajder@lsv.ens-cachan.fr

Marc Zeitoun

Distributed synthesis for well-connected architectures

HAL is

Introduction

Synthesis is an essential problem in computer science introduced by Church [START_REF] Church | Logic, arithmetics, and automata[END_REF]. It consists in translating a system property which relates input and output events, into a low-level model which computes the output from the input, so that the property is met. The property may be given in a high level specification language (such as monadic second order logic) while the low-level model can be a finite state machine. More generally, the problem can be parametrized by the specification language and the target model.

The controller synthesis problem, in which a system is also part of the input, extends the synthesis problem. The goal is to synthesize a controller such that the system, synchronized with the controller, meets the given specification. Thus, the synthesis problem corresponds to the particular case of the controller synthesis problem with a system having all possible behaviors. Both problems have a classical formulation in terms of games. See for instance [START_REF] Thomas | On the synthesis of strategies in infinite games[END_REF][START_REF] Thomas | Church's problem and a tour through automata theory[END_REF] for a presentation of relationships between two-player infinite games in an automata-theoretic setting, and the synthesis problem. Both problems also have several variants. Let us review some of them, in order to relate the contribution of the present paper to existing work.

Some variants of the synthesis problem.

Closed vs. open systems. Early approaches consider closed systems, in which there is no interaction with an environment [START_REF] Clarke | Design and synthesis of synchronization skeletons using branching time temporal logic[END_REF]. Synthesis has later been extended to open systems [START_REF] Pnueli | On the synthesis of a reactive module[END_REF][START_REF] Abadi | Realizable and unrealizable specifications of reactive systems[END_REF], that is, to systems interacting with an unpredictable environment. The goal is to enforce the specification no matter how the environment acts. In this work, we consider open systems. Centralized vs. distributed systems. A solution to Church's problem for centralized systems has been presented by Büchi and Landweber [START_REF] Donzeau-Gouge | Solving sequential conditions by finite-state strategies[END_REF], for monadic second order specifications. A distributed system is made up of several communicating processes. The additional difficulty showing up with distributed systems is that the information acquired by each individual process about the global state of the system is only partial. Indeed, data exchanges between processes are constrained by a given communication architecture. For controller synthesis, the controller itself is required to be distributed over the same communication architecture, so that each of its components cannot have a complete knowledge of what happens. In this paper we also consider distributed systems.

Partially supported by projects ARCUS Île-de-France/Inde, DOTS (ANR-06-SETIN-003), and P2R MODISTE-COVER/Timed-DISCOVERI.

Algorithms solving the synthesis problem with incomplete information are given in [START_REF] Kupferman | Synthesis with incomplete information[END_REF][START_REF] Kupferman | µ-calculus synthesis[END_REF][START_REF] Arnold | Games for synthesis of controllers with partial observation[END_REF] for branching-time logic specifications. Synthesis has also been studied for specifications in the logic of knowledge and linear time, in [START_REF] Van Der Meyden | Synthesis from knowledge-based specifications[END_REF] for systems with a single agent, and in [START_REF] Van Der Meyden | Synthesis of distributed systems from knowledge-based specifications[END_REF] for distributed systems. The game-theoretic framework remains useful in the distributed case [START_REF] Bernet | On distributed program specification and synthesis in architectures with cycles[END_REF]. Unifying several formalisms, [START_REF] Mohalik | Distributed games[END_REF] proposed the framework of distributed games, a specialized variant of multiplayer games, to reason about distributed synthesis. Synchronous vs. asynchronous systems. For distributed systems, two classical semantics have been previously considered. In synchronous systems, there is a global clock, and each process executes one computation step at each clock tick. In asynchronous systems, there is no such global clock: each process behaves at its own speed. This paper considers synchronous systems. Only a few cases for such systems have been identified as decidable. See [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF][START_REF] Kupferman | Synthesizing distributed systems[END_REF] where the problem is studied for temporal logic specifications. Full vs. local vs. external specifications. In addition to the specification language itself, another natural parameter concerns the variables that a specification is allowed to refer to. Variables are of three kinds: input variables carry the values provided by the environment. Output variables are written by the system, and are not used for internal communication. Finally, for a distributed system, there is a fixed number of variables, called internal, corresponding to communication links between processes. We define three types of specifications:

• Full specifications are the most general ones: they may refer to any variable.

• External specifications only refer to input and output variables, but not to internal ones.

• Local specifications are Boolean combinations of p-local specifications, where p denotes a process. For a given process p, a specification is said p-local if it only refers to variables read or written by process p.

In this work, we use external specifications. Before discussing this choice and presenting our contributions, let us review the most salient existing results on the synthesis problem.

1.2. Synthesis for distributed systems: related work. For asynchronous systems, synthesis has first been studied in [START_REF] Pnueli | On the synthesis of an asynchronous reactive module[END_REF] for single-process implementations and linear-time specifications.

In [START_REF] Madhusudan | A decidable class of asynchronous distributed controllers[END_REF], the synthesis problem in the distributed setting is proved decidable for trace-closed specifications, yet for a quite specific class of controllers. This result has been strengthened in [START_REF] Madhusudan | The MSO theory of connectedly communicating processes[END_REF], where restrictions on the communication patterns of the controllers have been relaxed. Another subclass of decidable systems, incomparable with the preceding one, has been identified in [START_REF] Gastin | Distributed games with causal memory are decidable for series-parallel systems[END_REF], using an enhanced memory for controllers. The synthesis of asynchronous distributed systems in the general case of µ-calculus specifications was studied in [START_REF] Finkbeiner | Synthesis of asynchronous systems[END_REF]. Also, the theory of asynchronous automata has been applied in [START_REF] Stefȃnescu | Synthesis of distributed algorithms using asynchronous automata[END_REF] to solve the synthesis problem of closed distributed systems.

For synchronous systems, undecidability is the point in common to most existing results. This question has been first studied in [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF], where synthesis has been proved undecidable for LTL specifications and arbitrary architectures. For pipeline architectures (where processes are linearly ordered and each process communicates to its right neighbor), synthesis becomes non elementarily decidable for LTL specifications. The lower bound follows from a former result on multiplayer games [START_REF] Gary | Multiple-person alternation[END_REF]. Even for local specifications, constraining only variables local to processes, the problem is still undecidable for most communication architectures [START_REF] Madhusudan | Distributed controller synthesis for local specifications[END_REF]. Synthesis has been shown decidable for the pipeline architecture and CTL * full specifications [START_REF] Kupferman | Synthesizing distributed systems[END_REF]. A decision criterion for full specifications has then been established in [START_REF] Finkbeiner | Uniform distributed synthesis[END_REF]. It implies that the problem is undecidable for the architecture of Figure 1. The reason is that full specifications make it possible to enforce a constant value on variable t, breaking the communication link between processes p 0 and p 1 .

1.3. Contributions. We address the synthesis problem for open distributed synchronous systems and temporal logic specifications. In contrast to the situation in the asynchronous setting, most decidability results for synthesis of synchronous systems are negative. The goal of this paper is to investigate relevant restrictions to obtain decidability. Undecidability often arises

x 0 x 1 p 0 p 1 y 0 y 1 t Figure 1.
Architecture decidable/undecidable for external/full specifications.

when dealing with full specifications. For the rare positive statements, as for the pipeline architecture, allowing full specifications strengthen the decidability result [START_REF] Kupferman | Synthesizing distributed systems[END_REF]. On the other hand, for the undecidability part of the criterion obtained in [START_REF] Finkbeiner | Uniform distributed synthesis[END_REF], allowing full specifications weakens the result by yielding easy reductions to the basic undecidable architecture of Pnueli and Rosner [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF] (see Figure 1), for instance by breaking communication links at will. In the seminal paper [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF], specifications were assumed to be external, or input-output: only variables communicating with the environment could be constrained. The way processes of the system communicate was only restricted by the communication architecture, not by the specification. This is very natural from a practical point of view: when writing a specification, we are only concerned by the input/output behavior of the system and we should leave to the implementation all freedom on its internal behavior. For that reason, solving the problem for external specifications is more relevant and useful-albeit more difficult-than a decidability criterion for arbitrary specifications. We will show that the synthesis problem is decidable for the architecture of Figure 1 and external specifications, that is, if we do not constrain the internal variable t. Results. We consider the synthesis problem for synchronous semantics, where each process is assigned a nonnegative delay. The delays can be used to model latency in communications, or slow processes. This model has the same expressive power as the one where delays sit on communication channels, and it subsumes both the 0-delay and the 1-delay classical semantics [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF][START_REF] Kupferman | Synthesizing distributed systems[END_REF].

To rule out unnatural properties yielding undecidability, the specifications we consider are external, coming back to the original framework of [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF][START_REF] Church | Logic, arithmetics, and automata[END_REF]. In Section 3, we first determine a sufficient condition for undecidability with external specifications, that generalizes the undecidability result of [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF]. We next introduce in Section 4 uniformly well-connected (UWC) architectures. Informally, an architecture is UWC if there exists a routing allowing each output process to get, as soon as possible, the values of all inputs it is connected to. Using tree automata, we prove that for such architectures and external specifications, the sufficient condition for undecidability becomes a criterion. (As already pointed out, synthesis may be undecidable for full specifications while decidable for external ones.) We also propose a natural restriction on specifications for which synthesis, on UWC architectures, becomes decidable. We call such specifications robust specifications. Finally, we introduce in Section 5 the larger class of wellconnected architectures, in which the routing of input variables to an output process may depend on that process. We show that our criterion is not a necessary condition anymore for this larger class. The undecidability proof highlights the surprising fact that in Figure 1, blanking out a single information bit in the transmission of x 0 to p 1 through t suffices to yield undecidability. This is a step forward in understanding decidability limits for distributed synthesis. It remains open whether the problem is decidable for robust external specifications and well-connected architectures.

An extended abstract of this work appeared in [START_REF] Gastin | Distributed synthesis for well-connected architectures[END_REF].

Preliminaries

Trees and tree automata. Given two finite sets X and Y , a Y -labeled X-tree (also called full tree) is a total function t : X * → Y where elements of X are called directions, and elements of Y are called labels. A word σ ∈ X * defines a node of t and t(σ) is its label. is the root of the tree. A word σ ∈ X ω is a branch. In the following, a tree t : X * → Y will be called an (X, Y )-tree.

A non-deterministic tree automaton (NDTA) A = (X, Y, Q, q 0 , δ, α) runs on (X, Y )-trees. It consists of a finite set of states Q, an initial state q 0 , a transition function δ : Q × Y → 2 Q X and an acceptance condition α ⊆ Q ω . A run ρ of such an automaton over an (X, Y )-tree t is an (X, Q)-tree ρ such that ρ(ε) = q 0 , and for all σ ∈ X * , (ρ(σ

• x)) x∈X ∈ δ(ρ(σ), t(σ)). The run ρ is accepting if all its branches s 1 s 2 • • • ∈ X ω are such that ρ(ε)ρ(s 1 )ρ(s 1 s 2 ) • • • ∈ α.
The specific acceptance condition chosen among the classical ones is not important in this paper.

Architectures. An architecture A = (V ⊎ P, E, (S v ) v∈V , s 0 , (d p ) p∈P ) is a finite directed acyclic bipartite graph, where V ⊎ P is the set of vertices, and E ⊆ (V × P ) ∪ (P × V ) is the set of edges, such that |E -1 (v)| ≤ 1 for all v ∈ V . Elements of P will be called processes and elements of V variables. Intuitively, an edge (v, p) ∈ V × P means that process p can read variable v, and an edge (p, v) ∈ P × V means that p can write on v. Thus, |E -1 (v)| ≤ 1 means that a variable v is written by at most one process. An example of an architecture is given in Figure 2, where processes are represented by boxes and variables by circles. Input and output variables are defined, respectively, by

V I = {v ∈ V | E -1 (v) = ∅}, V O = {v ∈ V | E(v) = ∅}.
Variables in V \ (V I ∪ V O ) will be called internal. We assume that no process is minimal or maximal in the graph: for p ∈ P , we have E(p) = ∅ and E -1 (p) = ∅.

Each variable v ranges over a finite domain S v , given with the architecture. For U ⊆ V , we denote by S U the set v∈U S v . A configuration of the architecture is given by a tuple s = (s v ) v∈V ∈ S V describing the value of all variables. For U ⊆ V , we denote by s U = (s v ) v∈U the projection of the configuration s to the subset of variables U . The initial configuration is s 0 = (s v 0 ) v∈V ∈ S V . We will assume that |S v | ≥ 2 for all v ∈ V , because a variable v for which |S v | = 1 always has the same value and may be ignored. It will be convenient in some proofs to assume that {0, 1} ⊆ S v and that s v 0 = 0 for all v ∈ V . Each process p ∈ P is associated with a delay d p ∈ N that corresponds to the time interval between the moment the process reads the variables v ∈ E -1 (p) and the moment it will be able to write on its own output variables. Note that delay 0 is allowed. In the following, for v ∈ V , we will often write d v for d p where E -1 (v) = {p}.

Runs. A run of an architecture is an infinite sequence of configurations, i.e., an infinite word over the alphabet S V , starting with the initial configuration s 0 ∈ S V given by the architecture.

If σ = s 0 s 1 s 2 • • • ∈ (S V ) ω is a run, then its projection on U ⊆ V is σ U = s U 0 s U 1 s U 2 • • •
. Also, we denote by σ[i, j] the factor s i . . . s j and by σ[i] the prefix of length i of σ (by convention, σ[i] = ε if i ≤ 0). A run tree is a full tree t : (S V I ) * → S V , where t(ε) = s 0 and for ρ ∈ (S V I ) * , r ∈ S V I , we have t(ρ • r) V I = r. The projection of t on U ⊆ V is the tree t U : (S V I ) * → S U defined by t U (ρ) = t(ρ) U .

Specifications. Specifications over a set U ⊆ V of variables can be given, for instance, by a µcalculus, CTL * , CTL, or LTL formula, using atomic propositions of the form (v = a) with v ∈ U and a ∈ S v . We then say that the formula is in L(U ) where L is the logic used. Specifications over U are external if U ⊆ V I ∪ V O . The validity of an external formula on a run tree t (or simply a run) only depends on its projection t

V I ∪V O onto V I ∪ V O .
Programs, strategies. We consider a discrete time, synchronous semantics. Informally, at step i = 1, 2, . . ., the environment provides new values for input variables. Then, each process p reading values written by its predecessors or by the environment at step id p , computes values for the variables in E(p), and writes them. Let v ∈ V \ V I and let R(v) = E -2 (v) be the set of variables read by the process writing to v. Intuitively, from a word σ R(v) in (S R(v) ) + representing the projection on R(v) of some run prefix, a program (or a strategy) advises a value to write on variable v. But, since the process may have a certain delay d v , the output of the strategy must not depend on the last d v values of σ R (v) .

Formally, a program (or local strategy) for variable v is a mapping

f v : S R(v) + → S v compatible with the delay d v , i.e., such that for all σ, σ ′ ∈ (S R(v) ) i , if σ[i -d v ] = σ ′ [i -d v ], then f v (σ) = f v (σ ′ ). This condition -called delay-compatibility or simply d-compatibility -ensures that the delay d v is respected when computing the next value of variable v. A distributed program (or distributed strategy) is a tuple F = (f v ) v∈V \V I of local strategies. A run σ = s 0 s 1 s 2 • • • ∈ (S V ) ω is an F -run (or is F -compatible) if for all v ∈ V \ V I and all i > 0, s v i = f v (σ R(v) [i]). Given an input sequence ρ ∈ (S V I ) ω , there is a unique run σ ∈ (S V ) ω which is F -compatible and such that σ V I = ρ.
The F -run tree is the run tree t : (S V I ) * → S V such that each branch is labeled by a word

s 0 s 1 s 2 • • • ∈ (S V ) ω which is an F -run. Note that, in an F -run σ ∈ (S V ) ω , the prefix σ[i] only depends on the prefix σ V I [i]
. This shows that the F -run tree is unique.

Distributed synthesis problem.

Let L be a specification language. The distributed synthesis problem for an architecture A is the following: given a formula ϕ ∈ L, decide whether there exists a distributed program F on A such that every F -run (or the F -run tree) satisfies ϕ. We will then say that F is a distributed implementation for the specification ϕ. If for some architecture the synthesis problem is undecidable, we say that the architecture itself is undecidable (for the specification language L).

Memoryless strategies. The strategy f v is memoryless if it does not depend on the past, that is, if there exists g :

S R(v) → S v such that f v (s 0 • • • s i • • • s i+dv ) = g(s i ) for s 0 • • • s i+dv ∈ (S R(v) ) + .
In case d v = 0, this corresponds to the usual definition of a memoryless strategy.

Summaries. For a variable

v ∈ V , we let View(v) = (E -2 ) * (v) ∩ V I be the set of input variables v might depend on. Observe that if σ is an F -run, then for all v ∈ V \ V I , for all i ≥ 0, s v i only depends on σ View(v) [i]. This allows us to define the summary f v : (S View(v) ) + → S v such that f v (σ View(v) [i]) = s v i ,

corresponding to the composition of all local strategies used to compute v.

Smallest cumulative delay. Throughout the paper, the notion of smallest cumulative delay of transmission from u to v will extensively be used. It is defined by

d(u, u) = 0, d(u, v) = +∞ if v / ∈ (E 2 ) + (u), i.e.
, if there is no path from u to v in the architecture, and for

u = v ∈ (E 2 ) + (u) d(u, v) = d v + min{d(u, w) | w ∈ R(v) and w ∈ (E 2 ) + (u)} .
d-compatibility for summaries. The compatibility of the strategies F = (f v ) v∈V \V I with the delays extends to the summaries F = ( f v ) v∈V \V I . Formally, a map h :

(S View(v) ) + → S v is d-compatible (or compatible with the delays (d v ) v∈V \V I ) if for all ρ ∈ (S View(v) ) i , h(ρ) only depends on the prefixes (ρ u [i -d(u, v)]) u∈View(v) . x 0 y 0 x n y m A x 0 y 0 p q x n y m A ′

Architectures with incomparable information

In this section, we state a sufficient condition for undecidability; this relies on an easy generalization of the undecidable architecture presented in [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF]. Definition 3.1. An architecture has incomparable information if there exist variables x, y ∈ V O such that View(x) \ View(y) = ∅ and View(y) \ View(x) = ∅. Otherwise the architecture has linearly preordered information.

For instance, the architectures of Figures 1, 2, 5 and 6 have linearly preordered information, while the architecture A ′ of Figure 3 has incomparable information. The following proposition extends the undecidability result of [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF][START_REF] Finkbeiner | Uniform distributed synthesis[END_REF].

Proposition 3.2. Architectures with incomparable information are undecidable for LTL or CTL external specifications.

In [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF], the architecture A ′ shown in Figure 3 is proved undecidable, both for LTL and CTL specifications. We will reduce the synthesis problem of A ′ to the synthesis problem of an architecture with incomparable information. This reduction is rather natural but not completely straightforward, for instance the specification needs to be changed in the reduction. For the sake of completeness, we give a precise proof of the reduction in the rest of this section.

Let A = (P ⊎ V, E, (S v ) v∈V , s 0 , (d p ) p∈P ) be an architecture with incomparable information. Without loss of generality, we assume that s v 0 = 0 for all v ∈ V . By definition, we find x 0 , y 0 ∈ V I and x n , y m ∈ V O such that x 0 / ∈ View(y m ) and y 0 / ∈ View(x n ). Consider paths

x 0 E 2 x 1 E 2 . . . E 2 x n from x 0 to x n , and y 0 E 2 y 1 E 2 . . . E 2 y m from y 0 to y m such that d(x 0 , x n ) = d x 1 + • • • + d xn and d(y 0 , y m ) = d y 1 + • • • + d ym .
Note that the sets of variables {x 0 , . . . , x n } and {y 0 , . . . , y m } are disjoint.

Let

A ′ = (P ′ ⊎ V ′ , E ′ , (S ′v ) v∈V ′ , s ′ 0 , (d ′ p ) p∈P ′
) be the architecture of Figure 3 with

V I ′ = {x 0 , y 0 }, V O ′ = {x n , y m };
with unchanged domains for output variables: S ′xn = S xn and S ′ym = S ym ; with S ′x 0 = S ′y 0 = {0, 1} as domain for input variables; and with s ′ 0 = s V ′ 0 . The delays for x n and y m are the smallest cumulative delays of transmission from x 0 to x n and y 0 to y m as defined earlier:

d ′ xn = d ′ p = d(x 0 , x n ) and d ′ ym = d ′ q = d(y 0 , y m ).
The architecture A ′ is undecidable for LTL or CTL specifications (it suffices to adapt the proofs of [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF][START_REF] Finkbeiner | Uniform distributed synthesis[END_REF] taking into account different delays on processes). We reduce the distributed synthesis problem for A ′ to the same problem for A. We first consider CTL specifications.

Note that we do need to modify the specification when reducing the distributed synthesis problem from A ′ to A. Indeed, observe that the specification

ψ = EG((x 0 = 0) ∧ (x n = 0)) ∧ EG((x 0 = 0) ∧ (x n = 1))
is not implementable over A ′ whereas it is implementable over A, provided View(x n ) \ {x 0 } = ∅ and assuming no delays.

To define an implementation F ′ over A ′ given an implementation F over A, we simulate the behavior of F when all variables in V I \ V I ′ are constantly set to 0. This will be enforced when defining the reduction of the specification from A ′ to A, using the formula χ = (x 0 ∈ {0, 1}) ∧ (y 0 ∈ {0, 1}) ∧ v∈V I \V I ′ (v = 0). We define a reduction that maps a formula ψ of CTL(V ′ ) into a formula ψ in CTL(V I ∪ V O ) that ensures ψ only on the subtree of executions respecting χ. This reduction is defined by

x 0 x n-1 d ′ xn σ x n-1 2 d ′ xn -d xn d xn
(x = s) = (x = s) ¬ψ = ¬ψ ϕ ∨ ψ = ϕ ∨ ψ EX ψ = EX(χ ∧ ψ) E ϕ U ψ = E(χ ∧ ϕ) U (χ ∧ ψ) EG ψ = EG(χ ∧ ψ).
We use the following notation: for r ∈ S ′V I ′ , we define r ∈ S V I by rV I ′ = r and rv = 0 for all v ∈ V I \ V I ′ , and we extend this definition to words (with ε = ε). This allows us to fix the run tree t : (S ′V I ′ ) * → S V ′ over A ′ that corresponds to a run tree t : (S V I ) * → S V over A: Proof. By an easy induction on ψ. Let t : (S V I ) * → S V and ρ ∈ (S ′V I ′ ) * . When ψ = (x = s) for some x ∈ V ′ and s ∈ S x , the result follows from t(ρ) x = t(ρ) x . The cases of boolean connectives are trivial. So let ψ = E ψ 1 U ψ 2 and assume that t, ρ |= ψ. Then we find

t(ρ) = t(ρ) V ′ for ρ ∈ (S ′V I ′ ) * .
s 1 • • • s n ∈ (S V I ) * such that t, ρ • s 1 • • • s n |= χ ∧ ψ 2 and t, ρ • s 1 • • • s i |= χ ∧ ψ 1 for all 0 ≤ i < n. Since s i |= χ, we deduce that s i = r i for r i = s V I ′ i ∈ S ′V I ′ . By induction we obtain t, ρ • r 1 • • • r n |= ψ 2 and t, ρ • r 1 • • • r i |= ψ 1 for all 0 ≤ i < n. Therefore, t, ρ |= ψ.
The converse implication can be shown similarly.

The cases EX and EG are left to the reader.

Now we prove the reduction:

Lemma 3.4. If there is a distributed program F ′ over A ′ that satisfies ψ, then there is a distributed program F over A that satisfies ψ.

Proof. Let F ′ = (f ′xn , f ′ym ) be a distributed implementation for ψ over A ′ . We will define a distributed strategy F = (f v ) v∈V for ψ over A so that the projection on V ′ of any F -run will be an F ′ -run. More precisely, if σ ∈ (S V ) + is a prefix of an F -run with σ x 0 ∈ {0, 1} + , then the following will hold:

(1)

f xn (σ R(xn) ) = f ′xn (σ x 0 )
and similarly for (y 0 , y m ).

To do so, we use the variables x 1 , . . . , x n-1 to transmit the value of x 0 through the architecture. Formally, at each step, f x k copies the last value of x k-1 it can read -the one that was written d x k steps before: for 0 < k < n and τ ∈ (S R(x k ) ) + , we define

f x k (τ ) = s x k-1 if τ = τ 1 sτ 2 with |τ 2 | = d x k and s x k-1 ∈ {0, 1}, 0 otherwise.
By definition, f x k is clearly compatible with the delay d x k . It is easy to check that if we provide ρ ∈ {0, 1} ω as input on x 0 and follow the strategies (f x k ) above then we get on x n-1 the outcome 0 d(x 0 ,x n-1 ) ρ corresponding to the shift by d(x 0 , x n-1 ) = d ′ xnd xn . In order to satisfy (1), the last strategy f xn simulates f ′xn taking into account the shift by d ′ xnd xn of their respective inputs. To explain the definition of f xn , consider σ ∈ (S V ) + compatible with (f x k ) 0<k<n and such that σ

x 0 ∈ {0, 1} + . If |σ| ≤ d ′ xn then f ′xn (σ x 0 ) does not depend on σ so we define f xn (σ R(xn) ) = f ′xn (0 |σ| ) = f ′xn (σ x 0 ) so that (1) holds. Assume now that σ = σ 1 σ 2 σ 3 with |σ 1 | = d ′ xn -d xn , |σ 3 | = d xn .
Note that f ′xn (σ x 0 ) only depends on the prefix of σ x 0 of length |σ 2 | which is precisely σ

x n-1 2
due to the shift induced by the strategies (f x k ) 0<k<n (see Figure 4). Hence, in this case, we define f xn (σ R(xn) ) = f ′xn (σ

x n-1 2 0 d ′ xn ) = f ′xn (σ x 0
) in order to get (1) again. The formal definition of f xn is given for arbitrary τ ∈ (S R(xn) ) + by

f xn (τ ) =            f ′xn (0 |τ | ) if |τ | ≤ d ′ xn , f ′xn (τ x n-1 2 0 d ′ xn ) if τ = τ 1 τ 2 τ 3 with |τ 1 | = d ′ xn -d xn , |τ 3 | = d xn and τ x n-1 2 ∈ {0, 1} + , 0 otherwise.
By definition, f xn is clearly compatible with the delay d xn . Also, we have explained that [START_REF] Abadi | Realizable and unrealizable specifications of reactive systems[END_REF] holds with this definition of (f x k ) 0<k≤n . For 0 < k ≤ m, we define similarly f y k and for every other variable v, we set f v = 0. The resulting distributed strategy F = (f v ) v∈V is indeed compatible with the delays. It remains to show that F is a distributed implementation for ψ over A.

Let t : (S V I ) * → S V be the F -run tree over A. We show below that t : (S ′V I ′ ) * → S V ′ is in fact the F ′ -run tree over A ′ . Then, since F ′ is a distributed implementation of ψ, we deduce t, ε |= ψ, and Lemma 3.

3 implies t, ε |= ψ. Hence F is a distributed implementation of ψ.
First, it is easy to see that t is a run-tree over

A ′ : t(ε) = t(ε) V ′ = s V ′ 0 = s ′ 0 , and for ρ ∈ (S ′V I ′ ) * and r ∈ S ′V I ′ we have t(ρ • r) V I ′ = t(ρ • r) V I ′ = rV I ′ = r V I ′ . Next, to show that t is the F ′ -run tree, we have to check that t(ρ) xn = f ′xn (ρ x 0 ) for each ρ = r 1 • • • r i ∈ (S V I ′ ) + and similarly for (y 0 , y m ). Let σ ∈ (S V ) + be the F -run induced by ρ: σ = t(ε)t(r 1 )t(r 1 r2 ) • • • t(ρ). Using (1) we obtain t(ρ) xn = t(ρ) xn = f xn (σ R(xn) ) = f ′xn (σ x 0 ) = f ′xn (ρ x 0 ).
Using the same arguments, we also obtain that t(ρ) ym = f ′ym (ρ y 0 ), and that t is the F ′ -run tree. Lemma 3.5. If there is a distributed program F over A that satisfies ψ, then there is a distributed program F ′ over A ′ that satisfies ψ.

Proof. Suppose F = (f v ) v∈V \V I is a distributed implementation of ψ over A. We need to define the strategies f ′xn : (S ′x 0 ) + → S xn and f ′ym : (S ′y 0 ) + → S ym of the variables in A ′ . The difficulty here is that f ′xn may have less input variables than f xn so it cannot simply simulate it. To overcome this, we use the fact that, due to the special form of ψ, the F -run tree t satisfies ψ if and only if the sub-tree restricted to branches where all input variables other than x 0 and y 0 are always 0 also satisfies ψ. So the processes of A ′ will behave like the processes of A writing respectively on x n and y m in the special executions when the values of input variables other than x 0 and y 0 are always 0.

Formally, for ρ ∈ (S ′V I ′ ) + , we set f ′xn (ρ x 0 ) = f xn (ρ View(xn) ). Observe that, due to incomparable information, f xn does not depend on ρy 0 . Hence f ′xn only depends on ρ x 0 and is a correct strategy for variable x n in the architecture A ′ . Moreover, f xn is d-compatible and so f ′xn is d ′ -compatible. We define f ′ym similarly. It is easy to check that F ′ = (f ′xn , f ′ym ) is a distributed implementation of ψ over A ′ : let t be the F -run tree and t ′ be the F ′ -run tree. We have t ′ (ρ) xn = f ′xn (ρ x 0 ) = f xn (ρ View(xn) ) = t(ρ) xn = t(ρ) xn and similarly, t ′ (ρ) ym = t(ρ) ym . Hence t ′ = t and since t, ε |= ψ, Lemma 3.3 implies that t, ε |= ψ and F ′ is a distributed implementation of ψ on A ′ . We consider the reduction for LTL specifications. In this case, the specification over A only needs to ensure ψ when the input values on x 0 and y 0 are in the domain allowed by A ′ . We use the reduction

ψ = (G ξ) → ψ
where the formula ξ is defined by ξ = (x 0 ∈ {0, 1}) ∧ (y 0 ∈ {0, 1}).

The same constructions as the ones described in the proofs of Lemma 3.4 and Lemma 3.5 yield the reduction. Indeed, let F ′ be a distributed implementation of ψ over A ′ , and let F be defined as in the proof of Lemma 3.4. Let ρ ∈ (S V I ) ω be an input sequence and σ

= s 0 s 1 s 2 • • • ∈ (S V ) ω be the induced F -run. If ρ x 0 / ∈ {0, 1} ω or ρ y 0 / ∈ {0, 1} ω then σ, ε |= G ξ.
Otherwise, by equation ( 1), we get for all i > 0,

s xn i = f xn (σ R(xn) [i]) = f ′xn (σ x 0 [i]) and s ym i = f ym (σ R(ym) [i]) = f ′ym (σ y 0 [i]
). Then σ V ′ is an F ′ -run, and σ V ′ , ε |= ψ. Since ψ ∈ LTL(V ′ ) we deduce σ, ε |= ψ. We obtain that any F -run σ is such that σ, ε |= (G ξ) → ψ, and F is a distributed implementation of ψ over A.

Conversely, given F a distributed implementation of ψ over A, define F ′ as in the proof of Lemma 3.5. Let ρ ∈ (S ′V I ′ ) ω be an input sequence and σ = s 0 s 1 s 2 • • • ∈ (S V ) ω be the F -run induced by ρ. By definition of ρ, we have σ, ε |= G ξ and since F is a distributed implementation of ψ we get σ, ε |= ψ. Again, ψ ∈ LTL(V ′ ) implies that σ V ′ , ε |= ψ. Given that σ V ′ is in fact the F ′ -run induced by ρ (this is immediate from the definition of f ′xn and f ′ym ), F ′ is a distributed implementation of ψ over A ′ .

We have defined a reduction from the distributed synthesis problem over the architecture A ′ to the distributed synthesis problem over an architecture with incomparable information, for LTL or CTL specifications. Since the synthesis problem is undecidable both for LTL and CTL specifications over A ′ , we obtain its undecidability for architectures with incomparable information.

Uniformly well-connected architectures

This section introduces the new class of uniformly well-connected (UWC) architectures and provides a decidability criterion for the synthesis problem on this class. It also introduces the notion of robust specification and shows that UWC architectures are always decidable for external and robust specifications.

Definition.

A routing for an architecture A = (V ⊎ P, E, (S v ) v∈V , s 0 , (d p ) p∈P ) is a family of memoryless local strategies Φ = (f v ) v∈V \(V I ∪V O ) . Observe that a routing does not include local strategies for output variables. Informally, we say that an architecture is uniformly well connected if there exists a routing Φ that makes it possible to transmit with a minimal delay to every process p writing to an output variable v, all the values of the variables in View(v). Definition 4.1. An architecture A is uniformly well-connected (UWC) if there exist a routing Φ and, for every v ∈ V O and u ∈ View(v), a decoding function g u,v : S R(v) + → S u that can reconstruct the value of u, i.e., such that for any Φ-compatible sequence σ

= s 0 s 1 s 2 • • • ∈ S V \V O + , we have for i ≥ 0 (2) s u i = g u,v (σ R(v) [i + d(u, v) -d v ])
In case there is no delay, the uniform well-connectedness refines the notion of adequate connectivity introduced by Pnueli and Rosner in [START_REF] Pnueli | Distributed reactive systems are hard to synthesize[END_REF], as we no longer require each output variable to be communicated the value of all input variables, but only of those belonging to its view. In fact, this gives us strategies for internal variables, that are simply to route the input to the processes writing on output variables.

Observe that, whereas the routing functions are memoryless, memory is required for the decoding functions. Indeed, consider the architecture of Figure 5. The delays are written next to the processes, and all variables range over the domain {0, 1}. Observe first that this architecture is UWC: process p writes to t the xor of u 1 and u 2 with delay 1. This could be written t = Y u 1 ⊕ Y u 2 where Y x denotes the previous value of variable x. In order to recover (decode) Y u 2 , process q 1 memorizes the previous value of u 1 and makes the xor with t: Y u 2 = t ⊕ Y u 1 . But if we restrict to memoryless decoding functions, then we only know u 1 and t and we cannot recover Y u 2 .

u 1 u 2 p 1 t q 1 0 q 2 0 v 1 v 2
Figure 5. A uniformly well-connected architecture 4.2. Decision criterion for UWC architectures. We first show that distributed programs are somewhat easier to find in a UWC architecture. As a matter of fact, in such architectures, to define a distributed strategy it suffices to define a collection of input-output strategies that respect the delays given by the architecture.

Lemma 4.2. Let

A = (V ⊎P, E, (S v ) v∈V , s 0 , (d p ) p∈P ) be a UWC architecture. For each v ∈ V O , let h v : (S View(v) ) + → S v be an input-output mapping which is d-compatible. Then there exists a distributed program F = (f v ) v∈V \V I over A such that h v = f v for all v ∈ V O . Proof. Let Φ = (f v ) v∈V \(V I ∪V O ) and (g u,v
) v∈V O ,u∈View(v) be respectively the routing and the decoding functions giving the uniform well-connectedness of the architecture A. We use the routing functions f v as memoryless strategies for the internal variables

v ∈ V (V I ∪ V O ). It remains to define f v for v ∈ V O . Let ρ ∈ (S V ) i for i > 0 and let σ ∈ (S V \V O ) i be the corresponding Φ-compatible sequence. For v ∈ V O , we want to define f v such that f v (σ R(v) ) = h v (ρ View(v)
). We need to verify that this is well-defined. Let i > 0 and ρ, ρ ′ ∈ (S V I ) i . Let σ, σ ′ ∈ (S V \V O ) i be the corresponding Φ-compatible sequences, and assume σ R(v)

[i -d v ] = σ ′R(v) [i -d v ]. Then, for all u ∈ View(v), ρ u [i -d(u, v)] = ρ ′u [i -d(u, v)]. Indeed, for all 0 ≤ j ≤ i -d(u, v), we have s u j = g u,v (σ R(v) [j + d(u, v) -d v ]
) and

s ′u j = g u,v (σ ′R(v) [j + d(u, v) -d v ]) by (2). Using σ R(v) [i -d v ] = σ ′R(v) [i -d v ] and j + d(u, v) ≤ i we get s u j = s ′u j as desired. Since h v is d-compatible, we deduce that h v (ρ View(v) ) = h v (ρ ′View(v)
). Hence for τ ∈ (S R(v) ) i with i > 0, we can define

f v (τ ) =        h v (σ View(v) ) if τ [i -d v ] = σ R(v) [i -d v ] for some Φ-compatible sequence σ 0 otherwise
By the above, f v is well-defined and obviously it depends only on τ [id v ]. Thus, it is indeed d-compatible. Now, let ρ ∈ (S V I ) + , and let σ be the F -run induced by ρ. We get, by definition of summaries,

f v (ρ View(v) ) = f v (σ R(v) ). Since σ V \V O is also a Φ-compatible sequence for ρ, we have f v (ρ View(v) ) = f v (σ R(v) ) = h v (ρ View(v) ).
We now give a decision criterion for this specific subclass of architectures.

Theorem 4.3. A UWC architecture is decidable for external (linear or branching) specifications if and only if it has linearly preordered information.

We have already seen in Section 3 that incomparable information yields undecidability of the synthesis problem for LTL or CTL external specifications. We prove now that, when restricted to the subclass of UWC architectures, this also becomes a necessary condition.

We assume that the architecture A is UWC and has linearly preordered information, and therefore we can order the output variables

V O = {v 1 , . . . , v n } so that View(v n ) ⊆ • • • ⊆ View(v 1 ) ⊆ V I .
In the following, in order to use tree-automata, we extend a local strategy f : (S X ) + → S Y by letting f (ε) = s Y 0 , so that it becomes an (S X , S Y )-tree. We proceed in two steps. First, we build an automaton accepting all the global input-output 0-delay strategies implementing the specification. A global input-output 0-delay strategy for A is an (S View(v 1 ) , S V O )-tree h satisfying h(ε) = s V O 0 . This first step is simply the program synthesis for a single process with incomplete information (since we may have View(v 1 ) V I ). This problem was solved in [START_REF] Kupferman | Church's problem revisited[END_REF] for CTL * specifications. Proposition 4.4 [START_REF] Kupferman | Church's problem revisited[END_REF]Th. 4.4]). Given an external specification ϕ ∈ CTL * (V I ∪ V O ), one can build a non-deterministic tree automaton (NDTA) A 1 over (S View(v 1 ) , S V O )-trees such that h ∈ L(A 1 ) if and only if the run tree induced by h satisfies ϕ.

If L(A 1 ) is empty then we already know that there are no distributed implementations for the specification ϕ over A. Otherwise, thanks to Lemma 4.2, we have to check whether for each v ∈ V O there exists an (S View(v) , S v )-tree h v which is d-compatible and such that the global strategy v∈V O h v induced by the collection (h v ) v∈V O is accepted by A 1 . Formally, the sum of strategies is defined as follows

. Let X = X 1 ∪ X 2 ⊆ V I and Y = Y 1 ⊎ Y 2 ⊆ V O , and for i = 1, 2 let h i be an (S X i , S Y i )-tree. We define the (S X , S Y )-tree h = h 1 ⊕ h 2 by h(σ) = (h 1 (σ X 1 ), h 2 (σ X 2 )) for σ ∈ (S X ) * .
To check the existence of such trees (h v ) v∈V O , we will inductively eliminate the output variables following the order v 1 , . . . , v n . It is important that we start with the variable that views the largest set of input variables, even though, due to the delays, it might get the information much later than the remaining variables. Let V k = {v k , . . . , v n } for k ≥ 1. The induction step relies on the following statement.

Proposition 4.5. Let 1 ≤ k < n. Given a NDTA A k accepting (S View(v k ) , S V k )-trees, one can build a NDTA A k+1 accepting (S View(v k+1
) , S V k+1 )-trees, such that a tree t is accepted by A k+1 if and only if there exists an

(S View(v k ) , S v k )-tree h v k which is d-compatible and such that h v k ⊕ t is accepted by A k .
The proof of Proposition 4.5 is split in two steps. Since V k = {v k } ⊎ V k+1 , we have t = t v k ⊕ t V k+1 for each (S View(v k ) , S V k )-tree t (recall that t U is the projection of t on U ). So one can first transform the automaton A k into A ′ k that accepts the trees t ∈ L(A k ) such that t v k is d-compatible (Lemma 4.6). Then, one can build an automaton that restricts the domain of the directions and the labeling of the accepted trees to S View(v k+1 ) and S V k+1 respectively. Lemma 4.6. Let v ∈ U ⊆ V O . Given a NDTA A over (S View(v) , S U )-trees one can build a NDTA A ′ = compat v (A) also over (S View(v)

, S U )-trees such that L(A ′ ) = {t ∈ L(A) | t v is d-compatible}.
Proof. Intuitively, to make sure that the function t v is d-compatible, the automaton A ′ will guess in advance the values of t v and then check that its guess is correct. The guess has to be made K = max{d(u, v), u ∈ View(v)} steps in advance and consists in a d-compatible function g : (S View(v) ) K → S v that predicts what will be K steps later the values of variable v. During a transition, the guess is sent in each direction r ∈ S View(v) as a function r -1 g defined by (r -1 g)(σ) = g(rσ) which is stored in the state of the automaton. Previous guesses are refined similarly and are also stored in the state of the automaton so that the new set of states is

Q ′ = Q × F where F is the set of d-compatible functions f : (S View(v) ) <K → S v
, where Z <K = i<K Z i . The value f (ε) is the guess that was made K steps earlier and has to be checked against the current value of v in the tree.

To formalize this, we define the (transition) function ∆ :

F × S View(v) → 2 F by ∆(f, r) = {f ′ | f ′ (σ) = f (rσ) for |σ| < K -1} .
Intuitively, if we are in state (q, f ) ∈ Q × F at some node τ and move in direction r ∈ S View(v) then ∆(f, r) computes the set of functions in F that could label the node τ • r. Observe that f ′ is determined by f and r for any σ such that |σ| < K -1 and corresponds to the specialization narrowing construction of [START_REF] Kupferman | Church's problem revisited[END_REF] yields an alternating tree automaton. Here we assume that the narrowing operation returns a NDTA using a classical transformation of alternating tree automata into NDTA [START_REF] Muller | Simulating alternating tree automata by nondeterministic automata: New results and new proofs of theorems of Rabin, McNaughton and Safra[END_REF]. The drawback is that this involves an exponential blow up. Unfortunately, this is needed since Lemma 4.6 requires a NDTA as input.

We can now conclude the proof of Theorem 4.3. Using Proposition 4.5 inductively starting from the NDTA A 1 of Proposition 4.4, we obtain a NDTA A n accepting an (S View(vn) , S vn )tree h vn if and only if for each 1 ≤ i < n, there exists an (S View(v i ) , S v i )-tree h v i which is d-compatible and such that h v 1 ⊕ • • • ⊕ h vn is accepted by A 1 . Therefore, using Lemma 4.2, there is a distributed implementation for the specification over A if and only if L(compat vn (A n )) is nonempty. The overall procedure is non-elementary due to the exponential blow-up of the inductive step in Proposition 4.5. We do not know for now the lower bound of the complexity of this problem.

Decidability for UWC architectures and robust specifications.

We now show that we can obtain decidability of the synthesis problem for the whole subclass of UWC architectures by restricting ourselves to specifications that only relate output variables to their own view.

Definition 4.7. A specification ϕ ∈ L with L ∈ {LTL, CTL, CTL * } is robust if it is a (finite) disjunction of formulas of the form v∈V O ϕ v where ϕ v ∈ L(View(v) ∪ {v}).
Note that a robust formula is always external. Proposition 4.8. The synthesis problem for robust CTL * specifications is decidable over UWC architectures.

Proof. Let A = (V ⊎ P, E, (S u ) u∈V , s 0 , (d p ) p∈P ) be a UWC architecture and ϕ be a robust CTL * specification. Without loss of generality, we may assume that ϕ = v∈V O ϕ v where ϕ v ∈ CTL * (View(v)∪{v}). Using Proposition 4.4, for each v ∈ V O we find a NDTA A v accepting a strategy h : (S View(v) ) * → S v if and only if the induced run tree t : (S View(v) ) * → S View(v)∪{v} satisfies ϕ v . The proposition then follows from the Claim 4.9. There exists a distributed implementation of ϕ over A if and only if for each v ∈ V O , the automaton compat v (A v ) is nonempty.

First, let F be a distributed implementation of ϕ over A and let t : (S V I ) * → S V be the induced run-tree. Fix some v ∈ V O . The map f v : (S View(v) ) * → S v is d-compatible. Let t ′ : (S View(v) ) * → S View(v)∪{v} be the run-tree induced by f v . For each σ ∈ (S V I ) * we have t(σ) View(v)∪{v} = t ′ (σ View(v) ). Since F implements ϕ, we have t |= ϕ and then t |= ϕ v . We can prove by structural induction on the formula that for any ψ ∈ CTL * (View(v) ∪ {v}), any branch σ ∈ (S V I ) ω and any position i we have t, σ, i |= ψ if and only if t ′ , σ View(v)

, i |= ψ. Since ϕ v ∈ CTL * (View(v) ∪ {v}), we deduce that t ′ |= ϕ v . Therefore, f v is accepted by A v and also by compat v (A v ). Conversely, for each v ∈ V O , let h v : (S View(v) ) * → S v be a strategy accepted by the automa- ton compat v (A v ). By Lemma 4.6, h v is d-compatible. Let t v : (S View(v) ) * → S View(v)
∪{v} be the run-tree induced by h v . We have t v |= ϕ v by definition of A v and Proposition 4.4. Now, using Lemma 4.2 we find a distributed program

F = (f v ) v∈V \V I such that f v = h v for each v ∈ V O . Let t : (S V I ) * → V V I ∪V O be the run-tree induced by F . For each σ ∈ (S V I ) * we have t(σ) View(v)∪{v} = t v (σ View(v)
) and we obtain as above that t |= ϕ v . Therefore, t |= ϕ and F implements ϕ on A.

Well-connected architectures

It is natural to ask whether the decision criterion for UWC architectures can be extended to a larger class. In this section, we relax the property of uniform well-connectedness and show that, in that case, linearly preordered information is not anymore a sufficient condition for decidability. Definition 5.1. An architecture is said to be well-connected, if for each output variable v ∈ V O , the sub-architecture consisting of (E -1 ) * (v) is uniformly well-connected.

Intuitively this means that for each output variable v there is a routing making it possible to transmit the values of the input variables in View(v) to the process that writes on v, but such a routing may vary from one output variable to another, in contrast with the case of UWC architectures, where a single routing is used for all output variables. For instance, the architecture of Figure 2 is well-connected. Indeed, to transmit the values of u and v to z ij , it is enough to write u on z i and v on z j . Note that this does not give a uniform routing. Actually, the architecture of Figure 2 is not UWC assuming that variables values range over {0, 1} (as shown by Proposition 5.3 below). Hence, the subclass of UWC architectures is strictly contained in the subclass of well-connected architectures.

In the proof of Proposition 5.3, we use the following lemma, established in [START_REF] Lehman | Complexity classification of network information flow problems[END_REF] for solving the network information flow problem introduced in [START_REF] Ahlswede | Network information flow[END_REF].

We say that two functions f and g from S 2 to S are independent if (f, g) : S 2 → S 2 is invertible. This lemma asserts that over a small alphabet, one cannot build a large set of pairwise independent functions. In our setting, it implies the following result: Proposition 5.3. Assuming that all variables are Boolean, the architecture of Figure 2 is wellconnected but not uniformly well-connected.

Proof. It is easy to see that the architecture A of Figure 2 is well-connected. However, it is not uniformly well-connected. Indeed, suppose it is. Then there exist a routing Φ = (f z 1 , f z 2 , f z 3 , f z 4 ) consisting of four memoryless strategies, and for all v ∈ V O , a decoding function g v : {0, 1} 2 → {0, 1} 2 . Therefore, uniform well-connectedness of implies that every pair (f z i , f z j ) is invertible, using g z ij as inverse. This is in contradiction with Lemma 5.2, which implies that for Boolean variables, there are at most three pairwise independent functions. Hence the architecture is not uniformly well-connected.

Interestingly enough, the size of the alphabet has an influence on the possibility to have a uniform routing and Lemma 5.2 helps to understand why. In our setting, this means that by enlarging the domains of internal variables, we may obtain uniform well-connectedness from a well-connected architecture.

The following theorem asserts that, unfortunately, the decision criterion cannot be extended to well-connected architectures.

Theorem 5.4. The synthesis problem for LTL specifications and well-connected architectures with linearly preordered information is undecidable.

Let A be the architecture of Figure 6, in which all the delays are set to 0, and which is clearly well-connected and linearly preordered. To show its undecidability, fix a deterministic Turing machine M with tape alphabet Γ and state set Q. We reduce the non halting problem of M starting from the empty tape to the distributed implementability of an LTL specification over A. Let S z = {0, 1} for z ∈ V \ {x, y} and S x = S y = Γ ⊎ Q ⊎ {#} where # is a new symbol. As usual, the configuration of M defined by state q and tape content γ 1 γ 2 , where the head scans the first symbol of γ 2 , is encoded by the word γ 1 qγ 2 ∈ Γ * QΓ + (we require that γ 2 = ε for technical reasons, including in it some blank symbols if necessary). An input word u ∈ 0 * 1 p 0{0, 1} ω encodes the integer n(u) = p and similarly for v. We construct an LTL specification ϕ M forcing any distributed implementation to output on variable x the n(u)-th configuration of M starting from the empty tape. Processes p 0 and p 6 play the role of the two processes of the undecidable architecture of Pnueli and Rosner (A ′ in Figure 3). The difficulty is to ensure that process p 6 cannot receive relevant information about u. The specification ϕ M = α ∧ β ∧ γ M ∧ δ ∧ ψ M is a conjunction of five properties described below that can all be expressed in LTL(V I ∪ V O ).

(1) The processes p i for 1 ≤ i ≤ 5 have to output the current values of (u, w) on (u i , w i ) until (including) the first 1 occurs on w. Afterwards, they are unconstrained. Process p 6 must always output the value of w on w 6 . Moreover, after the first 1 on w, it also has to output the current value of u on u 6 . Formally, this is defined by the LTL formula α:

α def = G(w 6 = w) ∧ (w = 0) ∧ α ′ W (w = 1) ∧ α ′ ∧ X G(u 6 = u) , where α ′ def = 1≤k≤5 (u k = u) ∧ (w k = w)
(2) If the input word on u (resp. v) is in 0 q 1 p 0{0, 1} ω , then the corresponding output word x (resp. y) is in # q+p Γ * QΓ + # ω . This is expressed by β = β u,x ∧ β v,y , where

β z,t def = ((z = 0) ∧ (t = #)) W (z = 1) ∧ ((z = 1) ∧ (t = #)) W ((z = 0) ∧ (t ∈ Γ * QΓ + # ω ))
where

(t ∈ Γ * QΓ + # ω ) def = (t ∈ Γ) U ((t ∈ Q) ∧ X(t ∈ Γ) U ((t ∈ Γ) ∧ X G(t = #)))
(3) We next express with a formula γ M that if n(u) = 1 then x has to output the first configuration C 1 of M starting from the empty tape. That is, if the input is in 0 q 10{0, 1} ω , then the corresponding output is # q+1 C 1 # ω . The LTL formula is

γ M def = (u = 0) W ((u = 1) ∧ X((u = 0) → (x ∈ C 1 # ω )))
where (x ∈ C 1 # ω ) can be expressed easily. (4) We say that the input words are synchronized either if u, v ∈ 0 q 1 p 0{0, 1} ω or else if u ∈ 0 q 1 p+1 0{0, 1} ω and v ∈ 0 q+1 1 p 0{0, 1} ω . We use a formula δ to express the fact that if u and v are synchronized and n(u) = n(v), then the outputs on x and y are equal. We first define the LTL formula

(n(u) = n(v)) def = (u = v = 0) U ((u = v = 1) ∧ (u = v = 1) U (u = v = 0))
to express the fact that the input words u and v are synchronized and n(u) = n(v).

Then the formula δ is defined by:

δ def = (n(u) = n(v)) → G(x = y)
(5) Finally, one can express with an LTL formula ψ M that if the input words are synchronized and n(u) = n(v) + 1 then the configuration encoded on x is obtained by a computation step of M from the configuration encoded on y. We use the LTL formula (n(u) = n(v) + 1) defined by

(u = v = 0) U (u = 1) ∧ (v = 0) ∧ X((u = v = 1) ∧ (u = v = 1) U (u = v = 0))
to express the fact that u and v are synchronized and n(u) = n(v) + 1. The formula ψ M is defined by

ψ M = (n(u) = n(v) + 1) → (x = y) U Trans(y, x) ∧ X 3 G(x = y)
where Trans(y, x) expresses the fact that the factor of length 3 of x is obtained from the one of y by a transition of the Turing machine M . We have Trans(y, x) = (p,a,q,b,←)∈T,c∈Γ

(y = cpa) ∧ (x = qcb) ∨ (p,a,q,b,→)∈T,c∈Γ (y = pac) ∧ (x = bqc) ∨ (p,a,q,b,→)∈T (y = pa#) ∧ (x = bq )
Here (x = abc) is an abbreviation for (x = a) ∧ X(x = b) ∧ X 2 (x = c). Furthermore, is the blank symbol of the tape and T is the set of transitions of M (the transition (p, a, q, b, dir ), taken when M is in state p and scans symbol a, switches the state to q, writes symbol b and moves the head according to the direction dir ∈ {←, →}). We first show that there exists a distributed implementation of ϕ M over A. Let ⊕ be the addition modulo 2 (xor). Process p 0 forwards u to z 0 . Process q forwards u to z 1 , u ⊕ w to z 2 and w to z 3 . The strategy for z 4 is not memoryless. Process q forwards w to z 4 until (including) the first 1 on w and then it forwards u ⊕ w to z 4 . Formally, f z 4 (u, 0 q b) = b and f z 4 (ua, 0 q 1wb) = a ⊕ b. We also use memoryless strategies for the processes p i so that α is satisfied. For instance, the strategy for p ). It is easy to see that with these strategies, the first property α of the specification is satisfied. Note that, until the first 1 on w, p 6 outputs 0 on u 6 , and after this first 1, p 5 cannot decode u and w anymore.

The strategy f x (respectively f y ) is to output the p-th configuration of M starting from the empty tape when u (respectively v) encodes p. Then, the rest of the specification, β∧γ M ∧δ∧ψ M , is satisfied. Remark 5.5. Actually, one can define another distributed implementation by changing only the strategy f z 4 : at each step, process q transmits to p 6 the value of u at the preceding step as the mod 2 difference between z 3 and z 4 , until the first 1 occurs on w. Formally,

f z 4 (a, b) = b, f z 4 (u • a 1 • a 2 , 0 q b) = a 1 ⊕ b and f z 4 (ua, 0 q 1wb) = a ⊕ b.
We also adapt the strategies of p 1 , . . . , p 6 so that α is satisfied. Note that these strategies are no longer memoryless, they have to remember the last bit of u. By xoring its two arguments, process p 6 can then recover the whole history of u, except the bit occurring simultaneously with the first 1 of w. Hence, we are almost in the situation of the decidable architecture of Figure 1, but surprisingly, missing only one bit of information suffices to yield undecidability.

Let now F = (f v ) v∈V \V I be a distributed implementation of ϕ M on the architecture A of Figure 6. We prove that f x must simulate the computation of M starting from the empty tape.

Step 1: relating the strategies for z 3 and z 4 . Lemma 5.6. Let g 1 , g 2 , g 3 : {0, 1} 2 → {0, 1} be pairwise independent functions. Then, there exists ε ∈ {0, 1} such that for all a, b ∈ {0, 1}:

g 3 (a, b) = ε ⊕ g 1 (a, b) ⊕ g 2 (a, b)
Proof. We first note that each function g k is two to one, i.e., |g -1 k (c)| = 2 for c ∈ {0, 1}. Indeed, if this is not the case then we have for instance |g -1 k (0)| ≥ 3 and the map (g k , g ℓ ) for ℓ = k cannot be injective.

For the same reason, if

g k (a, b) = g k (a ′ , b ′ ), then g ℓ (a, b) = g ℓ (a ′ , b ′ ).
Therefore, permuting indices if necessary, we may assume that g 1 (0, 0) = g 1 (0, 1), g 2 (0, 0) = g 2 (1, 0) and g 3 (0, 0) = g 3 (1, 1), so that each g k is completely determined by its value on (0, 0). A simple computation then shows that g 1 ⊕ g 2 ⊕ g 3 is constant. For instance, we have (g 1 ⊕ g 2 ⊕ g 3 )(1, 0) = (¬g 1 ⊕ g 2 ⊕ ¬g 3 )(0, 0) = (g 1 ⊕ g 2 ⊕ g 3 )(0, 0). Applying Lemma 5.6 both to ( f z 1 , f z 2 , f z 3 ) and ( f z 1 , f z 2 , f z 4 ) after an input (0 q , 0 q ) on (u, w), we get: Corollary 5.7. For all q ≥ 0, there exists ε ∈ {0, 1} such that

∀a, b ∈ {0, 1}, f z 3 (0 q a, 0 q b) = ε ⊕ f z 4 (0 q a, 0 q b).
Proof. Fix q ≥ 0. Let g i : {0, 1} 2 → {0, 1} be defined by g i (a, b) = f z i (0 q a, 0 q b). The conjunct α of the specification ϕ M imposes to p 1 , p 2 and p 4 to output the current value of (u, w), hence they must distinguish the four possible values of (u, w). Therefore, g 1 , g 2 and g 3 are pairwise independent. Applying Lemma 5.6, we obtain

ε 3 ∈ {0, 1} such that g 3 (a, b) = ε 3 ⊕ g 1 (a, b) ⊕ g 2 (a, b) for all (a, b) ∈ {0, 1} 2 .
Similarly, considering outputs of processes p 1 , p 3 , p 5 , we deduce that g 1 , g 2 and g 4 are also pairwise independent and that g

4 (a, b) = ε 4 ⊕ g 1 (a, b) ⊕ g 2 (a, b).
Therefore, for all (a, b) ∈ {0, 1} 2 , we have g 3 (a, b) ⊕ g 4 (a, b) = ε 3 ⊕ ε 4 = ε and we obtain f z 3 (0 q a, 0 q b) = ε ⊕ f z 4 (0 q a, 0 q b) as desired.

Step 2: masking one bit of u to p 6 .

Let q ≥ 0. For u = 0 q 1u ′ , we define u 0 = 0 q 0u ′ . Observe that if u ∈ 0 q 1 p+1 0{0, 1} ω encodes p + 1 > 1 then u 0 ∈ 0 q+1 1 p 0{0, 1} ω encodes p. The next lemma states that strategies f z 3 (resp. f z 4 ) must output the same sequence for u and u 0 if the input word w is suitable, so that p 6 cannot distinguish between encodings of p and p + 1 on input variable u. Lemma 5.8. Let u, w ∈ 0 q 1{0, 1} ω . For k ∈ {3, 4}, we have for all n > 0: Proof. By induction on n. If n ≤ q, then u 0 [n] = u[n] so (3) trivially holds. Next, assume n = q + 1, so u 0 [n] = 0 q 0 and u[n] = 0 q 1 = w[n]. Assume f z 3 (0 q 0, 0 q 0) = f z 3 (0 q 0, 0 q 1) then we have f z 4 (0 q 0, 0 q 0) = f z 4 (0 q 0, 0 q 1) by Corollary 5.7. Fixing some v ∈ {0, 1} n , we deduce that process p 6 has observed exactly the same history on the input triples (0 q 0, 0 q 0, v) and (0 q 0, 0 q 1, v), therefore it would write at step n the same value on w 6 , a contradiction with requirement α. Therefore, f z 3 (0 q 0, 0 q 0) = f z 3 (0 q 0, 0 q 1). Similarly, f z 3 (0 q 0, 0 q 0) = f z 3 (0 q 1, 0 q 1). Since the map f z 3 may only take two values, we get f z 3 (0 q 0, 0 q 1) = f z 3 (0 q 1, 0 q 1).

Applying again Corollary 5.7, we deduce that f z 4 (0 q 0, 0 q 1) = f z 4 (0 q 1, 0 q 1) and ( 3) is proved for n = q + 1.

Finally, assume that n > q + 1. By induction hypothesis, for k ∈ {3, 4} and all i < n, we have f z k (u 0 [i], w[i]) = f z k (u[i], w[i]). Therefore, the history z 3 [n -1] and z 4 [n -1] is the same on the inputs (u, w) and (u 0 , w). Fixing some v ∈ {0, 1} n , we deduce that process p 6 has observed exactly the same history on the input triples (u 0 We deduce from the requirement α that h is an inverse of h 1 and also an inverse of h 0 . Therefore, h 0 = h 1 and we obtain f z k (u 0 [n], w[n]) = f z k (u[n], w[n]) for k ∈ {3, 4}, as required.

Step 3: enforcing output of the n(u)-th configuration of M on x.

Lemma 5.9. If x is computed by f x from the input word u then for all p > 0 we have (4) ∀q ≥ 0, u ∈ 0 q 1 p 0{0, 1} ω =⇒ x = # p+q C p # ω where C p is the p-th configuration reached by M starting from the empty tape.

Proof. The proof is by induction on p. The case p = 1 follows from the specification γ M . Let now p > 1 and assume that u ∈ 0 q 1 p+1 0{0, 1} ω . Let v = 0 q+1 1 p 0 ω and w = 0 q 1 ω . By induction, for u 0 ∈ 0 q+1 1 p 0{0, 1} ω the output is x = # q+1+p C p # ω . Using δ, we deduce that on the input triple (u 0 , w, v) the output is y = x = # q+1+p C p # ω . Now, by Lemma 5.8, on the input pairs (u 0 , w) and (u, w), the outputs on z 3 and z 4 are the same. Hence, on the input triples (u 0 , w, v) and (u, w, v) the outputs on y must be y = # q+1+p C p # ω by the above. Using ψ M , we deduce that on the input triple (u, w, v) the output on x must be x = # q+1+p C p+1 # ω . This concludes the proof since x only depends on u.

By masking one bit of u to p 6 , we cause uncertainty with respect to the value of n(u), preventing this process to "cheat". In turn, process p 0 , which has no information about the other input values, only knows that p 6 is not always able to cheat, and has then to always output the correct Turing machine configuration. of Theorem 5.4. Starting from a Turing machine M , we have shown that any distributed implementation of the specification ϕ M is forced to output on x the n(u)-th configuration of M . Therefore, there is a distributed implementation on this architecture for the formula ϕ M ∧ G(x = halt) if and only if M does not halt starting from the empty tape. We have thus reduced the non halting problem of a Turing machine on the empty tape to the LTL distributed synthesis problem over a well-connected architecture with linearly preordered information, proving that this latter problem is undecidable (more precisely not co-RE).

Conclusion

In this paper, we have shown that every decidable architecture must have linearly preordered information, and that this condition is sufficient for deciding external specifications on UWC architectures. On the other hand, we have exhibited a well-connected architecture with linearly preordered information, yet undecidable for external LTL specifications, by simulating the loss of a single information bit on the UWC architecture of Figure 1.

Finally, we have shown that all UWC architectures are decidable for robust specifications, i.e., specifications constraining external variables which are causally related by a communication path. A challenging problem is to find whether this still holds for well-connected architectures.

Figure 2 .

 2 Figure 2. An architecture with input variables u, w and output variables z ij .

Figure 3 .

 3 Figure 3. Architectures A and A ′

Figure 4 .

 4 Figure 4. Simulation of f ′xn by f xn .

Lemma 5 . 2 (

 52 [START_REF] Lehman | Complexity classification of network information flow problems[END_REF] Lemma 3.1]). If f 1 , . . . , f n are pairwise independent functions from S 2 to S then n ≤ |S| + 1.

6 u 1 w 1 u 2 w 2 u 3 w 3 u 4 w 4 u 5 w 5 u 6 w 6 yFigure 6 .

 666 Figure 6. Undecidable, well-connected and linearly preordered architecture

1

 1 is f 1 (b 1 , b 2 ) = (b 1 , b 1 ⊕ b 2 ) and the strategy for p 6 (y excluded) is f 6 (b 3 , b 4 ) = (b 3 ⊕ b 4 , b 3

( 3 )

 3 f z k (u 0 [n], w[n]) = f z k (u[n], w[n]).

  [n -1], w[n -1], v[n -1]) and (u[n -1], w[n -1], v[n -1]).Consider now the 3 mappings from {0, 1} 2 to {0, 1} 2 defined byh(c, d) = (f u 6 , f w 6 )(z 3 [n -1]c, z 4 [n -1]d, v) h 1 (a, b) = ( f z 3 , f z 4 )(u[n -1]a, w[n -1]b) h 0 (a, b) = ( f z 3 , f z 4 )(u 0 [n -1]a, w[n -1]b)

Acknowledgements. We thank the anonymous referees for their remarks which helped us to improve the presentation of the paper.

of f according to the new direction r. The functions f ′ ∈ ∆(f, r) differ only on values f ′ (σ) for |σ| = K -1 which correspond to the new guesses. Now, the transition function of A ′ is defined for (q, f ) ∈ Q ′ and s ∈ S U only if s v = f (ε) (this ensures that the guess made K steps earlier was correct) and sends in each direction r ∈ S V iew (v) of the tree a copy of the automaton in the state (q r , g r ) where q r corresponds to the simulation of a run of A and g r ∈ ∆(f, r). Formally, if

Finally, the set of initial states of A ′ is I ′ = {q 0 } × F and α ′ = π -1 (α) where π : (Q × F) ω → Q ω is the projection on Q, i.e., a run of A ′ is successful if and only if its projection on Q is a successful run of A.

Let t be an (S View(v) , S U )-tree accepted by A and suppose that t v is d-compatible. Let ρ : (S View(v) ) * → Q be an accepting run of A over t. There is a unique way to extend ρ to a run ρ ′ : (S

) <K so that all guesses are correct. Since t v is d-compatible, we deduce that f τ is also d-compatible, hence it belongs to F. Then we can define the run ρ ′ by ρ ′ (τ ) = ρ(τ ), f τ for τ ∈ (S View(v) ) * . We show that it is an accepting run of A ′ over t. First, we prove that at each node τ ∈ (S View(v) ) * the transition function δ ′ is satisfied. Let (q, f τ ) = ρ ′ (τ ) and (q r , f τ r ) = ρ ′ (τ r) for all r ∈ S View(v) . By definition, f τ (ε) = t v (τ ) and δ ′ ((q r , f τ r ), t(τ )) is defined. Now, since π(ρ ′ ) = ρ which is a run of A over t we have (q r ) r∈S View(v) ∈ δ(q, t(τ )). It remains to show that f τ r ∈ ∆(f τ , r) for all r ∈ S View(v) . This is obvious from the definitions:

Conversely, suppose there is a successful run ρ ′ of A ′ over t. We need to show that t v is dcompatible and that t ∈ L(A). Let ρ ′ : S View(v) * → Q × F be such a run. We have ρ ′ = (ρ, H) with ρ : S View(v) * → Q and H : (S View(v) ) * → F. By definition of δ ′ , we immediately get that ρ is a run of A, which is successful since ρ ′ is successful.

It remains to prove that t v is d-compatible. Since ρ ′ is a run and the transition function δ ′ is only defined on ((q, f ), s) when s v = f (ε), we deduce that t v (τ ) = H(τ )(ε) for all τ ∈ (S View(v) ) * . Hence, we need to show that the map τ → H(τ

We can show, by successive applications of the transition function δ ′ and by definition of ∆, that the value of H(τ 1 τ 2 )(ε) is indeed the guess made at node τ 1 for the direction defined by τ 2 , i.e., H(τ

of Proposition 4.5. We consider the NDTA compat v k (A k ). It remains to project away the S v k component of the label and to make sure that the S V k+1 component of the label only depends on the S View(v k+1 ) component of the input. The first part is the classical projection on S V k+1 of the automaton and the second part is the narrowing construction introduced in [START_REF] Kupferman | Church's problem revisited[END_REF]. The automaton A k+1 fulfilling the requirements of Proposition 4.5 is therefore given by narrow View(v k+1 ) (proj V k+1 (compat v k (A k ))). Note that, even when applied to a NDTA, the