\section{Introduction}

Self-supervised learning aims to learn representations from abundant unlabeled data for benefiting various downstream tasks. Recently, many self-supervised approaches have been proposed in the vision domain, such as pre-text based methods~\citep{doersch2015unsupervised,zhang2016colorful,gidaris2018unsupervised}, contrastive learning with Siamese networks~\citep{oord2018representation,he2020momentum,chen2020simple,henaff2020data}, masked image modeling (MIM)~\citep{he2022masked,bao2021beit,Xie2021SimMIMAS}, and etc. Among them, MIM has shown a preponderant advantage in performance, and the representative method Masked Autoencoders (MAE)~\citep{he2022masked} has attracted much attention in the field. A natural question is then raised: {\em Where is the benefit of the transferability to downstream tasks from in MAE-based training?} This motivates us to develop a framework to shed light on the reasons for the superior latent representation from MAE. Also, as the interpretability of the MAE framework is still under-studied in this area, it is crucial to explore this in a specific and exhaustive way.

Intuitively, a good representation should be separable and contain enough semantics from its input, so that it can have a qualified ability to distinguish different classes with better performance on downstream tasks. Nonetheless, how to evaluate the separability and the degree of semantics on the latent features is not clear thus far. Moreover, the mechanism of an Autoencoder {\em compressing} the information from input by reconstructing itself has been a well-established self-supervised learning architecture, but the explanation of the features learned from such approaches is still under-explored.

To address the difficulties of identifying separability and semantics in latent features, we first propose a novel framework, i-MAE, upon vanilla MAE. It consists of a mixture-based masked autoencoder branch for disentangling the mixed representations by linearly separating two different instances, and a pre-trained vanilla MAE as the guidance to distill the disentangled representations. An illustration of the overview framework architecture is shown in Fig.~\ref{fig:framework}. This framework is designed for answering two interesting questions:  {\bf (i)} Are the latent representations in Masked Autoencoders {\em linearly separable}? {\bf (ii)} What is the {\em degree of semantics} encoded in the latent feature space by Masked Autoencoders? These two questions can reveal the fact that MAE learned features are good at separating different classes. We attribute the superior representation of MAE to it learning separable features for downstream tasks with enough semantics.

In addition to qualitative studies, we also develop two metrics to address the two questions quantitatively. In the first metric, we employ $\ell_2$ distance from high-dimensional Euclidean spaces to measure the similarity between i-MAE's disentangled feature and the ``ground-truth'' feature from pre-trained MAE on the same image. In the second metric, we control different ratios of semantic classes as a mixture within a mini-batch and evaluate the finetuning and linear probing results of the model to reflect the learned semantic information. More details will be provided in Section~\ref{approach}.

We conduct extensive experiments on different scales of datasets: small CIFAR-10/100, medium Tiny-ImageNet and large ImageNet-1K to verify the linear separability and the degree of semantics in the latent representations. We also provide both qualitative and quantitative results to explain our observations and discoveries.
The characteristics we observed in latent representations according to our proposed i-MAE framework are: {\bf(I)} i-MAE learned feature representation has great linear separability for its input data, which is proven beneficial for downstream tasks. {\bf(II)} Though the training scheme of MAE is different from instance classification pre-text in contrastive learning, its representation still encodes sufficient semantic information from input data. Moreover, {\em mixing the same-class images as the input training samples substantially improves the quality of learned features}. {\bf(III)} We can reconstruct an image from a mixture by i-MAE effortlessly, even if the it is the subordinate part. To the best of our knowledge, this is the pioneering study to explicitly explore the separability and semantics inside MAE's features with extensive well-designed qualitative and quantitative experiments.

 \begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth, height=10cm, keepaspectratio]{images/ImageNet_impressive3.pdf}
    \vspace{-0.15in}
    \caption{Reconstruction results of {\em i-MAE} on ImageNet-1K validation images with different mixing coefficients $\bm \alpha$ (listed on the left). i-MAE is pre-trained with linearly mixed input and the subordinate image ${\bm I_s}$ as the only target with a 0.5 mask ratio. Visually, i-MAE predictions reflect features of $\bm I_s$ even at 0.1 and still reconstructs the individual image well, whereas at 0.45 reconstructions show the appearance of dominant image (hence the green patches). More visualizations are provided in the Appendix.}
    \label{fig:ImageNet}
   \vspace{-0.15in}
\end{figure}

Our contributions in this work are:
\vspace{-0.1in}
\begin{itemize}[leftmargin=0.15in]
\addtolength{\itemsep}{-0.00in}
\item We propose an {\em i-MAE} framework with two-way image reconstruction and latent feature reconstruction with a distillation loss, to explore the interpretability of mechanisms and properties inside the learned representations of the MAE framework.

\item We introduce two metrics to examine the linear separability and the degree of semantics quantitatively on the learned latent representations.

\item We conduct extensive experiments on different scales of datasets: CIFAR-10/100, Tiny-ImageNet and ImageNet-1K  and provide sufficient qualitative and quantitative results.
\end{itemize}

\section{Related Work}

\textbf{Masked image modeling.} Motivated by masked language modeling's success in language tasks~\citep{bert, gpt1}, Masked Image Modeling (MIM) in the vision domain learn representations from images corrupted by masking. State-of-the-art results on downstream tasks are achieved by several approaches. BEiT~\citep{ bao2021beit}proposes to recover discrete visual tokens, whereas SimMIM~\citep{Xie2021SimMIMAS} addresses the MIM task as a pixel-level reconstruction. In this work, we focus on MAE~\citep{he2022masked}, which proposes to use a high masking ratio and a non-arbitrary ViT decoder. Despite the great popularity of MIM approaches and their conceptual similarity to language modeling, the question of why these representations are stronger has not been thoroughly addressed. Furthermore, as revealed by MAE, pixels are semantically sparse; therefore, we utilize a novel semantics mixing method to investigate semantic-level information quantitatively.

\textbf{Image mixtures.} Widely adopted mixture methods in visual supervised learning include Mixup~\citep{zhang2017mixup} and Cutmix~\citep{yun2019cutmix}. However, these methods require ground-truth labels for calculating mixed labels; in this work, we adapt Mixup to our unsupervised framework by formulating losses on only one of the two input images.
On the other hand, in very recent visual SSL, joint embedding methods and contrastive learning approaches such as MoCo~\citep{he2020momentum}, SimCLR~\citep{chen2020simple}, and more recently UnMix~\citep{shen2022mix} have acquired success and predominance in mixing visual inputs. These approaches promote instance discrimination by aligning features of augmented views of the same image. However, unlike joint embedding methods, i-MAE does not heavily rely on data augmentation and negative sampling. Moreover, whereas most MIM methods are generative tasks, i-MAE learns more separable representations for enhanced instance discrimination performance.

\textbf{Invariance and disentangling representation learning in Autoencoders.} Representation learning focuses on the properties of the features learned by the layers of deep models while remaining agnostic to the particular optimization process. Variance and entanglement are two commonly discussed factors that occur in data distribution for representation learning. In this work, we focus on the latent disentanglement that one feature is correlated or connected to other vectors in the latent space.
Autoencoder is a classical generative unsupervised representation learning framework based on image reconstruction as a loss function. Specifically, autoencoders learn both the mapping of inputs to latent features and the reconstruction of the original input. Denoising autoencoders reconstruct the original input from a corrupted input, and most MIM methods are categorized as denoising autoencoders that use masking as a noise type. We notice that recent work in the literature~\citep{he2022masked,bao2021beit} performs many experiments in masking strategies, but to the best of our knowledge, we are the first to introduce image mixtures in the pre-training of MIM.

\section{i-MAE} \label{approach}

In this section, we first introduce an overview of our proposed framework. Then, we present each component in detail. Ensuing, we elaborate on the metrics we proposed evaluating linear separability and degree of semantics, as well as broadly discuss the observations and discoveries.

\subsection{Framework Overview}

As shown in Fig~\ref{fig:framework}, our framework consists of three submodules: {\bf (i)} a mixture encoder module that takes the masked mixture image as the input and output mixed features; {\bf (ii)} a disentanglement module that splits the mixed feature to the individual ones; {\bf (iii)} a MAE teacher module that provides the pre-trained embedding for guiding the splitting process in the disentanglement module.

\begin{figure}
    \centering
    \includegraphics[width=0.95\linewidth,height=10cm, keepaspectratio]{images/i-MAE2.pdf}
    \vspace{-0.15in}
    \caption{Framework overview of our {\em i-MAE}. \ding{172} is the main branch that consists of a mixture encoder, a disentanglement module, and a two-way image reconstruction module. \ding{173} is the encoder part of a pre-trained vanilla MAE for distillation purposes (i.e., latent reconstruction). \ding{174} is the decoder part in MAE and is discarded in training.}
    \label{fig:framework}
    \vspace{-0.1in}
\end{figure}

\subsubsection{Components}

\textbf{Input Mixture with MAE Encoder.}
Inspired by Mixup, we use an unsupervised mixture of inputs formulated by $\alpha *{\bm I}_1$ and $(1-\alpha)*{\bm I}_2$,
${\bm I}_1, {\bm I}_2$ are the input images. Essentially, our encoder extrapolates mixed features from a tiny fraction (e.g., 25\%) of visible patches, which we then tune to only represent the subordinate image. The mixed image will be:
\begin{equation}
 {\bm I}_{\bm m} = \alpha * {\bm  I}_1 + (1-\alpha)*{\bm I}_2
\end{equation}
where $\alpha$ is the coefficient to mix two images following a Beta distribution.

\textbf{Two-branch Masked  Autoencoders with Shared Decoder.}
Although sufficient semantic information from both images is embedded in the mixed representation to reconstruct both images, the vanilla MAE cannot by itself associate separated features to either input. The MAE structure does not retain identification information about the two mixed inputs (e.g., order or positional information), i.e., the model cannot tell which of the two images to reconstruct to, since both are sampled from the same distribution and mixed randomly. The consequence is that both reconstructions look identical to each other and fail to look similar to either original input.

Similar to how positional embeddings are needed to explicitly encode spatial information, i-MAE implicitly encodes the semantic difference between the two inputs by using a dominant and subordinate mixture strategy. Concretely, through an unbalanced mix ratio and a reconstruction loss targeting only one of the inputs, our framework encodes sufficient information for i-MAE to linearly map the input mixture to two outputs.

\textbf{Two-way Image Reconstruction Loss.} Formally, we build our reconstruction loss to recover individual images from a mixed input, which is first fed into the encoder to generate mixed features:
\begin{equation}
   \bm h_m = \bm E_\text{i-MAE}(\bm I_m)
\end{equation}
where $\bm E_\text{i-MAE}$ is i-MAE's encoder, $\bm h_m$ is the latent mixed representation. Then, we employ two non-shareable linear embedding layers to separate the mixed representation from the individual ones:
\begin{equation}
  \begin{aligned} \bm h_1 = \bm f_1(\bm h_m) \\\bm h_2 = \bm f_2(\bm h_m) \end{aligned}
\end{equation}
where $\bm f_1$, $\bm f_2$ are two linear layers with different parameters for disentanglement and $\bm h_1$ and $\bm h_2$ are corresponding representations. After that, we feed the individual representations into the shared decoder with the corresponding reconstruction losses:
\begin{equation}
\begin{array}{l}\mathcal{L}_{\text {recon}}^{\boldsymbol{I}_{1}}=\mathbb{E}_{\boldsymbol{I}_{1} \sim p\left(\boldsymbol{I}_{1}\right)}[\left\|\boldsymbol{D}_{\text {shared}}\left(\boldsymbol{h}_{1}\right)-\boldsymbol{I}_{1}\right\|_{2}]. \\ \mathcal{L}_{\text {recon}}^{\boldsymbol{I}_{2}}=\mathbb{E}_{\boldsymbol{I}_{2} \sim p\left(\boldsymbol{I}_{2}\right)}[\left\|\boldsymbol{D}_{\text {shared}}\left(\boldsymbol{h}_{2}\right)-\boldsymbol{I}_{2}\right\|_{2}].\end{array}
\end{equation}
In practice, we train the linear separation layers to distinguish between the dominant input $\bm I_d$ (higher mix ratio) and the subordinate input $\bm I_s$ (lower ratio). Showing that our encoder learns to embed representations of both images, we intentionally choose to reconstruct only the subordinate image $\bm I_s$ to prevent the $\bm I_d$ from guiding the reconstruction. Essentially, successful reconstructions from only the $\bm I_s$ prove that representations of both images can be learned and that the subordinate image is not filtered out as noise.

\textbf{Patch-wise Distillation Loss for Latent Reconstruction.}
With the linear separation layers and an in-balanced mixture, the i-MAE encoder is presented with sufficient information about both images to perform visual reconstructions. However, information is inevitably lost during the mixing process, harming the value of the learned features in downstream tasks such as classification. To mitigate such an effect, we propose a knowledge distillation module for not only enhancing the learned features' quality, but also demonstrating that a successful distillation can evidently prove the linear separability of our features.

Intuitively, MAE's features can be regarded as ``ground-truth'' and i-MAE learns features distilled from the original MAE. Specifically, our loss function computes $\ell_2$ loss between disentangled representations and original representations to help our encoder learn useful features of both inputs.

Our Patch-wise latent reconstruction loss can be formulated as:
\begin{equation}
\begin{aligned} \mathcal{L}_{\text {recon }}^{h_{1}} &=\mathbb{E}_{\boldsymbol{h}_{1} \sim q\left(\boldsymbol{h}_{1}\right)}[\left\|\boldsymbol{E}_{\mathrm{p}-\mathrm{MAE}}\left(\boldsymbol{I}_{1}\right)-\boldsymbol{h}_{1}\right\|_{2}].\\ \mathcal{L}_{\text {recon }}^{\boldsymbol{h}_{2}} &=\mathbb{E}_{\boldsymbol{h}_{2} \sim q\left(\boldsymbol{h}_{2}\right)}[\left\|\boldsymbol{E}_{\mathrm{p}-\mathrm{MAE}}\left(\boldsymbol{I}_{2}\right)-\boldsymbol{h}_{2}\right\|_{2}].\end{aligned}
\end{equation}
where $\bm E_\text{p-MAE}$ is the pre-trained MAE encoder.

\subsection{Linear Separability}
For i-MAE to reconstruct the subordinate image from a potentially linear mixture, not only should the encoder be general enough to retain information from both inputs, but it also needs to generate embeddings that are specific enough for the decoder to distinguish them into their pixel-level forms. A straightforward interpretation of how i-MAE fulfills both conditions is that the latent mixture ${{\bm h}_m}$ is a linear combination of features that closely relate to ${\bm h_1}$ and ${\bm h_2}$, e.g., in a linear relationship. Our distillation module mitigates the information loss.
To verify this explanation, we employ a linear separability metric to experimentally observe such a behavior.

\textbf{Metric of Linear Separability.}
A core contribution of our i-MAE is the quantitative analysis of features. In general, linear separability is a property of two sets of features that can be separated into their respective sets by a hyperplane. In our example, the set of latent representations $\bm H_1$ and $\bm H_2 $ are linearly separable if there exists $ n+1$ real numbers $\bm w_1,\bm w_2, ...,\bm w_n,\bm b$, such that every $\bm h \in \bm H_1$ satisfies $\sum{{\bm w}_i{\bm h}_i > \bm b}$ and every $\bm h \in \bm H_2$ satisfies $\sum{{\bm w}_i{\bm h}_i < \bm b}$. It is a common practice to train a classical linear classifier (e.g., SVM) and evaluate if two sets of data are linearly separable.

However, to quantitatively measure the separation of latent representations, we devised a more intuitive yet effective metric.
Our metric computes the Mean Squared Error (MSE) distance between the disentangled feature of the subordinate image $I_s$ and the vanilla MAE feature of a single input $I_s$. Since the disentangled feature without constraints will unlikely resemble the vanilla feature, we utilize a linear layer to transform the disentangled feature space to the vanilla feature space. Note that this is similar to knowledge distillation, but happens after the pre-training process without finetuning the parameters and conceptually measures the distance between the two latent representations, and thus the linear transformation will not be needed for i-MAE with distillation. The detailed formulation of the metric is:
\begin{equation}
   \mathcal M_\text{ls} = \frac{1}{N} \sum_{n=1}^{\bm N}\left\|{\bm h}^{n}_{s}-\bm f_{\bm\theta}\left(\bm I^{n}_{s}\right)\right\|_{2}^{2}
\end{equation}
where $N$ is the total number of samples. $\bm f_{\bm \theta}$ is the encoder of vanilla MAE. $\bm I_s$ is the subordinate image and $\bm I_s \in \{\bm I_1, \bm I_2\}$.

\subsection{Semantics}

\textbf{Metric of Semantics.}
Vanilla MAE exhibits strong signs of semantics understanding~\citep{he2022masked}. However, studying the abstract concept of semantics in the visual domain is difficult due to its semantic sparsity and repetitiveness. Addressing this problem, we propose a metric unique to i-MAE that is readily available for examining the degree of semantics learned in the model. Apart from straightforwardly evaluating classification accuracy to measure the quality of latent representation, i-MAE utilizes the mixing of semantically similar instances to determine to what degree the disentangled latent representations can reflect image-level meaning.

Naturally, segmenting different instances from the same class is more difficult than segmenting different classes; intra-class separation necessitates knowledge of high-level visual concepts, such as semantic differences, rather than lower-level patterns, such as shape or color.

Moreover, when mixing images of the same class, their latent features are naturally more similar and their two-way loss functions will be updated in the same direction. This means that an intra-class mixture's latent features will encode more information that is more robust about a specific class than an inter-class mixture, where the two latent features may confuse or conflict with each other. Consequently, when the mixed representations have semantics more closely aligned, the information propagated into the two branches contains more information about a specific class; when the mixed representations are from different classes, the disentangled features may not have semantics perfectly resembling their classes, thus containing a lower degree of semantics for a single class.

Our {\em semantics-controllable mixture} scheme is another data augmentation that introduces significantly more mixtures of the same class into the training process.

We find our method to boost the semantics of features learned by this {\em semantics-controllable mixture} scheme. Specifically, we choose training instances from the same or different classes following different distributions to constitute an input mixture, so as to examine the quality of learned features as follows:
\begin{equation}
    \bm p = \bm f_{\bm m}(\bm I_{c_a}+\bm I_{c_b})
\end{equation}
where ${\bm f}_{\bm{m}}$ is the backbone network for mixture input and ${\bm p}$ is the corresponding prediction. ${\bm I}_{c_a}$ and ${\bm I}_{c_b}$ are the input samples and $c_a$, $c_b$ have a certain percentage ${\bm r}$ that belongs to the same category. For instance, if ${\bm r}=0.1$, it indicates that 10\% images in a mini-batch are mixed with the same class. When ${{\bm r}}=1.0$, all training images will be mixed with another one from the same class, which can be regarded as a semantically enhanced augmentation.
During training, ${\bm r}$ is fixed for individual models, and we study the degree of semantics that the model encodes by changing the percentage value ${\bm r}$. After the model is trained by i-MAE using such kind of input data, we finetune the model with Mixup strategy (both baseline and our models) and cross-entropy loss. We use accuracy as the metric of semantics under this percentage of instance mixture:
\begin{equation}
    \mathcal M_\text{sem} =-\sum_{i=1}^{n} \bm t_{i} \log \left(\bm p_{i}\right)
\end{equation}
where $\bm t_i$ is the ground-truth. The insight behind this is that: if the input mixture is composed of two images or instances with the same semantics (i.e., the same category), it will confuse the model during training and i-MAE will struggle to disentangle them. Thus, the encoded information and semantics may be weakened in the training process, and it can be reflected by the quality of learned representation. It is interesting to see whether this conjecture is supported by the empirical results. We use the representation quality through finetuned accuracy to monitor the degree of semantics with this {\em semantics-controllable mixture} scheme. Since in the metric we involve additional prior knowledge of same or different classes for the mixture samples, this is only for evaluating purposes in our framework. An alternative way to avoid using prior label information is clustering the samples to identify the same or different classes in a mini-batch.

\section{Empirical Results and Analysis}

In this section, we analyze the properties of i-MAE's disentangled representations through empirical studies on an extensive range of datasets. First, we provide the datasets used and our implementation details. Then, we thoroughly ablate our experiments, focusing on the properties of {\em linear separation}, and {\em controllable-semantic mixture}. Lastly, we give our final evaluation of the results.

\vspace{-0.06in}
\subsection{Datasets and Training Implementation for Baseline and i-MAE.}
\textbf{Settings}: We conduct experiments of i-MAE on CIFAR-10/100, Tiny-ImageNet, and ImageNet-1K. On CIFAR-10/100, we adjust MAE's structure to better fit the smaller datasets during unsupervised pre-training: ViT-Tiny~\citep{deit} in the encoder and a lite-version of ViT-Tiny (4 layers) as the decoder. Our pre-training lasts 2,000 epochs with a learning rate $1.5\times10^{-4}$ and 200 warm-up epochs. On Tiny-ImageNet, i-MAE's encoder is ViT-small and decoder is ViT-Tiny, trained for 1,000 epochs with a learning rate $1.5\times10^{-4}$. Additionally, we apply warm-up for the first 100 epochs, and use cosine learning rate decay with AdamW optimizer as in vanilla MAE.

\textbf{Supervised Finetuning}:
In the finetuning process, we apply Mixup for all experiments to fit our pre-training scheme, and compare our results with baselines of the same configuration. On CIFAR-10/100, we finetune 100 epochs using the AdamW optimizer and a learning rate of $1.5\times10^{-3}$.

\textbf{Linear Probing}:
For linear evaluation, we follow MAE~\citep{he2022masked} to train with no extra augmentations and use zero weight decay. Similarly, we adopt an additional BatchNorm layer without affine transformation.

\vspace{-0.08in}
\subsection{Ablation Study}
In this section, we perform ablation studies on i-MAE to concretely examine the property of linear separability and its existence at different mix-levels. Then, we analyze the effects of {\em semantics-controllable mixture} on i-MAE learned representations.

\vspace{-0.08in}
\subsubsection{Ablation for Linear Separability}

To begin, we thoroughly perform our ablation experiments on a diverse group of datasets (ImageNet-1K is performed for final evaluation) and demonstrate how i-MAE's learned features display linear separability with different settings. Specifically, we experiment with the separability of the following aspects of our methods: (i) constant and probability mix factors;
(ii) masking ratio of input mixtures; (iii) different ViT architectures.
Unless otherwise stated, the default settings used in our ablation experiments are ViT-Tiny, masking ratio of 75\%, fixed mixing ratio of 35\%, and reconstructing only the subordinate image for a harder task.

\textbf{Mix Ratio.}
To demonstrate the separable nature of the input mixtures for subordinate reconstruction, we compared different mixture factors between 0 and 0.5, and random mixture ratios from a Beta distribution. Intuitively, lower mixing ratios contain less meaning information that the encoder may easily confuse with noise, whereas higher ratios destroy the subordinate-dominant relationship. Experimentally, we observe matching visual results shown in the Appendix (Fig.~\ref{fig:ImageNet} and Fig.~\ref{fig:CIFAR100mix}). The better separation performance near 0.3 indicates that i-MAE features are better dichotomized when the mix factor is balanced between noise and useful signals. Whereas below 0.15, the subordinate image is noisy and reconstructions are not interpretable, mixing ratios above 0.45 break the subordinate relationship between the two images, and the two features are harder to distinguish from each other. Moreover, Fig.~\ref{fig:ImageNet} presents a problematic case where a mix factor of 0.45 reconstructs dominant features (hence the green patches in the background).

\textbf{Mask Ratio.}
In i-MAE, visible information of the subordinate image is inherently limited by the unbalanced mix ratio, in addition to masking. Hence, a high masking ratio (75\%~\citep{he2022masked}) may not be necessary to suppress the amount of information the encoder sees, and we consequently attempt lower ratios of 50\%, 60\% to introduce more information about the subordinate target. As shown in Fig.~\ref{fig:maskratio}, a lower masking ratio of 0.5 or 0.6 can significantly improve reconstruction quality.

Combining our findings in mix and mask ratios, we empirically find that i-MAE can compensate for the information loss at low ratios with the additional alleviation of more visible patches (lower mask ratio). Illustrated in Fig.~\ref{fig:ImageNet}, we display a case of i-MAE's reconstruction succeeding in separating the features an input with {\bf $\alpha=0.1$} mix factor and {0.5} masking ratio. Through studying the mix ratio and masking ratio, we reveal that i-MAE can learn linearly separable features under two conditions: {\bf (i)} enough information about both images must be present (determined by the trade-off between mask ratio and mix ratio). {\bf (ii)} the image-level distinguishing relationship between minority and majority (determined by mix ratio) is potent enough for i-MAE to encode the two images separately.

\textbf{ViT Backbone Architecture.}
We studied whether different scales of ViT effect linear separation in the Appendix of Fig.~\ref{fig:arch}. Our results show that larger backbones are not necessary for i-MAE to disentangle features on small datasets, as the insufficient training data cannot fully utilize the capability; however, large ViTs are crucial to the large-scale ImageNet-1K.

\vspace{-0.08in}
\subsubsection{Ablation for Degree of Semantics}
\textbf{Semantic Mixes.}
Depending on the number of classes and their overall size, datasets in pristine states usually contain around 10\% (e.g., CIFAR-10) to $<$1\% (e.g. ImageNet-1K) samples pertaining to the same class, meaning that by default, uniformly random sampling mixtures will most likely be of different objects. On the other hand, the {\em semantics-controllable mixture} scheme examines whether the introduction of semantically homogeneous mixtures affects the classification performance. That is, we intentionally test to see if similar instances during pre-training negatively influence the classification performance.

As shown in Tab.~\ref{tab:ft_sem}, after i-MAE pre-training, we perform finetuning and linear probing on classification tasks to evaluate the degree of semantics learned given different amounts of intra-class mix $\bm r$. From Tab.~\ref{tab:ft_sem}, we discover that i-MAE overall has a stronger performance in finetuning and linear probing with a non-zero same-class ratio. Specifically, a high $\bm r$ of 1.0 increases the accuracy in linear evaluation most in all datasets, meaning that the quality of learned features is best and separated, and it gains a strong prior of category information for semantically enhanced mixtures. On the other hand, setting $\bm r=0.5$ is advantageous during finetuning, as it gains a balanced prior of separating both intra- and inter-class mixtures.

\begin{table}[t]
    \begin{center}
    \caption{Classification performance of models pre-trained with {\em semantics-controllable mixture} with intra-class mix rate $\bm r$ from 0.0 to 1.0. Whereas the lower bound represents inputs that are all mixes of different classes, $\bm r =1.0$ pre-trains with solely mixtures of same-labeled objects. }
    \label{tab:ft_sem}
    \begin{tabular}{c | c | c | c| c| c|c}
     \hline
  & \multicolumn{2}{| c |}{CIFAR-10} & \multicolumn{2}{| c }{CIFAR-100} & \multicolumn{2}{| c }{Tiny-ImageNet} \\
     \hline
     Same-class Ratio & Finetune & Linear & Finetune & Linear & Finetune & Linear\\ [0.5ex]
     \hline
     baseline & 90.78 & 72.47 & 68.66 &  32.57 & 59.28& 19.62\\
     \hline
     0.0 & 91.67 & 70.53 & 68.34 & 29.22 &  60.91 & 18.23\\
     0.5 & \bf 92.34 & 72.80 & \bf 69.50 & 30.11 & 60.58 & 18.51 \\
     1.0 & 91.60 & \bf 77.61 &  69.33 & \bf 33.39 & \bf 61.13 & \bf 20.40 \\
     \hline
    \end{tabular}
    \end{center}
    \vspace{-0.1in}
\end{table}

\begin{figure}
    \centering
    \includegraphics[width=0.99\linewidth, height=4cm, keepaspectratio]{images/tin_mask_ratio.png}
    \vspace{-0.15in}
    \caption{Comparisons between different mask ratios on Tiny-ImageNet validation dataset. i-MAE produces enhanced visual reconstructions from lower masking ratios when reconstructing images. }
    \label{fig:maskratio}
    \vspace{-0.1in}
\end{figure}

\begin{table}[h]
\begin{center}
\vspace{-0.15in}
\caption{Linear separation metric using $\ell_2$ distance calculated before and after linear regression on CIFAR-10, CIFAR-100, Tiny-ImageNet, and ImageNet. Reported results are from 100 samples trained for 2000 (5000 on ImageNet-1K) epochs and a fixed mix ratio of 0.3.
{\em i-MAE} and {\em i-MAE without distillation} are embedding after disentanglement.
}
\label{tab:linear_separation}
 \resizebox{0.95\textwidth}{!}{
\begin{tabular}{  c| c |c |  c| c | c| c | c| c}
 \hline
  & \multicolumn{2}{ c |}{CIFAR-10} & \multicolumn{2}{| c| }{CIFAR-100} & \multicolumn{2}{| c |}{Tiny-ImageNet} & \multicolumn{2}{| c }{ImageNet-1K} \\
    \hline
    & Before & After  & Before & After & Before & After  & Before & After  \\
 \hline
 Baseline & 3.5899  &  0.0584   & 3.0840  & 0.0487 & 10.38 &  \bf 0.0204   & 13.91  & 0.2004 \\

 i-MAE w/o distill & 0.1384  &  0.0568 &  0.2999  &  0.0475 &  0.0723  &  0.0363  & 0.8799  &  \bf 0.1316\\

 i-MAE & \bf 0.0331 & \bf 0.0474 & \bf 0.0312 & \bf 0.0456 & \bf 0.0708 &  0.0352 & \bf 0.2760  & 0.1838 \\
 \hline
\end{tabular}
}
\end{center}
\vspace{-0.15in}
\end{table}

\begin{figure}
    \centering
    \includegraphics[width=0.95\linewidth, height=12cm, keepaspectratio]{images/c10_visuals_kd_gt_bl.png}
    \vspace{-0.15in}
    \caption{Qualitative comparisons on CIFAR-10. {\bf Row (a)}: baseline vanilla MAE; {\bf (b)}: MAE with unmixed input; {\bf (c)}: our i-MAE without distillation; and {\bf (d)}: i-MAE with distillation.}
    \label{fig:visual comparison}
    \vspace{-0.15in}
\end{figure}

\begin{table}[t]
\centering
\caption{Finetuning classification acc. on i-MAE with best {\em semantics-controllable mixture} settings.  }
\label{fig:class_acc}
\begin{tabular}{c | c| c | c }
 \hline
 Method & CIFAR-10 & CIFAR-100 & Tiny-ImageNet  \\
 \hline
 Baseline & 90.78 & 68.66 & 59.28 \\
 \hline
 i-MAE &  \bf 92.00 & \bf 69.50 & \bf 61.63 \\
 \hline
\end{tabular}
\caption{Linear Evaluation accuracy of i-MAE with best {\em semantics-controllable mixture} settings.}
\label{fig:class_linear_acc}
\begin{tabular}{c | c| c | c}
 \hline
 Method & CIFAR-10 & CIFAR-100 & Tiny-ImageNet  \\
 \hline
 Baseline &  72.47 &  32.57 &  19.62 \\
 \hline
 i-MAE & \bf 77.61 & \bf 33.39 & \bf 20.40 \\
 \hline
\end{tabular}
\vspace{-0.15in}
\end{table}

\subsection{Results of Final Evaluation }

In this section, we provide a summary of our main findings: how separable are i-MAE embedded features and the amount of semantics embedded in mixed-representations. Then, we evaluate the quality of our features with classification and analyze the features.

\vspace{-0.06in}
\subsubsection{Separability}
In this section, we show how i-MAE displays properties of linear separability, visually and quantitatively, and demonstrate our advantage over baseline (vanilla MAE).

In a visual comparison of the disentanglement capability in Fig.~\ref{fig:visual comparison}, vanilla MAE does not perform well out-of-the-box. In fact, the reconstructions represent the mixed input more so than the subordinate image. Since the mixture inputs of i-MAE is a linear combination of the two images, and our results show i-MAE's powerful ability to reconstruct both images, even at very low mixture ratios, we attribute such ability to i-MAE's disentanglement strongly correlating with the vanilla MAE's features.

As aforementioned, we previously gave the formal definition of linear separability; now, we empirically illustrate the strength of the linear relationship between MAE's features and i-MAE's disentangled features with a linear regressor. We employ $\ell_2$ distance as our criterion and results are reported in Tab.~\ref{tab:linear_separation}. Experimentally, we feed mixed inputs to i-MAE and a singular image to the target model (vanilla MAE), {\em Before} indicates that we directly calculate the distance between the ``ground-truth'' features from pre-trained MAE and our disentangled features. {\em After} indicates that we train the linear regressor's parameters to fit the ``ground-truth''.  {\em Baseline} is the model trained without the disentanglement module. It can be observed that our i-MAE has a significantly smaller distance than the vanilla model, reflecting that such a scheme can obtain better separability ability.

\subsubsection{Semantics}

\textbf{Finetune and Linear Evaluation.}
We evaluate our i-MAE's performance through finetuning and linear evaluation of regular inputs and targets. For all approaches in the finetuning phase, we only use Mixup as augmentation; no extra augmentations are used for the linear evaluation phase. Classification performance is outlined in Tab.~\ref{fig:class_acc} and Tab.~\ref{fig:class_linear_acc}. It can be observed that i-MAE outperforms the baseline by a remarkable margin. As our features are learned from a harder scenario, they encode more information with a more robust representation and classification accuracy. Besides, i-MAE shows a considerable performance boost with both evaluation methods.

\textbf{Analysis.} We emphasize that our enhanced performance comes from i-MAE's ability to learn more separable features with the disentanglement module, and the enhanced semantics learned from training with {\em semantics-controllable mixture}. Our classification results show the cruciality of MAE learning features that are linearly separable, which can help identify between different classes. However, to correctly identify features with their corresponding classes, semantically rich features are needed, which can be enhanced by the intra-class mix sampling strategy.

\section{Conclusion}

It is non-trivial to understand why Masked Image Modeling (MIM) in the self-supervised scheme can learn useful representations for downstream tasks without labels. In this work, we have introduced a novel interpretable framework upon Masked Autoencoders (i-MAE) to explore two critical properties in latent features: {\em linear separability} and {\em degree of semantics}. We identified that the two specialties are the core for superior latent representations and revealed the reasons where is the good transferability of MAE from. Moreover, we proposed two metrics to evaluate these two specialties quantitatively. Extensive experiments are conducted on CIFAR-10/100, Tiny-ImageNet, and ImageNet-1K datasets to demonstrate our discoveries and observations in this work. We also provided sufficient qualitative results and analyses of different hyperparameters. We hope this work can inspire more studies on the interpretability of the MIM frameworks in the future.


\section{S1.\ Data Analysis}
\subsection{S1.1.\ Maximum Likelihood Ion-Photon Tomography}
We perform maximum likelihood estimation of the joint ion-photon density matrix, for each detector $h\in\{0\dots 3\}$, by numerically minimizing the negative logarithm of the likelihood function
\begin{multline}
    \mathcal{L} \sim
    \prod_{i} \mathrm{Tr}\left(\hat{\Pi}_{\emptyset, i} \rho_P\right)^{n_{\emptyset,i}}
    \prod_{k\neq h} \mathrm{Tr}\left(\hat{\Pi}_{k, i} \rho_P\right)^{n_{k,i}}\\
    \times \prod_{j} \mathrm{Tr}\left[\left(\hat{\Xi}_{j,\mathrm{bright}}\otimes\hat{\Pi}_{h,i}\right) \rho_{IP} \right]^{n_{h, i, \mathrm{bright}, j}}\\
    \times \mathrm{Tr}\left[\left(\hat{\Xi}_{j, \mathrm{dark}} \otimes \hat{\Pi}_{h,i}\right) \rho_IP\right]^{n_{h, i, \mathrm{dark}, j}} \ ,
\end{multline}
where $\hat{\Pi}$ and $\hat{\Xi}$ denote the POVMs acting on the photonic and ionic part, respectively, $n$ are the number of experimental occurrences and $\rho_P = \mathrm{Tr}_{I}(\rho_{IP})$ is the purely photonic part of the joint ion-photon density matrix $\rho_{IP}$.
Index $i$ enumerates the photon polarization measurement bases, and $k$ enumerates the other detectors, for which only the likelihood of the photonic measurements contribute.
Index $j$ enumerates the ion qubit measurement bases, and dark/bright indicates the measurement outcome.

\begin{table}[hbp]
    \begin{tabular}{rlc@{\hspace{30pt}}rl}
        \cline{1-2}\cline{4-5}
        Parameter & Value && Parameter & Value \\
        \cline{1-2}\cline{4-5}
        $r_{\lambda/4}$ & $0.217 \times 2\pi$ && $\epsilon_{\mathrm{A}, H}$ & 1:12500 \\
        $r_{\lambda/2}$ & $0.449 \times 2\pi$ && $\epsilon_{\mathrm{A}, V}$ & 1:700 \\
        $t_{\mathrm{BS},H}$ & $0.5283$ && $\epsilon_{\mathrm{B}, H}$ & 1:3000 \\
        $t_{\mathrm{BS},V}$ & $0.5307$ && $\epsilon_{\mathrm{B}, V}$ & 1:1900
    \end{tabular}
    \label{tab:BellStateAnalyzer}
    \caption{Independently characterized parameters of optical elements in the photonic Bell state analyzer.
        Subscripts A and B refer to the optical paths corresponding to the two output ports of the non-polarizing beam splitter (BS).
        $H$ and $V$ refer to orthogonal linear polarization states aligned with the axis of the polarizing beam splitter (PBS).}
\end{table}

The detectors used in this experiment are embedded in a photonic Bell state analyzer with waveplates for polarization control at the input port.
The second input port is reserved for quantum networking experiments and is left open here.
The unitary map $U_{P}$ from the polarization basis of an incoming photon to the four spatially separated, $\{H, V\}\ni q$-polarized output modes $\ketfixed{h,q}$ is a function of waveplate retardances $r$, waveplate rotation angles relative to the fast axis $\beta$, transmission of the non-polarizing beam splitter $t_{\mathrm{BS}}$ and the polarization extinction ratios of the polarizing beam splitters $\epsilon$ (see Table~S1 for independently measured values).

The POVMs for detection of a photon on a particular detector $h$, dropping index $i$ for readability, are
\begin{align}
    \hat{\Pi}_h &= \sum_{q\in\{H, V\}}\eta_h U_{P}^{\dagger} \ket{h,q}\bra{h,q} U_{P} \ , \\
    \hat{\Pi}_{\emptyset} &= \hat{1} - \sum_{k=0}^3\hat{\Pi}_k \ ,
\end{align}
where $\eta_h$ is the overall detection efficiency for this detector.
We model the waveplates as unitary retarders. By placing the quarter waveplate nearest to the PBS, followed by the half waveplate, a measurement along a rotated polarization basis is implemented.
For tomography, the half waveplate angle is chosen from $\{0, \pi/8\}$ and the quarter waveplate angle from $\{0, \pi/4\}$ with respect to the respective fast axis.
The projector for the ion state is
\begin{align}
    \hat{\Xi}_s(\vartheta, \varphi) &= U_I(\vartheta, \varphi)^{\dagger} \ket{s}\bra{s} U_I \\
    \text{where} \ U_I &= \begin{bmatrix}
        \cos(\vartheta / 2) & -i \mathrm{e}^{i \varphi}\sin(\vartheta / 2) \\
        -i \mathrm{e}^{-i \varphi}\sin(\vartheta / 2) & \cos(\vartheta / 2)
    \end{bmatrix} \ ,
\end{align}
expressed in the computational qubit basis, with $\vartheta, \varphi$ parameterizing the rotation. For tomography, we use the settings $\vartheta=\pi /2, \varphi \in \{0, \pi/4, \pi/2, 3\pi/4\}$ and twice the setting $\vartheta=0$ to establish an over-complete set of measurement bases.
For ion-photon tomography, we exhaust all 24 measurement basis settings, collecting (typically) 500 ion-photon measurements at every step.
For simultaneous tomography on both \Sr{88} and \Ca{43}, the same measurement basis settings are used for both ions and both photons. The collected data from the two ion-photon states are analyzed separately using the MLE method described above.

\subsection{S1.2.\ Ion-Photon Entanglement Fidelity}
To quantify the fidelity of entanglement in a two-qubit system, we follow the procedure outlined in Ref.~\cite{badziag_local_2000}.
The fidelity of a state $\hat{\rho}$ is defined by
\begin{align*}
    \mathcal{F}[\hat{\varrho}]=\max_{U}\braket{\Psi^{+}|\hat{U} \hat{\varrho}\hat{U}^\dagger|\Psi^{+}} \ ,
\end{align*}
where $\ket{\Psi^{+}} = (\ket{\uparrow}\otimes\ket{\uparrow}+\ket{\downarrow}\otimes\ket{\downarrow})/\sqrt2$ is a maximally entangled two-qubit state and $\hat{U} = \hat{U_1}\otimes \hat{U_2}$ is a unitary operator.
We express a general bipartite state as
\begin{multline}
    \hat{\varrho} = \frac14\left(\hat{1}\otimes\hat{1}+\sum_{k=1}^3 a_k \hat{\sigma}_k\otimes\hat{1} + \sum_{k=1}^3 b_k \hat{1}\otimes\hat{\sigma} + \right.\\
    \left.\sum_{m,n=1}^3 t_{mn}\hat{\sigma}_m\otimes\hat{\sigma}_n\right)  \ ,
\end{multline}
and calculate the corresponding fidelity,
\begin{align*}
    \mathcal{F} = \max_U \left( 1 + \tilde{t}_{11} - \tilde{t}_{22} + \tilde{t}_{33} \right)/4 \ ,
\end{align*}
where $\sum_{m,n=1}^3\tilde{t}_{mn}\sigma_m\otimes\sigma_n = \sum_{m,n=1}^3t_{mn} (U_1\otimes U_2)\sigma_m\otimes\sigma_n (U_1\otimes U_2)^\dagger$.
As $\mathrm{SU(2)}\cong\mathrm{SO(3)}/\{\pm 1\}$, we can write
\begin{align}
    T &= O_1^\dagger \tilde{T} O_2 \label{eq:IsomorphismSU2SO3}
    \intertext{with $O_1, O_2 \in {\rm SO(3)}$ and $T,\tilde{T}$ are real $3\times 3$ matrices with entries $t_{mn},\tilde{t}_{mn}$.
        It is possible to choose $O_1$ and $O_2$ such that $\tilde{T}={\rm diag}(\tilde{t}_{11},\tilde{t}_{22},\tilde{t}_{33})$ with $|\tilde{t}_{11}|\geq |\tilde{t}_{22}| \geq |\tilde{t}_{33}|$.
        In practice, this is done using the singular value decomposition}
    T&=V\Sigma W^\dagger \ , \label{eq:SVD}
\end{align}
where $V,W$ are orthogonal $3\times 3$ matrices and $\Sigma={\rm diag}(s_1,s_2,s_3)$ with conventional ordering of singular values $s_{1}\geq s_2 \geq s_3\geq 0$. The difference between the decomposition \eqref{eq:IsomorphismSU2SO3} and \eqref{eq:SVD} is that $\det(\Sigma) = \pm\det(T)$, whereas $\det(\tilde{T})=\det(T)$, which expresses that, unlike $O_1$ and $O_2$, $V$ and $W$ are not proper rotations. Nevertheless, the sign difference is easily included:
\begin{align}
    \mathcal{F} = \left\{ 1 + s_1 + s_2 - s_3 \,{\rm sign}[\det(T)] \right\}/4 \ , \label{eq:FullyEntangledFraction}
\end{align}
which maximizes the entangled fraction. States with $\det(T)\geq 0$ are classical.

\subsection{S1.3.\ Nonparametric Bootstrapping}
Each data set can be resampled according to inherent statistical properties, in order to generate new datasets, which can be analyzed in the same way as the measured data. The bootstrapped results approximate the measured result on average, but with a spread indicating how sensitive the analysis is to statistical fluctuations in the input data.
For the ion-photon experiments presented here, the number of excitation attempts $n$ is Poisson distributed, photons are multinomially distributed into the four detectors, and the thresholded ion-fluorescence readout follows binomial statistics. The underlying probabilities for these distributions are estimated from the measured data set in frequentist manner.
To bootstrap process tomography measurements on two ions, combined ion-fluorescence readout results are resampled according to the multinomial distribution with four outcomes, using the experimentally observed frequentist probabilities as prior information.

\section{S2.\ Experimental Methods}
\subsection{S2.1.\ Cooling}
Each experimental sequence begins with Doppler cooling on both ions for \SI{300}{\micro\second}.
Next, a sequence of \num{30} red-sideband Raman pulses with durations linearly increasing from \SI{40}{\micro\second} to \SI{80}{\micro\second}, interleaved with optical pumping into the \Ca{43} logic qubit, pre-cool the \ac{OOP} axial mode at $\omega_\mathrm{oop}/(2\pi)=\OopModeFrequency{}$.
Finally, alternating pulses of electromagnetically-induced transparency-cooling target the two axial modes on \Sr{88} for a total of \SI{1.1}{\milli\second}.

\subsection{S2.2.\ Transfer between Ca-43 Logic and Memory Qubits}
The memory qubit, $\ketfixed{\hfslevshort{4}{0}} \leftrightarrow \ketfixed{\hfslevshort{3}{0}}$, is magnetic field-insensitive at low magnetic field, but -- unlike the logic qubit, $\ketfixed{\hfslevshort{4}{4}} \leftrightarrow \ketfixed{\hfslevshort{3}{3}}$ -- cannot be prepared using optical pumping, and does not experience the light shift force required for our gate scheme.
Therefore, a sequence of Raman $\pi$ pulses is used to coherently transfer population between these qubits.
First, population from $\ketfixed{\hfslevshort{3}{3}}$ is transferred into $\ketfixed{\hfslevshort{3}{0}}$, and subsequently population from $\ketfixed{\hfslevshort{4}{4}}$ is transferred into $\ketfixed{\hfslevshort{3}{1}}$.
At this point, a complication arises as the $\ketfixed{\hfslevshort{4}{1}} \leftrightarrow \ketfixed{\hfslevshort{3}{0}}$ and the $\ketfixed{\hfslevshort{4}{0}} \leftrightarrow \ketfixed{\hfslevshort{3}{1}}$ transitions are only separated by $\Delta f \approx\SI{15}{\kilo\hertz}$ at the \SI{0.5}{\milli\tesla} magnetic field.
To coherently reverse the effect of off-resonant excitation on the $\ketfixed{\hfslevshort{4}{1}} \leftrightarrow \ketfixed{\hfslevshort{3}{0}}$ transition, we apply two $\pi/2$ pulses on the $\ketfixed{\hfslevshort{4}{0}} \leftrightarrow \ketfixed{\hfslevshort{3}{1}}$ transition with a delay of $\SI{157}{\micro\second}\sim 2/\Delta f$ in between.

\subsection{S2.3.\ Errors in $\sigma_z \otimes \sigma_z$ Gate}
We identify the leading error mechanism to be heating. We include heating on both axial modes of motion in a master equation approach by adding the Lindblad collapse operators $\sqrt{\dot{\bar{n}}} a$ and $\sqrt{\dot{\bar{n}}} a^\dagger$ per mode, with the corresponding heating rate $\dot{\bar{n}}$, creation operator $a^\dagger$ and annihilation operator $a$.
In a mixed-species, two-ion crystal, the axial normal modes of motion are at found at frequencies
\begin{equation}
    \omega_{\substack{\mathrm{oop} \\ \mathrm{ip}}}^2 = \frac{\left(1 + \mu \pm \sqrt{1 + (\mu - 1) \mu}\right) \omega_1^2}{\mu} \ ,
\end{equation}
where $\mu=m_2 / m_1$ is the mass ratio of the two ions, and $\omega_1$ is the axial frequency of a single ion of mass $m_1$ in the same trap.
For \Sr{88} and \Ca{43}, the ratio $\omega_\mathrm{oop}/\omega_\mathrm{ip} \approx 1.94486$ is close to $2$, resulting in unavoidable off-resonant excitation of the second harmonic of the \ac{IP} mode when addressing the \ac{OOP} mode. In the absence of heating, a gate detuning can always be found which closes the phase-space trajectories for both modes. In our system, however, a high \ac{IP} mode heating rate of $\dot{\bar{n}}_\mathrm{ip}\simeq\IPHeatingRate{}$ causes an error, which is amplified by the high initial temperature of this mode. We simulate the system of two ions coupled by the two axial motional modes to quantify the infidelity due to this effect. We find that the contribution from the second harmonic of the \ac{IP} mode is of similar magnitude ($\sim \num{0.02}$) as the direct contribution from the $\dot{\bar{n}}_\mathrm{oop}\simeq\OOPHeatingRate{}$ heating rate of the \ac{OOP} gate mode.


\section{Introduction}

Message Sequence Chart (MSC) \cite{ITU-MSC'04} is a popular formalism for
specification of distributed systems behaviors (e.g. communication
protocols or multi-process systems). Its simplicity and intuitiveness
come from the fact that an MSC describes only exchange of messages between system
components, while other aspects of the system (e.g. content of the messages
and internal computation steps) are abstracted away.  The formalism consists
of two types of charts: (1)~basic Message Sequence Charts (bMSC) that are
suitable for designing finite communication patterns and (2)~High-level
Message Sequence Charts (HMSC) combining bMSC patterns into more complex
designs. In this paper, we focus on the further type reformulated as Message
Sequence Graphs (MSG) that has the same expressive power as HMSC but a simpler
structure, and hence it is often used in theoretical computer science
papers, see, e.g.\ \cite{MSC09,MSC01,MSC04,BOL08,gt_vmt_postproc}.

Even such incomplete models as MSG can indicate serious errors in the
designed system. The errors can cause problems during implementation or even
make it impossible. Concerning verification of MSC models, researchers have
studied a presence of a~race condition in an MSC
\cite{MSC02,MSC13,MSC27,gt_vmt_postproc}, boundedness of the~message
channels \cite{MSC01}, the~possibility to reach a~non-local branching node
\cite{MSC04,MSC35,BOL08,jard:inria-00584530,BOL01,BOL17,MSC45}, deadlocks,
livelocks, and many more. For a recent
overview of current results see, e.g. \cite{Dan2012}.

In this paper, we focus on the realizability problem of MSG
specifications,
i.e. implementation of the specification among parallel machines
communicating via messages. This problem has been studied in various
settings reflecting parameters of the parallel machines, the environment
providing message exchanges as well as the type of equivalence considered
between the MSG specification and its implementation. Some authors restricted
the communication to synchronous handshake \cite{BOL08,BOL19}, needed
several initial states in the synthesized machines \cite{MSC49}, or
considered language equivalence with global accepting states in the
implementation (the implementation accepts if the components are in specific
combinations of its states) \cite{MSC46}. From our point of view, the
crucial aspect is the attitude to non-accepted executions of the
implementation.  When language equivalence is taken into account, an
intentional deadlock can prevent a badly evolving execution from being
accepted \cite{BOL08}. In our setting every partial execution can be
extended into an accepting one. Therefore, we focus on a
deadlock-free implementation of a given MSG into Communicating Finite-State
Machines (CFM) with FIFO communicating channels and distributed acceptance
condition, i.e. a CFM accepts if each machine is in an accepting state. In
\cite{MSC41}, it has been shown that existence of a CFM realizing a given
MSG without deadlocks is undecidable. When restricted to \emph{bounded} MSG
(aka regular MSG, i.e. communicating via finite/bounded channels, and so
generating a regular language), the problem is EXPSPACE-complete
\cite{MSC41}.

In later work \cite{BOL08,MSC49}, a finite data extension of
messages was considered when realizing MSG. This is a very natural
concept because message labels in MSG are understood as message types
abstracting away from the full message content. Hence, during
implementation, the message content can be refined with additional (finite)
data that helps to control the computation of the CFM in order to achieve the
communication sequences as specified in the given MSG. The main obstacle when
realizing MSG are nodes with multiple outgoing edges --- choice nodes. In
a~CFM realization, it is necessary to ensure that all Finite-State Machines
 choose the~same successor of each choice node.
This can be hard to achieve as the~system is distributed.

In \cite{BOL08}, a class of so called \emph{local-choice} MSG
\cite{BOL01,MSC04} was shown to include only MSG realizable in the above
mentioned setting.
Local-choice specifications have the~communication after each choice node
initiated by a~single process --- the~choice leader.  Intuitively, whenever
a~local-choice node is reached, the~choice leader machine attaches to all its
outgoing messages the~information about the~chosen node. The other machines pass the~information on. This construction is
sufficient to obtain a~deadlock-free realization, for details see
\cite{BOL08}. Another possible realization of local-choice MSG is
presented in \cite{jard:inria-00584530}.
 Due to \cite{BOL17}, it is also decidable to determine whether a~given MSG is
language equivalent to some local-choice MSG and, moreover, each equivalent
MSG can be algorithmically realized by a CFM.
To the~best of our knowledge, this is the~largest class of deadlock-free realizable
specifications in the~standard setting, i.e. with additional data, FIFO
channels, and local accepting states.

In this paper, we introduce a  new class of \emph{controllable-choice} MSG that
extends this large class of realizable MSG. The crucial idea of
controllable-choice MSG is that even some non-local-choice nodes can be
implemented, if the processes initiating the communication after the
choice can agree on the successor node in advance. This is achieved by exchanging bounded additional content
in existing messages. We call choice nodes where such an agreement is
possible \emph{controllable-choice} nodes, and show that the class of MSG with
these nodes is more expressive than the class of MSG that are
language equivalent to local-choice MSG.

\section{Preliminaries}
\label{chap:foundations}

In this section, we introduce the~Message Sequence Chart (MSC) formalism that
was standardized by the~International Telecommunications Union (ITU-T) as
Recommendation Z.120 \cite{ITU-MSC'04}. It is used to model interactions
among parallel components in a~distributed environment. First, we introduce
the basic MSC.

\subsubsection{basic Message Sequence Charts (bMSC)}
Intuitively, a bMSC identifies a~single finite execution of
a~message passing system. Processes are denoted as vertical lines ---
instances. Message exchange is represented by an arrow from the~sending
process to the~receiving process.  Every process identifies a~sequence of
actions --- sends and receives --- that are to be executed in the~order from
the~top of the~diagram. The communication among the~instances is not
synchronous and can take arbitrarily long time.
\begin{definition}
A \emph{basic Message Sequence Chart (bMSC)} $M$ is defined by a~tuple
  $(E,<,\procSet,{\cal T},{P},{\cal M}, {l})$ where:
  \begin{compactitem}
  \item $E$ is a~finite set of events,
  \item $<$ is a~partial ordering on $E$ called visual order,
  \item $\procSet$ is a~finite set of processes,
  \item ${\cal T}: E \rightarrow \{$send$, $receive$\}$ is a~function
    dividing events into sends and receives,
  \item ${P}: E \rightarrow \procSet$ is a~mapping that associates
    each event with a~process,
  \item ${\cal M}: {\cal T}^{-1}(\mathrm{send}) \rightarrow
    {\cal T}^{-1}(\mathrm{receive})$ is a bijective mapping, relating every
    send with a~unique receive, such that

    a~process cannot send a message to itself, we refer to a pair of events $(e,
{\cal M}(e))$ as a \emph{message}, and
  \item ${l}$ is a function associating with every message $(e,f)$ a label
    $m$ from a finite set of message labels ${\cal C}$, i.e. $l(e,f)=m$.
  \end{compactitem}
  Visual order $<$ is defined as the~reflexive and transitive closure
  of $ \mathcal{M} \cup \bigcup_{p \in \mathcal{P}} <_{p}$ where
  $<_{p}$ is a~total order on ${P}^{-1}(p)$.
\end{definition}
We require the bMSC to be \emph{first-in-first-out (FIFO)}, i.e., the~visual order
satisfies for all messages $(e,f),(e', f')$ and processes $p,p'$ the~following condition
$$e <_{p} e' \wedge  {P}(f) = {P}(f') = p' \; \Rightarrow \; f <_{p'} f'.$$
Every event of a bMSC can be represented by a letter from an alphabet
$$\Sigma = \{p!q(m) \mid p,q \in \procSet, m \in {\cal C}\} \cup
\{q?p(m) \mid p,q \in \procSet ,m \in {\cal C}\}.$$ Intuitively, $p!q(m)$
denotes a~send event of a message with a label $m$ from a~process~$p$ to
a~process~$q$, and $q?p(m)$ represents a~receive event of a message with
a~label $m$ by $q$ from a~process~$p$.  We define a~\emph{linearization} as
a word over $\Sigma$ representing a total order of events that is consistent
with the partial order $<$.
For a given bMSC $M$, a \emph{language}  ${\cal L}(M)$ is
the set of all linearizations of $M$.

\subsubsection{Message Sequence Graphs}
It turns out that specifying finite communication patterns is not sufficient
for modelling complex systems.
Message Sequence Graphs allow us to combine bMSCs into more complex
systems using alternation and iteration. An MSG is a~directed graph
with nodes labeled by bMSCs and two special nodes, the~initial
and the~terminal node.  Applying the concept of finite automata
\cite{Gill-book_62}, the graph represents a set of paths from the initial
node to the terminal node. In MSG, every such a path identifies a~sequence
of bMSCs. As every finite sequence of bMSCs can be composed
into a~single bMSC, an MSG serves as a~finite representation
of an (infinite) set of bMSCs.

\begin{definition}
A \emph{Message Sequence Graph (MSG)} is defined by a~tuple $ G=({\cal S},\tau,s_{0},
  s_{f},{\it L})$, where
 ${\cal S}$ is a~finite set of states,
 $\tau \subseteq {\cal S} \times {\cal S}$ is an edge relation,
 $s_{0} \in {\cal S}$ is the initial state,
 $s_{f} \in {\cal S}$ is the~terminal state, and
 ${\it L}: {\cal S} \rightarrow \mathrm{bMSC}$ is a~labeling function.
\end{definition}

W.l.o.g., we assume that there is no incoming edge to $s_{0}$ and no outgoing edge
from $s_{f}$. Moreover, we assume that there are no nodes
unreachable
from
the initial node and the~terminal node is reachable from every node in
the~graph.

Given an MSG $G=({\cal S},\tau,s_{0}, s_{f},{\it L})$, a \emph{path} is
a~finite sequence of states $s_{1}s_{2} \ldots s_{k}$, where $\forall \:
1 \leq i < k : (s_{i},s_{i+1}) \in \tau$. A \emph{run} is defined as a path
with $s_{1} = s_{0}$ and $s_{k}=s_{f}$.

Intuitively, two bMSCs can be composed to a~single bMSC
by appending events of every process from the~latter bMSC at
the~end of the~process from the~precedent bMSC.
Formally, the \emph{sequential composition} of two bMSCs $M_{1}=(E_{1},$
$<_{1},\procSet,{\cal T}_{1},{P}_{1},{\cal M}_{1},{l}_{1})$ and
$M_{2}=(E_{2},$ $<_{2}, \procSet,{\cal T}_{2},{P}_{2},
{\cal M}_{2}, {l}_{2})$ such that the sets $E_{1}$ and $E_{2}$ are
disjoint (we can always rename events so that the sets become disjoint), is
the~bMSC $M_{1} \cdot M_{2} = ( E_{1} \cup E_{2},$ $<, \procSet,{\cal T}_{1}
\cup {\cal T}_{2}, {P}_{1} \cup {P}_{2},{\cal M}_{1} \cup
{\cal M}_{2}, {l}_{1} \cup {l}_{2})$, where $<$ is a~transitive
closure of $ <_{1} \cup <_{2} \cup \bigcup_{p \in \procSet} ({P}_{1}^{-1}
(p) \times {P}_{2}^{-1} (p))$.
Note that we consider the~weak concatenation, i.e. the~events from
the~latter bMSC may be executed even before some events from the~precedent
bMSC.

Now, we extend the~MSG labeling function ${\it L}$ to paths. Let $\sigma = s_{1}
s_{2} \ldots s_{n}$ be a~path in MSG $G$, then
${\it L}(\sigma) =  {\it L}(s_{1}) \cdot {\it L}(s_{2}) \cdot \ldots \cdot {\it L}(s_{n})$.
For a given MSG $G$, the \emph{language} ${\cal L}(G)$ is defined as $\bigcup\limits_{\sigma \:\mathrm{
    is~a~run~in } \:G} {\cal L}({\it L}(\sigma))$.  Hence, two MSG are said to be
\emph{language-equivalent} if and only if they have the~same languages.
\subsubsection{Communicating Finite-State Machines}
A natural formalism for implementing bMSCs are Communicating Finite--State
Machines (CFM) that are used for example in \cite{MSC02,MSC07,BOL08}. The
CFM consists of a~finite number of finite-state machines that communicate
with each other by passing messages via unbounded FIFO channels.
\begin{definition}
  Given a finite set $\procSet$ of processes and a finite set of message
labels~${\cal C}$, the~Communicating Finite-State Machine
  (CFM) ${\cal A}$ consists of Finite-State Machines (FSMs)
  $({\cal A}_{p})_{p \in \procSet}.$
  Every ${\cal A}_p$ is a~tuple
  $({\cal S}_p,{A}_p, \rightarrow_p,s_{p}, F_p)$, where:
  \begin{compactitem}
  \item ${\cal S}_p$ is a~finite set of states,

  \item ${A}_p \subseteq \{p!q(m) \mid q \in \procSet,m \in
{\cal C} \} \cup \{p?q(m) \mid q \in \procSet,m \in {\cal C} \}$ is a
set of actions,
  \item $\rightarrow_p \subseteq {\cal S}_p \times {A}_p \times
    {\cal S}_p$ is a~transition relation,
  \item $s_{p} \in {\cal S}_{p}$ is the~initial state, and
  \item $F_p \subseteq {\cal S}_p$ is a~set of local accepting states.
  \end{compactitem}
  We associate an unbounded FIFO error-free channel~${\cal B}_{p,q}$ with
  each pair of FSMs ${\cal A}_p, {\cal A}_q$. In every configuration,
  the~content of the~channel is a~finite word over the label alphabet
  ${\cal C}$.
\end{definition}

Whenever an FSM ${\cal A}_{p}$ wants to send a~message with a label $m \in
{\cal C}$ to ${\cal A}_{q}$, it enqueues the label $m$ into channel
${\cal B}_{p,q}$. We denote this action by $p!q(m)$. Provided there is
a~message with a label $m$ in the~head of channel ${\cal B}_{p,q}$, the FSM
${\cal A}_{q}$ can receive and dequeue the message with the label
$m$. This action is represented by
$q?p(m)$.
A \emph{configuration} of a~CFM ${\cal A} = ({\cal A}_{p})_{p \in
  \procSet}$ is a~tuple $C = (s,B)$, where $s \in \prod_{p \in \procSet}
({\cal S}_p)$ and $B \in ({\cal C}^{*})^{\procSet \times \procSet}$ ---
local states of the FSMs together with the~contents of the~channels. Whenever
there is a configuration transition $C_i \stackrel{a_i}{\rightarrow}
C_{i+1}$, there exists a process $p \in \procSet$ such that the
FSM~${\cal A}_p$ changes its local state by executing action $a_i \in A_p$
and modifies the content of one of the channels.

The CFM execution starts in an \emph{initial configuration} $s_{0} =
\prod_{p \in \procSet}\{s_{p}\}$ with all the~channels empty. The CFM is in
an \emph{accepting configuration}, if every FSM is in some of its final
states and all the~channels are empty. We will say that a~configuration is
a~\emph{deadlock}, if no accepting configuration is reachable from it. A~CFM
is \emph{deadlock-free} if no deadlock configuration is reachable from
the~initial configuration.  An \emph{accepting execution} of a CFM
${\cal A}$ is a~finite sequence of configurations $C_{1}
\stackrel{a_1}{\rightarrow} C_{2} \stackrel{a_2}{\rightarrow} \ldots
\stackrel{a_{n-1}}{\rightarrow} C_{n}$ such that $C_{1}$ is the~initial
configuration and $C_{n}$ is an accepting configuration. The word $a_1a_2
\cdots a_{n-1}$ is then an \emph{accepted word} of ${\cal A}$.
Given a CFM ${\cal A}$, the \emph{language} ${\cal L}({\cal A})$ is defined
as the set of all accepted words of ${\cal A}$.

\section{Controllable-choice Message Sequence Graphs}
For a~given MSG we try to construct a~CFM such that every execution
specified in the~MSG specification can be executed by the~CFM and the~CFM
does not introduce any additional unspecified execution.

\begin{definition}[\cite{MSC07}]
  An MSG $G$ is \emph{realizable} iff there exists a~deadlock-free CFM
  ${\cal A}$ such that ${\cal L}(G) = {\cal L}({\cal A})$.
\end{definition}

One of the most natural realizations are projections.  A
projection of a bMSC $M$ on a~process $p$, denoted by $M|_p$, is the sequence of events that are to
be executed by the process $p$ in $M$.  For every process $p
\in \procSet$, we construct a~FSM ${\cal A}_{p}$ that accepts a~single
word $M|_{p}$.  This construction is surprisingly powerful and models
all of the~bMSC linearizations.
\begin{proposition}
  \label{prop:msclang} Let $M$ be a~bMSC, then CFM ${\cal A} = (M|_{p})_{p
    \in \procSet}$ is a~realization, i.e. ${\cal L}(M) = {\cal L}({\cal A})$.
\end{proposition}

It turns out that the~main obstacle when realizing MSG are nodes with
multiple outgoing edges --- choice nodes. It is necessary to ensure that all
FSMs choose the~same run through the~MSG graph. This can be hard to achieve as the~system is distributed.

In what follows,  we present a~known class of local-choice MSG
specifications that admits a~deadlock-free realization by adding control
data into the messages. Then, we define a~new class of
\emph{controllable-choice} MSG and compare the~expressive power of the~presented
classes.

\subsubsection{Local-choice MSG} is a class studied by many authors
\cite{MSC04,MSC35,BOL08,jard:inria-00584530,BOL01,BOL17}. Let $M$ be a~bMSC,
we say that a~process $p \in \procSet$ \emph{initiates} the bMSC $M$ if
there exists an event $e$ in $M$, such that ${P}(e) = p$ and there is no
other event $e'$ in bMSC $M$ such that $e' < e$.  For a~given MSG, every
node $s \in {\cal S}$ identifies a set \emph{triggers}$(s)$, the set of
processes initiating the~communication after the node $s$. Note that it
may not be sufficient to check only the~direct successor nodes in the~MSG.

\begin{definition}
  Let $G = ({\cal S},\tau,s_{0}, s_{f},{\it L})$ be an MSG. For a node $s \in
  {\cal S}$, the~set \emph{triggers}$(s)$ contains process $p$ if and only
  if there exists a~path $\sigma = \sigma_{1} \sigma_{2} \ldots \sigma_{n}$
  in $G$ such that $(s,\sigma_{1}) \in \tau$ and $p$ initiates bMSC
  ${\it L}(\sigma).$
\end{definition}

\begin{definition}
  A choice node $u$ is a \emph{local-choice} node iff
  \emph{triggers}$(u)$ is a singleton. An MSG specification $G$ is
  \emph{local-choice} iff every choice node of $G$ is local-choice.
\end{definition}

Local-choice MSG specifications have the~communication after every choice node
initiated by a~single process --- the~choice leader.
In \cite{BOL08} a deadlock-free realization with additional data in messages
is proposed.  It is easy to see that every MSG specification $G$ is
deadlock-free realizable if there is a local-choice MSG $G'$ such that
${\cal L}(G) = {\cal L}(G')$. Note that the equivalence can be algorithmically
checked due to \cite{BOL17}.

\subsubsection{Controllable specifications.}
The difficulties when realizing MSG are introduced by choice nodes. In
local-choice MSG, the~additional message content is used to ensure a~single
run through the~graph is executed by all FSMs. In case of
controllable-choice MSG, the~additional content serves the~same purpose but
besides informing about the~node the~FSMs are currently executing the~FSMs
also attach a~prediction about its future execution.

This allows us to relax the~restriction on choice nodes and allows certain
non-local choice nodes to be present in the~specification.  However, it is
necessary to be able to resolve every occurrence of the~choice node, i.e.\
make the~decision in advance and inform all relevant processes.

\begin{definition}
  Let $M = (E,<,\procSet,{\cal T},{P},{\cal M}, {l})$ be a~bMSC
  and $P' \subseteq \procSet$ be a~subset of processes. A~send event $e \in
  E$ is a~\emph{resolving event} for $P'$ iff
$$ \forall p \in P' \ \exists e_{p} \in {P}^{-1}(p) \textrm{ such that } e < e_{p}.$$
\end{definition}

Intuitively, resolving events of $M$ for $P'$ can distribute information to
all processes of $P'$ while executing the~rest of $M$, provided that other
processes are forwarding the~information.

\begin{definition}
  Let $G = ({\cal S},\tau,s_{0}, s_{f},{\it L})$ be an MSG. A~choice node
  $u$ is said to be \emph{controllable-choice} iff it satisfies both of the
  following conditions:
  \begin{itemize}
  \item For every path $\sigma$ from $s_{0}$ to $u$ there exists a~resolving
    event in bMSC ${\it L}(\sigma)$ for \emph{triggers}$(u)$.
  \item For every path $\sigma = s_{1} s_{2} \ldots u$ such that $(u,s_{1})
    \in \tau$, there exists a~resolving event in bMSC ${\it L}(\sigma)$ for
    \emph{triggers}$(u)$.
  \end{itemize}
\end{definition}

Intuitively, a~choice node is controllable-choice, if every path from
the~initial node is labeled by a~bMSC with a~resolving event for all events
initiating the~communication after branching. Moreover, as it is necessary
to attach only bounded information, the~same restriction is required to hold
for all cycles containing a~controllable-choice node. In \cite{bachelor_thesis}
we propose an algorithm that determines whether a~given choice node is
a controllable-choice node.

\begin{definition}
  An MSG specification $G$ is \emph{controllable-choice} iff every choice
  node is either local-choice or controllable.
\end{definition}

Note that there is no bound on the~distance between the~resolving event and
the~choice node it is resolving.

\subsubsection{Local-choice vs. controllable-choice MSG.}
In the~following, we show that the controllable-choice MSG are more
expressive than local-choice MSG.  It is easy to see that every
local-choice MSG is also a~controllable-choice MSG and that not every
controllable-choice MSG is local-choice. In the following theorem, we
strengthen the result by stating that the class of MSG that are language
equivalent to some controllable-choice MSG is more expressive than the~class
of MSG that are language-equivalent to some local-choice MSG.

\begin{theorem}
  The class of MSG that are language-equivalent to some local-choice MSG,
  forms a~proper subset of MSG that are language-equivalent to some
  controllable-choice MSG.
\end{theorem}

\begin{proof}
  Consider a MSG $G = ({\cal S},\tau,s_{0}, s_{f},{\it L})$ with three nodes $s_0, s_f$ and $s$, such
that $(s_0,s), (s,s), (s,s_f) \in \tau$ and the only non--empty bMSC is
${\it L}(s)$ with two processes $p,q$. The projection
of events on $p$ is $p!q(m), p?q(m')$ and similarly for $q$ the
projection is $q!p(m'), q?p(m)$. Note that the only choice node $s$ is
controllable as both send events are resolving events for both of the
processes.

The MSG $G$ violates a necessary condition to be language equivalent to
a local-choice specification. Intuitively, the condition states that its language must be a subset
of a language of a generic local-choice equivalent MSG (for more details
see \cite{BOL17}).
\end{proof}

\section{Realizability of Controllable-choice MSG}
In this section we present an algorithm for realization of
controllable-choice MSG.  The class of local-choice specifications admits
a~natural deadlock-free realization because every branching is controlled by
a~single process.

As the~\emph{triggers} set for controllable-choice nodes can contain
multiple processes, we need to ensure that all of them reach a~consensus
about which branch to choose.  To achieve this goal, we allow the~FSMs in
certain situations to add a~behavior prediction into its outgoing
messages. Those predictions are stored in the~finite-state control units and
are forwarded within the~existing communication to other FSMs.

The length of the~prediction should be bounded, as we can attach only
bounded information to the~messages and we need to store it in
the~finite-state control unit. Therefore, it may be necessary to generate
the~behavior predictions multiple times.  As the~realization should be
deadlock-free, we must ensure that the~predictions are not conflicting ---
generated concurrently by different FSMs. To solve this we sometimes send
together with the~prediction also an event where the~next prediction should
be generated.

\begin{definition}
  A \emph{prediction} for an MSG $G = ({\cal S},\tau,s_{0}, s_{f},{\it L})$
  is a~pair $(\sigma,e) \in {\cal S}^{*} \times (E \cup \bot)$, where
  $E$ is the set of all events of bMSCs assigned by ${\it L}$, the path
  $\sigma$ is called a~\emph{prediction path}, and
  $e$, called a \emph{control event}, is an

  event from ${\it L}(\sigma)$.
  A prediction path must satisfy one of the~following conditions:
  \begin{compactitem}
  \item The prediction path $\sigma$ is the~longest common prefix of all MSG
    runs. This special initial prediction path is named $initialPath$.
  \item The prediction path $\sigma$ is the~shortest path $\sigma =
    \sigma_{1} \sigma_{2} \ldots \sigma_{n}$ in $G$ satisfying

    \begin{enumerate}
    \item $\sigma_{n} \in {\cal L}$,  or
    \item $\sigma_{n} \in {\cal U} \: \wedge \: \exists \: 1 \leq i < n:
      \sigma_{i} = \sigma_{n}$, or
    \item $\sigma_{n} = s_{f}$,
    \end{enumerate}
    where ${\cal L} \subseteq {\cal S}$ is the~set of all local-choice nodes
    and ${\cal U} \subseteq {\cal S}$ is the~set of all controllable-choice
    nodes.
  \end{compactitem}
\end{definition}

We refer to the~first node and to the~last node of a~prediction path
$\sigma$ by $\mathrm{\emph{firstNode}}(\sigma)$ and
$\mathrm{\emph{lastNode}}(\sigma)$, respectively.

\begin{lemma}
  \label{lem:resolv}
  If the~prediction path $\sigma$ ends with a~controllable-choice node $u$,
  the~bMSC ${\it L}(\sigma)$ contains a~resolving event for
  \emph{triggers}$(u)$ on ${\it L}(\sigma)$.
\end{lemma}
\begin{proof}
  There are two cases to consider
  \begin{itemize}
  \item If $\sigma = \mathrm{\emph{initialPath}}$, then
    \emph{firstNode}$(\sigma) = s_{0}$ and as node $u$ is controllable-choice,
    the~path $\sigma$ contains a~resolving event for \emph{triggers}$(u)$.
  \item Otherwise, the~controllable-choice node $u$ occurs twice in the~path
    $\sigma$. As every cycle containing a~controllable-choice node has to
    contain a~resolving event for the~node,
    there is a~resolving event for \emph{triggers}$(u)$ on path $\sigma$.
  \end{itemize}
  As there are no outgoing edges allowed in $s_{f}$, the~terminal node
  $s_{f}\not\in{\cal U}$.
\qed
\end{proof}
Note, that the number of events in a~given MSG is finite and
the~length of each~prediction path is bounded by $2 \cdot \vert {\cal S}
\vert$.

When the~CFM execution starts, every FSM is initialized with an initial
prediction --- $($\emph{initialPath}$,e_{i})$ --- and starts to execute
the~appropriate projection of ${\it L}($\emph{initialPath}$)$. The value of
$e_{i}$ depends on the~\emph{initialPath}. Let
\emph{lastNode}$($\emph{initialPath}$) = \sigma_{n}$.  In case of $\sigma_{n}
\in {\cal U}$, the~event $e_{i}$ is an arbitrary resolving event from
${\it L}($\emph{initialPath}$)$ for \emph{triggers}$(\sigma_{n})$. It
follows from Lemma~\ref{lem:resolv} that there exists such an event.  If
$\sigma_{n} \in {\cal L} \cup \{s_{f}\}$, we set $e_{i} = \bot$.

Every FSM stores two predictions, one that is being currently executed and
a~future prediction that is to be executed after the~current one. Depending
on the~\emph{lastNode} of the~current prediction, there are the following
possibilities where to generate the~future prediction.
\begin{compactitem}
\item If \emph{lastNode} of the~current prediction is in ${\cal L}$,
  the~future prediction is generated by the~local-choice leader, while
  executing the~first event after branching.
\item If \emph{lastNode} of the~current prediction is in ${\cal U}$,
  the~future prediction is generated by an FSM that executes the~control
  event of the~current prediction, while executing the~resolving event.
\item If the~\emph{lastNode} of the~current prediction is $s_{f}$, no
  further execution is possible and so no new prediction is generated.
\end{compactitem}
When an FSM generates a~new prediction, we require that there exists a
transition in the MSG from the last node of the current prediction path to
the first node of the future prediction path, as the concatenation of
prediction paths should result in a~path in the~MSG.  If an FSM
generates a~future prediction ending with a~controllable-choice node $u$, it
chooses an arbitrary resolving event for \emph{triggers}$(u)$ to be
the~resolving event in the~prediction. The existence of such an event
follows from Lemma~\ref{lem:resolv}.  To ensure that other FSMs are informed
about the~decisions, both predictions are attached to every outgoing
message. The computation ends when no FSM is allowed to generate any future
behavior.

\subsection{Algorithm}
\begin{algorithm}[p]
\caption{Process $p$ implementation}
\label{alg:impl}
\begin{algorithmic}[1]

\STATE \textbf{Variables}: $currentPrediction, nextPrediction, eventQueue;$
\STATE $currentPrediction \leftarrow (initialPath,e_{i});$
\STATE $nextPrediction \leftarrow \bot;$
\STATE $eventQueue \leftarrow $\textbf{push}$({\it L}(initialPath)|_{p});$
\WHILE{true}
\IF{$eventQueue$ is empty}
 \STATE \textbf{getNextNode}$();$
\ENDIF
\STATE $e \leftarrow \textbf{pop}(eventQueue);$

\IF{$e$ is a~send event}
 \IF{$e$ is the~resolving event in $currentPrediction$}

  \STATE $node \leftarrow \mathrm{lastNode}(\textbf{path}(currentPrediction))$;
  \STATE $nextPrediction \leftarrow \textbf{guessPrediction} (node);$
 \ENDIF
\STATE \textbf{send}$(e,currentPrediction,nextPrediction)$;
\ENDIF
\IF{$e$ is a~receive event}
 \STATE \textbf{receive}$(e,cP,nP);$
 \IF{$nextPrediction = \bot$}
 \STATE $nextPrediction \leftarrow nP;$
 \ENDIF
\ENDIF
\ENDWHILE
\end{algorithmic}
\end{algorithm}

\floatname{algorithm}{Function}

\begin{algorithm}[p]
\caption{getNextNode function for process $p$}
\label{proc:getnextnode}
\begin{algorithmic}[1]
\FUNCTION{\textbf{getNextNode}()}

\STATE  $node \leftarrow \mathrm{lastNode}(\textbf{path}(currentPrediction))$;

\IF{$node \in {\cal U} \wedge p \in \mathrm{triggers}(node)$}
\STATE $currentPrediction \leftarrow nextPrediction;$
\STATE $nextPrediction \leftarrow \bot;$
\STATE $eventQueue \leftarrow $\textbf{push}$({\it L}(\textbf{path}(currentPrediction))|_{p});$
\ELSIF {$node \in {\cal L} \wedge p \in \mathrm{triggers}(node)$}
\STATE $currentPrediction \leftarrow \textbf{guessPrediction} (node);$
\STATE $nextPrediction \leftarrow \bot$
\STATE $eventQueue \leftarrow $\textbf{push}$({\it L}( \textbf{path}(currentPrediction))|_{p});$
\ELSE
\STATE $currentPrediction \leftarrow \bot$;
\STATE $nextPrediction \leftarrow \bot$;
\STATE \textbf{polling}(); \hspace{3em}
\ENDIF

\ENDFUNCTION{}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[p]
\caption{Polling function for process $p$}
\label{proc:polling}
\begin{algorithmic}[1]
\FUNCTION{\textbf{polling}$()$}
\WHILE{true}
\IF{$p$ has a~message in some of its input buffers}
\STATE \textbf{receive}$(e,cP,nP);$
\STATE $currentPrediction \leftarrow cP;$
\STATE $nextPrediction \leftarrow nP;$
\STATE $eventQueue \leftarrow $\textbf{push}$({\it L}(\textbf{path}(currentPrediction))|_{p});$
\STATE $\textbf{pop}(eventQueue);$
\STATE $\textbf{return;}$
\ENDIF
\ENDWHILE
\ENDFUNCTION{}
\end{algorithmic}
\end{algorithm}

In this section, we describe the~realization algorithm. All the~FSMs execute
the~same algorithm, an implementation of the~FSM ${\cal A}_{p}$ is
described in Algorithm~\ref{alg:impl}.
We use an auxiliary function \textbf{path} that returns a~prediction path
for a~given prediction.  Every FSM stores a~queue of events that it should
execute --- $eventQueue$. The queue is filled with projections of bMSCs
labeling projection paths --- ${\it L}(\mathrm{prediction~path})|_{p}$ for
FSM ${\cal A}_{p}$. The execution starts with filling the~queue with
the~projection of the~$initialPath$.

The FSM executes a~sequence of events according to its $eventQueue$. In
order to exchange information with other FSMs, it adds its knowledge of
predictions to every outgoing message, and improves its own predictions by
receiving messages from other FSMs.

When the~FSM executes a~control event of
the~current prediction, it is responsible for generating the~next
prediction. The function \textbf{guessPrediction}$(u)$ behaves as described
in the~previous section. It chooses a~prediction $(\sigma, e)$, such that
$(u, \mathrm{firstNode}(\sigma)) \in \tau$. If \emph{lastNode}$(\sigma) \in
{\cal U}$, then $e$ is a~chosen resolving event in bMSC ${\it L}(\sigma)$ for
the~\emph{triggers} set of the~\emph{lastNode}$(\sigma)$. Otherwise, we
leave $e = \bot$.

If the~$eventQueue$ is empty, the~FSM runs the~\textbf{getNextNode} function
to determine the~continuation of the~execution.  If the~\emph{lastNode}
of the~current prediction is a~controllable-choice node and $p$ is in
the~\emph{triggers} set of this node, it uses the~prediction from its
variable $nextPrediction$ as its $currentPrediction$. The variable
$nextPrediction$ is set to $\bot$.

If the~\emph{lastNode} of the~currentPrediction is a~local-choice node and
$p$ is the~leader of the~choice, it guesses the~prediction and assigns it to
the~appropriate variables.
Otherwise, the~FSM forgets its predictions and enters a~special polling
state. This state is represented by the~\textbf{Polling} function. Whenever
the~FSM receives a~message, it sets its predictions according to
the~message. The pop function on line $8$ ensures the~consistency of
the~$eventQueue$.

An execution is finished successfully if all the FSMs are in the~polling
state and all the~buffers are empty. The correctness proof of the
following theorem is attached in the Appendix~\ref{chap:correctness}.

\begin{theorem}
  Let $G$ be a~controllable-choice MSG. Then the~CFM ${\cal A}$
  constructed by Algorithm~\ref{alg:impl} is a~deadlock-free realization
  i.e. ${\cal L}(G) = {\cal L}({\cal A})$.
\end{theorem}

\section{Conclusion}

In this work we studied the message sequence graph realizability problem,
i.e., the~possibility to make an efficient and correct distributed
implementation of the~specified system.  In general, the~problem of
determining whether a~given specification is realizable is
undecidable. Therefore, restricted classes of realizable specifications are
in a~great interest of software designers.

In recent years, a promissing research direction is to study deadlock-free
realizability allowing to attach bounded control data into existing
messages. This concept turns out to be possible to realize reasonable
specifications that are not realizable in the~very original setting.  In
this work we introduced a~new class of so called controllable-choice message
sequence graphs that admits a~deadlock-free realization with additional
control data in messages. In other words, we have sucesfully extended the
class of MSG conforming in the established setting of realizability.
Moreover, we have presented an algorithm producing realization for a given
controllable-choice message sequence graphs.

\bibliographystyle{plain}