Daniel Kästner

Jan Pohland

Program Analysis on Evolving Software

Static analysis is well-suited for continuous verification during the software development stage since it only works on the source code and does not require a running system for testing. However, applying the program analysis during software development means that the analysis has to cope with evolving software and evolving analyzer configurations, especially in a model-based development process. In this article we present a unique history-aware concept for program analysis that has been developed for the static analyzer Astrée. It not only provides the ability to backtrack and access previous versions of the analysis configuration, it can also automatically determine the differences between two analysis configurations and relate them to the correct source code versions. Users can explicitly create a revision, i.e. a snapshot of the analysis project; changes of the source code, analysis options, analysis directives and results in different revisions are automatically detected and highlighted. The analyzer provides automatic correctness checks for all specified analysis directives, e.g., to tune the precision of the analyzer or provide information about the environment. This makes software verification applicable during the implementation stage, significantly reduces the effort to adapt the analyzer configuration to new source code versions, and makes analysis results on previous software versions easily reproducible.

I. INTRODUCTION

Traditionally software verification is done in a separate stage at the end of the development process. As a rule of thumb the later a bug is discovered, the greater are the costs to fix them. Therefore software verification should already be started during the implementation stage. Especially static analysis is well-suited for continuous application since it only works on the source code and does not require a running system for testing. As an example, run-time error analysis can be done at the level of software components while developing the software. However, applying the program analysis during software development means that the analysis has to cope with evolving software, especially in a model-based development process.

The static analyzer Astrée detects all potential run-time errors in C programs. If no alarms are reported the absence of run-time errors is proven. However, getting down to zero alarms typically requires some interaction with the analyzer: environment information and side conditions have to be specified and the precision of the analyzer has to be tuned to the software under analysis. In Astrée such interactions are expressed via formal directives which are inserted at specific program points. To support model-based development the directives can also be specified externally, without modifying the source code: they are localized by defining a path to the program point where the directive is to be inserted. So not only the source code, but also the program analysis evolves: starting from an initial analysis, the analysis configuration and options are fine-tuned, and missing information and precision adaptations are added step by step.

Therefore similar to software development the ability to backtrack and access previous versions of the analysis configuration are important development features. Being able to investigate the differences between two analysis configurations and relate them to the correct source code versions is very desirable. Furthermore users should be warned about analysis directives which have become invalid because of source code changes.

All these issues have been addressed by developing a unique history-aware concept for program analysis in Astrée. Users can explicitly create a revision, i.e. a snapshot of the analysis project; changes of the source code, analysis options, analysis directives and results in different revisions are automatically detected and highlighted. The analyzer provides automatic correctness checks for all externally specified analysis directives. This makes software verification applicable during the implementation stage, significantly reduces the effort to adapt the analyzer configuration to new source code versions, and makes analysis results on previous software versions easily reproducible.

II. THE STATIC ANALYZER ASTR ÉE

The static analyzer Astrée aims at finding all potential runtime in C programs [START_REF] Kästner | Astrée: Proving the Absence of Runtime Errors[END_REF]. Basically run-time errors are errors that occur during run-time of the software. Astrée focuses on run-time errors which correspond to undefined or unspecified behavior with respect to the semantics of the programming language C99 [6]. Examples are arithmetic exceptions (e.g. divide by zero), overflows, invalid pointer accesses and manipulations, or array bound errors [START_REF]MISRA-C:2004 -Guidelines for the use of the C language in critical systems[END_REF]. The C standard provides a list of unspecified and undefined behaviors in Section J of [6].

Astrée is sound which means that the analysis never omits to signal an error that can appear in some execution environment. If no potential error is signaled, definitely no run-time error can occur: the absence of run-time errors has been proven. This is possible since Astrée is based on the theory of abstract interpretation [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF], a mathematically rigorous formalism providing a semantics-based methodology for static program analysis. It provides rules for defining an abstract semantics that approximates the concrete semantics of the program and is efficiently computable. The correctness of the abstraction, i.e., the soundness of the analyzer can be formally proven; all necessary correctness proofs for Astrée have been done and published, e.g., [START_REF] Miné | Relational Abstract Domains for the Detection of Floating-Point Run-Time Errors[END_REF], [START_REF] Mauborgne | Trace Partitioning in Abstract Interpretation Based Static Analyzers[END_REF]. Abstract Interpretation, like model checking and theorem proving, is recognized as a formal verification method and recommended by the DO-178C and other safety standards (cf. Formal Methods Supplement [START_REF]Formal Methods[END_REF] to DO-178C [START_REF]Airborne Systems and Equipment Certification[END_REF]).

While the primary goal of Astrée is to prove the absence of run-time errors, the analysis can also be leveraged to compute further program properties relevant for functional safety. Astrée detects read accesses to uninitialized variables, detects shared variables accessed by asynchronous threads, computes detailed control and data flow reports, and enables users to prove userdefined static assertions. The static assertions can be applied to arbitrary C expressions so that functional program properties can be addressed. When Astrée does not report an assertion failure alarm, the correctness of the asserted expression has been formally proven. Astrée is sound for floating-point computations and handles them precisely and safely [START_REF] Blanchet | A Static Analyzer for Large Safety-Critical Software[END_REF]. It takes all possible rounding errors into account which makes it possible to prove the stability of numeric algorithms (e.g., digital filters) with floating-point arithmetic [START_REF] Dierkes | Transferring Stability Proof Obligations from Model Level to Code Level[END_REF].

Astrée finds all potential run-time errors, but it may err on the other side and produce false alarms. The design of the analyzer aims at reaching the zero false alarm objective [START_REF] Blanchet | A Static Analyzer for Large Safety-Critical Software[END_REF], which was accomplished for the first time on large industrial applications at the end of November 2003 [START_REF] Delmas | ASTR ÉE: from Research to Industry[END_REF]. Only with zero alarms the absence of run-time errors is automatically proven. For keeping the initial number of false alarms low, a high analysis precision is mandatory, which is achieved by computing a variety of predefined abstract domains. Any remaining alarm has to be manually checked by the developers -and this manual effort should be as low as possible. Astrée provides intuitive and powerful mechanisms to to investigate the reasons for alarms. As an example, alarm contexts can be interactively explored: all parents in the call stack, relevant loop iterations or conditional statements can be visited per mouse click, and the computed value ranges of variables can be displayed for all abstract domains in all potential context. If there is a true error it has to be fixed. A false alarm can often be eliminated by a suitable parameterization of Astrée. If the error cannot occur due to certain preconditions which are not known to Astrée, they can be made available to Astrée via dedicated directives. These directives make the side conditions explicit which have to be satisfied for a correct program execution. If the false alarm is caused by insufficient analysis precision, steering directives are available that allow to locally tune the analysis precision to eliminate the false alarm [START_REF] Mauborgne | Trace Partitioning in Abstract Interpretation Based Static Analyzers[END_REF]. That means that in one analysis run important program parts can be analyzed very precisely while less relevant parts can be analyzed very quickly -without compromising system safety.

Figure 1: AAL annotations displayed in code view

All directives can either be written directly in the source code, or they can be specified in a formal language AAL [START_REF] Absint | The Static Analyzer Astrée-User Documentation for AAL Annotations[END_REF] and stored in a dedicated file without any source code changes. An AAL annotation consists of an Astrée directive and a path specifying the program point to insert the directive at. The path is specified in a robust way by exploiting the program's syntactical structure without relying on line number information. An example of the syntax of an AAL annotation is shown here: main { + 1 if {then: + 1 statement }} insert before: __ASTREE_assert(( x >= 0));

All AAL annotations are displayed in Astrée's source code editors as overlays at the specified code locations, as shown in the Astrée screen shot of Fig 1.

The AAL language is a prerequisite for supporting modelbased code generators. It makes it possible to separate the annotations from the source code, so that when the code is regenerated, all previously generated annotations from structurally unchanged code parts are still valid, even if the line numbers change.

III. EXPLOITING THE ANALYSIS HISTORY

In today's development infrastructures it is standard practice to manage source code with a revision control system. While it is theoretically possible to store report files of an analyzer run with each revision this is seldom done, and in order to reproduce analysis results for an older revision, the analysis typically has to be set up from scratch.

We have extended Astrée by an integrated revision system which works orthogonally to the standard revision control systems already in place. Its main purpose is to automatically compute and display differences between the setup and results of multiple analyzer runs on the same or different revisions of the same project. This approach makes it possible to reproduce analysis results on old revisions by mouse-click, to easily compare the analysis results of different source code versions, to compare the analyzer configuration of different revisions, etc.

This revision system is complemented by a mechanism to automatically check the correctness of Astrée directives specified in the AAL language. With AAL the locations can be specified in a robust way without relying on line numbers but if the code structure changes too much, they still may become invalid. The key idea to address this issue is to manage a reference file which keeps track of relevant source code properties for each AAL annotation. When a preconfigured analysis is re-run on an updated version of the source code, users will be notified about potentially invalid analysis directives. In the following sections both mechanism will be explained in more detail.

A. Analysis Revisions

Astrée has a client-server architecture. The client is used to set up the analysis and investigate the analysis results. The analysis itself is performed by the Astrée server which can run either on the same computer, or on a dedicated server machine. The Astrée server manages analysis projects in its data directory. Each analysis project has a unique analysis ID and all required information is stored under a folder named by this analysis ID. This information includes e.g., the original and preprocessed source files, the option setting, the log file of the analyzer, and a file containing all specified AAL annotations.

The creation of a new revision can be seen as a snapshot of the current state: the current state is saved, and copies are created for new revisions. The same base revision can be cloned to several child revisions, e.g., to apply different analyzer configurations and later investigate the differences in the corresponding analysis results. To create a new analysis revision for a new source code revision first a new analysis revision can be cloned from the current analysis state, and in the new analysis revision the source code files are updated from the normal source code repository. After running the analysis on the new files in the new revision the analysis results can be compared.

The Differences viewer enables users to efficiently compare several analysis revisions. It shows the total number of alarms and errors, the number of alarms per category, the option setting of the different analysis revisions, differences in the Astrée annotations specified by the user, the number of total statements and unreachable statements per file and the percentage of unreachable code per file. The Differences Viewer can also be applied to the XML report file of an analysis, so that also reports of unrevisioned analysis runs can be compared.

B. Automatically Validating User Annotations

AAL [START_REF] Absint | The Static Analyzer Astrée-User Documentation for AAL Annotations[END_REF] is a formal language that makes it possible to place an Astrée directive in the code without actually modifying the source code. This is a prerequisite for model-based development where the code is automatically regenerated after each model change. It is also important when the code has been frozen and can only be modified after a formal change process, or when the person doing the analysis is not entitled to modify the code. For robustness reasons, AAL is not based on line number information but on the structure of the program's abstract syntax tree. AAL annotations are stored in a dedicated file and the specified directives are inserted into the internal syntax tree of a function body generated in the parsing stage of Astrée.

Still, in the life cycle of a software project the source code will change and such changes may cause previously written Astrée annotations to become invalid. The specified position may not exist any more, the directive might end up in an unwanted location, or the directive may become semantically invalid. Our goal is to warn the user about such invalid annotations. AAL annotations consist of three parts [START_REF] Pohland | Program Analysis on Evolving Software[END_REF]: a path description, an ordering, and the Astrée directive to be located. For inserting directives into a function body, the syntactic elements that occur before the insertion place -the significant statements -must be specified which can simply be done by counting the corresponding statement types. For robustness and usability, the most specific statement types should be preferred, e.g. labeled statements, loops and if statements. This is the purpose of the path description which is composed of a set of distance expressions. In the following AAL annotation: main { +3 loops +1 if {then: +2 statements}} insert after: __ASTREE_assert((x > 0)); +1 if is a distance expression, main { +3 loops +1 if {then: +2 statements}} is the path description, after the ordering. It inserts an assertion after the second statement of the then branch of the first if statements after the third loop in the function.

When inserting a directive into the syntax tree the significant statements of the path in the syntax tree are stored in a dedicated history file, a reference file. In our example, the significant statements are three loops, one if statement and 2 unspecific statements. This information can be used to detect changes in the source code, that might lead to the directive being placed at a wrong position when restarting the analysis on the new source code version.

1) Invalid Path Description: In the easiest case of an invalid annotation the target point of the annotation's path description does not exist in the Astrée internal syntax tree. Then, the path description of the annotation does not match to the internal syntax tree and it is invalid. In this case, the annotation inserter reports an error during the attempt to insert the annotation at the specified program point.

2) Detecting Structurally Invalid Annotations: If the annotation inserter is able to insert an annotation inside a modified source code version, it cannot be guaranteed that the annotation's path description addresses the correct target point it was written for in the old version. If the annotation is inserted to a wrong target point, the annotation is structurally invalid.

It is possible to detect this kind of errors with the help of the reference file created in the last analyzer run before the source code modification. The history information from the reference file and a new temporary reference file are compared. Users can control for which analyzer runs the reference file should be created or updated.

We have developed two algorithms to exploit the history information to detect structurally invalid annotations, which will shortly be summarized in the following. They can be used to classify the annotations as possibly correct or possibly incorrect. In general, the correctness of annotations in a modified source code version cannot be guaranteed, since this would be equivalent to deciding whether two different programs have the same semantics, which is an undecidable problem [START_REF] Rice | Classes of recursively enumerable sets and their decision problems[END_REF].

• Annotation Path Comparison: In this approach the significant statements of the annotation path of each annotation are compared in the old and the new reference file. To be independent from formatting and line or column numbers, the comparison is done on the elements of the internal syntax tree of Astrée. Differences in statements not contained in the annotation path are irrelevant for the structural validity of an annotation.

• Statement Counting: Here the numbers of the available statements of the type counted by the distanceexpressions is counted. This way even differences caused by duplicated identical statements are detected.

IV. EXPERIMENTAL RESULTS

In this section we summarize our experiments to assess the usability of the history evaluation approaches. The experiments were performed on an Intel Core2Duo with 8GB RAM under openSUSE Linux 64-bit.

To evaluate the work flow using analysis revisions we investigated three real-life industry projects:

• Project A Avionics application consisting of 530 preprocessed source files using 24 MB disk space.

• Project B Automotive application consisting of 168 preprocessed source files using 37 MB disk space.

• Project C Automotive application consisting of more than 1200 preprocessed source files with a size of 622 MB and 16.8 million lines of code with up to 99,000 lines per file (generated from more than 3,000 original source and header files).

Tab. 2 shows the revision size, the time to create a new revision, and the time to delete a revision. To account for variations of the file system I/O load the reported times are are the maximum times observed in five analyzer runs. As we can see, creating new revisions takes a couple of seconds while project deletion is in the milliseconds range, even for large industry applications.

Project Revision Size

The execution time of the Difference Viewer is dominated by the time needed to compare the XML report files of the analysis revisions to be compared. The maximal comparison time observed in our experiments was about two minutes.

Regarding the performance of the algorithms for checking the validity of AAL annotations in all experiments we conducted the time needed to write a reference file, run the Annotation Path Comparison algorithm, and run the Statement Counting algorithm are below one second.

V. CONCLUSION

Applying program analysis during software development means that the analysis has to cope with evolving software and evolving analyzer configurations, especially in a modelbased development process. To facilitate this we have developed a unique history-aware concept for the static analyzer Astrée which consists of two parts: The first component is an integrated revision system which works orthogonally to the standard revision control systems already in place.

It not only provides the ability to backtrack and access previous versions of the analysis configuration, it can also automatically determine the differences between two analysis configurations and relate them to the correct source code versions. Users can explicitly create a revision, i.e. a snapshot of the analysis project; changes of the source code, analysis options, analysis directives and results in different revisions are automatically detected and highlighted. This revision system is complemented by a mechanism to automatically check the correctness of Astrée directives specified in the AAL language. A reference file is maintained which keeps track of relevant source code properties for each AAL annotation. When a pre-configured analysis is re-run on an updated version of the source code, users will be notified about potentially invalid analysis directives. Experimental results show that both approaches are applicable on large-scale industrial projects. This makes software verification applicable during the implementation stage, significantly reduces the effort to adapt the analyzer configuration to new source code versions, and makes analysis results on previous software versions easily reproducible.

ACKNOWLEDGEMENTS

The work presented in this paper has been supported by the German BMBF project FORTE.


Klaus Becker

Jelena Frtunikj

Meik Felser

Ludger Fiege

Christian Buckl

Stefan Rothbauer

Licong Zhang

Cornel Klein

RACE RTE: A Runtime Environment for Robust Fault-Tolerant Vehicle Functions

published or not. The documents may come

I. INTRODUCTION

The number of complex functions of high-end vehicles is steadily increasing. As a result, the complexity of the IT architecture implementing these functions has reached a level that is increasingly difficult to manage. Upcoming functions such as connected mobility and autonomous driving will further increase the functional complexity and safety requirements. Hence, it is necessary to rethink today's E/E architectures.

Within the RACE project (Robust and Reliant Automotive Computing Environment for Future eCars) such an E/E architecture was developed. The RACE platform provides generic configurable services covering functional safety requirements up to ASIL-D. The generic safety mechanisms simplify the development of complex vehicle functions and their integration on the platform. With scalable computing capacity that can be increased retroactively, the RACE system is equipped to meet the increasing demand for processing power to enable a long and attractive service life for vehicles. The integration of new application software or hardware may also happen after sale.

In this paper, we describe the core concepts of the RACE Runtime-Environment (RTE). The RTE provides inherent platform mechanisms for qualities such as safety. It therefore interconnects software applications, hardware sensors and vehicle actuators. App-developers for instance do not have to take care on handling probabilistic faults, since these are dealt within the platform, which takes appropriate counter measures. Instead, the developers have only to select the right level of safety both with respect to the required ASIL and availability (e.g. fail-operational). App-developers are supported in creating modular independent application components by the concept of data-centrism and a topic-based publish/subscribe description of interfaces. In this paper, we show the RTE mechanisms applied to a steer-by-wire example application, which we integrated into a RACE demonstrator car that we constructed [START_REF] Buechel | An automated electric vehicle prototype showing new trends in automotive architectures[END_REF]. In the long term, however, also more complex functions like highly automated driving may be deployed on top of the platform.

II. FOUNDATIONS OF THE RACE PLATFORM

A. RACE Platform Architecture

The RACE platform is a new system architecture for the information and communication infrastructure of future vehicles. It introduces a logically centralized platform computer that executes functions like control loops on vehicle level, fusion of different sensor values, situation detection and strategy planning of driver assistance functions. The Central Platform Computer (CPC) is connected to smart sensors and smart actuators (together called smart aggregates) with an Ethernetbased network. Smart aggregates run closed-loop controls of local physical processes (e.g. inverter of e-engines) and provide pre-processed raw sensor data. The CPC works on vehicle level and is responsible for vehicle-wide decisions and control algorithms that need or affect more than one aggregate.

The CPC consists of a scalable set of multiple so called Duplex-Control-Computers (DCCs) with each of them performing the calculations on two parallel computation paths (called lanes) to ensure high integrity. The software core for each of the DCC lanes is the middleware called RACE RTE. It handles the redundant data streams and checks their integrity.

B. Scheduling, Networking and Partitioning

The RACE system works in fixed time-triggered real-time execution cycles. In each cycle a DCC receives data from other components via the RACE Ethernet, executes the scheduled applications and sends data to other DCCs or aggregates. The RACE network employs a scalable ring-based full-duplex switched Ethernet architecture, where an inner ring connects the DCCs of the CPC (cf. Fig 1) and outer rings or branches connect aggregates to the CPC. Frame preemption is used to reduce network transport delay for time-critical frames by allowing them to preempt the transmission of non-time-critical frames. This mechanism is currently being standardized in IEEE802.1Qbu (Time-Sensitive Networking, TSN) 1 . Further details of the network communication are provided in [START_REF] Armbruster | Ethernet-Based and Function-Independent Vehicle Control-Platform: Motivation, Idea and Technical Concept Fulfilling Quantitative Safety-Requirements from ISO 26262[END_REF].

Spatial and temporal separation of mixed critical applications is ensured by running the RTE on top of the PikeOS 2 operating system and using partitioning mechanisms of PikeOS.

C. Integrity and Reliability

Depending on the use case and the system safety requirements, the system needs to provide different levels of integrity and reliability. In order to ensure data integrity, the RTE is able to execute applications on the two lanes of a DCC and check their results for bitwise equivalence. This bitwise comparison of lane results checks a DCC as fault-containment region to avoid any failure propagation in the platform. Reliability is guaranteed with fail-operational behavior in master-slave configurations, where a second DCC takes over in case of failures (hot or cold standby). Further DCCs can be employed to scale capacity or increase the mission time.

Aggregate redundancy (virtual layer)

Sensor redundancy (logical layer) Redundancy of the CPC is complemented by a variety of aggregate redundancies on different layers (Table I). We distinguish the physical, logical and virtual layer. The aggregate redundancy (virtual layer) defines how many instances of a physical aggregate exist. The sensor redundancy (logical layer) defines how many sensors are present for one physical information per aggregate. The communication link redundancy (physical layer) defines with how many Ethernet connections an aggregate is connected to the rest of the system.

III. RTE ARCHITECTURE

The RACE RTE is a modular layered architecture and contains inherent features for error detection and error handling. The RTE runs on all DCCs and a tailored version is used on the aggregates. Some basic principles about the RTE have been already presented in [START_REF] Sommer | RACE: A Centralized Platform Computer Based Architecture for Automotive Applications[END_REF] and [START_REF] Frtunikj | A safety aware run-time environment for adaptive automotive control systems[END_REF]. To some extent, the RACE RTE is based on the Chromosome Middleware (XME) [START_REF] Buckl | Chromosome -a run-time environment for plug & play-capable embedded real-time systems[END_REF] and reuses some of its components. In this paper, we go more into detail about certain RTE concepts such as data flow between RTE components, runtime error management and configuration of the RTE. Dedicated RTE layers are present for certain purposes, such as Network Management layer (for Frame packing/unpacking, CRC handling, etc.), Data Monitoring and Fusion layer, Indication Management as well as Application and Platform State Management. One cross cutting feature of the RTE is the Test System, which allows monitoring and manipulation of all data, status information and error indications during runtime without disturbing the system behavior, allowing diagnosis as well as fault-injection. The basic architecture and data-flow between the RTE components is shown in Fig. 2

A. Example Vehicle Function

As an example function, in this paper we consider a steerby-wire application. A steering application runs on a DCC of the CPC, subscribes a steering-wheel-angle topic and publishes a control topic for the steering rack aggregate. Due to posed safety requirements, both steering aggregates are setup redundantly. The steering wheel data is sensed by a dual-triple/duallink aggregate, meaning that two physical aggregates exist, each having three sensors. Hence, the angle of the steering wheel is sensed overall six times. Both aggregates publish their data. In the CPC, a steering application is executed (also redundantly as Master and Slave instance on two DCCs), which subscribes the sensed steering wheel angle. The RTE checks the sensor values for validity, masks erroneous values and finally fuses the values to one single value, which is given to the steering app. Finally, the steering application computes a control value for the also redundantly existing steering rack aggregates. This application architecture is shown in Fig. 3. The RACE RTE provides configurable fault-tolerance mechanisms that enable safe integration of safety-critical automotive functions, such as the steering function. Moreover, by decoupling the functionality from the safety mechanisms, we achieve a clear separation between the control steering functionality and the non-functional features. The mechanisms are grouped in three steps: error detection, error recovery, and fault treatment. Error detection raises Error Indications on the various data processing levels: Ethernet frames (physical aggregates, e.g. CRCs, timeouts), sensor values (logical aggregates, e.g. range checks), and fusioned data (virtual aggregates, e.g. deviations, inconsistencies). Based on configurable thresholds for each aggregate's indications, last-valid data or default values can be used for error recovery. As fault treatment, the RTE isolates erroneous fault-containment regions and supports fail-over to redundant hot-standby slaves or to more basic variants of applications (normal-law / direct-law fail-over).

We explain the input data-flow and the fault tolerance mechanisms within the RACE RTE for the steering application example (Fig. 4). The Network Management layer checks the CRC of the messages delivered by the steering aggregates and whether it was received in the correct time slot. Then one of the two dual-link messages is selected and unpacked. After the triple sensor data of the redundant steering wheel aggregates is unpacked, the monitors on logical level check for plausibility and consistency of each data instance. Here, checks w.r.t. validation of data against a predefined range of expected values are performed, and in case of an error the corresponding error indication is set (Fig. 4, red and green circles on logical level). The triple data from each aggregate is fused on the Data Monitoring and Fusion layer. On virtual layer, aggregate and data redundancies are hidden from the applications by a voting mechanism that selects and delivers the error-free data. In the case of the two triple aggregates, the data from the error-free aggregate is selected by the voting mechanism (Fig. 4, left aggregate). Only valid data is forwarded to the applications. Moreover, a quality information in form of a green/yellow/red indication is attached to the data, which is given to the applications. The steering-wheel sensor data gets a yellow quality indicator, since one of the redundant aggregates was detected as faulty. In case of a red indication, the last good known or a default value is forwarded. The error indication set is also cyclically exchanged and synchronized with other nodes in the RACE network in order to achieve a consistent view on the system as a whole. The consolidated error indications are then made available to the State Management components (Application Management and Platform State Management). These RTE components provide a unified state management. The benefit of this kind of state management is the always deterministic state of all system components (aggregates, application software components and execution nodes) and with that the known state of the complete system, which is essential w.r.t. safety. A system component state is changed to isolated when an error is detected in order to prevent further error propagation. The state management components also trigger recovery actions (restart, activate a redundant copy, or shutdown) in case of failures in the system.

When two or more DCCs redundantly execute a control program such as the steering application then, for sake of unambiguous control, at each time point only one of these application instances is allowed to send signals to the connected actuators. This unambiguous control is handled by the state management components, which take care that only the data of the steering application instance that is marked as a master is forwarded to the steering rack. If the master becomes faulty, the RTE handles the fail-over switching and therewith the slave becomes the new master and the old master becomes isolated.

C. Non-Intrusive Fault-Injection Tests

The RACE architecture enables non-intrusive fault injection [START_REF] Froehlich | Architecture for a Hard-Real-Time System Enabling Non-intrusive Tests[END_REF]. This is possible due to several measures such as exclusively reserved time slots, memory areas and network bandwidth for test actions. In addition, each DCC lane contains a system datastore that captures system-relevant data flows within and among RTE components. The RTE contains a test probe component, which enables monitoring of data and injection of faults at exact location and cycles. The test probe operates in a cyclical manner like all RTE components. In this way, the test probe is able to deterministically monitor system data (including error indications and state data) accumulated in the last cycle and to manipulate system data for the next cycle. For example, the test probe is able to inject a fault in one of the redundant aggregates by overwriting a sensor value with an invalid value. In accordance to the injected fault, a test is executed that checks the effectiveness of the RTE safety mechanisms that tolerate the corresponding fault. Such fault injection tests support both the development and certification of the systems. A complementary part to the test probes is the VITE3 system, which efficiently runs the fault injection tests that spread over several nodes of the RACE system by instructing the test probes on each node.

D. Application Development and Configuration of the RTE

RACE application software components as well as physical aggregates are delivered with self-describing information contained in manifests. A manifest contains all data that is required to integrate a software component or an aggregate into a vehicle design. We use a RACE specific extension of the CHROMOSOME Modeling Tool (XMT) [START_REF] Buckl | Chromosome -a run-time environment for plug & play-capable embedded real-time systems[END_REF] to describe these manifests. For instance, the user has to define component interfaces in form of publications and subscriptions of topics and attached attributes, as well as the Worst Case Execution Time (WCET) of the cyclic executable function and safety relevant information such as the component's requirement to behave fail-operational. The set of possible topics and attributes in one system is predefined in a so called dictionary. Topics may be for instance physical properties (temperature, pressure, etc.) or system data (recognized objects in front of the vehicle, a trajectory, etc.). Attributes describe the instances of a topic, such as the location and meaning of a temperature and the unit of measurement. The dictionary concept allows data compatibility between different applications, without requiring additional synchronization of interfaces.

The XMT tool offers to analyze virtual compositions of manifests in integrated product models. During the analysis, e.g. the logical data-flow between software components and aggregates is checked for completeness and unambiguity [START_REF] Schorp | Component-Based Modeling and Integration of Automotive Application Architectures[END_REF]. The analysis can be done in the tool for early integration prototyping, but is also done again by the RTE itself during RTE configuration. We also provide analysis of valid initial deployments of software-components to DCCs and possibly required graceful degradation in case of DCC failure scenarios [START_REF] Becker | Analyzing graceful degradation for mixed critical fault-tolerant real-time systems[END_REF]. Finally, manifest files are generated by the XMT design tool together with wrappers of the software components. In the wrappers, all read/write operations for the modeled interfaces are already present, as well as an initialization function and a function which is executed by the RTE in each cycle. Into this template, the developer can easily integrate its application behavior, for instance code generated from Matlab/Simulink. The RTE configuration may happen at system start-up based on the set of given manifests, or later during a Plug&Play scenario. The logical data-flow is checked again as well as the fulfillment of all safety relevant properties. In case of conflicts or other problems, the configuration process is aborted and the integration is rejected. After a successful analysis, finally the configuration data structures for the RTE components are created and the RTE is put into operation.

IV. RELATED WORK

RACE extends the idea of AUTOSAR [START_REF]AUTomotive Open System ARchitecture (AUTOSAR) Release 4.2[END_REF] with a blueprint system architecture and generic safety mechanisms to enable fail-operational features. In RACE, configurable services support changes of deployed functions and thus Plug&Play extensions of vehicles with new software-based functions and new physical aggregates. Reifying the configuration of the platform, instead of tailoring the RTE for the deployed applications, introduces a certain runtime overhead, but is the key for changing the system in field. With the help of the runtime datastore, RACE supports non-intrusive fault injection tests that are impossible with AUTOSAR, since AUTOSAR lacks a build-in module comparable to the test probe.

RACE uses the data-centric design known from standards such as DDS [START_REF]Data-distribution-service[END_REF] to achieve decoupling of functions and hence Plug&Play capability. Compared to DDS, RACE adds safety mechanisms and guarantees w.r.t. extra-functional properties.

Other related work, like Integrated Modular Avionics (IMA), ARINC 653, SIMATIC, Avionics Full DupleX Switched Ethernet (AFDX), FlexRay, TTEthernet and Audio Video Bridging (AVB) have been considered in [START_REF] Sommer | RACE: A Centralized Platform Computer Based Architecture for Automotive Applications[END_REF].

V. CONCLUSION AND FUTURE WORK

In this paper, we have shown the core concepts of the RACE Runtime Environment of a new robust E/E architecture for electric vehicles. The RACE RTE offers built-in faulttolerance mechanisms like error detection and isolation of faulty components and non-intrusive fault-injection tests. A data-centric design provides independent development of modular application software components and physical aggregates. Manifests provide self-descriptions of software components and physical aggregates, which are used to analyze their composability and determine a valid configuration of the RTE. The application of redundancy mechanisms and runtime failover switching supports fail-operational features. We illustrated the RTE mechanisms on a steer-by-wire application.

As future work, we work in various directions for instance on improving the configuration process for Plug&Play, providing open models for representing environment information and methods and tools for agile development of vehicle functions. Furthermore, we want to introduce additional fault-detection mechanisms, such as plausibility functions, reducing resource footprint and supporting heterogeneous replication (diversity) of hardware and software in order to cover systematic faults. Modular and flexible data fusion mechanisms are tackled in project SADA (http://www.projekt-sada.de/en-sada).

Fig. 1 .

 1 Fig. 1. The RACE platform Fig. 1 shows an example CPC with four DCCs, connected with an Ethernet ring and having two different power supplies.

  1 http://www.ieee802.org/1/pages/tsn.html 2 http://www.sysgo.com/products/pikeos-rtos-and-virtualization-concept

Fig. 2 .

 2 Fig. 2. Data-Flow through the RTE

Fig. 3 .

 3 Fig. 3. Example Steering Application Architecture

Fig. 4 .

 4 Fig. 4. Data-Flow and Fault-Tolerance within the RTE

  .

		Test System
				Test Ethernet
	Application	Appli ..	.. cation	Application
	Error Handling	Test Probe		Data Validation
	Data Monitor			Data
	and Fusion	RACE		Distribution
	Network	Datastore	Network
	Management			Management
		RACE RTE
	Sensor	DCC Lane A	Actuator
		DCC Lane B
	RACE Ethernet

Verification and Integration Testing Environment, www.aviotech.de

ACKNOWLEDGMENT

This work is partially funded by the German Federal Ministry for Economic Affairs and Energy (BMWi) under grant no. 01ME12009, project RACE (http://www.projekt-race.de).


Michel Planat
email: michel.planat@femto-st.fr

A moonshine dialogue in mathematical physics

Keywords: 00A09, 81P45, 81P13, 11G32, 20C34, 11F06, 51E12

Phys and Math are two colleagues at the University of Saçenbon (Crefan Kingdom), dialoguing about the remarkable efficiency of mathematics for physics. They talk about the notches on the Ishango bone, the various uses of psi in maths and physics, they arrive at dessins d'enfants, moonshine concepts, Rademacher sums and their significance in the quantum world. You should not miss their eccentric proposal of relating Bell's theorem to the Baby Monster group. Their hyperbolic polygons show a considerable singularity/cusp structure that our modern age of computers is able to capture. Henri Poincaré would have been happy to see it.

Math: At that time, Africans used the thumb of a hand to count the bones in the fingers of their hands. Four fingers times three little bones on a hand yield 12 as a counting unit. As there are 24 little bones in the two hands one gets: 60 = σ [START_REF] He | Modular subgroups, dessins d'enfants and elliptic K 3 surfaces[END_REF] and 48 = ψ [START_REF] He | Modular subgroups, dessins d'enfants and elliptic K 3 surfaces[END_REF].

Phys: What are these strange symbols σ and ψ? In quantum physics, ψ(x, t) denotes the wave function in space time but some scientists doubt its reality, it leads to many paradoxes such as Schrödinger's cat that may be simultaneously dead or alive. One finally introduced the qubit concept ψ = a |0 +b |1 to model the superposition, but problems arise with two qubits or more with such strange phenomena as non-locality and the non-reality of objects prior to measurements, a phenomenon called contextuality.

Math: In number theory, ψ(x) may designate the second Chebyshev function, a very important concept for looking accurately at the distribution of prime numbers. But I refer to the Dedekind psi function ψ(d) = d p|d (1 + 1 d ), where the product is over the primes p that divide d. At square free numbers d, ψ(d) equals the sum of divisor function σ(d). There are papers showing that both functions simultaneously arise for counting the number of maximal commuting sets of a d-level quantum system [START_REF] Planat | Pauli graphs when the Hilbert space dimension contains a square: Why the Dedekind psi function?[END_REF].

Phys: You are right. The (general) Pauli group for a qudit-a d-level system-is generated by two operators X (shift) and Z (clock) as P d = X, Z (generalizing the case of the two-qubit Pauli group when X and Z are the standard Pauli spin matrices). The You can easily observe how much different a 4-level system is from a 2-qubit system. A 2-qubit system comprises 15 operators and 15 mcs organized as the smallest thick generalized quadrangle GQ(2, 2) while a 4-level system has the same number of operators but only σ(4) = ψ(4) + 1 = 7 mcs [4, Table 1].

Math: Both arithmetic functions ψ(x) and ψ(d) can be used to formulate the Riemann hypothesis (RH) about the critical zeros of the Riemann zeta ζ(s). As for the Dedekind ψ(n), it was first introduced as the index of a particular congruence subgroup Γ 0 (q) of the modular group Γ = PSL 2 (Z). Congruence subgroups Γ 0 (p), for p prime, are used for defining genus zero surfaces if p -1 divides 24. [START_REF] Shimura | Introduction to the Arithmetic Theory of Automorphic Functions[END_REF]. The relation to RH is as follows. Taking the ratio R(d) = ψ(d)/(d log log d), it has been shown that the statement R(d) > e γ /ζ(2) (where γ is Euler constant) is equivalent to RH [START_REF] Solé | Extreme values of the Dedekind ψ function[END_REF]. As for ψ(x), I know that the logarithmic integral li[ψ(x)] does much better than li(x) for counting the number of primes. Here the statement li[ψ(x)] -π(x) > 0 is equivalent to RH [START_REF] Planat | Improving Riemann prime counting[END_REF].

Phys: Impressive! I am interested in advanced maths for clarifying problems in physics. I like Wolfgang Pauli's quote There is no God and Dirac is his prophet [START_REF] Heisenberg | Physics and beyond; encounters and conversations[END_REF]. Do you think that God is a mathematician or, like Alfred Jarry, that God is the tangential point between zero and infinity? [START_REF] Jarry | Exploits and Opinions of Doctor Faustroll, Pataphysician[END_REF]. It is a bit provocative, isn't it? So, the number 24 occurs in the 'prime groups' Γ 0 (p), as it occurs in the explanation of the tracks in the Ishango bone. It is quite remarkable that a hot topic of physics -quantum entanglementalso relates to 24. The group of automorphisms of Euclidean dense lattices such as the root lattices D 4 and E 8 , the Barnes-Wall lattice BW 16 , the unimodular lattice D + 12 and the Leech lattice Λ 24 may be generated by entangled quantum gates of the corresponding dimension, as shown in [START_REF] Planat | Multipartite entanglement arising from dense Euclidean lattices in dimensions[END_REF] and so on, in which the numbers at the left column occur in the q-expansion of the modular j-invariant (q = e 2iπτ and τ in the upper-half plane) and the numbers at the right column are sums of dimensions of the smallest irreducible representations of the Monster M [START_REF] Gannon | Monstrous moonshine: the fist twenty-five years[END_REF]. The coincidence is known as the 'monstrous moonshine' (in the sense of being a crazy idea). I quote the Fields medalist Richard Borcherds after his proof of the puzzle with the help of string theoretical concepts: I sometimes wonder if this is the feeling you get when you take certain drugs. I don't actually know, as I have not tested this theory of mine [12]. This is an illustration of the pre-established harmony between maths and physics. Concerning Jarry's quote, I have put labels 0, 1 and ∞ on Ubu's portrait in Fig. 1b in order to illustrate a salient feature of Grothendieck's 'dessins d'enfants' [START_REF] Grothendieck | Sketch of a programme[END_REF], another way to approach the moonshine subject.

Phys: Thanks, may be this approach helps to clarify the ψ-quantum puzzle. Let us discuss this point tomorrow. There is an edge between two vertices if they commute. As the result of a measurement can only be the eigenvalue ±1 of a s i , one expects to satisfy the inequality

C = | s 1 s 2 + s 2 s 3 + s 3 s 4 -s 4 s 2 | ≤ 2.
But the calculations with the operators s i lead to the norm ||C|| = 2 √ 2 instead of 2, and the experiments confirm this fact. There are many choices for a square graph with multiple qudits s i and the result is always a maximal violation 2 √ 2. Math: Do you have an explanation of the algebraic equation C 2 = 8? Phys: One cannot escape the quantum formalism on this matter. Observe that there is no commuting entangled pair (s i , s j ) in my example, the proof of Bell's theorem does not refer to entanglement. But I found another argument based on the permutation group P = α, β with the two generators α = (1, 2, 4, 3) and β = (2, 3), this is pictured in my Fig. 2b where i means s i . Each edge of my drawing corresponds to the same stabilizer subgroup of P .

Math: Your graph is a Grothendieck's 'dessin d'enfant' and the generators mean how you go around the black and white vertices, isn't it? And I see that the vertices live in the extension field Q( √ 2). This means that your dessin can also be seen as a complex algebraic curve over the field of algebraic numbers. Congratulations, this is a nice use of a quite sophisticated mathematical trick. Is your graph (b) the only choice to stabilize the square?

Phys: You are right, there are essentially four choices as shown in Fig. 1 of the article [START_REF] Planat | Quantum contextual finite geometries from dessins d'enfants[END_REF]. I kept the most asymmetric graph because I have the vague feeling that, as Einstein wrote: Everything should be made as simple as possible, but not simpler [16]. The three other choices are too symmetric, I feel one needs some breaking of the symmetry to allow a deeper explanation of Bell's theorem. I suspect that mathematics can help.

Math: You know, I met your dessin before. It corresponds to one (the case I) of the non-normal inclusions of triangle groups classified by D. Singerman [START_REF] Hoshino | The Belyi functions and dessins d'enfants corresponding to the non-normal inclusions of triangle groups[END_REF]. The monodromy permutation P that you introduced is the subcover

X 0 (4) → X + 0 (2)
of the famous Klein quartic X(7

) = X 3 Y + Y 3 Z + Z 3 X.
The triangle groups corresponding to the modular curves X 0 (4) and X + 0 (2) are the congruence subgroup Γ 0 (4) and the smallest moonshine group Γ + 0 (2) that we discussed yesterday. I suspect that your Bell's theorem is an elementary stone of a modular physical theory based on the Monster M, a kind of atom. This reminds me the vortex atoms of Lord Kelvin. The modern language is knot theory and Witten developed his topological quantum field theory based on this set of ideas.

Even more intriguing, the moonshine group Γ + 0 (2) is related to the Baby Monster group B of order 2 41 3 13 and so on, where the numbers a i correspond to the q-expansion of the main modular invariant T 2A (also called a Hauptmodul) for Γ + 0 (2) and the numbers 1, 4371, 96255, 1139374, . . . are all dimensions of smallest irreducible representations of B. One has the property: 24 i=1 a 2 i mod(70) = 42 as for the q-expansion of j(q) and that of the modular discriminant ∆(q) [START_REF] He | Moonshine and the meaning of life[END_REF].

That moonshine for B relates to Bell's theorem is a remarkable coincidence! Phys: The approach is the application of a simple axiomatic with only two letters a and b [START_REF] Planat | Geometry of contextuality from Grothendieck's coset space[END_REF]. Mathematically, my language is also called a free group G = a, b|b 2 = e . Elements in the group are words u, any combination uu -1 = e (the neutral element) is annihilated and I also write that b is an involution that is, b 2 = e. The relative size of a subgroup H of G is called the index which means that there are n inequivalent copies (called cosets) of H that fill up G. The action of generators on these cosets creates the permutation group P by the Todd-Coxeter algorithm. You can name the cosets by a word representative, the other elements in the coset are conjugate to the representative. I did it in Fig. 3 for the case just discussed where the index is 4.

With a little effort, you can check that pairs of cosets on a edge are commuting in the group sense that is, the commutator (u, v) = u -1 v -1 uv = e. In this special case, coset commutation respects quantum commutation.

But I can show that it is not always the case for a geometry stabilized by a higher index group. Following Gottlob Frege quote: Never ask for the meaning of a word in isolation, but only in the context of a sentence [START_REF] Frege | Die Grundlagen der Arithmetik. Eine logisch-mathema-tische Untersuchung uber den Begriff der Zahl[END_REF].

Look at Mermin's pentagram shown on Fig. 4b [START_REF] Mermin | Hidden variables and two theorems of John Bell[END_REF], I labeled the vertices from 1 to 10 and with 3-qubit coordinates. The product of operators on a thin line is III and -III on a thick line so that, as shown by David Mermin, this pentagram is a contextuality proof [START_REF] Planat | It from qubit: how to draw quantum contextuality[END_REF][START_REF] Planat | Quantum contextual finite geometries from dessins d'enfants[END_REF].

Remember that I was able to stabilize a square with the permutation group (i.e. the dessin d'enfant) shown in Fig. 2b. With the same reasoning, I stabilize the pentagram with a permutation group P generated by the permutations α = (2, 3, 4)(5, 7, 8)(6, 9, 10) and β = (1, 2)(3, 5)(4, 6)(7, 10) as shown in Fig. 4a. Each point on a selected line of the pentagram corresponds to the same stabilizer subgroup S of P (all the S are isomorphic but they act on different sets of points). Then in Fig. 3b, I have put the coset representatives for labeling the edges. In this way you can check that on a thick line of the pentagram not all cosets are commuting. Of course the cosets on a (thin) line containing the identity element e are commuting. I call a geometry 'contextual' when it happens that at least a line fails to have its points/cosets commuting. In this way, geometric contextuality reflects quantum contextuality [START_REF] Planat | Geometry of contextuality from Grothendieck's coset space[END_REF].

Math: You didn't comment on your Fig. 4c but I recognize the tiling of a fundamental domain in the upper-half plane H. I see that the tiles of H reflect the edge (coset) structure of your dessin and, of course, the tiles also correspond to your three-qubit operators.

Phys: Yes, the 'modular' representation of the pentagram is in the spirit of what you explained yesterday. As the generators α and β have order three and two respectively, they build a subgroup Γ ′ of the modular group Γ that is a congruence subgroup of level 5. The set of cusps for Γ ′ consists of the Γ ′ -orbits of {Q} ∪ {∞}, cusps are at -3 and ∞ and they have width 3. My Γ ′ is of type '5C 0 ' in Cummins-Pauli classification (http://www.uncg.edu/mat/faculty/pauli/congruence/congruence.html). I used the software Sage to draw the fundamental domain of Γ ′ thanks to the Farey symbol methodology. I am not the first to play with Sage on modular aspects of dessins, you can read the essay by Lieven le Bruyn [START_REF] Le Bruyn | Monsters and moonshine[END_REF].

Math: If your approach makes sense, you should also encounter other moonshine groups, did you? Phys: It is true that moonshine groups relate to geometric contextuality. There exists six congruence subgroups of the modular group Γ that are simultaneously torsion free, of genus 0 and index 12 and three of them have a moonshine group as their normalizer [START_REF] Sebbar | Modular subgroups, forms, curves and surfaces[END_REF]Table 5]. The corresponding dessins can be seen in [START_REF] He | Modular subgroups, dessins d'enfants and elliptic K 3 surfaces[END_REF]Sec. 2.3.1]. Look at the results in my Table 1: the normalizer of Γ( 3) is Γ and three extra congruence subgroups have the normalizer Γ + 0 (d), d = 2, 5, 6. It is known that j 1/3 occurs as a generating function for Γ(3) [11, p. 7]. I also showed which geometry these groups stabilize.

Group

Normalizer Geometry cusps Γ(3) Γ 11-simplex

3 4 Γ 0 (4) ∩ Γ(2) Γ + 0 (2) K(4, 4, 4) 4 2 2 2 Γ 1 (5) Γ + 0 (5) 6-orthoplex 5 2 1 2 Γ 0 (6) Γ + 0 (6) K(6, 6) 6 1 3 1 2 1 1 1 Γ 0 (8) . K(4, 4, 4) 8 2 2 1 1 2 Γ 0 (9) . K(3, 3, 3, 3) 9 1 1 3
Tomorrow, I tell you more about my work inspired by the moonshine topic.

Day3: Dessins d'enfants, hyperbolic polygons, Rademacher sums Phys: It seems not to be widely known that most sporadic groups may be defined as permutation groups P with two generators [START_REF] Mazurov | Minimal permutation representation of Thompson's simple group, translated from Algebra i[END_REF] -acting on a G-set of cardinality n. These representations can be found explicitly in the 'Atlas of finite group representations' [START_REF] Wilson | ATLAS of Finite Group Representations -Version 3[END_REF].

As at the previous section, a P may be seen as 'dessin d'enfant' D endowed with a natural topological structure with Euler characteristic 2 -2g = B + W + F -n with B black points, W white points, F faces, n edges and genus g (see [START_REF] Grothendieck | Sketch of a programme[END_REF][START_REF] Planat | Quantum contextual finite geometries from dessins d'enfants[END_REF][START_REF] Planat | Geometry of contextuality from Grothendieck's coset space[END_REF] for details). Another remarkable property is that, in many cases, a P (and its D), stabilizes a graph/geometry G. First, a pair of elements of the G-set attached to P defines a stabilizer subgroup S of P . Second, the collection of isomorphic S acting on different subsets of the G-set defines the edges/lines of G. A list of the stabilized G ′ s of small index can be found in [15, Tables 1 and2]. In the following I restrict to 'modular dessins' that are defined from a subgroup Γ ′ of the modular group Γ (as for the pentagram of the previous section). For these D the valency of black and white points is three and two, respectively (except for the elliptic points where the valency is one).

Lieven le Bruyn writes in [START_REF] Le Bruyn | Monsters and moonshine[END_REF]: It would be nice to have (a) other Farey-symbols associated to the second Janko group, hopefully showing a pattern that one can extend into an infinite family as in the iguanodon series and (b) to determine Farey-symbols of more sporadic groups.

This is precisely what I did for several 'sporadic' iguanodons (dessins d'enfants [START_REF] Grothendieck | Sketch of a programme[END_REF], [START_REF] Planat | Quantum contextual finite geometries from dessins d'enfants[END_REF]). In table 1, I list a few of them (those related to J 1 , J 2 , J 3 , McL, M 24 , T , Suz, Fi 23 , Co 1 , Fi ′ 24 ) and give the main characteristics of their fundamental domain P in the upper-half plane H. All the groups are represented as non-congruence subgroups of the modular group Γ. The number n of edges of the dessin D is the index of the (sporadic) group representation. The genus g of D equals that of the hyperbolic polygon P, a face of D corresponds to a cusp of P, the number of black points (resp. of white points) of D is B = f + ν 3 -1 (resp. W = n + 2 -2g -B -c), where f is the number of fractions, c is the number of cusps, ν 2 and ν 3 are the number of elliptic points of order two and three I suggest that you look at a promising line of moonshine research by I. Frenkel ('not E. Frenkel') and J. Dunkan [START_REF] Duncan | Rademacher sums, moonshine and gravity[END_REF] based on the use of a Rademacher sum for the modular invariant j(τ ) = q -1 + 744 + 196884q + 21493760q 2 + • • •, with q = e 2iπτ as j(τ ) + 12 = e -2iπτ + lim Phys: I am familiar with Rademacher work. Some time ago, I investigated the thermodynamics of the Euler gas whose partition function is that of the number of unrestricted partitions p(n). This was useful to model the low frequency fluctuations (of the 1/f type) occurring in a gaz of bosons, like the phonons in a quartz crystal resonator [START_REF] Planat | Quantum 1/f noise in equilibrium: from Planck to Ramanujan[END_REF]. The mathematics involves the Hardy-Ramanujan circle method in analytic number theory and this was improved by Rademacher.

K→∞ 0 < c < K, -K 2 < d < K 2 (c, d) = 1 e -2iπ aτ +b cτ +d -e -2iπ a c , with
Math: Do you think that our mathematics is the real world?

Phys: As a provisional response, I offer you a quote of Stephen Hawking from his lecture "Godel and the end of the universe" [START_REF] Hawking | Godel and the End of the Universe[END_REF]: In the standard positivist approach to the philosophy of science, physical theories live rent free in a Platonic heaven of ideal mathematical models... But we are not angels, who view the universe from the outside. Instead, we and our models are both part of the universe we are describing. Thus a physical theory is self referencing, like in Godels theorem. One might therefore expect it to be either inconsistent or incomplete. The theories we have so far are both inconsistent and incomplete.

Math: But you should know Dyson's words in 1981: I have a sneaking hope, a hope unsupported by any facts or any evidence, that sometime in the twenty-first century physicists will stumble upon the Monster group, built in some unsuspected way into the structure of the universe. This is of course only a wild speculation, almost certainly wrong [START_REF] Roberts | Curiosities: Pursuing the Monster, Institute of Advanced Study[END_REF]. Today we also know that monstrous moonshine has a shadow -umbral moonshine [START_REF] Duncan | Proof of the umbral moonshine conjecture[END_REF], that is potentially of huge interest for theoretical physics.

Figure 1 .

 1 Figure 1. (a) A schematic of the notches on the Ishango bone, (b) Véritable Portrait de Monsieur Ubu, by Alfred Jarry (1896) ( with a free labeling by the author).

  operators in P d are organized into σ(d) maximal commuting sets (mcs) of size d-1, where ψ(d) ≤ σ(d) of them are 'admissible'. A non-admissible mcs turns out to be transversal to every admissible mcs and can be removed. The geometry of admissible mcs is the projective line P 1 (Z d ), where Z d is the ring of integers mod d, and |P 1 (Z d )| = ψ(d).

Day 2 :

 2 the ψ-quantum puzzle revisited Phys: Look at what I see as the simplest ψ-quantum diagram of all, a square graph (shown in Fig. 2a) that is the paragon of two-qubit Bell's theorem about non-locality [15, Fig. 1]. Imagine that Alice and Bob are spatially separated and do electron spin measurements (along the orthogonal directions x and z) with their Stern-Gerlach. The four (two-qubit) operators involved are denoted s i , i = 1..4 as shown in my picture (a) where X = (0, 1; 1, 0) and Z = (1, 0; 0, -1) are the Pauli spin matrices and a notation such as IX means the tensorial product of the identity matrix I and the Pauli matrix X.

Figure 2 .

 2 Figure 2. (a) The square graph of Bell's theorem, (b) the dessin stabilizing the square graph where the labeling 'i' of the edges corresponds to the (operator) vertices 's i ' of the square.

5 6 7 2

 2 [START_REF] Gannon | Monstrous moonshine: the fist twenty-five years[END_REF] [START_REF] Grothendieck | Sketch of a programme[END_REF] 17 19 23 31 47 ∼ 4.10 33 through another puzzling series [11, p. 20] a 1 = 4372 = 1 + 4371, a 2 = 96256 = 1 + 96255, a 3 = 1240002 = 2.1 + 4371 + 96255 + 1139374,

Figure 3 .

 3 Figure 3. (a) The representatives of cosets for the dessin (b) stabilizing the square graph (a). For this special case, mutually commuting operators correspond to mutually commuting cosets.

Figure 4 .

 4 Figure 4. A dessin (a) stabilizing Mermin's pentagram (b) and (c) the fundamental domain of congruence subgroup '5C 0 '. The pictures have coordinates in the G-set {1..10} with the corresponding cosets shown on (a) and a set of 3-qubit operators shown on (b).

  a, b relative integers and ad -bc = 1, τ ∈ H. The authors show that the McKay-Thomson series T g (τ ) of an element g ∈ M coincides with a generalized Rademacher sum. They expect to get a version of the simplest chiral 3d quantum gravity with 24 charges, as the original construction of the chiral 2d conformal field theory by McKay based on the partition function j(q).

46 3 20 5 9 7 6 11 2 13 3 17 19 23 29 31 41 47 59 71 ∼ 10 54 -this would correspond to the mass in Kg of the known universe. Now if you add to Γ 0 (d) (d square free) the Fricke involution matrix 1

  . The Leech lattice is the densest known lattice in dimension 24. It has the kissing number 196560 and automorphism group Z 2 .Co 1 , where the sporadic Conway group Co 1 has order about 4.10 18 . Math: But the story is not finished, the group you mention is a sporadic part of the largest finite group, the Monster group M of cardinality |M| = 2

	√ 0 (d). For prime d = p, the group has genus zero if and only if p is in the d (0, -1; d, 0) you get another group with a single cusp at ∞ called Γ +
	sequence {2, 3, • • • 71} occurring in the factors of [M|. This coincidence is again a puzzle when it is rewritten as
	196884 = 1 + 196883,
	21493760 = 1 + 196883 + 21296876,

Table 1 .

 1 Characteristics of torsion free, genus 0, index 12 congruence subgroups. The notation K(., • • • , .) means the corresponding complete multipartite graph.

Table 2 .

 2 Characteristics of a few small 'sporadic' fundamental polygons. The keyword for the link between moonshine and the Langlands program is VOA (for vertex operator algebra). The Monster vertex algebra is conjectured (by E. Frenkel and collaborators) to be the unique holomorphic VOA with charge 24 and partition function j -744 (where j is again the modular invariant).I quote E. Frenkel[START_REF] Frenkel | The Atlantic[END_REF]: Mathematics is not about studying boring and useless equations: It is about accessing a new way of thinking and understanding reality at a deeper level. It endows us with an extra sense and enables humanity to keep pushing the boundaries of the unknown.

	Graph/geometry	Group	n	g	ν 2	ν 3 cusps	f
	Hall-Janko	J 2	100	0	0	4 1 2 7 14	33
	Livingstone	J 1	266	0 10 5 7 38	88
	McLaughin	McL : 2	275	10 11 14 11 1 22 12	88
	T (24)	M 24	276	10 12 15 23 12	12
	Ree-Tits GO(2, 4)	T 1755	57 91 0 13 135	586
	Suzuki	Suz	1782	70 42 0 1 1 3 137	595
	Janko	J 3	6156	321 76 36 19 324	2041
	Fischer	Fi 23 31671	1876 695 27 2 1 4 2 7 9 14 45 28 1106	10549
	Conway	Co 1 98280	6922	0	27 10 12 20 108 40 2400	32752
	Fischer	Fi ′ 24	306936 19409 3512 0 29 10584	155225
	every function is analytic [29].

The fundamental domain for the index 1755 permutation group stabilizing the Ree-Tits octagon (details can be found at http://brauer.maths.qmul.ac.uk/Atlas/exc/TF42/mag/TF42G1-p1755B0.M) and an excerpt of the permutation representation.

of P, respectively. Elliptic points forbid most of these 'sporadic dessins' to be trivalent (when ν 3 = 0) and clean (when ν 2 = 0).

For instance, the smallest permutation representation P of our friend, the Conway group Co 1 can be found in the Atlas [START_REF] Wilson | ATLAS of Finite Group Representations -Version 3[END_REF], it may be seen as a dessin D of index n = 98280 (half the kissing number of the Leech lattice). An excellent signature consists of the cycle structure [START_REF] Planat | Quantum contextual finite geometries from dessins d'enfants[END_REF][START_REF] Lando | Graphs on surfaces and their applications[END_REF] The genus g follows from Euler formula given at the beginning of this section. This D can also be seen as an hyperbolic polygon P of the upper-half plane (not shown).

Similarly, the dessin D for the Tits group with permutation representation of index n = 1755 has the cycle structure [3 585 , 2 8321 1 91 , 13 135 ] and characteristics shown in Table 1. The fundamental domain for this representation of the Tits group T is shown in Fig. 5. The geometry G stabilized by D is the Ree-Tits octagon GO(2, 4) (see https://en.wikipedia.org/wiki/Generalized polygon for details about the generalized polygons).

Math: Excellent, the next step would be to compute the modular symbols, the relative homology of the extended upper half plane and the corresponding modular forms of weight two and higher. I am curious to see if the noncongruence cusp forms for these 'sporadic' polygons have unbounded denominators, as conjectured [START_REF] Li | Atkin and Swinnerton-Dyer congruences and noncongruence modular forms[END_REF].

You are close to the 'philosophy of cusp forms' of Harish-Chandra. He was studying under Dirac himself but turned to mathematics when he learned in Princeton that not


Gérard Le Lann
email: gerard.le_lann@inria.fri.

Some Open Safety Issues in Vehicular Networks

INTRODUCTION

We consider autonomous and automated vehicles circulating on major roads and highways, forming vehicular networks ranging from strings (single-lane pre-planned platoons or ad hoc strings) to multi-lane ad hoc vehicular networks (VANETs) [START_REF] Karagiannis | Vehicular networking: A survey and tutorial on requirements, architectures, challenges, standards and solutions[END_REF]. Efficiency (e.g., higher asphalt utilization ratio, shorter travelling times, no human time devoted to driving) and improved safety are major motivations for such vehicles and networks. In a nutshell, safety objectives are to reduce fatalities and accidents by a large factor (e.g., ratio of 10) compared to current statistics, for all driving scenarios, under demanding worst-case conditions which cannot be handled by humans (goal Ω). For example, reaction latencies shall be much smaller than 1 second, in the presence of very small inter-vehicular spacing (ranging from 1 meter to a few meters), at low/high velocities, respectively.

For proving safety, it is necessary (albeit not sufficient) to demonstrate that vehicular networks are endowed with two major properties: dependability and timeliness (timebounded termination). Safety in vehicular networks rests on various disciplines such as, e.g., robotics, signal processing, kinematics, mobile wireless (radio, optical) communications, computer science, formal software engineering, artificial intelligence, cyber security, human/behavioral sciences, to name a few.

In this position paper, we briefly review some accepted beliefs which may hide open issues regarding dependability or timeliness in SC scenarios, and we give examples of shortcomings and challenges. Due to space constraints, we focus solely on protocol/algorithmic design issues, failures, limitations of on-board technologies, and radio channel access latencies in the presence of contention. Despite their importance, software issues (correct instantiations of protocols, algorithms, and applications) are not addressed here. We use the terminology defined by S. Shladover: Automation is autonomy augmented with wireless communication capabilities. For fulfilling goal Ω, should we shoot for autonomous driving or for automated driving? Should we trust human supervision (ultimately, if ever needed, some human is in charge) or full automation rather (absolutely no human intervention)?

II. ISSUES RELATED TO AUTONOMOUS DRIVING

Autonomous vehicles are equipped with on-board perception capabilities (e.g., lasers, radars, lidars, cameras), GNSS devices (e.g., GPS), emaps, and companion software (e.g., navigation, SLAM). On-board perception capabilities work exclusively in line-of-sight (LOS) conditions, and achieve reactive safety only, i.e. avoidance of visible static or moving obstacles.

A. Issue 1: Human factors-Is safety improved with autonomous driving?

With autonomy, supposedly most of the time, humans can do whatever they like while travelling. However, autonomy does not free humans from being vigilant. Whenever some hazardous condition develops (can they be enumerated?), a human is responsible for taking proper actions in case his/her vehicle appears not to be doing "the right thing at the right time". Such are the laws in many countries, and this is stipulated in contracts issued by car manufacturers and insurance companies. Problem is that a human may not react quickly enough and appropriately to an event occurring unexpectedly while he/she is playing some game on a smartphone (to give an example). And we know perfectly well that "authority sharing" (is it better to trust a human or some automaton in exceptional or unexpected situations?) is an area with numerous open problems. Likely, that could be the reason why a number of respected experts posit that "with autonomous vehicles, we might see more accidents than with ordinary human driving". It may well be that autonomy will not fulfill goal Ω.

B. Issue 2: Unavailability and inaccuracies-Can we trust emaps and GNSS devices for achieving safety?

Local situational awareness is a necessity (hazards may develop with proximate vehicles only). Despite impressive achievements, emaps do not provide what is expected. Emaps provide static data (topology, geography, infrastructures), previously recorded. They are not meant to reflect the occurrence of some hazardous condition (vehicles about to collide) in no more than about 100 ms. Furthermore, global views and absolute geo-localization are not needed. Accurate knowledge of local relative positioning of vehicles suffices, measured by LOS perception devices. Finally, space-time coordinates provided by GNSS devices may be inaccurate, due to adverse conditions (bad weather, physical obstructions). Since losses of satellite signals may last several seconds, worst-case global time (UTC) inaccuracy τ may be in the order of a few milliseconds and worst-case geo-positioning inaccuracy γ in the order of a few dozens of meters, enough for causing accidents. Solutions based on ignoring inaccuracies γ and τ cannot fulfill goal Ω.

C. Issue 3: Limited knowledge-Are LOS capabilities sufficient for achieving safety?

There are obvious limitations with LOS capabilities and reactive safety. Consider lane changes. So far, the insertion of a vehicle in a string has been mostly looked at on a "local scale", implicitly assuming that no more than 1 insertion operation would be performed at any given time, which is unrealistic. Indeed, multiple concurrent insertions at different "slots" within a string are routinely attempted. Most often, whenever necessary, human drivers are able to decide that it is better to defer an intended lane change that would result into unfeasible or/and abrupt decelerations for some string members, which is especially useful when vehicles move at medium/high velocities. Consider now some autonomous vehicle W that starts moving to lane L, for being inserted behind vehicle V. Inevitably, an accident occurs if, simultaneously, V brakes abruptly (due to insertions "granted" by vehicles further ahead in the string), and W enters lane L. Since causal conditions develop beyond LOS, W cannot "know" that this maneuver shall not be attempted. Non-LOS (NLOS) capabilities-that do not come with autonomy-are mandatory for fulfilling goal Ω.

D. Issue 4: Does safety hold in the presence of failing

LOS perception capabilities? Safety may not be guaranteed in case a short-range radar would fail. Consider Y following X closely, and a SC scenario where, at the same time, X brakes abruptly and Y's radar fails (permanently or temporarily). Inevitably, Y collides with X. Duplicated radars might not be safer (the same cause would bring them down). This observation holds for every LOS capability, e.g. lidar scanners that do not work when it rains (reflectance of rain drops). Diversified redundancy is a well-known principle applied in every mature safety-critical domain. Some NLOS capabilities radically different from LOS capabilities are needed for fulfilling goal Ω. This issue is raised here (and echoed further) for the reason that, so far, too little work has been directed at the problem of how to achieve safety in the presence of failures in vehicular networks.

E. Issue 5: Does autonomy entail time-bounded actions/reactions?

Since perception capabilities achieve reactive safety only, an autonomous vehicle can only "adapt" its behavior according to other vehicles' motions, unable to "influence" these motions, a severe limitation. Consider autonomous car V on highway 101 that wants to move to rightmost lane and exit 101. V's indicators may or may not be "obeyed" by vehicles (human driven or not) in this lane. Unless they are "cooperative", i.e. they manage to create a convenient "slot" for V's insertion, that lane change maneuver is impossible. There is no difference with human driving. With autonomy, one faces the following dilemma:

-either reactive safety is achieved, but intended maneuvers may not be performed as desired, i.e. no timeliness (V cannot exit highway 101 where desired), -or the opposite. Proactive capabilities (that do not come with autonomy) are mandatory for fulfilling goal Ω.

III. ISSUES RELATED TO AUTOMATED DRIVING

Let us now consider automated vehicles, i.e. autonomous vehicles equipped with wireless communication capabilities. Let us focus exclusively on radio communications (due to space limitations, optical communications are not examined). So-called "connected vehicles" are vehicles enabling WiFi communications for infotainment purposes. They are not within our scope of consideration. Starting 2020, vehicles built in the USA will have to be equipped with radios conformant to the IEEE 802.11p and 1609 standards (very similar to ETSI G5 standard), enabling V2X medium-range (≈ 250 m) omnidirectional communications based on CSMA-CA. On roads and highways, SC scenarios may develop far away from road-side units. Thus, safety shall be proved assuming V2V (vehicle-to-vehicle) communications only. Over the past decade, numerous publications have been devoted to "demonstrating" that automated vehicles can achieve proactive safety in LOS and NLOS conditions, by resorting to published MAC protocols and companion V2V communications protocols. Let us review some open issues.

A. Issue 6: Are bounded MAC level access delays achievable with existing protocols?

Current MAC protocols designed for omnidirectional radios (standards, scientific publications) fail to solve the BCAD (bounded channel access delays) problem, under realistic worst-case assumptions, i.e. hundreds of contenders, variable number of lanes, space-time inaccuracies γ and τ. We mean strict, non-stochastic, time bounds. CSMA protocols and their variants only provide a "best effort" service, which is unsatisfactory. Unfairness may be experienced by contenders [START_REF] Kyasanur | Selfish MAC layer misbehavior in wireless networks[END_REF][START_REF] Tang | Real-time misbehavior detection in IEEE 802.11-based wireless networks: An analytical approach[END_REF], due to numerous causes. For example, since propagation of omnidirectional signals (messages and collisions) is anisotropic, a collision may not be detected by all silent processes within interference range of one of the senders; as a result, computations of backoff periods are incorrect, which leads to augmented unfairness. Reservation-based protocols, a.k.a. scheduling-based protocols, do not solve BCAD [START_REF] Borgonovo | ADHOC MAC: New MAC architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services[END_REF][START_REF] Cozzetti | RR-Aloha+: A slotted and distributed MAC protocol for vehicular communications[END_REF][START_REF] Ba | A new approach to channel access scheduling for ad hoc networks[END_REF]. First, access to reservation slots is not collision-free. Second, due to unreliable radio links, not all intended recipients are made aware of reservations heard by others, which results in contention and message collisions. Published variations of TDMA (time-division-multi-access) protocols do not solve BCAD either. Crux of the problem is how to assign a unique slot to every contender without resorting to collision-prone communications, under realistic assumptions. STDMA [START_REF] Grönkvist | Assignment methods for spatial reuse TDMA[END_REF][START_REF] Amouris | Space-time division multiple access (STDMA) and coordinated, power-aware MACA for mobile ad hoc networks[END_REF] which is based on observing that no two contenders may reside at the same space coordinates at the same time, cannot be considered either since inaccuracies γ or τ need be assumed arbitrarily small for STDMA to be correct (or simply efficient). Ditto for SDMA [START_REF] Bana | Space division multiple access (SDMA) for robust ad hoc vehicle communication networks[END_REF] and LCA [START_REF] Katragadda | A decentralized location-based channel access protocol for inter-vehicle communication[END_REF]. To the best of our knowledge, none of the published MAC protocols devised for directional antennas solves BCAD either, under realistic worst-case assumptions.

B. Issue 7: Are time-bounded deliveries of V2V messages achievable with traditional PAR protocols?

Mobile radio communications are prone to failures, and V2V message losses may exceed acceptable figures, even in LOS conditions [START_REF] Karlsson | Field measurements of IEEE 802.11p communication in NLOS environments for a platooning application[END_REF]. Solutions proposed for Xcast operations (Multicast, Broadcast, or Geocast) rest on a "no acknowledgment" policy, or on positive-acknowledgmentand-retransmission (PAR) protocols [START_REF] Ros | Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks[END_REF]. Without acknowledgments (acks), failed message deliveries go unnoticed, which is not acceptable. PAR protocols cannot be used when a sender does not know a priori which vehicles shall receive its message and return acknowledgments (Geocast). Moreover, PAR protocols are inadequate for the handling of most SC scenarios. Consider the set of V2V messages and acks exchanged for coordinating a safe lane change or for broadcasting and relaying a V2V emergency message reliably. The time budget for delivering V2V messages and acks successfully is in the order of 300 ms (a vehicle moving at 108 km/h would travel 9 m, enough for creating collisions). Given that omnidirectional radio links may be garbled longer than 300 ms, resending messages and/or acknowledgments is useless. Novel approaches and protocols specifically designed for achieving reliable timebounded V2V message deliveries are needed.

C. Issue 8: Longitudinal safety-String-wide time-bounded message dissemination and distributed agreement

Adaptive Cruise Control (ACC) has been extensively studied in control theory and by the robotics community [START_REF] Shladover | Longitudinal control of automated guideway transit vehicles within platoons[END_REF][START_REF] Swaroop | String stability of interconnected systems[END_REF] in the particular case of platoons. A lead vehicle, driven by a human, makes unilateral decisions such as changing velocity, which is sensed by its follower, and so on-platoon members instantiate a velocity change one after the other. Step-by-step perception takes time, thus cannot fully eliminate instability, i.e. sequences of successive amplifying accelerations or decelerations, while keeping safe, possibly optimal, inter-vehicular spacing. In Cooperative ACC (CACC) solutions, V2V communications are "added" to ACC. Typically, a velocity change triggered by a lead vehicle is carried in a V2V message multicast to platoon members. As expected, doing this leads to better performance figures and higher stability [START_REF] Xiangheng | Effects of communication delay on string stability in vehicle platoons[END_REF][START_REF] Naus | String-stable CACC design and experimental validation: A frequency-domain approach[END_REF][START_REF] Rajmani | Semiautonomous adaptive cruise control systems[END_REF]. However, in analyses of CACC, channel contention delays are ignored, and message losses are not considered, with some notable exceptions [START_REF] Lei | Impact of packet loss on CACC string stability performance[END_REF][START_REF] Sepulcre | Cooperative vehicle-tovehicle active safety testing under challenging conditions[END_REF][START_REF] Bergenhem | V2V communication quality: Measurements in a cooperative automotive platooning application[END_REF][START_REF] Öncü | Cooperative adaptive cruise control: Network-aware analysis of string stability[END_REF]. In addition to lack of time bounds, there are two major weaknesses with CACC:

-What if a V2V message multicast by a platoon leader conflicts with a SC V2V message broadcast by a vehicle not member of that string?

-What if a V2V emergency message (e.g., "accident, break or change lane") multicast by a vehicle circulating ahead of a platoon leader is not received by that leader?

There is a need for (1) allowing any platoon member to multicast a SC V2V message (say M) to other members, (2) disseminating the contents of M downstream and upstream, despite failures of on-board systems and radio "links", deliveries completed in some worst-case bounded time (analytical expression given). This is foreign to the CACC concept. Moreover, some unique UTC time must be known to every member, time at which the action stipulated in M shall be performed (e.g., "new velocity is 45 km/h"). Note that doing this would achieve perfect string stability, unfeasible with CACC.

Whenever string members issue proposals (contents of various SC V2V messages) concurrently, some unique decision shall be made in (computable) bounded time by every member. Despite resemblance with Approximate Agreement or Consensus, these problems are not correctly solved with traditional algorithms, since physics matter with vehicular networks (see below).

D. Issue 9: Lateral safety-Needs beyond communications

With SC multi-lane scenarios (e.g., lane changes, merging lanes, overtaking, on-ramp merging), where one or multiple ad hoc short-lived groups of vehicles must coordinate their behaviors, we face problems similar to those investigated since the 80's in distributed cyber systems. Vehicles replace processes, and asphalt slots are the resources to be shared. Indeed, regarding distributed coordination for proactive safety in multi-lane scenarios, there is a need for solving such problems as Reliable Multicast, Non-Blocking Mutual Exclusion, Terminating Reliable Commit, Consensus (to name a few) in the presence of failures and concurrency [START_REF] Lynch | Distributed Algorithms[END_REF]. Let us give an example of a scenario where the classical specification of Consensus is invalid (picking up any proposal as the unique decision may make no sense at all). Consider a set of vehicles circulating in lane 1, small intervehicular spacing and within radio range of each other, approaching a highway entrance. They must decide which vehicle V shall decelerate in order to let an incoming vehicle (on ramp) enter lane 1 ahead of V. Classical consensus algorithms (devised for cyber systems) may elect a vehicle that is too far away from the highway entrance location. (There are publications of that sort.) Let us give another example. A long truck T circulates in lane j; one vehicle circulating in the lane left of j and another vehicle circulating in the lane right of j undertake concurrent conflicting lane changes, moving to the same "slot" ahead of T; with cameras or/and radars obstructed by T, either a crash occurs (vehicles do not see each other "in time") or none of the intended lane changes is performed. This is the wellknown starvation-free mutual exclusion problem. Which kind of communication-based algorithms would break ties, within very small latencies, under realistic assumptions?

In the presence of concurrent requests for joining a string issued by proximate vehicles, corresponding agreements shall be instantiated and terminated sequentially, despite being run concurrently. (Recall that there are physical actions undertaken when agreement is reached; totally ordered terminations are mandatory.) Besides solving scheduling problems (agreement requests may be assigned different priorities or termination deadlines), we are invited to show how strings can be endowed with the (short-lived, physical) isolation and atomicity properties. Indeed, in the absence of aborts (emergency conditions), all string members must have completed an agreed action (e.g., "reduce velocity to …") prior to performing a new one (e.g., "accept new members"). Which kinds of distributed algorithms (lock-based, timestamp-based, etc.) should we be looking for? Running a distributed agreement algorithm (or any kind of communication-based algorithm) takes time, especially under worst-case contention and failure conditions (goal Ω). This may turn out to be problematic in complex and demanding, albeit common, SC scenarios. This echoes the following challenging question.

E. Issue 10: Is fully automated driving achievable?

There are SC scenarios where not enough time is left for inter-vehicular negotiations. Consider on-ramp merging with highway lane 1 under dense traffic conditions-small intervehicular spacing (e.g., 2 m)-and significant velocities (e.g., 60 km/h), at rush hour. Every vehicle has very little time for deciding "who goes first". Humans are reasonably good at handling such scenarios, performing alternated intertwining of vehicles in lane 1. Question: Can this be fully automated, and what would it take for meeting that challenge? (We have a response.)

Can it be that the handling of every possible SC scenario on major roads and highways be fully automated, scenarios not well mastered by humans included? In other words, can it be that fully automated driving may surpass human driving on roads/highways, despite failures and limitations of onboard technologies? If the answer is no, then we know that we have to address the highly complex issues related to human factors and "authority sharing", possibly making goal Ω elusive. Research is underway to solve those numerous open problems that arise with fully automated driving on roads and highways, exploiting every appropriate technology (e.g., ultra-high frequency sensing, vision, radio-based and visible light communications), so as to fulfill goal Ω. It might be that the full potential of some cheap existing technologies has yet to be tapped.

IV. SUMMARY

The need for solving those problems quickly reviewed in this position paper has been stressed recently [START_REF] Dressler | Inter-vehicle communication: Quo vadis[END_REF]. We, among others, have been working on such problems. Issue 4 is addressed in [START_REF] Lann | Cohorts and groups for safe and efficient autonomous driving on highways[END_REF][START_REF] Lann | Integrated safety and efficiency in intelligent vehicular networks: Issues and novel constructs[END_REF]. Issues 7 and 9 are addressed in [START_REF] Lann | On the power of cohorts -Multipoint protocols for fast and reliable safety-critical communications in intelligent vehicular networks[END_REF]. Issues 8 and 9 are addressed in [START_REF] Lann | Safety in vehicular networks-On the inevitability of short-range directional communications[END_REF].