Ph.D Marco Congedo

Fernando H Lopes

Donald L Schomer

M.D Fernando H Lopes Da Silva

Chapter # 36 -Event-related potentials: General aspects of methodology and quantification

Keywords: Event-related potentials, EPs, wavelets, denoising, spatio-temporal filtering, PCA, CSTP, BSS, ICA, statistical testing

HAL is

Introduction

Electroencephalography as a general method for the investigation of human brain function includes ways of determining the reactions of the brain to a variety of discrete events. Some of these reactions may be associated with clear-cut changes in the EEG; some others, however, consist of changes that are difficult to visualize. The research field dedicated to the detection, quantification, and physiological analysis of those slight EEG changes that are related to particular events has steadily grown as a field of great interest in the last decades. These EEG changes may be treated globally under the common term event-related potentials (ERPs); a subset of the ERPs is constituted by the classic sensory (e.g. visual, auditory, somatosensory) evoked potentials (EPs). Generally there are three main areas of human research where ERPs play an important role: (A) clinical studies that aim at the identification of pathophysiological processes for diagnostic purposes and monitoring of brain and/or spinal cord functions; (B) neurocognitive and psychophysiological studies with the aim of disclosing neural mechanisms underlying, or associated with, cognitive and psychological phenomena; (C) brain-computer interfaces (BCI), where the classification of ERPs is used to convey messages directly from the brain to the external world without any muscle activity. The methods of analysis of ERPs have to be appropriately fit to the research question of interest. Thus, clinical applications need the knowledge of well standardized ERPs, as much as possible in quantitative terms so that deviations from the normality may be readily detectable; neurocognitive applications imply paying special attention to single-trial ERPs with the emphasis on their time-varying properties that may be analyzed along the same time scale as cognitive processes evolve; BCI studies require the application of robust methods of ERP detection, so that relevant brain signals may be used to operate external devices with a high level of reliability. This Chapter focuses on some general aspects of the methodology of analyzing ERPs, taking into consideration the different requirements alluded to above. Detailed descriptions of specific aspects of ERPs to stimuli of different modalities are presented in separate chapters of this book (visual modality in Chapter 38, auditory in Chapter 39, and somatosensory in Chapter 40), as well as general aspects of event-related (de)synchronization in Chapter 37. Specialized aspects of ERPs of children and infants are presented in Chapter 41 and the use of ERPs in the operating room is covered in Chapter 31. Frequency and time-frequency analysis methods that can be applied to the study of ERPs are presented in Chapter 44. There is a long list of important texts dedicated to the field of ERPs since the authoritative specialized textbook [START_REF] Regan | Human brain electrophysiology: Evoked potentials and evoked magnetic fields in science and medicine[END_REF]. A recent comprehensive "Introduction to the Event-Related Potentials technique" is [START_REF] Luck | An Introduction to the Event-Related Potential Technique[END_REF]. Time-Frequency analysis methods are extensively and clearly treated in [START_REF] Cohen | Analyzing Neural Time Series Data[END_REF]. This field has benefited from theoretical advances in signal analysis and the development of techniques in various research areas, since the questions raised by the need to identify signals as ERPs of small amplitude in a varying EEG of much larger amplitude (this applies equally to event-related fields recorded by MEG), are similar to those encountered in many different areas of physics and engineering. We should note that, although several sophisticated methods have been introduced in the field of ERPs, in the setting of the clinical routine simple averaging is still the dominant methodology used.

Basic Models of ERPs

For decades ERPs have been conceived as stereotyped fluctuations with approximately fixed polarity, shape, latency, amplitude and spatial distribution. According to this view, ERPs are considered independent of the ongoing EEG, i.e., ERPs, time-and phase-locked with respect to a given event, would be simply added to the ongoing EEG. This concept constitutes the socalled additive generative model. Nonetheless, several observations show that the ongoing synchrony within a neuronal population, manifest in spontaneous EEG oscillations, changes as neurons are recruited by a sensory stimulus that elicits also an attention reaction.

The possibility that evoked responses may be caused by a process of phase resetting was put forward based on the seminal findings [START_REF] Sayers | Objective evaluation of auditory evoked EEG responses[END_REF][START_REF] Sayers | The mechanism of auditory evoked EEG responses[END_REF][START_REF] Mcclelland | Towards fully objective evoked responses audiometry[END_REF], showing in the auditory system that stimuli at low intensity, near hearing threshold, evoke responses that can be discriminated better based on ensemble phase spectral measures as compared to amplitude measures. These findings indicate that the ERP may consist, at least partially, of an enhanced alignment of phase components of the spontaneous neuronal activity. In line with these seminal observations, several authors [START_REF] Basar | EEG-Brain dynamics: relation between EEG and Brain Evoked Potentials[END_REF][START_REF] Makeig | Dynamic brain sources of visual evoked responses[END_REF][START_REF] Penny | Event-related brain dynamics[END_REF] have proposed to consider ERPs as time/frequency modulations of the activity of local neuronal populations. From a theoretical point of view we noted in [START_REF] Lopes Da Silva | Event-related neural activities: what about phase?[END_REF] that it is not probable that two independent neuronal populations, one generating exclusively ongoing activity and another one responsible only for the evoked response, would co-exist side by side as distinct and independent entities in a given brain area. It is more likely that the same neuronal elements contribute to the generation of both types of activity. This same idea was formulated in [START_REF] Shah | Neural dynamics and the fundamental mechanisms of Event-Related brain potentials[END_REF],

where it was noted that EEG ongoing activity and EPs are generated by overlapping neuronal elements. According to this model, event-related responses may engage a group of neurons, by way of two basic mechanisms: either by enhancing (or decreasing) synchrony of on-going neuronal firing and/or by synchronizing the activity of specific neuronal populations. These two mechanisms are not mutually exclusive. Thus several combinations of neural processes may take place in the generation of evoked responses: narrow-band power decreases and increases (event-related spectral perturbations) as well as phase-locking and/or phase-resetting of ongoing EEG frequency components. Furthermore, since the ongoing EEG activity is commonly non-symmetric around zero, slow components may contribute to averaged responses, according to the potential asymmetry model in [START_REF] Mazaheri | Rhythmic pulsing: linking ongoing brain activity with evoked responses[END_REF] and [START_REF] Nikulin | Non-zero mean and asymmetry of neuronal oscillations have different implications for evoked responses[END_REF]. In an editorial where these and other fundamental aspects of the generation of evoked responses are analyzed, [START_REF] De Munck | How are evoked responses generated? The need for a unified mathematical framework[END_REF] stressed the need for a mathematical framework enabling the comparison of different models of ERP generation. We may add that a better understanding of the biophysics underpinning the generation of ERPs is an important prerequisite for advancing our knowledge in this field. The methods described in this Chapter are mainly based on the additive model. This may be considered a basic working hypothesis, which may yield meaningful results even if the data does not precisely conform to this model, as decades of practice have confirmed.

Time Averaging of ERPs

Ensemble Averaging

According to the additive model, ERP analysis in the time domain is based on two assumptions: (i) the electrical response evoked by the brain is time-and phase-locked to the event and (ii) the ongoing activity is a stationary 'noise'. In this way, the observed ERP can be decomposed in a signal term (assumed fixed across sweeps, although amplitude and latency inter-sweep variability should be taken into account, as discussed further below), plus a 'noise' term, which actually include all recordable activity besides the ERPs (instrumental noise, environmental artifacts, biological artifacts, induced EEG and ongoing EEG) and is highly variable from sweep to sweep. The former constitutes the generally called Evoked Response, or in classic EEG literature "Evoked Potential". ERP detection becomes, accordingly, a matter of improving the signal-to-noise ratio (SNR).

Let us consider a real case where it is of interest to study evoked potentials related to sensory stimuli. The presentation of the stimuli is repeated a number of times. Each repetition is named a sweep (or trial). The aim is to estimate the corresponding event-related responses. Throughout this Chapter we will make use of the following notation and nomenclature: there is a set of K sweeps, which we will index by k∈ {1,..,K}. EEG signals are recorded from N electrodes (also referred to as sensors or derivations) at a succession of equally spaced discrete time samples. T According to this model, the evoked responses in Q may be continuously modulated in amplitude and latency across sweeps. The single-sweep SNR is the ratio between the variance of σk Q(τk) and the variance of Nk. Since the amplitude of ERP responses on the average is in the order of a few μV, whereas the background EEG is in the order of several tens of μV, the SNR of single sweeps is very low. Therefore averaging, smoothing and/or filtering is warranted to improve the SNR.

The weighted and aligned arithmetic ensemble average of the K sweeps is given by

, ( 36.2)
where the hat symbol (ˆ) on σk and τk indicates that these quantities are unknown and therefore must be estimated. Of course, with all weights equal to one and time-shifts equal to zero, ensemble average estimation (Eq 36.2) reduces to the usual arithmetic mean. Using equal weights, the above estimator is unbiased if the noise term is zero-mean, uncorrelated to the signal, spatially and temporally uncorrelated and stationary. It is actually optimal if the noise is also Gaussian [START_REF] Lęski | Robust Weighted Averaging[END_REF]. However these conditions are never matched in practice. For instance, EEG

    ˆk k k k k k X X      
data are highly spatially and temporally correlated and typically contain outliers and artifacts, thus are non-stationary. As a rule of thumb, the SNR of the arithmetic ensemble average improves proportionally to the square root of the number of sweeps. In practice, it is well known that the arithmetic mean is an acceptable ensemble average estimator provided that sweeps with low SNR are removed and that enough sweeps are available.

In the following we consider several methods that have been proposed to improve the arithmetic average estimator. We will first review briefly univariate methods, and thereafter describe in some detail multivariate methods. Nowadays ERP recordings most often involve several channels and it is not uncommon to see studies using tens or hundreds of channels. The spatial diversity of the signal recorded at many derivations can be specifically exploited by spatial filtering to improve the ensemble average and single-sweep estimation, thus in practice univariate methods are slowly being replaced by multivariate methods.

Univariate Methods

The goal being suppressing noise while preserving the ERP components, early attempts addressed the univariate problem, that is, at each available sensor separately, by using Wiener filtering [START_REF] Doyle | Some comments on the use of Wiener-filtering for the estimation of evoked potentials[END_REF][START_REF] Albrecht | Wiener filtration versus averaging of evoked responses[END_REF]. In order to overcome deviations from signal stationarity, [START_REF] Weerd | A posteriori time-varying filtering of averaged evoked potentials. I. introduction and conceptual basis[END_REF][START_REF] Weerd | A posteriori time-varying filtering of averaged evoked potentials. II. mathematical and computational aspects[END_REF] introduced an adaptive time-varying Wiener filter capable of optimizing the estimation of both lowfrequency components of relatively long duration and high frequency components of short duration. In the same vein several approaches, borrowed from the field of signal processing, were proposed in the course of time: autoregressive models [START_REF] Cerutti | Single sweep analysis of visual evoked potentials through a model of parametric identification[END_REF], autoregressive moving average models [START_REF] Heinze | ARMA-filtering of evoked potentials[END_REF], Kalman filters [START_REF] Tarvainen | Estimation of nonstationary EEG with Kalman smoother approach: an application to event-related synchronization (ERS)[END_REF] and wavelets denoising [START_REF] Bartnik | Single evoked potential reconstruction by means of wavelet transform[END_REF][START_REF] Bertrand | Time frequency digital filtering based on an invertible wavelet transform: An application to evoked potentials[END_REF][START_REF] Schiff | Fast wavelet transformation of EEG[END_REF][START_REF] Demiralp | Decomposition of event-related brain potentials into multiple functional components using wavelet transform[END_REF][START_REF] Effern | Nonlinear denoising of transient signals with application to event-related potentials[END_REF][START_REF] Quian Quiroga | Obtaining single stimulus evoked potential with wavelet denoising[END_REF][START_REF] Quiroga | Single-trial event-related potentials with wavelet denoising[END_REF]. In the next section we consider the latter since it has interesting potentiality in neurocognitive studies, in particular.

Wavelet decomposition, denoising and single-trial analysis

Wavelet transforms yield a time-frequency decomposition of non-stationary signals [START_REF] Mallat | A theory for multiresolution signal decmposition: the wavelet representation[END_REF], as described further in Chapter 44, where the reader may find the basic concepts of the methodology of wavelet decomposition. In [START_REF] Aniyan | A wavelet based algorithm for the identification of oscillatory event-related potential components[END_REF] the authors noted that wavelet analysis provide reliable measures for the detection of ERPs, more robust than conventional filtering techniques, and summarize a number of applications of this methodology in the field of ERPs. Specifically regarding ERPs it is important to emphasize that these signals are non-stationary, and present different frequency components with different durations distributed along the time signal.

Typically the earlier components of ERPs have relatively high frequencies and short duration, while the later components have lower frequencies and extend over longer durations. These features make ERPs particularly suitable for an analysis using wavelet decomposition. The seminal papers [START_REF] Bartnik | Single evoked potential reconstruction by means of wavelet transform[END_REF][START_REF] Bertrand | Time frequency digital filtering based on an invertible wavelet transform: An application to evoked potentials[END_REF][START_REF] Tallon-Baudry | Stimulus Specificity of Phase-Locked and Non-Phase-Locked 40 Hz Visual Responses in Human[END_REF] paved the way for the application of ERPs wavelet decomposition.

The process of automatic denoising is, however, not simple. Several algorithms have been proposed with this purpose. Recently [START_REF] Ahmadi | Automatic denoising of single-trial evoked potentials[END_REF] introduced an algorithm for the automatic selection of wavelet coefficients (the so-called NZT algorithm) based on the inter-and intra-scale correlation of neighboring wavelet coefficients. An example of this application is shown in Fig 36.

1, illustrating the potential of this methodology to extract single-trial evoked potentials with an enhanced signal-to-noise ratio. Such methods are being actively explored particularly in neurocognitive studies of perception, learning and memory [START_REF] Rey | Single trial analysis of field potentials in perception, learning and memory[END_REF]. The possibility of reliably recording single-trial evoked potentials is particularly relevant, for example, in studies where it is of interest to study trial-to-trial variability in relation to perceptual performance, or to follow changes in latency of a given component associated with a memory task, for instance. In this way it is possible to reliably extract single-trial EPs from a session consisting of many stimuli presentations, while the subject is performing a cognitive task.

Multivariate Methods

Several multivariate methods have been developed with the aim of improving the estimation of ERP ensemble averages by means of spatial, temporal or spatio-temporal filtering. Spatial filtering is more common; according to the macroscopic model of EEG generation, the brain current sources of EEG/ MEG signals contribute linearly to the scalp electric/magnetic fields (see Chapter 4). The aim of a spatial filter is to find an optimal linear combination of the data across sensors to enhance the SNR. The aim of a temporal filter is to find an optimal linear combination of data across samples. One can design a spatial filter, a temporal filter or a spatiotemporal filter. The mathematical description of the three kinds of filters is presented in BOX I.

In this context we introduce briefly three methods that have similar objectives: Principal Component Analysis (PCA), the Common Spatial Pattern (CSP) and Blind Source Separation (BSS). The performance of these methods for removing eye artifacts is illustrated in Figs 36.2 and 36.3 using an example of a visual oddball paradigm eliciting a P300 for infrequent stimuli.

BOX I -Filtering

Given an ensemble average estimation X ∈ ℝ N.T as in Eq 36.2, where N is the number of electrodes and T the number of sample time points in a trial, the output of a spatial, temporal and spatiotemporal filter are the components given by, respectively, (

In Eq.36.3 B ∈ ℝ N.P is a spatial filter and D ∈ ℝ T.P a temporal filter matrix. For both we require 0<P<N, where P is named the subspace dimension. The upper bound for P is due to the fact that for ERP data we assume N<T and that filtering is achieved by discarding from the ensemble average estimation the N-P components not accounted for by the filter. The task of a filter is indeed to retain from the raw data a small number of meaningful components so as to suppress noise while preserving the relevant signal. Once the matrix B and/or matrix D are designed by means of optimization techniques, the spatio-temporal filtered ensemble average estimation is obtained by projecting back the components onto the sensor space, as ' X = AB T X DE T (36.4) where matrix A∈ ℝ N.P and E ∈ ℝ T.P are found so as to verify , (36.5) with I the identity matrix. If one wants to design a sole spatial filter (first expression in Eq 36.3), D and E are simply to be ignored in Eq 36. [START_REF] Sayers | Objective evaluation of auditory evoked EEG responses[END_REF]. Similarly, if one wants to design a sole temporal filter (second expression in Eq. 36.3), A and B are to be ignored.

T spatial temporal T spatio temporal Y B X Y X D Y B X D            T T B A E D I  

Principal Component Analysis

Principal component analysis (PCA) was the first filter of this kind to be applied to ERP data [START_REF] Donchin | A multivariate approach to the analysis of average evoked potentials[END_REF][START_REF] John | Experimental background: signal analysis and behavioral correlates of evoked potential configurations in cats[END_REF] and has been often employed since then [START_REF] Chapman | EP Component Identification and Measurement by Principal Component Analysis[END_REF][START_REF] Lagerlund | Spatial filtering of multichannel electroencephalographic recordings through principal component analysis by singular value decomposition[END_REF][START_REF] Kayser | Trusting in or breaking with convention: towards a renaissance of principal components analysis in electrophysiology[END_REF][START_REF] Dien | Evaluating two-step PCA of ERP data with Geomin, Infomax, Oblimin, Promax, and Varimax rotations[END_REF]. A long-lasting debate has concerned the choice of spatial vs. temporal PCA [START_REF] Lopes Da Silva | Event-related neural activities: what about phase?[END_REF][START_REF] Picton | Human Auditory Evoked Potentials[END_REF]. This debate, however, could be resolved performing a spatio-temporal PCA, combining the advantages of both. The PCA seeks uncorrelated components maximizing the variance of the ensemble average estimation; the first component explains the maximum of the variance, while the remaining components explain the maximum of the remaining variance, assuming that it is uncorrelated to all the previous. Hence, the variance explained by the N-P discarded components (P is the subspace dimension, see BOX I) explains the variance of the 'noise' that has been filtered out by the PCA. The spatial and/or temporal filter matrix B and D are found by singular value decomposition as the left and right singular vectors of the ensemble average given by Eq.(36.2). An example of spatial PCA applied to a P300 data set is shown in Fig. 36.2.

The Common Spatial and Temporal Pattern

References [START_REF] Koles | The Quantitative extraction and Topographic Mapping of the Abnormal Components in the Clinical EEG[END_REF][START_REF] Koles | EEG Source Localization: Implementing the Spatio-Temporal Decomposition Approach[END_REF] first adapted to EEG en extension of PCA proposed in [START_REF] Fukunaga | Statistical Pattern Recognition[END_REF]. The objective is obtaining a spatial filter separating EEG signals from distinct classes, with possible diagnostic value in the clinical domain or, more in general, distinguishing EEG signals obtained in different conditions [START_REF] Ramoser | Optimal Spatial Filtering of single trial EEG during Imagined Hand Movement[END_REF]. Specifically, the aim is finding spatial filters maximizing the ratio of the variance of the EEG obtained in two conditions. Since the resulting spatial components are common to EEG signals obtained in two different conditions, the approach is named Common Spatial Pattern (CSP). In contrast to the PCA, the CSP does not require orthogonality of the components. The ERPs components resulting from a spatial filter are given by the first expression of Eq. 36.3 in BOX I. A CSP adapted for time-and phase-locked activity such as ERPs was proposed in [START_REF] Rivet | xDAWN algorithm to enhance evoked potentials: application to brain-computer interface[END_REF]; the two conditions in this case are defined as the evoked activity and the evoked activity plus the noise, respectively, the noise being defined in section 3.1. Since the spatial filter maximizes the variance (energy) of the evoked activity with respect to the total EEG variance, it effectively seeks the optimal linear combinations of EEG derivations enhancing the SNR of the evoked activity. As for the PCA, the first P components are usually retained, with P smaller than N (see BOX I). A later extension of this method accounted for inter-sweep latency variability as well [START_REF] Souloumiac | Improved estimation of EEG evoked potentials by jitter compensation and enhancing spatial filters[END_REF]. Reference [START_REF] Yu | Bilinear common spatial pattern for single-trial ERPbased rapid serial visual presentation triage[END_REF] extended the idea to the spatiotemporal setting, yielding the common spatio-temporal pattern (CSTP), which components for ERPs are given by the third expression of Eq. 36.3 in BOX I. A closed-form solution for the CSTP accounting for inter-sweep latency and amplitude variability has been provided in [START_REF] Congedo | Spatio-temporal common pattern: A companion method for ERP analysis in the time domain[END_REF].

The reader can find comprehensive reviews on spatial filters and linear analysis of EEG in [START_REF] Parra | Recipes for the linear analysis of EEG[END_REF] and a tutorial on single-trial analysis and classification of ERP components in [START_REF] Blankertz | Single-trial analysis and classification of ERP components -a Tutorial[END_REF]. An example of CSTP applied to a P300 data set is shown in Fig. 36.2.

Blind Source Separation

Blind Source Separation is introduced and described in Chapter 44. For more details the reader is referred to that chapter. Here we briefly consider the specificities of its application as applied to ERP data. In Chapter 44 the two main families of BSS methods are considered; the methods based on high-order statistics (HOS), better known as independent component analysis (ICA)

and those based on second-order statistics (SOS).

Independent Component Analysis (ICA, HOS-based BSS) has been applied to a collection of ERP ensemble averages (e.g., [START_REF] Jung | Imaging brain dynamics using independent component analysis[END_REF][START_REF] Makeig | Blind separation of auditory event-related brain responses into independent components[END_REF]) or to unaveraged single sweeps (e.g., [START_REF] Jung | Removing electroencephalographic artifacts by blind source separation[END_REF]). In the former case the ICA decomposition focuses on evoked ERP components only, since time but not phaselocked components have been drastically attenuated by the averaging process. The latter approach is more general, since it allows the decomposition at the same time of evoked components, induced components, background EEG and artifact. It faces, however, the problem of the low SNR of evoked and induced ERP components in unaveraged data [START_REF] Jung | Imaging brain dynamics using independent component analysis[END_REF],

therefore in practice it requires a large and clean ERP recording set [START_REF] Makeig | Mining event-related brain dynamics[END_REF].

Second-order-statistics based BSS in the context of ERPs has been introduced in [START_REF] Congedo | EEG Source Analysis[END_REF]. In that work evoked components, induced components as well as background EEG and artifacts were modeled by means of spatial covariance matrices (CM). Computing these CM separately for an "error" class and a "correct" class of ERPs in an error-related potential experiment, the author was able to separate the source responsible for an evoked negativity component and the source responsible for an induced event-related synchronization, despite the two phenomena peaked at the same time (500 ms post-stimulus) and had very similar spatial distribution. An example of BSS based on second-order statistics applied to the same data set used in 4 Special Considerations

Overlapping ERPs

Special care in ERP time domain analysis must be undertaken when we record overlapping ERPs, since in this case estimation (36.2) is biased [START_REF] Ruchkin | An Analysis of Average response Computations based Upon Aperiodic Stimuli[END_REF][START_REF] Woldorff | Distortion of ERP averages due to overlap from temporally adjacent ERPs: analysis and correction[END_REF]. ERP are non-overlapping if the minimum inter-stimulus interval (ISI) is longer than the length of the latest recordable ERP component. There is today increasing interest in paradigms eliciting overlapping ERPs, such as some odd-ball paradigms and rapid image triage [START_REF] Yu | Bilinear common spatial pattern for single-trial ERPbased rapid serial visual presentation triage[END_REF], which are heavily employed in braincomputer interfaces for increasing the transfer rate [START_REF]Brain-Computer Interfaces. Principles and Practice[END_REF] and in the study of eye-fixation potentials, where the "stimulus onset" is the time of an eye fixation and saccades follow each other rapidly [START_REF] Sereno | K Measuring word recognition in reading: eye-movements and event-related potentials[END_REF]. The strongest distortion is observed when the ISI is fixed. Less severe is the distortion when the ISI is drawn at random from an exponential distribution [START_REF] Ruchkin | An Analysis of Average response Computations based Upon Aperiodic Stimuli[END_REF]. Remedies for overlapping ERPs have been proposed by a few authors. The method in [START_REF] Woldorff | Distortion of ERP averages due to overlap from temporally adjacent ERPs: analysis and correction[END_REF] takes into consideration only the case of maximum three overlapping ERPs, and thus it is not general. The multivariate regression method proposed in [START_REF] Rivet | xDAWN algorithm to enhance evoked potentials: application to brain-computer interface[END_REF] and an improved version formulated in [START_REF] Souloumiac | Improved estimation of EEG evoked potentials by jitter compensation and enhancing spatial filters[END_REF] consider any occurrence and any form of overlapping, that is overlapping of any number of ERPs of the same as well as of different classes, in any combination. A further extension of the multivariate regression method, accounting for amplitude weights and latency time-shifts in the resulting ensemble average estimation, has been considered in [START_REF] Congedo | Spatio-temporal common pattern: A companion method for ERP analysis in the time domain[END_REF]. Reference [START_REF] Smith | Regression-based estimation of ERP waveforms: II. Nonlinear effects, overlap correction, and practical considerations[END_REF] discusses a univariate regression method and other weighting procedures that can be used to refine the study of the ERPs in relation to some properties of a stimulus. Note that the regression method is very general in that it reduces to the usual averaging when no overlapping is present [START_REF] Congedo | Spatio-temporal common pattern: A companion method for ERP analysis in the time domain[END_REF].

Latency and Amplitude Variability

In the section 3.2.1 we emphasized the use of methods with the aim of obtaining reliable estimates of single-trial ERPs, particularly in the case of neurocognitive studies, where it is relevant to relate dynamic changes of the amplitude of a peak or its latency of a single-trial ERP to the performance of a subject in tasks, where the neural correlates of attention, perception or memory are the targets of the investigation. Another face of the same coin, however, consists in improving the estimation of an average ERP in the presence of latency jitter or amplitude variations. According to this perspective one assumes that inter-sweep latency variability should be eliminated.

The multivariate ensemble average estimation introduced in (36.2) accounts for both latency and amplitude variability by means of the τ (latency) and σ (amplitude) variables therein introduced. Indeed, the usual approach in ERP studies requires the estimation of a time-shift (in sample units) and a (non-negative) weight for each sweep. An appropriate estimation of the time shifts aims at aligning the ERP peaks. An appropriate estimation of weights dampens the contribution of sweeps contaminated by artifacts and strong spontaneous background activity.

Using optimization techniques to estimate either variable, an improvement of the ensemble average signal to noise ratio is expected. Of course, estimating both time shifts and weights is preferable.

In this context several approaches have been proposed to optimize the estimation of ERPs, starting from Woody's adaptive matched filter method [START_REF] Woody | Characterization of an adaptive filter for the analysis of variable latency neuroelectric signals[END_REF], where the cross-correlation between each sweep and a template is computed to estimate the time by which each sweep should be shifted in order to obtain the maximal cross-correlation with the template. The method was extended in [START_REF] Jaśkowski | Amplitudes and latencies of single-trial ERP's estimated by a maximumlikelihood method[END_REF] allowing to compensate not only for latency, but also for amplitude variability. Several modifications of this basic approach have been proposed [START_REF] Souloumiac | Improved estimation of EEG evoked potentials by jitter compensation and enhancing spatial filters[END_REF][START_REF] Congedo | Spatio-temporal common pattern: A companion method for ERP analysis in the time domain[END_REF][START_REF] Cabasson | Time Delay Estimation: A New Insight Into the Woody's Method[END_REF].

Refining the ERP averaging procedure

In addition to the methods presented above, a number of other statistical techniques can be used for refining the averaging procedure applied to ERPs. Instead of computing the average, according to Eq 36.2, it has been proposed to use the median, trimmed mean or trimmed Lmean (TL-mean) [START_REF] Leonowicz | Trimmed estimators for robust averaging of eventrelated potentials[END_REF][START_REF] Hosking | L-moments: analysis and estimation of distributions using linear combinations of order statistics[END_REF]. The simplest method of this family is to use the median, i.e., the middle observation in case of odd number of observations or the average of the two middle observations in the case of even number of observations. In the computation of the "trimmed mean" a pre-defined percentage of extreme values are given weight zero, i.e. are discarded, while the remaining observations keep equal weights; the trimmed L-mean applies higher weights for the observations near the median. Examples of these different computational methods are given in [START_REF] Leonowicz | Trimmed estimators for robust averaging of eventrelated potentials[END_REF]. Extensive testing has shown that the median leads to noisy ensemble average estimates with spurious high-frequency components [START_REF] Lęski | Robust Weighted Averaging[END_REF][START_REF] Leonowicz | Trimmed estimators for robust averaging of eventrelated potentials[END_REF]. Smoothing the ERP sweeps by low-pass filtering (e.g. by a moving average filter) can yield useful results in this context [START_REF] Möcks | Does Filtering and Smoothing of Average Potentials really Pay? A Statistical Comparison[END_REF].

Estimating the onset of an ERP

The researcher using ERPs is often confronted with the question of how to estimate the onset of an ERP. A useful method, the SD method, based on the t-test, consists in setting a threshold at 3 standard deviations (SDs) from the mean of the pre-stimulus baseline signal as exemplified in Fig 36.4. Reference [START_REF] Letham | Statistically robust measurement of evoked onset latencies[END_REF] proposed an alternative method called the "median rule". It makes use of boxplot rules for outlier detection using a threshold that is set based on the inter-quartile range. The onset latency is the first post-stimulus point above this threshold. Simulations studies demonstrated that the SD method is more sensitive to outliers than the "median rule" method.

The latter does not make assumptions with respect to the distribution of the data, and can be applied to single-sweep ERPs. In cases where the baseline is of good quality as those presented in Fig 36 .4, the differences between the two methods are small.

Frequency and Time-Frequency Domain Analysis

Analysis in Frequency and Time-Frequency domains of EEG signals in general terms is described in detail in Chapter 44, to which the reader is referred. Although in ERP studies representations in the time domain are much more common, there is a large body of studies that used frequency domain analysis of ERPs, particularly elicited by steady-state visual stimuli stimuli (SSVEPs), since the pioneering work of the Amsterdam's school of van der Tweel, [START_REF] Spekreijse | Sequential analysis of the visual evoked potential system in man: nonlinear analysis of a sandwich system[END_REF] and in [START_REF] Regan | Human brain electrophysiology: Evoked potentials and evoked magnetic fields in science and medicine[END_REF]. This early work has yielded significant contributes to a better understanding of the physiology of the visual system as reviewed in [START_REF] Regan | Some early uses of evoked brain responses in investigations of human visual function[END_REF]. Reference [START_REF] Vialatte | Steady-state visually evoked potentials: focus on essential paradigms and future perspectives[END_REF] pointed out the relevance of SSVEPs in new applications in brain-computer interface systems. Besides SSVEP studies, also steady-state amplitude-or frequency-modulated sound stimuli are used to investigate functional properties of the auditory system; the corresponding SSAEPs can be analyzed using frequency analysis [START_REF] Picton | Potentials evoked by the sinusoidal modulation of the amplitude or frequency of a tone[END_REF][START_REF] Picton | Guidelines for using human event-related potentials to study cognition: recording standards and publication criteria[END_REF] and applied in the objective evaluation of auditory thresholds, and also to analyze supra-threshold hearing [START_REF] Picton | Human auditory steady-state responses: the effects of recording technique and state of arousal[END_REF].

Topography and Source Localization

Scalp topography and source localization of ERPs are the basic tools to perform analysis in the spatial domain of the electrical activity generating ERPs. This is fundamental for linking experimental results to brain anatomy and physiology. It also represents an important dimension for studying ERP dynamics per se, complementing the information provided in time and/or frequency dimensions [START_REF] Lehmann | Spatial Analysis of evoked potentials in mana review[END_REF]. The spatial pattern of ERP scalp potential or of an ERP source component provides useful information to recognize and categorize ERP features, as well as to identify artifacts and background EEG. Current research typically uses several tens and even hundreds of electrodes covering the whole scalp surface. An increasing number of high-density EEG studies involve realistic head models for increasing the precision of source localization methods (for the biophysical aspects see Chapter 4, and for source imaging techniques see Chapter 45). Advanced spatial analysis with high spatial resolution has therefore become common practice in ERP research. A comprehensive tutorial of topographic ERP analyses can be found in [START_REF] Murray | Topographic ERP analyses: a step-by-step tutorial review[END_REF]. In contrast to continuous EEG, ERP studies allow the generation of topographical and source localization maps for each time sample. This is due to the SNR gain engendered by averaging across sweeps. The SNR of spatial analysis increases with the number of averaged sweeps. One can further increase the SNR by using multivariate filtering methods, as discussed above. An example is given by the application of BSS to ERPs, yielding a number of time series with associated spatial patterns that are fixed for the whole duration of the sweeps (Fig 36 .3).

Statistical Testing

ERP studies involve both space (scalp location) and time dimensions (latency and duration of the ERP components). Frequency and time-frequency-domain variables may also be added depending on the objective of the study. Typical hypotheses to be tested in ERP studies concern differences in central location (mean) between and within subjects (t-tests), the generalization of these tests to multiple experimental factors extending to more than two levels, including their interaction (ANOVA) and the correlation between ERP variables and subject characteristics or behavioral variables such as response-time, age of the participants, complexity of the cognitive task, etc. (linear and non-linear regression, ANCOVA). These questions entail statistical analysis of ERPs, which may be rather complex and cumbersome. This Chapter cannot deal with these statistical questions in depth. Nonetheless it is useful to call attention to a number of specific questions that appear frequently in the field of ERP studies. In these studies it is common to have data sets constituted by ERPs recorded at, say, 32 scalp derivations and 128 sampling points, while the objective may be to test the null hypothesis that the mean ERP amplitude does not differ substantially in two experimental conditions (for ex. in a treatment versus a control group), for each time point and each derivation. Such an experiment requires testing 128x32=4096 hypotheses. This yields the well-known multiple-comparisons problem [START_REF] Hochberg | Multiple Comparison Procedures[END_REF], which is very common in ERP studies: whereas a statistical test guarantees that the probability to reject a null hypothesis when it is actually true is inferior to a desired probability (the α level of the test), this is no more guaranteed when multiple hypotheses are tested at once.

Two families of procedures have been applied in ERP studies to deal with the multiple comparison problem: those controlling the family-wise error rate (FWER) and those controlling the false-discovery rate (FDR).

The family-wise error rate (FWER) is the probability of making one or more false rejections among all tested hypotheses. The term "family" represents the collection of hypotheses that are being considered for joint testing [START_REF] Lehmann | Generalizations of the family error rate[END_REF]; this is what is meant by the expression family-wise error rate (FWER). The popular Bonferroni procedure [START_REF] Shaffer | Multiple Hypothesis testing[END_REF] belongs to this family. It consists in adjusting the alpha level to α/M, where M is the number of hypotheses being tested. All Bonferroni-like procedures fail to take into consideration explicitly the correlation structure of the hypotheses, thus they are unduly conservative, the more so the higher the number of hypotheses to be tested.

An important general class of test procedures controlling the FWER while preserving power is known as permutation tests based on maximal statistics, tracing back to the seminal work of Ronald Fisher [START_REF] Fisher | Design of Experiments[END_REF]. Permutation tests based on maximal statistics are able to account adaptively for any correlation structure of hypotheses, regardless their form and degree. Also, they do not need a distributional model for the observed variables, e.g., Gaussianity, as required by t-tests, ANOVA, etc. Given these characteristics, permutation tests are ideal options for testing hypotheses in ERP studies and have received much attention in the neuroimaging community (for a review see [START_REF] Petersson | Statistical limitations in functional neuroimaging II. Signal detection and statistical inference[END_REF] and for excellent treatises see [START_REF] Pesarin | Multivariate Permutation tests[END_REF][START_REF] Westfall | Resampling-Based Multiple Testing[END_REF]).

Another family of testing procedures controls the false discovery rate (FDR). The FDR is the expected proportion of falsely rejected hypotheses [START_REF] Benjamini | Controlling the False discovery Rate: A Practical and Powerful Approach to Multiple Testing[END_REF]. Indicating by R the number of rejected hypotheses and by F the number of those that have been falsely rejected, simply stated the FDR controls the expectation of the ratio F/R. This is a less stringent criterion as compared to the FWER, since, as the number of discoveries increases, we allow proportionally more errors [START_REF] Benjamini | Controlling the False discovery Rate: A Practical and Powerful Approach to Multiple Testing[END_REF][START_REF] Benjamini | The control of the false discovery rate in multiple testing under dependency?[END_REF]. The FDR procedure and its version for dependent hypotheses have been the subject of several improvements (e.g., [START_REF] Yekutieli | Hierarchical False Discovery Rate-Controlling Methodology[END_REF]).

A very efficient approach in ERP analysis is the supra-threshold cluster permutation test included in the EEG toolbox "Fieldtrip" in [START_REF] Oostenveld | FieldTrip: Open Source Software for Advanced Analysis of MEG, EEG, and Invasive Electrophysiological Data[END_REF], as described in [START_REF] Maris | Nonparametric statistical testing of EEG-and MEG-data[END_REF]. The reader can find in these references as well as in the original and pioneering work of [START_REF] Holmes | Nonparametric Analysis of Statistic Images from Functional Mapping Experiments[END_REF] useful tips to realize this kind of testing; in ERP data we may assume that the effect of interest is concentrated simultaneously along some specific dimensions. For example, in testing the mean amplitude difference of a P300 ERP, one expects the effect to be concentrated along time and space: the former around 300-500 ms, and the latter at midline central and adjacent parietal locations. This leads to a typical correlation structure of hypothesis in ERP data; under the basic null hypothesis the effect would instead be scattered all over both the whole time and spatial dimensions. The concentration of the effect along relevant dimensions is the rationale of the supra-threshold cluster size test. An example in the time-space ERP domain is shown in Figure 36.5.

Classification of Single-Sweeps

The goal of a classification method is to automatically estimate the class to which a singlesweep belongs. The task is challenging because of the very low amplitude of ERPs as compared to the background EEG. Large EEG artifacts, the non-stationary nature of EEG and inter-sweep variability exacerbate the difficulty of the task. Although single-sweep classification has been investigated since a long time [START_REF] Donchin | Discriminant analysis in average evoked response studies: the study of single trial data[END_REF], it has recently received a strong impulse thanks to development of ERP-based brain computer interfaces (BCI: [START_REF]Brain-Computer Interfaces. Principles and Practice[END_REF]). In fact, a popular family of such interfaces is based on the recognition of the P300 ERP. The most famous example is the P300 Speller [START_REF] Farwell | Talking off the top of your head: toward a mental prothesis utilizing event-related brain potentials[END_REF][START_REF] Krusienski | A comparison of classification techniques for the P300 Speller[END_REF], a system allowing the user to spell text without moving, but just by focusing attention on symbols (e.g., letters) that are flashed on a virtual keyboard.

Classification methods typically involve the following steps:

(i) describing each ERP sweep by a set of features: in the simplest case, the amplitude values of time samples and derivations concatenated so as to form a vector, (ii) using a training set, that is, a number of labeled sweeps for all classes, to find a discriminant function that can partition the space occupied by all objects so that unique patterns corresponding to different classes can be identified (for example pathological versus healthy subjects), (iii) determining the class to which a new object (i.e., an unlabeled single-sweep ERP) belongs; this is accomplished by computing a discriminant score for the object to be classified. Thus, each sweep is classified in the class corresponding to the subspace within which the discriminant score falls.

The fundamental criterion for choosing a classification method is the achieved accuracy for the data at hand. However, other criteria may be relevant. In most applications training of the classifier (step ii. above) starts with a calibration session carried out just before the actual session.

Classification methods are characterized by the set of features and the discriminant function they employ. The approaches emphasizing the definition of the set of features attempt to increase the SNR of single-sweeps by using multivariate filtering, as discussed previously in this Chapter, but specifically designed to increase the separation of the classes in a reduced feature space where the filter projects the data [START_REF] Rivet | xDAWN algorithm to enhance evoked potentials: application to brain-computer interface[END_REF][START_REF] Yu | Bilinear common spatial pattern for single-trial ERPbased rapid serial visual presentation triage[END_REF]. Without entering in technical details of the methodologies involved in this process, we may refer the reader to the useful tutorial dealing with the single-trial analysis and classification of ERPs in [START_REF] Blankertz | Single-trial analysis and classification of ERP components -a Tutorial[END_REF].

Recently, it has been recommended to start regarding the pre-processing, feature extraction and discrimination not as isolated processes, but jointly, as a whole [START_REF] Mak | Optimizing the P300-based brain-computer interface: current status, limitations and future directions[END_REF][START_REF] Jrad | sw-SVM : sensor weighting support vector machines for EEG-based Brain-Computer Interfaces[END_REF]. An approach that features at the same time good accuracy, good generalization and good adaptation capabilities in the case of ERP data has been recently borrowed from the field of Riemannian geometry [START_REF] Congedo | EEG Source Analysis[END_REF][START_REF] Barachant | Multi-Class Brain Computer Interface Classification by Riemannian Geometry[END_REF][START_REF] Barachant | Classification of covariance matrices using a Riemannian-based kernel for BCI applications[END_REF].

  is the number of sampled time points in a sweep. A sweep starts at a given time related to the presentation of a stimulus. The k th observed sweep for a given class of ERP signals is held matrix contains N rows and T columns of real numbers (the electric potential). The additive generative model for the observed sweep of a given class can then be written representing the evoked responses for the class under analysis, σk are (optional) positive scaling factors accounting for inter-sweep variations in the amplitude of Q, τk are (optional) time-shifts, in samples units, accounting for inter-sweep variations in the latency of Q, and Nk N×T  are matrices representing the noise term added to the k th sweep.

Figure 36 . 1 .

 361 Figure 36.1. Result of the application of the automatic denoising algorithm applied to a VEP (visual evoked potential) recorded from an occipital site. (a) the original VEP is in black and the denoised version of it in red; (b) wavelet decomposition showing the wavelet coefficients chosen automatically for denoising by the NZT algorithm; (c) Contour plot of the amplitude of the original single-trial VEPs of successive trials as a function of time (stimulus presentation at moment 0). (d) Idem but for the denoised single-trial VEPs. The amplitude scale in color is indicated by the bar on the left. Note that the components (N200, P111 and P300) of the single-trial VEPs are much more evident in the denoised traces shown in (d). (Adapted with permission from [33] Ahmadi, M., Quian Quiroga, R. Automatic denoising of single-trial evoked potentials. NeuroImage, 2015; 66, 672-680).

Figure 36 . 2 .

 362 Figure 36.2. Comparison of the arithmetic ensemble average estimations (EA) with the ensemble average estimation obtained by a PCA (with P=4, see BOX I) and a CSTP (with P=12). Data is from one subject performing a visual oddball ERP paradigm. The averages are computed on 80 1s sweeps following the infrequent stimulus (stimulus onset=time 0). All plots have the same horizontal and vertical scales. All available sweeps have been used and no artifact rejection has been performed on the recording. Note that only the CSTP method filters out the eye-related artefact peaking at about 500 ms, better visible at derivations FP1 and FP2.

Fig 3 . 2

 32 Fig. 36.3.

Figure 36 . 3 .

 363 Figure 36.3. SOS-based blind source separation of the ERP data presented in Fig. 36.2. The left plot of the top figure shows the 16 temporal components separated by BSS. The associated spatial patterns are shown in the bottom figure in the form of monochromatic topographic maps. The sign of the potential is arbitrary in BSS analysis, thus in these maps positive and negative potentials are plotted with the same color. The scale of the components is also arbitrary, thus each map is scaled to its own (arbitrary) maximum. The plots in the top figures entitled "ERPsource 2" and "ERP -source 7" show the ensemble average of Fig 36.2 obtained retaining only the second and seventh BSS component, i.e., they show the ERP ensemble average produced by these two components once all the others have been filtered out. Note that component 2 focuses on the eye-related artifact responsible for the peak visible in the ensemble average at about 500 ms at derivations FP1 and FP2 (Fig. 36.2), separating this feature from the P300 component, which has a maximal amplitude at the vertex, that is clearly identified by component 7.

Figure 36 . 4 .

 364 Figure 36.4. MEG source-specific time course for the Auditory (A1, Heschl's gyri) cortex (light blue background) and Visual (V1, calcarine fissure) cortex (yellow background) to stimuli of both modalities (auditory in black and visual in red). The circular insets show the onset of each response, indicated by the vertical lines (red for visual and black for auditory). Both sensory-specific and cross-sensory ERPs are shown. Note that the onset latencies of the sensory-specific stimulation are shorter than those of the cross-sensory activation, particularly in the case of the auditory modality. Time scales -200 to 1000ms poststimulus, stimulus duration 300ms (black bar). (Adapted with permission from [68] Letham, B, Raij T. Statistically robust measurement of evoked onset latencies. J. Neurosci. Methods, 2011; 194, 374-379, see Fig 3 therein).

Figure 36 . 5 .

 365 Figure 36.5. a): Grand ensemble average error-related potentials (19 subjects) for "Correct" and "Error" trials at different electrodes, the location of which is schematically indicated in the circular heads below (in b) for three time samples. The supra-threshold cluster size permutation test applied in time and spatial dimension, with α=0.05, yields three time windows, indicated in (a) by the grey areas, where there were significant different between the two sets of ERPs, corresponding to the "Correct" and "Error" trials. The significant differences between the two sets of ERPs were the following: a significant positivity for Error trials was found at time window 320-400ms at electrode Cz (p<0.01), a significant negativity for Error trials at time window 450-550ms at clustered electrodes Fz, FCz, Cz (p <0.01) and a significant positivity for Error trials at time 650-775ms at clustered electrodes Fz, FCz (p = 0.025). Significant clustered derivations are represented by white disks in b). (Adapted, with permission, from [56] Congedo M. EEG Source Analysis. HDR thesis presented at Doctoral School EDISCE, University of Grenoble Alpes, 2013, 268 pp).

Fig 36 . 6

 366 Fig 36.6 illustrates the performance of this method compared to two others: the classic (uncorrected) t-test and the t-test adjusted by Bonferroni correction. The three methods were applied to a MEG Event-Related Potentials recorded from the temporal cortex in one subject, in a linguistic experiment separately for congruent and incongruent sentences endings. It can be seen that the classic t-test yields a too large number of rejections of the null-hypothesis, i.e., of false discoveries, the Bonferroni-corrected test yields a very conservative result, whereas the permutation test yields a result that is consistent for eight different test statistics.

Figure 36 . 6 .

 366 Figure 36.6. Statistical testing of MEG evoked responses obtained in an experiment where subjects heard sentences where the last word was either semantically congruent or incongruent. The response of interest is the ERP elicited by the last word in the two conditions. The aim was to test the differences between the latter. Panel (a), evoked responses of one single subject at one sensor are shown, separately for congruent (dotted line) and incongruent (solid line) sentence endings. Panel (b), displays the time series of sample-specific t-values. Panel (c), presents the significant samples separately for each of three statistical procedures: -sample-specific t-tests at the uncorrected 0.05-level (two-sided), -sample-specific t-tests at the Bonferroni corrected level of 0.05/600 = 0.00008 (two-sided), and (3) a non-parametric test based on clustering of adjacent time-samples (cluster mass test). Note that major result is an ERP that is most prominent in the interval 400 -800ms; but the t-test procedure yields a large (8 clusters) number of samples where the uncorrected 0.05 level is crossed; on the contrary lowering α level according to Bonferroni procedure delivers a very conservative estimate; the non-parametric test, based on the permutation distribution of the maximum of the cluster-level statistics, results in a more robust estimate (see methodological details in [88]) (Adapted with permission from Fig 1 of Oostenveld, R., Fries, P., Maris, E., Schoffelen, J.M., FieldTrip: Open Source Software for Advanced Analysis of MEG, EEG, and Invasive Electrophysiological Data. Computational Intelligence and Neuroscience, 2011; 156869).


Martin Vassor

Jean-Bernard Stefani

Checkpoint/rollback vs causally-consistent reversibility

come

Checkpoint/rollback vs causally-consistent reversibility

Introduction

Motivations. Undo capabilities constitute a key and early example of reversibility ideas in languages and systems [?]. Checkpoint/rollback schemes in distributed systems [?] constitute prime examples of such capabilities and of their application to the construction of fault-tolerant systems. There are certainly distinctions to be made between complete reversibility and checkpoint/rollback schemes, if only in terms of the granularity of undone computations, and in terms of the space/time trade-offs that can be made, as illustrated in [?] that advocates the use of a reversible language for high performance computing applications. However, one can ask what is the exact relationship between the checkpoint/rollback schemes that have been proposed in the literature, and concurrent reversible models of computation which have been proposed in the past fifteen years, especially the causally consistent ones that have been proposed following Danos and Krivine's work on Reversible CCS [?]. More specifically, one can ask what is the relationship between checkpoint/rollback distributed algorithms based on causal logging [?], and the distributed algorithms which are implicit in the semantics of reversible concurrent languages such as in the low-level semantics of the reversible higher-order calculus studied in [?]. The question is particularly relevant in these cases, because both exploit causal relations between events in distributed computations. But are these relations identical, and how do associated algorithms compare? Comparing causal relations in concurrent models is in itself not trivial. For instance, recent works on concurrent reversible calculi, e.g. [?,?] show that even when dealing with the same model of computation, causal information can be captured in subtly different ways. To the best of our knowledge, the question of the relationship between checkpoint/rollback and reversible models of computation has not been tackled the literature. This paper Contributions We show a rather tight relationship between rollback based on causal logging as performed in Manetho and the rollback algorithm of roll-π. Our main result is that lr-π can simulate scl (hence, so does the regular roll-π), where the notion of simulation we use is that of weak barbed simulation [?], and that the converse only holds for a weaker version of lr-π, where possible rollbacks are restricted. This shows that the causal information captured by Manetho is essentially the same as that captured by roll-π, and that the difference between the two schemes lies in the capabilities of the rollback operations, which are limited in Manetho (as in most checkpoint/rollback schemes) to rolling back to the last checkpointed state.

Outline. The paper is organized as follows. Section ?? briefly presents Manetho, formally defines scl and proves the soundness of rollback in scl. Section ?? introduces the lr-π calculus and shows that it can be faithfully encoded in the roll-π) calculus. Section ?? presents our main result. Section ?? discusses related work. Section ?? concludes the paper. Due to the size limit, proofs of our results are not presented in the paper, but they are available online [?].

Formalizing Manetho

Manetho

Manetho [?] is a checkpoint-rollback protocol that allows a fixed number of processes, that communicate via asynchronous message passing, to tolerate process crash failures 1 . To achieve this result, each time a non-deterministic event happens, the concerned process enters a new state interval. Processes keep track of the current state interval causal dependencies in an antecedence graph. Processes can take checkpoints and, upon failure, the failed process rolls back to a causally consistent state from this checkpoint. For instance, in the execution in Figure ??, at some point, process p receives a message m 3 from process q. Since delivering a message is a non-deterministic event, p enters a new state interval si 1 p . When sending a message, the sender piggybacks its antecedence graph in the message. This allows the receiver to update its own antecedence graph. For instance, in Figure ??, when q sends message m 3 to p, it piggybacks the antecedence graph shown in Figure ??, which p uses to update its own antecedence graph, by merging them, resulting in the antecedence graph shown in Figure ??. Moreover, when a process sends a message, it keeps a local copy of the message.

When a failure occurs, for instance process q in Figure ??, the process recovers from its last checkpoint (for instance checkpoint c 1 q ). Other processes can inform the recovering process of its last known state interval. In the example, process q sent a message m 3 to process p when it was in state interval si 2 q . Hence, the antecedence graph of the state interval si 2 q is a subgraph of the antecedence graph of state interval si 1 p : process p can then retransmit it to q in an out of band message (the red message from p to q in Figure ??). With its antecedence graph recovered, the process can replay the message sequence to recover its last state interval globally known, by asking for copies of the received messages (message m 2 ). Notice that the recovering process does not resend its message (internally, it only replays the sending event without actually sending the message in order to keep track of message counter values).

Notice that during the recovery, only the recovering process changes: apart from efficiency considerations, this is to ensure Manetho processes that use checkpoint/rollback can coexist with replicated processes.

Formalization

We formalize Manetho processes by means of a small language of configurations, called scl. Following the original description of Manetho [?], we model 1 The description of the Manetho protocol differs slightly between the publication

[?] and Elnozahy's PhD thesis [?]. In particular, the latter involves a coordinating checkpointing scheme, which is not the case in the former. For the sake of simplicity, in this paper we follow the description in [?]. Checkpoint coordination in any case is not necessary for the correct operation of the recovery process in a causal logging checkpoint/rollback scheme. In [?] it is essentially used to simplify the garbage collection of recovery information. a configuration C as a tuple of three elements: (i) a set of processes M; (ii) a set of messages L; (iii) a set of checkpoints K. Checkpoints are just copies of processes, together with a checkpoint identifier.

p q r c 0 p c 0 q c 1 q c 0 r si 0 p si 0 q si 0 r m1 si 1 q m2 si 2 q m3 si 1 p si 1 q AG si 2 q m 2 si 2 q
The processes themselves are composed of a program P, an antecedence graph AG , and a record of sent messages R. They also contain a process identifier k (the set of process identifiers is noted P) and three counters si, inc, ssn which respectively record the state interval, the number of incarnations (i.e. the number of times the process has failed and recovered) and the number of messages sent. Originally, in Manetho, a receive counter is also present. We do not include it in our formalisation, for it can be retrieved from the antecedence graph (the number of messages received is the number of tree merges). We can also retrieve which message triggered each state interval (this information is encoded in each antecedence graph node with a special case for initial state intervals). Finally, processes are decorated with a mark which is used to separate the regular evolution of processes from their recovery.

The complete grammar of configurations is provided in Figure ??, where an empty set is denoted by ε. In the term receive(source, X) • P, source and X are bound in P. In the term send(dest, P) • Q, dest is a process id, constant or variable, and P is a closed process. An antecedence graph AG is a graph whose nodes are tuples si, ssn . Notice that scl is a higher-order language, where processes exchange messages which carry programs. Although strictly not necessary to model Manetho configurations, this allows us to accommodate very simply processes with unbounded executions. Consider for instance the following configuration C:

k 0 , P, AG 0 , si 0 , inc 0 , ssn 0 , R 0 || k 1 , Q, AG 1 , si 1 , inc 1 , ssn 1 , R 1 , L, K with Q = receive(source, X)•send(k 0 , send(k 1 , X)•receive(source, Y )•Y )•X and P = send(k 1 , Q) • receive(source, Y ) • Y .
This configuration evolves into itself after the exchange of two messages, from k 0 to k 1 and from k 1 to k 0 .

For the sake of conciseness, we use the notation inc(k) to denote the incarnation number of the process with process id k.

Starting and Correct Configurations

We now define the set of starting configurations: C s scl . A configuration C s = M, L, K is said to be starting if and only if:

all X and dest are bound; -T i are not marked; there is no pending message: L = ∅; the set of checkpoint contains a checkpoint of the initial state of each process:

K = k∈P { cid 0 k , k, P k , AG k , si k , inc 0 k , ssn 0 k }; -processes are not crashed: ∀T i ∈ M • T i = k, ⊥, AG, si, inc, ssn, R ;
there is no causal dependency between processes, i.e. the antecedence graph of each process is a single vertice: ∀ k, P, AG, inc, ssn, R ∈ M • AG = root(AG).

We also define correct configurations (C scl ) which are configurations C such that there exists a starting configuration C s and C s → C (with → the reflexive and transitive closure of → defined hereafter).

Operational Semantics The operational semantics of scl is defined by means of a reduction relation between configurations, noted →. The transition relation is the union of two relations: a forward relation, noted , that corresponds to normal process execution, and a rollback relation, noted , that implements process recovery. Our reduction relations and are defined as the smallest relations defined by a set of inference rules. For space reasons, we do not present all the inference rules but only a relevant sample.

To define the reduction relations, we rely on the usual functions and predicates: succ(), pred() on natural numbers, ∪, ∩, ∈, etc. on sets, as well as a parallel substitution that operates on free variables: P { a1,...,an / b1,...,bn } substitutes each b i with a i in P . The substitution is performed in parallel, hence P { a1 / b1 }{ a2 / b2 } = P { a1,a2 / b1,b2 }2 . Concerning antecedence graphs, we use a merge operation (noted AG 1 ∪ t AG 2 ) between two graphs, which simply creates a new common ancestor t for the roots of the two graphs to be merged, here AG 1 and AG 2 .

Forward Rules. We have six forward reduction rules: a rule to send a message from one process to another, a rule for a process to receive a message, a rule for a process to lose a message, a rule to set a new checkpoint, a rule for a process to idle, and finally a rule corresponding to a process failure. For instance, the rule for receiving a message is defined as follows:

S.receive AG = AG ∪ succ(si),ssn0 AG 0 L = L\{ k 0 , k, ssn 0 , AG 0 , Q, inc 0 } inc(k 0 ) = inc 0 k, receive(source, X) • P, AG, si, inc, ssn, R || M, L, K k, P { k0,Q / source,X }, AG , succ(si), inc, ssn, R || M, L , K
In this rule, process k receives a message Q with number ssn 0 and antecedence graph AG 0 from process k 0 . The antecedence graph AG of process k is updated to AG ∪ succ(si),ssn0 AG 0 . Notice that the condition inc(k 0 ) = inc 0 in the rule premises is non local. This is a simplification from the original Manetho protocol, in which processes maintain a local vector containing incarnation numbers of all processes which is updated by a message broadcast to all other processes following a process recovery, and the condition inc(k 0 ) = inc 0 corresponds to a local look-up at the vector. For the sake of simplicity, we chose not to model this part of the protocol, which is of no relevance for our simulation results.

The rule for process failure is defined as follows:

S.fail k, P, AG, si, inc, ssn, R || M, L, K k, ⊥, AG, si, inc, ssn, R , L, K
With this rule, any process which is not recovering (i.e. any process without a mark) can fail (i.e. the program is replaced by ⊥). This rule does not need any additional condition since processes can fail at any time.

Rollback Rules. Rollback is done in three steps: restarting the process from its last checkpoint (one rule initialise checkpoint), retrieving the antecedence graph from other processes (two rules: one for the antecedence graph reconstitution and one for ending the antecedence graph reconstitution) and finally, replaying locally message exchanges until the last state interval of the received tree is reached (three rules: one to replay messages sent, one to replay messages delivered and the last to end the replay sequence). We thus have six reduction rules implementing rollback. In the following, we only give full details on some of them. The first step of the recovery is to re-instantiate the process from its last checkpoint:

S.roll cid r , k, P r , AG r , si r , ssn r , R r ∈ K cid r biggest checkpoint id of process k. k, ⊥, AG, si, inc, ssn, R || M, L, K k, P r , AG r , si r , succ(inc), ssn r , R r • || M, L, K
Notice that only inc is preserved during this rule, and the other fields are recovered from the checkpoint record. This is in line with Manetho, which assumes that both checkpoint and incarnation number are held in stable storage in order to survive a process crash. Then, we can retrieve the new antecedence graph from other processes. To do that, each other process sends the biggest subtree of their antecedence graph which root belongs to the failed process state intervals. The failed process can then rebuild a new antecedence graph consistent with other processes using the rule S.getAG below:

AG 1 ⊂ AG 1 root AG 1 is the biggest si of k 0 in AG 1 root AG 1 > root AG 0 k 0 , P 0 , AG 0 , si 0 , inc 0 , ssn 0 , R 0 • || k 1 , P 1 , AG 1 , si 1 , inc 1 , ssn 1 , R 1 || M, L, K k 0 , P 0 , AG 1 , si 0 , inc 0 , ssn 0 , R 0 • || k 1 , P 1 , AG 1 , si 1 , inc 1 , ssn 1 , R 1 || M, L, K
This ends when the reconstructed antecedence graph cannot be augmented anymore (rule S.endAG not shown, which changes the mark of the process under recovery from • to •).

The new antecedence graph is consistent with other processes, but the current state of the recovering process does not match the antecedence graph. Hence, we have to simulate locally the messages sent and received (rules S.replay.send and S.replay.deliver). To replay a delivery, the process simply gathers a saved copy of the message from the sender. To replay a send, it updates its memory, but does not send anything (to avoid double delivery). For instance, the rule S.replay.send is the following:

si 0 ≤ root AG 0 R 0 = R 0 ∪ k 0 , ssn 0 , Q k 0 , send(k 1 , Q) • P 0 , AG 0 , si 0 , inc 0 , ssn 0 , R 0 • || M, L, K k 0 , P 0 , AG 0 , si 0 , inc 0 , succ(ssn 0 ), R 0 • || M, L, K
Once the message is about to enter a new state interval that is not in the recovering antecedence graph, the rollback sequence ends: the end recovery rule S.replay.stop (not shown) simply erases the mark.

Rollback Soundness

We now show that scl has sound rollback semantics. This in itself is not surprising since the Manetho recovery process was already proven correct in [?,?]. Nonetheless, our proof method differs from that in [?,?]. The original Manetho semantics is described in pseudo-code while our formalization of Manetho configurations and their operational semantics uses reduction rules. Hence, our proofs are based on case studies on the reduction relation, which is a step closer to a computer assisted verification of its correctness.

Definition 1 (Execution and recovery sequence). Given a set of configurations {C 1 , . . . , C n }, an execution is a sequence of reductions of the form C 1 → . . . → C n . A recovery sequence for a process k in a configuration C ⊥ is the shortest execution C ⊥ → C such that process k is failed in C ⊥ and that it has no mark in C.

Definition 2 (Soundness of recovery sequence). Let C 1 → C 2 → C 3 be an execution, with C 2 → C 3 a recovery sequence for a process k. C 2 → C 3 is sound if and only if there exists a configuration C 3 such that C 1 → C 3 with C 3 and C 3 being identical except for the incarnation number of process k.

Theorem 1 (Rollback soundness). If C 1 is a correct configuration and C 1 → C 2 is a recovery sequence for some process k in C 1 , then C 1 → C 2 is sound.

The lr-π Language

We now describe the lr-π language. This language is an intermediate language between the roll-π calculus [?] and Manetho. The lr-π language is a higher order reversible π calculus in which processes are located and messages are exchanged asynchronously with continuations. The syntax is similar to roll-π's syntax, except that (i) there is no name creation; (ii) processes are identified by a tag (to record causal dependencies between events) and a label (which acts as a process identifier); (iii) there are continuations after sending a message; (iv) the number of parallel processes in an lr-π configuration is fixed and does not change during execution.

Syntax

A configuration is a list of processes running in parallel. Each process is identified by a location λ and a tag k, which serves the same purpose of tracking causality as the tags in [?]. We are given a set X of variables (elements among x, y, . . .), a set L v of location variables (l 1 , l 2 , . . .) and a set L c of location constants (λ 1 , λ 2 , . . .). We let L denote L v ∪ L c , with elements among λ, λ , . . .. The action of sending program P to a process λ creates a message at that location: k i , λ : λ j [P]. Failed processes are written with the symbol ⊥.

The lr-π constructs are similar to roll-π ones: upon delivery of a message, a memory is created to keep track of the evolution of the configuration in order to reverse deliveries. The tag of the memory corresponds to the tag of the resulting process. For instance, the configuration k 0 , λ 1 :

x l 0 || k , λ 1 : λ 2 [0] reduces to k 1 , λ 1 : 0 || [k 0 , λ 1 : x l 0 || k , λ 1 : λ 2 [0]; k 1 ].
We know from the tags that the process k 1 , λ 1 : 0 results from the delivery kept in the memory [. . . ; k 1 ]. Finally, frozen variants of processes are used during backward reductions to mark processes that should be reverted.

The complete grammar is provided in Figure ??.

:= 0 | x Empty program/Variable | λ P • Q | x l P Send/Deliver message µ ::= k1, λ2 : λ1[P] || k2, λ2 : X λ Q Record | k1, λ2 : λ1[P] || k2, λ2 : X λ Q Record with frozen message | k1, λ2 : λ1[P] || k2, λ2 : X λ Q Record with frozen delivery | k1, λ2 : λ1[P] || k2, λ2 : X λ Q Record fully frozen

Semantics

The semantics of the lr-π language is defined using a forward reduction relation (noted ) and a backward reduction relation (noted ). Reduction rules are given in Figure ??.

The forward reduction is defined by inference rules to send and deliver a message (L.send and L.deliver), to idle (L.idle), to fail (L.fail) and to lose a message (L.Lose).

The backward reduction works in three steps. First, one needs to target a previous state to revert to: the rule L.rollback creates a rollback token (rlk) which indicates that the memory tagged k is to be restored3 . The second step consists in tracking the causal dependency of the targeted memory: the span rule (L.span) recursively freezes dependent processes; when all dependent processes are frozen, this step ends (rule L.top). The last steps consists in recursively restoring memories (rule L.descend). Notice that, in lr-π, in contrast to scl, a single rollback can affect multiple processes.

The L.span rule actually comes in multiple flavours, depending on whether the message or the delivery process are already frozen. For the sake of conciseness, we only present one flavour where message and delivery process are not frozen.

L.deliver The example in Figure ?? shows two processes λ 1 and λ 2 exchanging a process P . λ 1 sends P to λ 2 and waits for an answer. When λ 2 receives the message, a memory is created and λ 2 sends back the message to λ 1 then executes P . When λ 1 receives the answer, a second memory is created.

µ = k1, λ2 : λ1[P ] || k2, λ2 : X l Q k1, λ2 : λ1[P ] || k2, λ2 : X l Q d succ(k2), λ2 : Q{ P,λ 1 / X,l } || [µ, succ(k2)] L.send k1, λ1 : λ2 P • Q1 || k2, λ2 : Q2 s k1, λ1 : Q1 || k1, λ2 : λ1[P ] || k2, λ2 : Q2 L.idle M i M L.
The second part of the example shows the reverse execution of the previous exchanges. A rollback token rlk 2 is introduced. In a L.span reduction, the process and the message tagged with k 2 are frozen, and a rollback roken rlk 1 is created. Then, the process tagged with k 1 is frozen in a L.top reduction. Finally, two L.descend reductions reverse the configuration in the state preceding the first delivery of λ 2 . This example highlight a major difference from scl: reversing λ 2 requires to reverse λ 1 in order to preserve the causal dependency. Contrary to scl (and Manetho), reversing a process is guarantee to only affect this process.

k1, λ1 : λ2 P • X l X || k2, λ2 : Y m (m Y • Y ) s k1, λ1 : X l X || k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ) d k1, λ1 : X l X || k 2 , λ2 : λ1 P • P || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] s k1, λ1 : X l X || k 2 , λ2 : P || k 2 , λ1 : λ2[P ] || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] d k 1 , λ1 : P || k 2 , λ2 : P || [k 2 , λ1 : λ2[P ] || k1, λ1 : X l X; k 1 ] || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] s k 1 , λ1 : P || k 2 , λ2 : P || [k 2 , λ1 : λ2[P ] || k1, λ1 : X l X; k 1 ] || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] || rlk 2 sp k 1 , λ1 : P || k 2 , λ2 : P || [ k 2 , λ1 : λ2[P ] || k1, λ1 : X l X; k 1 ] || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] || rlk 1 t k 1 , λ1 : P || k 2 , λ2 : P || [ k 2 , λ1 : λ2[P ] || k1, λ1 : X l X; k 1 ] || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] d k 2 , λ2 : P || k 2 , λ1 : λ2[P ] || k1, λ1 : X l X || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] d k1, λ1 : X l X || k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y )

Starting and Correct Configurations

Among all lr-π configurations, we distinguish correct and starting configurations.

A configuration is correct when (1) all variables and location variables are bound; (2) there is a single process for each λ i ; and (3) for each process k, λ : P, for each k 0 < k i ≤ k, there is a memory tagged with k i . A starting configuration is a correct configuration such that (1) there is no memory; (2) there is no pending message; (3) there is no frozen memory or frozen process; and (4) there is no rollback token.

The set of correct configurations is written C lr-π and the set of starting configurations is written C s lr-π .

Encoding in roll-π

The lr-π language is inspired by roll-π described in [?]. Similarly to lr-π, C roll-π denotes the set of correct roll-π configurations. In order to show it inherits the causal consistency property of roll-π, we sketch in this section, how lr-π can be encoded into roll-π (full details available in [?]). The major difference between the two languages is that lr-π allows failure, which roll-π doesn't, and that roll-π message sending is without continuation. A few minor subtleties also occurs: implementing the loss of message, an idle process and the introduction of roll tokens, which can all be encoded very simply.

Process Failure We want to be able to stop each process at any point. Given a process P , we encode it as νI • I(X) X || I 0 || I P . Hence, it reduces either to νI • P || I 0 (the I 0 part being garbage), either to νI • 0 || I P , with I P being blocked (memory creation and tag changes not shown).

By applying this strategy recursively to P , it is possible to block the execution at each step. The only way to unblock the process is to revert it, which is exactly what a failure does in lr-π.

Thus, we define δ • (•) which creates the failure machinery as follow:

δ λ (P ) = νI • I(X) X || I 0 || I tr λ (P ) (1)
with tr (•) translating lr-π programs into roll-π ones.

Message Loss

In the original roll-π, messages cannot be lost. To encode message loss, we simply add a consumer process.

γ(M ) = γ T (T 1 ) || . . . || γ T (T n ) || γ L (L) || γ M (M ) (2)
where γ T trivially translates the scl process into its lr-π equivalent (and defaults to ⊥ if the process is marked or ⊥). γ L recreates an lr-π pending message for each message in a list. Finally γ M recreates memories according to the idea below.

Managing Memories Given an scl configuration, we can infer the last step of a process k (and thus the previous state of the configuration):

if there is a pending message m sent by k such that the antecedence graph piggybacked is the current antecedence graph of k and that the ssn of k is the successor of the ssn piggybacked in m, then the last step of k was to send m. otherwise, if the AG of k is not a single node, then the last step was to receive a message. The message that triggered the current state interval can be retrieved from the antecedence graph. finally, if the antecedence graph of k is a single node, then k is in its initial state.

Hence, by applying recursively the above idea, one can infer the full history of a given process k and then, each time a message delivery is matched, create the corresponding memory in lr-π.

Unlike lr-π, reversing a memory is done in a single LM.roll step in lr-π -. Since, as explained above, the marked memory in lr-π -corresponds to the state interval scl rolls back to, scl can simulate the LM.roll and LM.forward rules with a complete rollback sequence. Also, LM.ignore is simulated by S.lose. Finally, the rule LM.start simply adds marks and is simulated by S.idle.

Figure ?? shows an example of lr-π -backward execution. The initial configuration is the same than in Figure ??. Since forward rules are the same in both languages, we only show the backward reduction.

k 1 , λ1 : P || k 2 , λ2 : P || [k 2 , λ1 : λ2[P ] || k1, λ1 : X l X; k 1 ] || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] s k 1 , λ1 : P || k 2 , λ2 : P || [k 2 , λ1 : λ2[P ] || k1, λ1 : X l X; k 1 ] • || rlk 1 || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ] r k 2 , λ2 : P || k1, λ1 : X l X || [k1, λ2 : λ1[P ] || k2, λ2 : Y m (m Y • Y ); k 2 ]
Fig. 9. Example of lr-π -backward execution. In this example, the process λ1 is reverted.

In order to study the simulation of lr-π -, we define observable messages:

Definition 7 (Observable in lr-π -). In a lr-π -configuration M lr-π -, λ 2 is observable (noted M lr-π -↓ λ2 ) if and only if M lr-π -≡ k, λ 2 : λ 1 [Q] || M .
Notice that marked messages are not observable. We refine the definition of observable message in scl:

Definition 8 (Observable in scl ( 2)). In a scl configuration M scl , d is observable (noted M scl ↓ d ) if and only if there exists a k, ssn, AG, si, Q, inc ∈ s L d and the incarnation number of k is inc.

This definition only differs from the first one in the way that only messages which have been sent since the last rollback are observable.

Theorem 3 (Simulation). The relation R = {(M, γ -1 + (M ))|M ∈ C lr-π -} is a weak barbed simulation.
The proof is similar to the proof of Theorem ?? and is provided in [?].

Related Work

We do not know of any work that attempts to relate a distributed checkpoint rollback scheme with a reversible model of computation, as we do in this paper. However, our work touches upon several topics, including the formal specification and verification of distributed checkpoint rollback algorithms, the definition of rollback and recovery primitives and abstractions in concurrent programming languages and models, and the study of reversible programming models and languages. We discuss these connections below.

Several works consider the correctness of distributed checkpoint rollback algorithms. The Manetho algorithm was introduced informally using pseudo code and proved correct in [?,?]. Several other checkpointing algorithms have been considered and proved correct, such as e.g. adaptive checkpointing [?] or checkpointing with mutable checkpoints [?]. Our proof of correctness for Manetho relies on a more formal presentation of the algorithm, by way of operational semantics rules, and the analysis of the associated transition relation. In that respect, the work which seems closer to ours is [?], which also formalizes a checkpointing algorithm (the algorithm from [?], which is not a causal logging checkpoint/rollback algorithm) by means of operational semantics rules, and also proves its correctness by an inductive analysis of its transition relation.

The rollback capability in lr-π is directly derived from the low-level semantics of roll-π [?]. Compared to [?], the rollback capability in lr-π can be triggered by the occurrence of a process crash, but we have shown above that this could be encoded in roll-π. Undo or rollback capabilities in programming languages have a long history (see e.g. [?] for an early survey in sequential languages). More recent works which have introduced undo or rollback capabilities in a concurrent programming language or model include [?], which defines logging and group primitives for programming fault-tolerant systems, [?], which extends the actor model of computation with primitives for creating globally-consistent checkpoints, [?], which introduces checkpointing primitives in concurrent ML, [?], which extends the Klaim tuple space programming language with rollback capabilities directly inspired by roll-π, and [?] which extends a subset of Core Erlang with a reversible semantics similar to the roll-π one. The rollback capabilities in roll-π have several advantages over these different works: rollback is possible at any moment during execution, in contrast to [?]; does not suffer from the domino effect, in contrast to [?]; and provides direct support for consistently undoing all the consequences of a given action, in contrast to [?]. The same properties hold for lr-π and reversible Klaim.

Conclusion

We have shown in this paper the tight relationship that exists between a checkpoint/rollback scheme based on causal logging and a reversible concurrent programming model based on causal consistency. More precisely, we have shown that the scl language, whose operational semantics formalizes the behaviour of the Manetho algorithm, can be (weakly barbed) simulated by lr-π, a reversible asynchronous concurrent language with process crash failures, based on the roll-π language, a reversible π-calculus with explicit rollbacks. The converse is not true, but we have shown that scl can (weakly barbed) simulate a variant of lr-π with limited rollbacks. These results probably extend to other checkpoint/rollback schemes based on causal logging, but one would need first to formally specify them as we did in this paper for Manetho.

Apart from showing this relationship, the results are interesting for several reasons. On the one hand, they point to interesting extensions to causal logging checkpoint/rollback schemes. In effect lr-π constitutes an extension of checkpoint/rollback causal logging that does not limit rollbacks to the last saved checkpoint of a failed process: this can be a useful feature to protect against catastrophic faults such as those resulting from faulty upgrades. Also, it is trivial to add to lr-π the ability to create new processes and to exchange processes in messages as in roll-π, thus extending checkpoint/rollback capabilities to dynamic environments, where new code can be added and new processes can be created at runtime, or to add compensation capabilities as in [?] to avoid retrying a faulty execution path. We do not know of checkpoint/rollback schemes that combine these different capabilities and the tight connection established in this paper shows with lr-π how they can be added to causal logging checkpoint/rollback schemes. On the other hand, they suggest interesting directions to optimize rollback in reversible concurrent languages. For instance, as in Manetho, one can avoid rolling back all processes in lr-π by a judicious use of local replay.

Fig. 1 .Fig. 3 .

 13 Fig. 1. Message exchanges, failure and recovery.

  Fig. 4. scl syntax

  Rollback token | k1, λ2 : λ1[P] Message | k1, λ1 : ⊥ Failed process P, Q :

Fig. 5 .

 5 Fig. 5. lr-π syntax

Fig. 6 .

 6 Fig. 6. Reduction rules of lr-π

Fig. 7 .

 7 Fig. 7. Example of lr-π forward and backward execution

4

  Simulation of scl by lr-π 4.1 Translation from scl to lr-π We now define the function γ which translates an scl configuration into an lr-π one. Most of this translation is intuitive, only creating memories is not trivial and the intuition is given below. The long version of the paper contains details of the translation. Given an scl configuration M = T 1 || . . . || T n , L, P we define

In particular:X{ Y /X }{ Z /Y } = Z and X{ Y,Z /X,Y } = Y .

For simplicity, we let this choice be non-deterministic, but we could easily extend the syntax of lr-π to accommodate e.g. imperative rollback instructions as in[?].

We now show that, for any scl configuration M , its encoding γ(M ) in lr-π faithfully simulates M . In both scl and lr-π, an observable is a message targeted to some process denoted by its identifier d (noted M ↓ d ).

Definition 3 (Barbed bisimulation). A relation R ⊆ C scl × C lr-π is a strong (resp. weak) barbed simulation if whenever (M, N ) ∈ R

The proof, which is detailed in [?], relies on the two following lemmas.

The lemma is a simple consequence of the definition of observable and of the encoding function γ(•).

Lemma 2 (R closure under reduction). Assuming M ∈ C scl and M lr-π = γ(M ) (i.e. (M, M lr-π ) ∈ R).

If M → M then exists a sequence of lr-π reductions → lr-π such that

The proof of this lemma proceeds by case study on the scl reduction. Most cases are trivial, in particular, all backward rules except S.replay.stop are either L.lose or L.idle. The S.fail rule matches L.fail. The forward rules are verbose, but direct. Only the S.replay.stop case involves some complication.

To prove it, we first show that for any scl recovery sequence, there exists a corresponding lr-π one. Since none of the other scl backward reductions match the lr-π, then S.replay.stop does.

Discussion on bisimulation

The above relation R is a simulation but is not a bisimulation. In scl, once a process takes a checkpoint, the process can not rollback before this checkpoint.

To tackle this difference, we define a weak version of lr-π called lr-π -with constraints on the rollback point and on message loss.

The lr-π -Language In Manetho, when a single process fails, it rolls back to its last public state, i.e. to the last state in which it sent a message which has been received. In lr-π, when such a message is delivered, the receiver creates a memory, hence, we constrain the rollback of a process to the last state such that exists a memory with a message tagged with this state. Furthermore, we know that all messages sent during and before the target state interval are ignored, hence, in lr-π -, these are marked and ignored. The forward semantics of lr-π -are the same than lr-π, only the backward rules change. Starting configurations of lr-π -are the same than lr-π, and correct configurations (C lr-π -) are defined analogously.

The rollback start is modified to restrict rollback targets: let k i j be the biggest

. This memory ensures that the state k i j is the last state known by an other process. If there exists a memory containing a process tagged with k i j , we mark that memory using LM.Start, as well as all pending messages sent by the process being reverted:

If no such memory exists, we simply fast forward toward the end of the current state interval with LM.Forward:

where the function θ simulates the local replay of messages:

Marked messages are messages to be ignored, hence only these can be removed: LM.Ignore replaces L.Lose:

The rollback semantics consists in reverting back to a marked memory, then replaying all send actions locally: Definition 5 (k-dependence). Given M = i∈I k i , λ i :

Definition 6 (Complete configuration). An lr-π -configuration M is complete (noted complete(M )) if, for each memory [µ; k] in M , there exists a process k, λ : P or a memory [k, λ : P || Q; k ] in M .