# Dynamic Multimodal Information Bottleneck for Multimodality Classification

Yingying Fang1∗, Shuang Wu3, Sheng Zhang1, Chaoyan Huang4, Tieyong Zeng4,
Xiaodan Xing2,
Simon Walsh1, Guang Yang1,2

1National Heart and Lung Institute, Imperial College London, London, SW7 2AZ,
UK
2Bioengineering Department and Imperial-X, Imperial College London, London,
W12 7SL, UK
3Black Sesame Technologies, Fusionopolis, Singapore
4The Chinese University of Hong Kong, Shatin, Hong Kong
<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Equal
ContributionCorresponding Author

###### Abstract

Effectively leveraging multimodal data such as various images, laboratory
tests and clinical information is becoming increasingly attractive in a
variety of AI-based medical diagnosis and prognosis tasks. Most existing
multi-modal techniques only focus on enhancing their performance by leveraging
the differences or shared features from various modalities and fusing feature
across different modalities. These approaches are generally not optimal for
clinical settings, which pose the additional challenges of limited training
data, as well as being rife with redundant data or noisy modality channels,
leading to subpar performance. To address this gap, we study the robustness of
existing methods to data redundancy and noise and propose a generalized
dynamic multimodal information bottleneck framework for attaining a robust
fused feature representation. Specifically, our information bottleneck module
serves to filter out the task-irrelevant information and noises in the fused
feature, and we further introduce a sufficiency loss to prevent dropping of
task-relevant information, thus explicitly preserving the sufficiency of
prediction information in the distilled feature. We validate our model on an
in-house and a public COVID19 dataset for mortality prediction as well as two
public biomedical datasets for diagnostic tasks. Extensive experiments show
that our method surpasses the state-of-the-art and is significantly more
robust, being the only method to remain performance when large-scale noisy
channels exist. Our code is publicly available at
https://github.com/ayanglab/DMIB.

##  1 Introduction

Medical practitioners utilize various sources of data such as electronic
health records, laboratory tests, genetic information and medical imaging
modalities such as Computerized Tomography (CT), Magnetic Resonance Imaging
(MRI), Positron Emission Tomography (PET) etc. for medical diagnosis and
prognosis. Historically, partly due to domain gaps and specialization,
clinicians primarily operated on each data modality in silo, drawing upon the
distinctive features from an individual source to perform diagnosis and
prognosis. Nonetheless, it is undeniable that integrating multi-modal data
effectively would be beneficial for diagnosis and prognosis tasks, by not only
incorporating extra guidance but also possibly providing novel insights,
enabled by a more holistic understanding of the entirety.

The advent of deep learning has sparked several lines of works centered on
healthcare applications [46], among which AI-based medical image analysis [34]
has enjoyed prominent success, with deep learning models achieving performance
on par with or even surpassing radiologists on some tasks. Likewise, deep
learning has also demonstrated immense potential for analysing electronic
health records [32] and genetic information [48]. Yet, despite impressive
performance on individual modalities, developing techniques to effectively
leverage multiple modalities remains challenging [21, 7, 26, 3].

The general multimodal learning approach is to separately train a model for
each modality to extract a modal-specific feature vector, and subsequently
fusing these individual features to obtain a multimodal feature
representation. The fused feature is then propagated to downstream task
modules to perform supervised learning. Common approaches for feature fusion
include concatenation, attention-weighted, common subspace projection, graph-
based, and transformer-based methods [9, 1].

While experimenting with these different fusion schemes in the context of
clinical applications, we observe that they generally suffer from significant
drops in model performance. Clinical applications typically have limited
training data, and the difficulty is compounded by the fact that clinical data
is often subject to various forms of noise such as missing data, inaccurate
clinical records, and subjective biases in patients’ self-assessment. Existing
methods generally suffer from a susceptibility to overfitting, and learning to
extract task-relevant information is often suboptimal when training data is
scarce. An even more glaring weakness is the sensitivity and low robustness
towards noisy modality channels, where most existing models suffer from
significant performance drops.

To address these issues, we propose a Dynamic Multimodal Information
Bottleneck (DMIB) framework, drawing inspirations from mutual information
theory [40, 29], information bottleneck [12, 41, 38]. Specifically, our DMIB
consists of the following key components: i) an information bottleneck module
along with dropout regularization and masking of modalities to remediate
feature redundancy and model overfitting; ii) an explicit supervision to
maximize the task relevant information in the final fused feature. We conduct
comprehensive experiments for multimodality classification tasks across four
datasets. Our method not only achieves state-of-the-art performance, but also
demonstrates remarkable robustness, retaining similar performance when a
modality consists of pure noise.

To summarize, our key contributions are: i) We design an information
bottleneck module together with a mutual information inspired sufficiency loss
which can be applied to arbitrary multimodal classification tasks as a plug-
and-play module. Our fusion strategy dynamically filters out noise, maximizes
the inclusion of relevant information and eliminates the need for heuristic or
greedy feature selection approaches that were often employed in previous
studies, leading to a superior performance. ii) To our knowledge, we are the
first to conduct principled experiments to study the performance of fusion
methods under different levels of noisy and redundant modalities. iii) Our
method demonstrates outstanding robustness by retaining prediction performance
even when noise and redundancy are introduced, making it particularly suitable
for clinical settings where datasets tend to be small and biomarkers are
unclear.

Figure 1: (A) Illustration of our Dynamic Multimodal Information Bottleneck
framework for a lung disease prognosis task: a) Separate backbones are used to
first extract features from each modality. b) These features are concatenated
to form a preliminary fused feature $f$. c) $f$ is distilled via an
information bottleneck module, arriving at a final fused feature $f^{*}$. d)
We formulate a sufficiency loss to preserve task-relevant information in
$f^{*}$. (B) The mutual information between various entities can be visualized
with Venn diagrams.

##  2 Related Works

###  2.1 Multimodal Learning for Clinical Applications

In recent years, there has been growing interests and efforts in developing
multimodal fusion for clinical applications [26, 3, 9, 1]. Compared to the
early fusion cannot address the domain gaps between modalities [24] and late
fusion strategies which overlook the cross-modality information [33],
intermediate fusion methods which perform fusion at the feature level [30, 14]
has attracted much investigation on various techniques for extracting
multimodal feature learning in deep neural techniques. These methods could be
broadly categorised into concatenation-based [45, 24, 2], attention-based [19,
10, 30], projection into aligned subspaces [44, 50, 39, 13], graph-based [49,
8, 20], and recent Transformer-based [25, 43, 6]. While concatenation methods
are parameter-free and straightforward, they might not identify the intricate
relationships between diverse modalities. Attention-based methods learns
importance scores for intermediate multi-modality features, which allows for
modeling the complex relationships between different modalities. However,
introducing the attention mechanisms, along with additional network parameters
increases the propensity to overfitting. Recently, a major trend in multimodal
learning is to leverage transformer modules to perform cross-attention across
the various modalities to obtain a fused feature representation. While
transformer based multimodal learning deliver state-of-the-art performance for
large scale datasets, they tend to be lackluster when training data are scarce
[43]. Besides, graph models are also gaining traction in multimodal tasks with
their unique ability to leverage the relations between the data from various
modalities.

###  2.2 Mutual Information

Mutual information is a measure of the statistical dependency between random
variables [11]. The core principle of deep learning approaches is to
automatically learn how to extract optimal features from data, instead of
manually crafting features from heuristic guidance. In this light, mutual
information lies at the heart of deep learning, since it could be invoked to
quantify the dependency between the learned feature representation and desired
network output.

Mutual Information Estimation [22] proposes the InfoMax principle which seeks
to maximize the mutual information between feature and model output. This
serves as a general prescription which is generally pertinent to neural
networks and there have been many works in the recent years that explore
optimal ways for mutual information estimation. One line of approach is to
employ an additional neural network for estimation [4, 17] while another
approach seeks variational bounds for mutual information [31]. However, mutual
information remains a notoriously difficult problem due to the curse of
dimensionality [29]. In other words, the amount of data samples to accurately
bound mutual information scales exponentially with the dimensionality of the
feature. To tackle this, researchers have proposed alternatives to mutual
information, such as the Wasserstein dependency measure in [29] and the
variational distillation loss in [36].

Information Bottleneck Closely related to mutual information is the concept of
information bottleneck. Introduced in [37], the authors further advance this
principle to put forward an explanation of the learning process in deep neural
networks [38]. Given raw data inputs, the notion of a bottleneck in the model
effectuates an information distillation process, which retains only useful
information, while discarding irrelevant information and superfluous noises.
This is analogous to how humans learn and master knowledge and abstractions.
The information bottleneck method is highly pertinent for improving model
generalization and robustness and reducing overfitting [40, 5]. This can be
inherently understood from the intuition that a generalisable model should
learn feature abstractions that capture the essence of the task, instead of
memorizing instance-specific characteristics in the training set.

##  3 Methodology

An overview of our DMIB framework is found in Figure 1 (A). We employ separate
backbones to extract features from different modalities. Supervision is
applied for each backbone to guarantee the intermediate features have
sufficient prediction information 111To prevent the model predictions from
being dominated by the modality with larger dimensions, we also enforce
dimension equality by upsampling low dimensional modality features..
Subsequently, we concatenate the extracted features for each modality to form
an initial fused feature $f$, which preserves complete information from each
modality. We introduce an information bottleneck module to perform information
distillation, arriving at our final feature $f^{*}$. To ensure sufficiency of
task information in $f^{*}$, we introduce a sufficiency loss to ensure that no
task-relevant information are being discarded.

To begin, we introduce our overall supervision objective displayed in Figure 1
(B) which motivates the design of our DMIB framework222An overview of relevant
mutual information definitions is given in the Appendix.. Subsequently, we
cover the details of our information bottleneck module and our sufficiency
loss.

###  3.1 Overall supervision

Given $f^{*}$ an encoded fused feature from the direct fused feature $f$, we
would like the ideal fused feature representation to contain sufficient
predictive information in $f$ while discarding all redundancy and noise. The
information contained in $f^{*}$, is given by the mutual information between
$f^{*}$ and $f$:

$I(f;f^{*})=\mathbb{E}_{p(f,f^{*})}\left[\log\frac{p(f,f^{*})}{p(f)p(f^{*})}\right].$
(1)

It can be further decomposed into two components by the chain rule of mutual
information [12] (given in the Appendix) as:

$I(f;f^{*})=I(f;f^{*}|y)+I(f^{*};y).$ (2)

$I(f;f^{*}|y)$ quantifies the amount of task-irrelevant information in $f^{*}$
and $I(f^{*};y)$ quantifies the predictive information in $f^{*}$ for task
$y$. The goal is to simultaneously minimize redundancy $I(f;f^{*}|y)$ and
maximize task relevance $I(f^{*};y)$, which can be combined into the
information bottleneck objective [37]:

$\begin{aligned} \min_{{f^{*}}}\mathcal{L}_{IB}=I(f;f^{*}|y)-\gamma
I(f^{*};y)\end{aligned}.$ (3)

However, estimating for mutual information in high dimensions is intractable
in general [31, 27] due to the curse of dimensionality [29], _i.e._ accurate
estimation of the expected information in empirical distributions requires a
sample size that scales exponentially with the dimension of the data. In light
of this, we do not explicitly optimize for Eqn. (3) via mutual information
estimation. Instead, we delegate information distillation to our information
bottleneck module in Section 3.2. For maximizing the task-relevant information
$I(f^{*};y)$, we formulate a tractable sufficiency loss in Section 3.3. The
joint framework consisting of the information bottleneck module and the
sufficiency loss enables $f^{*}$ to converge to an ideal feature with maximal
relevance and minimal redundancy.

###  3.2 Information Bottleneck Module

Given $n$ features $f_{1},\cdots,f_{n}$ extracted from $n$ modalities, we
first generate an initial fused feature $f$ by direct concatenation with a
masking

$f=\bigoplus_{i=1}^{n}m_{i}f_{i},$

where $f\in\mathbb{R}^{N}$ and $m_{i}$ denotes a masking coefficient.
Specifically, at each training iteration, we uniformly sample a random number
$u\sim U([0,1])$, and the masking coefficients are formally given by
$m_{i}=\mathbbm{1}_{[\frac{i-1}{2n)};\frac{i}{2n}]}(u).$ In other words, the
model can only access the full features across all modalities for half of the
training iterations, while for the other half, a single modality $f_{i}$ is
masked out. The motivation of masking individual modalities is to allow the
model to function in the absence of data-streams from a modality, thus
improving robustness [15]. Subsequently, our information bottleneck module
comprises of two linear projection layers along with dropouts and ReLU. The
operations may be summarized as:

$f\xrightarrow[\text{Dropouts + ReLU}]{\text{Linear
Projection}}z\xrightarrow[\text{Dropouts + ReLU}]{\text{Linear
Projection}}f^{*}.$ (4)

$z$ is of dimension $p<n$ while the final feature representation $f^{*}$ has
$n$ dimensions. The purpose of re-projecting $z$ back to the same dimensions
as $f$ is in order to perform more effective feature-level supervision of the
distilled feature and the initial feature to learn a more predictive feature
$f^{*}$, which is introduced in the next section. It is observed that the
feature-level supervision is more effective when $f^{*}$ and the initial
feature $f$ is aligned with equal dimensions.

###  3.3 Sufficiency Loss

In this section, we introduce our sufficiency loss which serves as a feature-
level supervision to maximize the task-relevant information $I(f^{*};y)$ in
Eqn. (3). Since $f^{*}$ is a feature extracted from $f$, the information
contained in $f^{*}$ cannot exceed that of $f$, and $I(f^{*};y)\leq I(f;y)$.
Maximizing $I(f^{*};y)$ is therefore equivalent to:

$\min I(f;y)-I(f^{*};y).$ (5)

To solve this optimization problem, we make use of the following proposition
[36, 23] (proof can be found in the Appendix):

$KL[p(y|f)\|p(y|f^{*})]=0\implies I(y;f)-I(y;f^{*})=0,$ (6)

where $KL$ denotes the Kullback-Leibler divergence. Therefore, instead of
having to estimate the mutual information in Eqn. (5), we formulate our
sufficiency loss as

$\mathcal{L}_{\text{Sufficiency}}=KL[p_{\theta}(y|f)\|p(y|f^{*})].$ (7)

###  3.4 Overall objective

The overall loss function in our DMIB framework is:

$\displaystyle\mathcal{L}=\mathcal{L}_{f}(y,\hat{y}_{f})+\alpha\sum_{i}\mathcal{L}_{\text{modality}}(y,\hat{y}_{f_{i}})+$
$\displaystyle\underbrace{\mathcal{L}_{f^{*}}(y,\hat{y}_{f^{*}})+\beta\mathcal{L}_{\text{sufficiency}}(\hat{y}_{f},\hat{y}_{f^{*}})}_{\text{Supervision
of Information Bottleneck Module}}$ (8)

where $\mathcal{L}_{f}$ and $\mathcal{L}_{f^{*}}$ are respective losses to
supervise the direct fused expression datafeature and distilled fused
features, and $\mathcal{L}_{\text{modality}}$ supervises each modality
backbone. Here, $\alpha$ and $\beta$ are model hyperparameters to control the
roles of modal-specific supervision and feature-level supervision,
respectively. $\hat{y}_{f}$ and $\hat{y}_{f^{*}}$ are the classifier results
from the observed fused feature and distilled fused feature.

##  4 Experiments

###  4.1 Datasets

We trained our proposed DMIB for various multimodal medical classification
tasks on four datasets: i) Our in-house ITAC dataset, which includes HRCT and
18 clinical features of 566 COVID19 inpatients, is utilized for predicting the
10-day mortality rate of COVID19 inpatients; ii) the public iCTCF dataset
[28]333Available at https://ngdc.cncb.ac.cn/ictcf/, which includes HRCT scans
and up to 81 clinical features, is used to predict the morbidity outcomes of
751 COVID19 patients and the detection of 751 COVID19 patients from 529 non-
COVID19 patients respectively; iii) BRCA dataset for diagnosis of breast
carcinoma PAM50 subtypes (mRNA expression data, DNA methylation data, and
miRNA expression data) of 875 patients [42]; iv) ROSMAP dataset for diagnosis
of Alzheimer’s Disease from 351 patients [42] 444iii) and iv) are available at
https://github.com/txWang/MOGONET. A summary of the various datasets is found
in Table 1. It is worth mentioning that ITAC and iCTCF are collected from
different countries and have no overlap in enrolled patients.

Table 1: Summary of datasets

Dataset | Modality | Task Description | Enrolled Patients | Generated montages
---|---|---|---|---
ITAC | HRCT scans + up to 18 clinical features | Prognosis for COVID19 mortality in 10 Days | Deceased: 257 / Cured: 309 | Deceased: 3084 / Cured: 3090
iCTCF | HRCT scans + up to 81 clinical features | Prognosis for COVID19 morbidity outcome | Severe symptoms: 202 / Mild symptoms: 549 | Severe symptoms: 606 / Mild symptoms: 549
Diagnosis for COVID19 patients | PCR positive: 751 / PCR negative: 529 | PCR positive: 3755 / PCR negative: 3174
BRCA | mRNA, DNA methylation, miRNA | Diagnosis for breast carcinoma PAM50 subtype | Normal: 115 / Basal: 131 / Her2: 46 / LumA: 436 / LumB: 147 | /
ROSMAP | mRNA, DNA methylation, miRNA | Diagnosis for Alzheimer’s Disease | Normal: 169 / AD: 182 | /

Table 2: Performance of various methods on the ITAC dataset. Bold denotes the
clinical settings where each methods achieves best AUC.

| Test |  | Test
---|---|---|---
| AUC | Accuracy | Sensitivity | Specificity | $\mbox{JW}_{0.5}$ | $\mbox{JW}_{0.6}$ |  | AUC | Accuracy | Sensitivity | Specificity | $\mbox{JW}_{0.5}$ | $\mbox{JW}_{0.6}$
| Single modality |  | Fusion: Concatenation [24]
clinical 1 | 0.76 | 0.69 | 0.75 | 0.63 | 0.69 | 0.70 | clinical 1 | 0.77 | 0.71 | 0.74 | 0.68 | 0.71 | 0.72
clinical 4 | 0.82 | 0.75 | 0.77 | 0.73 | 0.75 | 0.75 | clinical 4 | 0.78 | 0.69 | 0.65 | 0.72 | 0.69 | 0.68
clinical 7 | 0.82 | 0.75 | 0.74 | 0.76 | 0.75 | 0.75 | clinical 7 | 0.83 | 0.76 | 0.72 | 0.78 | 0.75 | 0.74
clinical 18 | 0.81 | 0.73 | 0.71 | 0.76 | 0.74 | 0.73 | clinical 18 | 0.80 | 0.74 | 0.62 | 0.85 | 0.74 | 0.71
CT only | 0.77 | 0.72 | 0.57 | 0.85 | 0.71 | 0.68 | pure noise | 0.74 | 0.66 | 0.72 | 0.62 | 0.67 | 0.68
| Fusion: Attention [10] |  | Fusion: Transformer [25]
clinical 1 | 0.81 | 0.76 | 0.72 | 0.78 | 0.75 | 0.74 | clinical 1 | 0.66 | 0.65 | 0.54 | 0.74 | 0.64 | 0.62
clinical 4 | 0.81 | 0.74 | 0.77 | 0.72 | 0.75 | 0.75 | clinical 4 | 0.64 | 0.57 | 0.51 | 0.62 | 0.62 | 0.55
clinical 7 | 0.68 | 0.62 | 0.51 | 0.71 | 0.61 | 0.59 | clinical 7 | 0.73 | 0.67 | 0.66 | 0.68 | 0.67 | 0.67
clinical 18 | 0.76 | 0.67 | 0.65 | 0.69 | 0.67 | 0.66 | clinical 18 | 0.73 | 0.66 | 0.65 | 0.67 | 0.66 | 0.66
pure noise | 0.65 | 0.62 | 0.51 | 0.72 | 0.61 | 0.59 | pure noise | 0.65 | 0.64 | 0.54 | 0.73 | 0.64 | 0.62
| Fusion: Dynamic [14] |  | Fusion: Graph [49]
clinical 1 | 0.82 | 0.76 | 0.58 | 0.91 | 0.75 | 0.71 | clinical 1 | 0.73 | 0.72 | 0.67 | 0.77 | 0.72 | 0.71
clinical 4 | 0.83 | 0.70 | 0.85 | 0.58 | 0.72 | 0.74 | clinical 4 | 0.69 | 0.68 | 0.62 | 0.74 | 0.68 | 0.67
clinical 7 | 0.85 | 0.76 | 0.77 | 0.74 | 0.76 | 0.76 | clinical 7 | 0.76 | 0.75 | 0.75 | 0.78 | 0.77 | 0.76
clinical 18 | 0.83 | 0.74 | 0.88 | 0.63 | 0.75 | 0.78 | clinical 18 | 0.75 | 0.75 | 0.74 | 0.76 | 0.75 | 0.75
pure noise | 0.75 | 0.66 | 0.66 | 0.67 | 0.67 | 0.66 | pure noise | 0.68 | 0.67 | 0.60 | 0.74 | 0.67 | 0.66
| Fusion: Subspace [50] |  | Fusion: DMIB
clinical 1 | 0.84 | 0.75 | 0.69 | 0.79 | 0.74 | 0.73 | clinical 1 | 0.85 | 0.76 | 0.82 | 0.72 | 0.77 | 0.78
clinical 4 | 0.84 | 0.76 | 0.75 | 0.76 | 0.76 | 0.75 | clinical 4 | 0.85 | 0.78 | 0.78 | 0.77 | 0.78 | 0.78
clinical 7 | 0.84 | 0.78 | 0.77 | 0.78 | 0.78 | 0.77 | clinical 7 | 0.86 | 0.80 | 0.75 | 0.83 | 0.79 | 0.78
clinical 18 | 0.83 | 0.76 | 0.57 | 0.92 | 0.75 | 0.71 | clinical 18 | 0.86 | 0.76 | 0.77 | 0.76 | 0.77 | 0.77
pure noise | 0.71 | 0.63 | 0.55 | 0.69 | 0.62 | 0.61 | pure noise | 0.76 | 0.72 | 0.66 | 0.77 | 0.72 | 0.70

Table 3: Performance of various methods on the iCTCF dataset for morbidity
prediction. Bold denotes the best AUC in each fusion setting.

| Test |  | Test
---|---|---|---
| AUC | Accuracy | Sensitivity | Specificity | $\mbox{JW}_{0.5}$ | $\mbox{JW}_{0.6}$ |  | AUC | Accuracy | Sensitivity | Specificity | $\mbox{JW}_{0.5}$ | $\mbox{JW}_{0.6}$
| Single modality |  | Fusion: Concatenation [24]
clinical 1 | 0.72 | 0.62 | 0.71 | 0.59 | 0.65 | 0.66 | clinical 1 | 0.71 | 0.63 | 0.67 | 0.62 | 0.64 | 0.65
All clinical | 0.74 | 0.69 | 0.67 | 0.70 | 0.68 | 0.68 | All clinical | 0.77 | 0.72 | 0.65 | 0.75 | 0.70 | 0.69
CT only | 0.71 | 0.68 | 0.63 | 0.70 | 0.67 | 0.66 | pure noise | 0.71 | 0.65 | 0.67 | 0.64 | 0.66 | 0.66
| Fusion: Attention [10] |  | Fusion: Transformer [25]
clinical 1 | 0.72 | 0.65 | 0.63 | 0.65 | 0.64 | 0.64 | clinical 1 | 0.59 | 0.74 | 0.06 | 0.99 | 0.53 | 0.43
All clinical | 0.77 | 0.75 | 0.65 | 0.79 | 0.72 | 0.70 | All clinical | 0.67 | 0.67 | 0.59 | 0.70 | 0.65 | 0.63
pure noise | 0.56 | 0.69 | 0.31 | 0.83 | 0.57 | 0.52 | pure noise | 0.65 | 0.38 | 0.90 | 0.18 | 0.54 | 0.61
| Fusion: Dynamic [14] |  | Fusion: Graph [49]
clinical 1 | 0.78 | 0.75 | 0.16 | 0.96 | 0.56 | 0.48 | clinical 1 | 0.71 | 0.70 | 0.67 | 0.72 | 0.70 | 0.69
All clinical | 0.78 | 0.50 | 0.90 | 0.35 | 0.62 | 0.68 | All clinical | 0.74 | 0.72 | 0.67 | 0.77 | 0.72 | 0.71
pure noise | 0.67 | 0.73 | 0.00 | 1.00 | 0.50 | 0.40 | pure noise | 0.62 | 0.64 | 0.69 | 0.60 | 0.65 | 0.65
| Fusion: Subspace [50] |  | Fusion: DMIB
clinical 1 | 0.78 | 0.63 | 0.88 | 0.54 | 0.71 | 0.75 | clinical 1 | 0.79 | 0.70 | 0.76 | 0.68 | 0.72 | 0.73
All clinical | 0.80 | 0.68 | 0.76 | 0.64 | 0.70 | 0.72 | All clinical | 0.82 | 0.73 | 0.71 | 0.74 | 0.72 | 0.72
pure noise | 0.71 | 0.58 | 0.75 | 0.52 | 0.63 | 0.66 | pure noise | 0.71 | 0.63 | 0.69 | 0.62 | 0.65 | 0.66

Table 4: Performance of various methods on the iCTCF dataset for COVID19
diagnosis. Bold denotes the best AUC in each fusion setting.

| Test |  | Test
---|---|---|---
| AUC | Accuracy | Sensitivity | Specificity | $\mbox{JW}_{0.5}$ | $\mbox{JW}_{0.6}$ |  | AUC | Accuracy | Sensitivity | Specificity | $\mbox{JW}_{0.5}$ | $\mbox{JW}_{0.6}$
| Single modality |  | Fusion: Concatenation [24]
clinical 1 | 0.51 | 0.51 | 0.55 | 0.46 | 0.51 | 0.52 | clinical 1 | 0.81 | 0.74 | 0.72 | 0.76 | 0.74 | 0.73
All clinical | 0.80 | 0.74 | 0.77 | 0.70 | 0.73 | 0.74 | All clinical | 0.85 | 0.78 | 0.85 | 0.68 | 0.76 | 0.78
CT only | 0.80 | 0.72 | 0.85 | 0.55 | 0.70 | 0.73 | pure noise | 0.81 | 0.73 | 0.81 | 0.61 | 0.71 | 0.73
| Fusion: Attention [10] |  | Fusion: Transformer [25]
clinical 1 | 0.70 | 0.67 | 0.74 | 0.58 | 0.66 | 0.68 | clinical 1 | 0.62 | 0.63 | 0.86 | 0.29 | 0.58 | 0.63
All clinical | 0.80 | 0.75 | 0.80 | 0.69 | 0.74 | 0.76 | All clinical | 0.66 | 0.64 | 0.68 | 0.59 | 0.63 | 0.64
pure noise | 0.50 | 0.49 | 0.61 | 0.33 | 0.47 | 0.50 | pure noise | 0.64 | 0.59 | 0.60 | 0.59 | 0.59 | 0.59
| Fusion: Dynamic [14] |  | Fusion: Graph [49]
clinical 1 | 0.80 | 0.74 | 0.85 | 0.59 | 0.72 | 0.74 | clinical 1 | 0.74 | 0.73 | 0.74 | 0.73 | 0.74 | 0.74
All clinical | 0.86 | 0.76 | 0.86 | 0.62 | 0.74 | 0.76 | All clinical | 0.83 | 0.83 | 0.84 | 0.83 | 0.84 | 0.84
pure noise | 0.80 | 0.74 | 0.82 | 0.62 | 0.72 | 0.74 | pure noise | 0.73 | 0.73 | 0.72 | 0.74 | 0.73 | 0.73
| Fusion: Subspace [50] |  | Fusion: DMIB
clinical 1 | 0.79 | 0.70 | 0.80 | 0.56 | 0.68 | 0.71 | clinical 1 | 0.80 | 0.73 | 0.86 | 0.53 | 0.70 | 0.73
All clinical | 0.86 | 0.77 | 0.79 | 0.74 | 0.77 | 0.77 | All clinical | 0.89 | 0.82 | 0.78 | 0.87 | 0.83 | 0.82
pure noise | 0.80 | 0.72 | 0.95 | 0.40 | 0.67 | 0.73 | pure noise | 0.80 | 0.73 | 0.74 | 0.71 | 0.73 | 0.73

###  4.2 Implementation details

ITAC and iCTCF. For data preprocessing, we crop the lung regions from the
complete 3D scan and resize each slice to the dimensions of 350 $\times$ 350
pixels, preserving its original depth. Subsequently, we generate 2D montages
for each patient from their 3D HRCT scans. Each montage is composed of 4
randomly chosen axial slices, with each slice originating from one of the 4
equally divided regions of the scan, placed on a 2x2 grid. The utilization of
2D montages enables us to generate diverse montages for each scan without
duplication. This approach can effectively mitigate the challenges of data
scarcity and data imbalance commonly encountered in medical image datasets. It
offers an advantage over using the entire scan as input, as well as compared
to single-slice input, by preserving an adequate amount of predictive
information in the input. The number of generated montages for each class is
summarized in Table 1.

For training and testing the proposed model, we conduct patient-level data
splitting to prevent information leakage. We reserve 20% of patients from each
class for testing and using the remaining patients for model training with
five-fold cross-validation. Patients are divided into five folds with no
overlaps using stratified sampling, with each having the same patient
distribution. Each of this fold serves as a validation set, and we train five
models from scratch on the remaining four folds. From the five models, the
model attaining the top AUC on its validation set is chosen as the final
testing model. For testing, we generate 10 montages for each patient and take
the median prediction over the 10 montages as the final result.

We employ DensetNet-121 [18] as the backbone for the CT montage modality to
obtain an image feature $f_{1}\in\mathbb{R}^{1024}$. For the clinical data, we
perform mean imputation for missing records followed by data normalization. We
employ four linear layers to obtain a clinical feature
$f_{2}\in\mathbb{R}^{1024}$. The dimension of $z$ in the IB module is set to
1024 and loss function weights are set to $\alpha=1,\beta=10$. We use the
cross-entropy loss for
$\mathcal{L}_{f},\mathcal{L}_{f^{*}},\mathcal{L}_{\text{modality}}$. All
training are done with the Adam optimizer (initial learning rate of 1e-6 and a
linear decay rate of 1e-2), a batch size of 8, and trained for 70 epochs on a
single RTX3090.

ROSMAP and BRCA. For fair comparison, we adopt similar experimental settings
as [14], and we reenacted their experiments using their open-sourced codes. We
set the dimension of $z$ to 1024 for the bottleneck.

###  4.3 Evaluation setting

ITAC. To evaluate the robustness of different fusion strategies in handling
noises and redundant information, we consider multiple experimental settings,
starting with the most informative and complete clinical variables, and
gradually expanding to those with larger degrees of redundancy and noise.
Specifically, we fix five settings: i) 1 clinical variable (age) which is the
most informative feature. ii) 4 clinical variables (i) + oxygen saturation,
platelets, measured saturation oxygen, which are also deemed as relevant by
domain experts. iii) 7 clinical variables (ii) + respiratory rate, pO2, and
D-Dimer, which are informative but have a considerable 30% of the data are
missing. iv) (iii) + reported symptoms and health records, which are more
prone to missing data and subjective biases in the symptoms description, and
deemed to be of secondary importance. v) 1 random integer between 0 and 100
that serves as a noise input replacing age. In the Appendix, we further
include the details of the clinical data for our ITAC dataset.

We benchmark DMIB against single modality models (CT backbone and clinical
backbone in our method), as well as various multimodal fusion schemes
including direct concatenation (Concatenation [24]), fusion via channelwise
attention (Attention [10]), fusion via transformer-based cross-attention
(Transformer [25]), fusion via dynamic weighing of each modality channel
(Dynamic [14]), fusion via projection to a common subspace (Fusion: Subspace
[50]) and graph-based fusion (Graph [49]). We adopt the Area Under Receiver
Operating Characteristic Curve (AUC) as the primary evaluation metric, with
accuracy, sensitivity, specificity, and the weighted Youden indices $JW_{0.5}$
and $JW_{0.6}$ as auxiliary metrics. Results are reported in Table 2.

iCTCF. To eliminate the manual selection of optimal clinical data combinations
for improved fusion performance, we extend our evaluation on this dataset to
assess the robustness of the proposed model for both diagnostic and prognostic
tasks. We integrate the CT scans with all 81 available clinical variables, to
showcase the superiority of DMIB in fusing potentially redundant and noisy
data without requiring manual selection. Furthermore, we perform fusion with
single variables, ‘Age’ and ‘pure noise’ (consisting of random age and
temperature), as reference points for assessing fusion performance with all
clinical information.

BRCA & ROSMAP. To further evaluate the generalization of DMIB to other
modalities, we also performed experiments on the BRCA and ROSMAP dataset
consisting of multimodal genomic data. We benchmark against Fusion: Dynamic
[14], the state-of-the-art method which employs fusion strategy consisting of
model-specific supervision, attention, sparsity constraints and dynamic
assignment of confidence to each modality. Following [14], we report AUC,
WeightedF1 and MAcroF1 and F1 in Table 5.

Table 5: Performance of multimodal methods on BRCA and ROSMAP. † denotes the
result showing significant difference to that of DMIB with $p<1e-4$ by paired
T test.

| BRCA | ROSMAP
---|---|---
Method | ACC | WeightedF1 | MacroF1 | ACC | F1 | AUC†
Fusion: Dynamic | 87.1+0.5† | 87.4+0.6† | 83.5+0.9† | 81.7+1.5† | 82.3+1.5† | 90.0+1.2†
Fusion: DMIB | 86.0+0.7 | 86.0+0.8 | 81.6+0.9 | 84.9+1.8 | 85.3+1.7 | 91.6+0.7

Table 6: Ablation studies on ITAC and BRCA datasets

| Ablation Setting | ITAC | BRCA
---|---|---|---
No. | $\mathcal{L}_{f}$ | IB | $\mathcal{L}_{f^{*}}$ | $\mathcal{L}_{\mbox{sufficiency}}$ | $\mathcal{L}_{\mbox{modality}}$ | AUC | Accuracy | Sensitivity | Specificity | ACC | WeightedF1 | MacroF1
1. | ✓ | - | - | - | - | 0.83 | 0.78 | 0.65 | 0.90 | 81.4+0.6† | 81.1+0.7† | 76.2+1.0†
2. | - | ✓ | ✓ | - | ✓ | 0.83 | 0.77 | 0.74 | 0.79 | 81.0+1.0† | 80.2+1.2† | 75.3+1.2†
3. | ✓ | ✓ | ✓ | - | ✓ | 0.83 | 0.75 | 0.69 | 0.79 | 81.1+0.8† | 80.4+0.8† | 75.4+1.0†
4. | ✓ | ✓ | ✓ | ✓ | - | 0.85 | 0.77 | 0.75 | 0.78 | 83.9+1.5† | 83.8+1.7† | 79.7+1.8†
5. | ✓ | ✓ | - | ✓ | ✓ | 0.84 | 0.78 | 0.65 | 0.88 | 86.1+0.5† | 86.2+0.6† | 81.8+0.7†
6. | ✓ | ✓ | ✓ | ✓ | ✓ | 0.86 | 0.76 | 0.77 | 0.76 | 86.0+0.7† | 86.0+0.8† | 81.6+0.9†

Table 7: Experimenting with different image backbones and unchanged clinical
backbone on ITAC (with all clinical variables). Bond fonts denote the best
result for each backbone.

Image Backbone | Experiment | AUC | ACC | Sens | Spec | JW5 | JW6
---|---|---|---|---|---|---|---
| CT Only | 0.77 | 0.71 | 0.68 | 0.74 | 0.71 | 0.7
ResNet18 [16] | Concat | 0.77 | 0.72 | 0.7 | 0.75 | 0.73 | 0.72
| Subspace | 0.79 | 0.73 | 0.73 | 0.73 | 0.73 | 0.73
| Proposed | 0.83 | 0.77 | 0.77 | 0.77 | 0.77 | 0.77
| CT Only | 0.71 | 0.69 | 0.75 | 0.63 | 0.69 | 0.7
ResNet50 [16] | Concat | 0.75 | 0.67 | 0.74 | 0.62 | 0.68 | 0.69
| Subspace | 0.77 | 0.72 | 0.75 | 0.69 | 0.72 | 0.73
| Proposed | 0.81 | 0.72 | 0.74 | 0.71 | 0.72 | 0.73
| CT Only | 0.71 | 0.62 | 0.58 | 0.65 | 0.62 | 0.61
EfficientNet_b0 [35] | Concat | 0.76 | 0.66 | 0.72 | 0.62 | 0.67 | 0.68
| Subspace | 0.74 | 0.65 | 0.71 | 0.60 | 0.66 | 0.67
| Proposed | 0.82 | 0.73 | 0.74 | 0.72 | 0.73 | 0.73
| CT Only | 0.69 | 0.62 | 0.62 | 0.63 | 0.62 | 0.62
PoolFormer_v2_tiny [47] | Concat | 0.73 | 0.67 | 0.66 | 0.68 | 0.67 | 0.67
| Subspace | 0.77 | 0.71 | 0.71 | 0.72 | 0.71 | 0.71
| Proposed | 0.79 | 0.73 | 0.74 | 0.72 | 0.73 | 0.73

###  4.4 Results

ITAC. As reported in Table 2, our DMIB outperforms all competing methods
across all settings for our ITAC dataset. As expected, we observe that
inclusion of more clinical variables often fails to improve prognostic
performance in many existing methods. In fact, the inclusion of more
modalities in attention-based, transformer-based and graph-based fusion might
even lead to weaker performance than single modalities. Such fluctuations
across different experimental settings reflect a lack of robustness in the
models.

By inspecting gradients for each variable, we observe that age is predominant,
followed by GOT, O2 saturation, PCR, Glucose, Platelets of secondary
importance, in agreement with expert knowledge. This is reflected in our
method, where our model attains peak performance when fusing the image
modality with 7 clinical variables. Furthermore, our DMIB maintains peak
performance upon adding more noisy and redundant clinical features, unlike
most existing methods which show declining trend. Another noteworthy point is
when fusing the CT modality with a random noise input, our method retains its
performance, whereas all existing fusion methods except concatenation method
experience considerable performance drops. Again, this demonstrates the
robustness of our approach and its ability to filter out noises. Overall, our
method is more feasible and reliable for real-world clinical applications,
when noise and redundant information are often present, and there is no prior
guidance for which features are informative.

We discuss some insights for the various fusion schemes. Concatenation [24]
fails to surpass the clinical modality for 1 and 4 clinical variables. This is
probably due to the image feature dimensions being much larger than the
clinical feature dimensions, resulting in the dominant influence of one
modality. Channel-wise attention fusion [10] only boosts performance when the
modality data is complete and informative. It is particularly sensitive to
noise, and drops significantly upon inclusion of noisy and redundant data.
Transformer-based fusion also delivers very poor performance, never surpassing
single-modality results. This is consistent with observations that attention-
based mechanisms and transformers typically require a larger corpus of
training data for effective training [43]. Dynamic fusion [14], subspace-based
fusion [50] and graph-based fusion [25] demonstrated better consistency and
solid fusion performance. However, they are prone to be affected by noisy
modalities. For subspace projection-based fusion, replacing the clinical
variable with noise leads to considerable performance dips. Intuitively,
aligning normal inputs to random noise could remove predictive information in
the normal channels. For dynamic fusion, learning to weigh the reliability of
features from a modality does not generalize well to test samples at an
instance level, leading to a drop when including unreliable clinical inputs.

iCTCF. Furthermore, we demonstrate the exceptional fusion performance of DMIB
when combined with all clinical data in both prognosis and diagnosis tasks,
along with its resilience to noise input, as evidenced in Table 3 and Table 4.
Notably, when compared to using CT only, adding the singular feature ‘Age’,
has a significant impact on predicting COVID-19 patient outcomes (Table 3).
However, it shows only a marginal improvement in the COVID-19 diagnosis task
(Table 4). As such, for COVID19 diagnosis, age can be deemed as a redundant
feature and indeed. We observe similar performance in iCTCF when combining the
CT modality with the noise feature. In both tables, our method and the
concatenation method demonstrate the highest level of robustness, with our
method achieving the best fusion performance.

BRCA & ROSMAP. As reported in Table 5, DMIB is slightly inferior for breast
cancer subtype classification but significantly superior for Alzheimer’s
diagnosis than [14], which proves its adaptability across different
modalities.

###  4.5 Ablation studies

We performed ablation studies on the ITAC and BRCA datasets to study the
effectiveness of various key components, with results reported in Table 6. It
is observed that preserving all information (No. 1) is worse than
incorporating a bottleneck with sufficiency loss (No. 4, 5, 6). Furthermore,
employing a bottleneck module without the sufficiency loss also fails to be
useful, which is consistent with our intuitions that unconstrained discarding
of information could remove predictive information (comparing No. 2, 3 to No.
6). Moreover, including modal-specific supervision
$\mathcal{L}_{\mbox{\small{modality}}}$ leads to improvement, suggesting that
boosting the extraction of modality-level task-relevant information
facilitates learning of fused feature (No. 4 and No. 6). This provides strong
evidence for the effectiveness of the sufficiency loss in preserving
predictive information.

We further investigate whether DMIB remains effective under different network
architectures by switching the image backbones for the prognosis experiment on
our ITAC dataset. As reported in Table 7, we experimented with ResNet18,
ResNet50 [16], EfficientNet [35] and PoolFormer [47]. Regardless of the
backbone, DMIB performs significantly better than the baselines of CT only and
fusion methods such as concatenation (which retains all information) and
subspace-based fusion (which extracts common information). These results
strongly affirm the efficacy of our approach and its viability as a plug-and-
play component for multimodal classification tasks.

##  5 Conclusion

Utilising insights from mutual information and information bottleneck theory,
we have introduced a general multimodal classification approach which has
achieved a state-of-the-art performance in various clinical tasks. Notably,
our method holds great significance and applicability in the field of clinical
practice, as it consistently delivers high performance, even when faced with
limited training data and noisy input modalities. In the context of future
research, our efforts will be directed towards expanding the application of
information bottleneck theory to facilitate feature importance analysis and
enhance the interpretability of multimodal learning.

## Acknowledgment

This study was supported in part by the ERC IMI (101005122), the H2020
(952172), the MRC (MC/PC/21013), the Royal Society (IEC\NSFC\211235), the
NVIDIA Academic Hardware Grant Program, the SABER project supported by
Boehringer Ingelheim Ltd, Wellcome Leap Dynamic Resilience, and the UKRI
Future Leaders Fellowship (MR/V023799/1).

##  Appendix A Preliminary Definitions

Given continuous random variables $X,Y,Z$, supported on
$\mathcal{X},\mathcal{Y},\mathcal{Z}$ with probability distributions
$p_{X},p_{Y},p_{Z}$:

$\left(i\right)$ The definition of mutual information of $X$ and $Y$ and its
relation to information entropy:

$\displaystyle I(X;Y)$
$\displaystyle\equiv\mathbb{E}\left[\log\frac{p_{X,Y}(X,Y)}{p_{X}(X)p_{Y}(Y)}\right]$
(9)
$\displaystyle=\int_{\mathcal{X},\mathcal{Y}}p_{X,Y}(x,y)\log\frac{p_{X,Y}(x,y)}{p_{X}(x)p_{Y}(y)}dxdy$
$\displaystyle=\mathbb{E}[\log
p_{X,Y}(X,Y)]-\mathbb{E}[p_{X}(X)]-\mathbb{E}[p_{Y}(Y)]$
$\displaystyle=-H(X,Y)+H(X)+H(Y)$ $\displaystyle=H(Y)-H(Y|X)$
$\displaystyle=H(X)-H(X|Y)$

where

$\displaystyle H(X)$ $\displaystyle\equiv\mathbb{E}[-\log
p_{X}(X)]=-\int_{\mathcal{X}}p_{X}(x)\log p_{X}(x)dx$ $\displaystyle H(X,Y)$
$\displaystyle\equiv\mathbb{E}[-\log p_{X,Y}(X,Y)]$
$\displaystyle=-\int_{\mathcal{X},\mathcal{Y}}p_{X,Y}(x,y)\log
p_{X,Y}(x,y)dxdy$ $\displaystyle H(Y|X)$ $\displaystyle\equiv\mathbb{E}[-\log
p_{Y|X}(Y|X)]$ $\displaystyle=-\int_{\mathcal{X},\mathcal{Y}}p_{X,Y}(x,y)\log
p_{Y|X}(y|x)dxdy$

(ii) The conditional mutual information of $X$ and $Y$ given $Z$ is defined
as:

$\displaystyle I(X;Y|Z)$
$\displaystyle\equiv\mathbb{E}\left[\log\frac{p_{X,Y|Z}(x,y|z)}{p_{X|Z}(x|z)p_{Y|Z}(y|z)}\right]$
(10)
$\displaystyle=\int_{\mathcal{X},\mathcal{Y},\mathcal{Z}}p_{X,Y|Z}(x,y|z)p_{Z}(z)$
$\displaystyle\quad\log\frac{p_{X,Y|Z}(x,y|z)}{p_{X|Z}(x|z)p_{Y|Z}(y|z)}dxdydz$

##  Appendix B Proof of $I(f;f^{*})=I(f;f^{*}|y)+I(y;f^{*})$

###### Proof.

We have $I(f^{*};y)=H(f^{*})-H(f^{*}|y)$ by Eq.(9). Furthermore, since $f^{*}$
is obtained (deterministically) from $f$, we have
$p_{f,f^{*}}(f,f^{*})=p_{f}(f)$. Therefore, $I(f;f^{*})=\mathbb{E}\left[-\log
p_{f^{*}}(f^{*})\right]=\mathbb{E}\left[\log\frac{p_{f,f^{*}}(f,f^{*})}{p_{f^{*}}(f^{*})p_{f}(f)}\right]=H(f^{*})$
and similarly, $I(f;f^{*}|y)=H(f^{*}|y)$. Combining these, we have the desired
result. ∎

Table 8: Clinical variables in ITAC and percentage of missing data

$\\#$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
Variable | Age | Oxygen saturation | Platelets | Measured saturation oxygen | Respiratory rate | PO2 | D-Dimer | Cough | Dyspnea
Missing (%) | 0 | 7.60 | 4.42 | 35.69 | 42.76 | 31.45 | 44.52 | N/A | N/A
$\\#$ | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
Variable | Diabetes | Neurological disease | Other CV disease | Admitted to ICU | Glucose | Urea | eGFR | GOT | PCR
Missing (%) | N/A | N/A | N/A | N/A | 15.72 | 7.24 | 7.77 | 24.56 | 16.43

##  Appendix C Proof of Proposition

$KL\left[p(y|f)\|p(y|f^{*})\right]=0\implies I(y;f)-I\left(y;f^{*}\right)=0$

###### Proof.

$\displaystyle I(y;f)-I(y;f^{*})=$ $\displaystyle-\int
p\left(f^{*}\right)p\left(y|f^{*}\right)\log p(y|f^{*})df^{*}dy$
$\displaystyle\;\;\;\;+\int p(f)p(y|f)\log p(y|f)dfdy$ $\displaystyle=-\int
p\left(f^{*}\right)p\left(y|f^{*}\right)\log\left[\frac{p\left(y|f^{*}\right)}{p(y|f)}p(y|f)\right]df^{*}dy$
$\displaystyle\;\;\;\;+\int
p(f)p(y|f)\log\left[\frac{p(y|f)}{p\left(y|f^{*}\right)}p\left(y|f^{*}\right)\right]dfdy$
$\displaystyle=-\int
p\left(f^{*}\right)KL\left[p(y|f^{*})\|p\left(y|f\right)\right]df^{*}$
$\displaystyle\;\;\;\;-\int p\left(f^{*}\right)p\left(y|f^{*}\right)\log
p(y|f)df^{*}dy$ $\displaystyle\;\;\;\;+\int p(f)KL[p(y|f)\|p(y|f^{*})]df$
$\displaystyle\;\;\;\;+\int p\left(f\right)p\left(y|f\right)\log
p\left(y|f^{*}\right)dfdy$
$\displaystyle=\mathbb{E}_{f}\left[KL[p(y|f)\|p(y|f^{*})]\right]-\mathbb{E}_{f^{*}}\left[KL[p(y|f^{*})\|p(y|f)]\right]$
$\displaystyle\;\;\;\;+\int p(y)\log\frac{p(y|f^{*})}{p\left(y|f\right)}dy$
$\displaystyle\leq\mathbb{E}_{f}\left[KL[p(y|f)\|p(y|f^{*})]\right]+\int
p(y)\log\frac{p(y|f^{*})}{p\left(y|f\right)}dy.$

Using Jensen’s inequality and the fact that $-\log$ is strictly convex, we can
show that the KL-divergence is always non-negative and the equality only holds
when the distributions are equal almost-everywhere, which is proven as below:

$\displaystyle KL[P\|Q]$
$\displaystyle=\mathbb{E}\left[-\log\frac{Q}{P}\right]$ (11)
$\displaystyle\geq-\log\mathbb{E}\left[\frac{Q}{P}\right]\;(\text{by Jensen's
inequality})$ $\displaystyle=-\log\int_{\mathcal{X}}\frac{Q(x)}{P(x)}P(x)dx=0$

where $P$ and $Q$ are two arbitrary distributions supported on $\mathcal{X}$.
We have $KL[P\|Q]\geq 0$.

Hence, when $KL\left[p(y|f)\|p(y|f^{*})\right]=0$, we have
$p\left(y|f^{*}\right)=p\left(y|f\right)$ almost everywhere (follows from Eq.
(11)), which implies $\int p(y)\log\frac{p(y|f^{*})}{p\left(y|f\right)}dy=0$
and hence $I(y;f)-I(y;f^{*})\leq 0$. We also have $I(y;f)-I(y;f^{*})\leq 0$,
therefore $KL\left[p(y|f)\|p(y|f^{*})\right]=0\implies
I(y;f)-I\left(y;f^{*}\right)=0$. ∎

##  Appendix D Summary of clinical variables in ITAC

The overview of the missing data in the clinical variables in ITAC is given in
Table 8. We simply fill the missing value by the mean value calculated from
the overall datasets.

## References

  * [1] Julián N Acosta, Guido J Falcone, Pranav Rajpurkar, and Eric J Topol.  Multimodal biomedical ai.  Nature Medicine, 28(9):1773–1784, 2022.
  * [2] Francis Bach.  Breaking the curse of dimensionality with convex neural networks.  The Journal of Machine Learning Research, 18(1):629–681, 2017.
  * [3] Fatemeh Behrad and Mohammad Saniee Abadeh.  An overview of deep learning methods for multimodal medical data mining.  Expert Systems with Applications, page 117006, 2022.
  * [4] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm.  Mine: mutual information neural estimation.  arXiv preprint arXiv:1801.04062, 2018.
  * [5] Yonatan Belinkov, James Henderson, et al.  Variational information bottleneck for effective low-resource fine-tuning.  In International Conference on Learning Representations, 2020.
  * [6] Gan Cai, Yu Zhu, Yue Wu, Xiaoben Jiang, Jiongyao Ye, and Dawei Yang.  A multimodal transformer to fuse images and metadata for skin disease classification.  The Visual Computer, pages 1–13, 2022.
  * [7] Qiong Cai, Hao Wang, Zhenmin Li, and Xiao Liu.  A survey on multimodal data-driven smart healthcare systems: approaches and applications.  IEEE Access, 7:133583–133599, 2019.
  * [8] Menglin Cao, Ming Yang, Chi Qin, Xiaofei Zhu, Yanni Chen, Jue Wang, and Tian Liu.  Using deepgcn to identify the autism spectrum disorder from multi-site resting-state data.  Biomedical Signal Processing and Control, 70:103015, 2021.
  * [9] Can Cui, Haichun Yang, Yaohong Wang, Shilin Zhao, Zuhayr Asad, Lori A Coburn, Keith T Wilson, Bennett A Landman, and Yuankai Huo.  Deep multi-modal fusion of image and non-image data in disease diagnosis and prognosis: A review.  arXiv preprint arXiv:2203.15588, 2022.
  * [10] Hongyi Duanmu, Pauline Boning Huang, Srinidhi Brahmavar, Stephanie Lin, Thomas Ren, Jun Kong, Fusheng Wang, and Tim Q Duong.  Prediction of pathological complete response to neoadjuvant chemotherapy in breast cancer using deep learning with integrative imaging, molecular and demographic data.  In International conference on medical image computing and computer-assisted intervention, pages 242–252. Springer, 2020.
  * [11] Tyrone E Duncan.  On the calculation of mutual information.  SIAM Journal on Applied Mathematics, 19(1):215–220, 1970.
  * [12] Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata.  Learning robust representations via multi-view information bottleneck.  In 8th International Conference on Learning Representations. OpenReview. net, 2020.
  * [13] Fengjiao Gong, Yuzhou Nie, and Hongteng Xu.  Gromov-wasserstein multi-modal alignment and clustering.  In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 603–613, 2022.
  * [14] Zongbo Han, Fan Yang, Junzhou Huang, Changqing Zhang, and Jianhua Yao.  Multimodal dynamics: Dynamical fusion for trustworthy multimodal classification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 20707–20717, 2022.
  * [15] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16000–16009, 2022.
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [17] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  In International Conference on Learning Representations, 2018.
  * [18] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017.
  * [19] Grzegorz Jacenków, Alison Q O’Neil, and Sotirios A Tsaftaris.  Indication as prior knowledge for multimodal disease classification in chest radiographs with transformers.  In 2022 IEEE 19th International Symposium on Biomedical Imaging (ISBI), pages 1–5. IEEE, 2022.
  * [20] Matthias Keicher, Hendrik Burwinkel, David Bani-Harouni, Magdalini Paschali, Tobias Czempiel, Egon Burian, Marcus R Makowski, Rickmer Braren, Nassir Navab, and Thomas Wendler.  U-gat: Multimodal graph attention network for covid-19 outcome prediction.  arXiv preprint arXiv:2108.00860, 2021.
  * [21] Paul Pu Liang, Amir Zadeh, and Louis-Philippe Morency.  Foundations and recent trends in multimodal machine learning: Principles, challenges, and open questions.  arXiv preprint arXiv:2209.03430, 2022.
  * [22] Ralph Linsker.  Self-organization in a perceptual network.  Computer, 21(3):105–117, 1988.
  * [23] Zhenguang Liu, Runyang Feng, Haoming Chen, Shuang Wu, Yixing Gao, Yunjun Gao, and Xiang Wang.  Temporal feature alignment and mutual information maximization for video-based human pose estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11006–11016, 2022.
  * [24] Lingwei Meng, Di Dong, Liang Li, Meng Niu, Yan Bai, Meiyun Wang, Xiaoming Qiu, Yunfei Zha, and Jie Tian.  A deep learning prognosis model help alert for covid-19 patients at high-risk of death: a multi-center study.  IEEE journal of biomedical and health informatics, 24(12):3576–3584, 2020.
  * [25] Satyam Mohla, Shivam Pande, Biplab Banerjee, and Subhasis Chaudhuri.  Fusatnet: Dual attention based spectrospatial multimodal fusion network for hyperspectral and lidar classification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 92–93, 2020.
  * [26] Ghulam Muhammad, Fatima Alshehri, Fakhri Karray, Abdulmotaleb El Saddik, Mansour Alsulaiman, and Tiago H Falk.  A comprehensive survey on multimodal medical signals fusion for smart healthcare systems.  Information Fusion, 76:355–375, 2021.
  * [27] XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan.  Estimating divergence functionals and the likelihood ratio by convex risk minimization.  IEEE Transactions on Information Theory, 56(11):5847–5861, 2010\.
  * [28] Wanshan Ning, Shijun Lei, Jingjing Yang, Yukun Cao, Peiran Jiang, Qianqian Yang, Jiao Zhang, Xiaobei Wang, Fenghua Chen, Zhi Geng, et al.  Open resource of clinical data from patients with pneumonia for the prediction of covid-19 outcomes via deep learning.  Nature biomedical engineering, 4(12):1197–1207, 2020.
  * [29] Sherjil Ozair, Corey Lynch, Yoshua Bengio, Aaron Van den Oord, Sergey Levine, and Pierre Sermanet.  Wasserstein dependency measure for representation learning.  Advances in Neural Information Processing Systems, 32, 2019.
  * [30] Sebastian Pölsterl, Tom Nuno Wolf, and Christian Wachinger.  Combining 3d image and tabular data via the dynamic affine feature map transform.  In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 688–698. Springer, 2021.
  * [31] Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker.  On variational bounds of mutual information.  In International Conference on Machine Learning, pages 5171–5180. PMLR, 2019.
  * [32] Alvin Rajkomar, Eyal Oren, Kai Chen, Andrew M Dai, Nissan Hajaj, Michaela Hardt, Peter J Liu, Xiaobing Liu, Jake Marcus, Mimi Sun, et al.  Scalable and accurate deep learning with electronic health records.  NPJ digital medicine, 1(1):1–10, 2018.
  * [33] Farah E Shamout, Yiqiu Shen, Nan Wu, Aakash Kaku, Jungkyu Park, Taro Makino, Stanislaw Jastrzebski, Jan Witowski, Duo Wang, Ben Zhang, et al.  An artificial intelligence system for predicting the deterioration of covid-19 patients in the emergency department.  NPJ digital medicine, 4(1):1–11, 2021.
  * [34] Dinggang Shen, Guorong Wu, and Heung-Il Suk.  Deep learning in medical image analysis.  Annual review of biomedical engineering, 19:221, 2017.
  * [35] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In International conference on machine learning, pages 6105–6114. PMLR, 2019.
  * [36] Xudong Tian, Zhizhong Zhang, Shaohui Lin, Yanyun Qu, Yuan Xie, and Lizhuang Ma.  Farewell to mutual information: Variational distillation for cross-modal person re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1522–1531, 2021.
  * [37] Naftali Tishby, Fernando C Pereira, and William Bialek.  The information bottleneck method.  arXiv preprint physics/0004057, 2000.
  * [38] Naftali Tishby and Noga Zaslavsky.  Deep learning and the information bottleneck principle.  In 2015 ieee information theory workshop (itw), pages 1–5. IEEE, 2015.
  * [39] Tom van Sonsbeek, Xiantong Zhen, Marcel Worring, and Ling Shao.  Variational knowledge distillation for disease classification in chest x-rays.  In Information Processing in Medical Imaging: 27th International Conference, IPMI 2021, Virtual Event, June 28–June 30, 2021, Proceedings 27, pages 334–345. Springer, 2021.
  * [40] Matias Vera, Pablo Piantanida, and Leonardo Rey Vega.  The role of the information bottleneck in representation learning.  In 2018 IEEE International Symposium on Information Theory (ISIT), pages 1580–1584. IEEE, 2018.
  * [41] Zhibin Wan, Changqing Zhang, Pengfei Zhu, and Qinghua Hu.  Multi-view information-bottleneck representation learning.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10085–10092, 2021.
  * [42] Tongxin Wang, Wei Shao, Zhi Huang, Haixu Tang, Jie Zhang, Zhengming Ding, and Kun Huang.  Moronet: multi-omics integration via graph convolutional networks for biomedical data classification.  bioRxiv, pages 2020–07, 2020.
  * [43] Peng Xu, Xiatian Zhu, and David A Clifton.  Multimodal learning with transformers: A survey.  arXiv preprint arXiv:2206.06488, 2022.
  * [44] Jiawen Yao, Xinliang Zhu, Feiyun Zhu, and Junzhou Huang.  Deep correlational learning for survival prediction from multi-modality data.  In Medical Image Computing and Computer-Assisted Intervention- MICCAI 2017: 20th International Conference, Quebec City, QC, Canada, September 11-13, 2017, Proceedings, Part II, pages 406–414. Springer, 2017.
  * [45] Jordan Yap, William Yolland, and Philipp Tschandl.  Multimodal skin lesion classification using deep learning.  Experimental dermatology, 27(11):1261–1267, 2018.
  * [46] Kun-Hsing Yu, Andrew L Beam, and Isaac S Kohane.  Artificial intelligence in healthcare.  Nature biomedical engineering, 2(10):719–731, 2018.
  * [47] Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng, and Shuicheng Yan.  Metaformer is actually what you need for vision.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10819–10829, 2022.
  * [48] Zexian Zeng, Chengsheng Mao, Andy Vo, Xiaoyu Li, Janna Ore Nugent, Seema A Khan, Susan E Clare, and Yuan Luo.  Deep learning for cancer type classification and driver gene identification.  BMC bioinformatics, 22(4):1–13, 2021.
  * [49] Shuai Zheng, Zhenfeng Zhu, Zhizhe Liu, Zhenyu Guo, Yang Liu, Yuchen Yang, and Yao Zhao.  Multi-modal graph learning for disease prediction.  IEEE Transactions on Medical Imaging, 41(9):2207–2216, 2022.
  * [50] Jinzhao Zhou, Xingming Zhang, Ziwei Zhu, Xiangyuan Lan, Lunkai Fu, Haoxiang Wang, and Hanchun Wen.  Cohesive multi-modality feature learning and fusion for covid-19 patient severity prediction.  IEEE Transactions on Circuits and Systems for Video Technology, 32(5):2535–2549, 2021.


state before $\domi$ has a self-loop (not drawn) and $\get{}$ $S$
means a sequence of forced transitions with the operations
$\get{t}$ for each $t \in S$ (in some order). For
simplicity only the $\ver$ case is shown.

§ ARBITRARILY MANY LOCKS

In this last section we show that the "deadlock avoidance control problem" for  becomes
undecidable if we do not limit the number of locks that each process can use nor
their usage patterns.
We show that the problem is undecidable already with $4$ locks per process.
We do not know if it is decidable with $3$ locks per process.
The undecidability argument quite short if we allow $8$ locks per process.
It takes more effort to get the number of locks down to $4$.

§.§ Initial lock ownership

§.§ Undecidability of deadlock avoidance

In this section we show that the "deadlock avoidance control problem"
for  is
undecidable if every process can use arbitrarily many locks.

The "deadlock avoidance control problem for LSS with initial lock ownership" and at most 7 locks per process is undecidable.

We reduce from the question whether a PCP instance has an infinite
Let $(\alpha_i,\beta_i)_{i=1}^m$ be a PCP instance with
$\alpha_i,\beta_i \in \set{0,1}^*$.
We construct below an  with three processes $P, \bP, C$, using locks from the set

\[\set{c, s_0,s_1,p,\bs_0,\bs_1,\bp}\,.
\]

Process $P$ will use  locks from $\set{c, s_0,s_1,p}$, process $\bP$
from $\set{c, \bs_0,\bs_1,\bp}$, and $C$  all seven locks.

Processes $P,\bP$ are supposed to synchronize
over a PCP solution with the
controller process $C$.
That is, $P$ and $C$ synchronize over a sequence
$\alpha_{i_1}  \alpha_{i_2} \dots$, whereas $\bP$ and $C$
synchronize over a sequence
$\beta_{j_1} \beta_{j_2} \dots$.
The environment tells $C$ at the beginning
whether she should check index equality $i_1 i_2 \dots =j_1 j_2 \dots$ or
word equality $\alpha_{i_1} \alpha_{i_2} \dots =\beta_{j_1} \beta_{j_2} \dots$.

For the initial configuration we assume that $P$ owns $p$, $\bP$ owns
$\bp$ and $C$ owns $c, s_0,s_1,\bs_0,\bs_1$.

We describe now the three processes $P,\bP,C$.
Define first for $b=0,1$:

\begin{eqnarray*}
\r_P(b) &=& \get{s_b} \rel{p}\, \get{c} \; \rel{s_b} \get{p}
\rel{c}\\
\r_{\bP}(b) &=& \get{\bs_b} \rel{\bp}\, \get{c}\; \rel{\bs_b} \get{\bp}
\rel{c}
\end{eqnarray*}

The automaton of $\aut_P$ ($\aut_{\bP}$, resp.) allows all possible action sequences from
$(\r_P(0)+\r_P(1))^\omega$ ($( \r_{\bP}(0)+ \r_{\bP}(1))^\omega$, resp.).
If e.g. process $P$ manages to execute a sequence $\r_P(b_1) \r_P(b_2) \dots$
then this means that $C,P$ synchronize over the sequence

Process $C$'s method for checking word equality consists in
repeating the following procedure: she chooses a bit $b$ through a
"controllable" action, then tries to do $\r_C(P,b)  \r_C(\bP,b)$, with:

\begin{eqnarray*}
\r_C(P,b) &=& \rel{s_b}\, \get{p} \, \rel{c} \; \get{s_b} \rel{p}
\,
\get{c} \\
\r_C(\bP,b) &=& \rel{\bs_b} \get{\bp} \, \rel{c} \; \get{\bs_b}
\rel{\bp}\,
\get{c}
\end{eqnarray*}

For index equality $C$'s method is similar: she chooses an index
$i$ and then tries to do $\r_C(P,b_1) \dots \r_C(P,b_k) \r_C(\bP,b'_1) \dots
\r_C(\bP,b'_\ell)$, where $\alpha_i=b_1 \dots b_k$, $\beta_i=b'_1 \dots b'_\ell$.

The next lemma is the key property showing that the  has a
"winning" "strategy" if and only if the PCP instance has a solution.

Assume that $C$ owns $\{s_0,s_1,c\}$, $P$ owns $\{p\}$, $C$ wants to execute
$C(b)$, and $P$ wants to execute $P(b')$.
Then the system "deadlocks" if and only if $b \not= b'$.
If $b=b'$ then $C$
and $P$ finish executing $\r_C(P,b)$ and $\r_P(b)$,
respectively, and the lock ownership is the same as before the

If, say, $b=0$ and $b'=1$ then $C$ releases $s_0$ but $P$ wants to
acquire $s_1$, so that $P$ is blocked.
Since $C$ wants to acquire $p$ as second step, she is blocked too.
Process $\bP$ will be blocked as well, because he is waiting for either
$\bs_0$ or $\bs_1$. Hence the system "deadlocks".

Suppose now that $b=b'$, say with $b=0$.
Then there is only one possible run alternating between steps of $\r_C(P,0)$
and $\r_P(0)$, until $C$ finally acquires $c$.
Then both $C$ and $P$ have finished the
execution of $\r_C(P,0)$ and $\r_P(0)$, respectively.
Moreover, $C$ re-owns $\{c,s_0, s_1\}$ and $P$ re-owns $\{p\}$.

§ UNDECIDABILITY IN THE GENERAL CASE

We have seen that the control problem is decidable when each process
can use at most 2 locks.
Here we show that it becomes undecidable with $4$ locks per process.
The case of $3$ locks per process remains open.

The general principle of the proof is as follows.
Using 3 locks, it is not hard to show that two processes are able to communicate.
We will use altogether 4 locks in order to implement a reduction from
the infinitary variant of the PCP problem.

We will construct three processes, $C$, $P$ and $\bP$. Processes $P$
and $\bP$ are in charge of producing
each an infinite sequence of bits, by acquiring and releasing their
locks in a specific order.
The third process $C$ (the controller) has to produce two sequences of
bits, one for each of $P$ and $\bP$.
The system will deadlock if the first sequence of $C$ does not match
the one of $P$,  or the second one the one of $\bP$.
At the start the environment makes a choice: $C$ will either have to
produce two identical sequences of bits, or two identical sequences of
indices of pairs of the PCP instance.
As the local strategies for $P$ and $\bP$ are unaware of the
environment's choice, the only way to win is to produce matching
sequences of bits that describe an infinite PCP solution.

One additional difficulty is the initialization: as processes do not
hold any lock at the beginning, the environment could cheat by having
one process run alone a long time before the others start, in order to
prevent the synchronization.
That is why we make processes synchronize over a specific sequence of
bits that does not appear later at the beginning, and add self-loops
so that a process cannot be deadlocked while in that phase. This
forces the environment to make them execute that phase together, after
which they are in a configuration where they all hold locks and cannot
be easily desynchronized.

The "deadlock avoidance control problem" for 	with 3 processes and  $4$ locks is undecidable.

Let $(u_i,v_i)_{i=1}^m$ be the PCP instance with
$u_i,v_i \in \set{0,1}^*$.
An infinite solution is an infinite sequence of indices $i_1i_2,\dots$ such that
W.l.o.g. we assume that there is either a unique solution,
or none.

The  we construct has three processes $P, \bP, C$, using locks from the set

\[\set{s_0,s_1,p,\bp}\,.
\]

Process $P$ uses only locks from $\set{s_0,s_1,p}$, process $\bP$
from $\set{s_0,s_1,\bp}$, and $C$ uses all 4 locks.

Each of the processes $P,\bP$ is supposed to synchronize with process $C$
over an infinite binary sequence representing a PCP solution.
Processes $P$ and $C$ synchronize over a sequence
$u_{i_1}  u_{i_2} \dots$, whereas $\bP$ and $C$
synchronize over a sequence
$v_{j_1} v_{j_2} \dots$.

A local choice of the environment tells $C$ at the beginning
whether she should check index equality $i_1 i_2 \ldots =j_1 j_2 \dots$ or
word equality $u_{i_1} u_{i_2} \ldots =v_{j_1} v_{j_2} \dots$.

We first give a high-level description of how the processes $P,\bP,C$
synchronize over a single bit.
Define  for $b \in\set{0,1}$, sequences of operations for
$P$ and $\bP$, respectively:

\begin{eqnarray*}
B(b) &=& \get{s_b} \rel{p}\, \get{s_{1-b}} \; \rel{s_b} \get{p}
\rel{s_{1-b}}\\
\bB(b) &=& \get{s_b} \rel{\bp}\, \get{s_{1-b}}\; \rel{s_b} \get{\bp}
\rel{s_{1-b}}
\end{eqnarray*}

and the matching sequences on $C$'s side:

\begin{eqnarray*}
C(b) &=& \rel{s_b} \get{p}\, \rel{s_{1-b}} \; \get{s_b} \rel{p}
\get{s_{1-b}}\\
\bC(b) &=& \rel{s_b} \get{\bp}\, \rel{s_{1-b}}\; \get{s_b} \rel{\bp}
\get{s_{1-b}}
\end{eqnarray*}

At the beginning of a synchronization round between e.g. $C$ and
$P$, process $C$ owns locks $s_0$ and $s_1$, and $P$ owns $p$.
Having $C,P$ execute $C(b)$ and $B(b)$, respectively, in lock-step
manner, amounts to have $C$ and $P$ synchronize over bit $b$.
However, this synchronization can be “spoiled” by the other process,
here $\bP$, who may interfere with the executions of $C$ and $P$.
This makes the definition of $C$'s behavior more complicated (see
$C(P,b)$ in Figure <ref>, that contains $C(b)$ as the main branch).

We provide now a high-level description of the structure of the .
We start with processes $P$ and $\bP$, which are simpler than $C$
because it is process $C$ who controls the verification and who
initiates the synchronizations.
Process  $P$ is built as follows: after an initial phase it enters the choice
state where it has two "controllable" actions, each taking him to a sequence of
"uncontrollable" actions
realizing one of the sequences $B(b)$, and then returning to the  choice state
(see Figure <ref>).
Process $\bP$ is built similarly.
As we will see, a strategy for a processes simply amount to making choices in
the choice state, hence a strategy is a binary sequence.
The correctness of this sequence is checked via synchronization with $C$.

The behaviour of $C$ is as follows: after the initial phase, the environment tells $C$
whether she should check word equality or index equality (see Figure <ref>).
To check word equality, $C$
repeats the following procedure: she chooses a bit $b$ through a
"controllable" action, then checks that $b$ is the current bit of $P$,
and then the same for $\bP$ (cf. Figure <ref>).
For index equality the procedure is similar: $C$ chooses an index $i$
through a "controllable" action.
Then she checks that the next bits of $P$ correspond to $u_i$, and
that the next bits of $\bP$ correspond to $v_i$ (see Figure <ref>).
Figure <ref> shows the overall structure of $C$.

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) at (0,0) 0;

[state, rectangle] (qi) at (3.2,0) $\Init_C$;

[state] (q1) at (6.5,0) 1;
[state, rectangle] (q2) at (10,1) $C_{\mathit{letters}}$;
[state, rectangle] (q3) at (10,-1) $C_{\mathit{indices}}$;

(q0) edge (qi)
(qi) edge (q1)
(q1) edge[bend left] (q2)
(q1) edge[bend right] (q3)

After the initialization phase of $C$, the environment
chooses to check either that the two sequences of $P,\bP$
are equal or that they are produced by the same index
The parts $C_{\mathit{letters}}$ and $C_{\mathit{indices}}$
are described in Figures <ref>, <ref>.

The initialization  $\Init_C$ of process $C$ is  depicted
in Figure <ref>: process $C$ first acquires  $s_0,s_1$,
then synchronizes twice with $P$ over bit 0 and twice with $\bP$ over
bit 0.
This is done using components $C^\top(P,0)$ and $C^\top(\bP,b)$ as shown in
Figure <ref>.
These components are essentially the sequence $C(b)$ from page p:Cb with
added self-loops on every state where $C$ awaits a lock.
As we can see from Figures <ref> and <ref>, process $C$
cannot block in $\Init_C$ because there
is a self-loop from every state with outgoing acquire transition.

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) at (0,0) 0;
[state] (q1) at (3,0) 1;
[state, rectangle] (qi) at (10,0) $C^\top(P,0) C^\top(P,0)
C^\top(\bP,0) C^\top(\bP,0)$;

(q0) edge node[above] $\get{s_0}$ (q1)
(q0) edge[loop above] node $\top$ ()
(q1) edge[loop above] node $\top$ ()
(q1) edge node[above] $\get{s_1}$ (qi);

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) 0;
[state] (q1) [right of =q0] 1;
[state] (q2) [right of =q1] 2;
[state] (q3) [right of =q2] 3;
[state] (q4) [right of =q3] 4;
[state] (q5) [right of =q4] 5;
[state,accepting] (q6) [right of =q5] 6;

[->] (q0) edge node $\rel{s_b}$ (q1)
(q1) edge node $\get{p}$ (q2)
(q2) edge node $\rel{s_{1-b}}$ (q3)
(q3) edge node $\get{s_b}$ (q4)
(q4) edge node $\rel{p}$ (q5)
(q5) edge node $\get{s_{1-b}}$ (q6)

(q1) edge [loop below] node $\top$ ()
(q3) edge [loop below] node $\top$ ()
(q5) edge [loop below] node $\top$ ()

Component $C^\top(P,b)$ of process $C$, $b \in \set{0,1}$

To check word equality in $C_{\mathit{letters}}$, process $C$ selects transitions
matching the sequence of bits of both $P$ and $\bP$.
Because of the lock ownership initialization, the three processes
synchronize over the sequence $00\, 1b_1 \, 1 b_2 \dots$ instead of the PCP solution $b_1
b_2 \dots$ (cf. Figure <ref>).

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) 0;
[state] (q1) [above right of =q0] 1;
[state] (q2) [above left of =q1] 2;
[state] (q3) [below right of =q0] 3;
[state] (q4) [below left of =q3] 4;

[->] (q0) edge[dashed] node  (q1)
(q1) edge node[right] $C(P,1)C(P,0)$ (q2)
(q2) edge node[left] $C(\bP,1)C(\bP,0)$ (q0)
(q0) edge[dashed] node  (q3)
(q3) edge node $C(P,1)C(P,1)$ (q4)
(q4) edge node $C(\bP,1)C(\bP,1)$ (q0)

$C$ either synchronizes with $P$ and $\bP$ over bit 0
(upper branch) or over bit 1 (lower branch). The two outgoing
transitions of state 0 are "controllable".

To check index equality in $C_{\mathit{indices}}$, process $C$ selects a sequence
of indices and checks for each index $i$ with $P$ and $\bP$ that
their bit sequences match the sequences $u_i$ and $v_i$,
respectively, see Figure <ref>.

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) 0;
[state] (q1) [above right of =q0] 1;
[state] (q2) [above left of =q1] 2;
(q3) [right of =q0] ;
(q4) [below right of =q0] ;
(susp) [below of =q1] ...;

[->] (q0) edge[dashed] node 1 (q1)
(q1) edge node[right] $C(P,h(u_1))$ (q2)
(q2) edge node[left] $C(\bP,h(v_1))$ (q0)
(q0) edge[dashed] node 2 (q3)
(q0) edge[dashed] node[below left] $n$ (q4)

$C$ either synchronizes with $P$ and $\bP$ over some
index $i$, with $h(0)=10$ and $h(1)=11$. The outgoing
transitions of state 0 are "controllable".

The component $C(P,b_1\cdots b_k)$ in Figure <ref>  stands for the sequential composition of
$C(P,b_1), \ldots, C(P, b_k)$, see $C(P,b)$ defined in Figure <ref> (similarly for $C(\bP,b_1\cdots b_k)$).

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) 0;
[state] (q1) [right of =q0] 1;
[state] (q2) [right of =q1] 2;
[state] (q3) [right of =q2] 3;
[state] (q4) [right of =q3] 4;
[state] (q5) [right of =q4] 5;
[state,accepting] (q6) [right of =q5] 6;
[state] (q7) [above of =q1] 7;
[state] (q8) [right of =q7] 8;
[state] (q9) [right of =q8] 9;

[->] (q0) edge node $\rel{s_b}$ (q1)
(q1) edge node $\get{p}$ (q2)
(q2) edge node $\rel{s_{1-b}}$ (q3)
(q3) edge node $\get{s_b}$ (q4)
(q4) edge node $\rel{p}$ (q5)
(q5) edge node $\get{s_{1-b}}$ (q6)
(q1) edge node $\get{\bp}$ (q7)
(q7) edge node $\rel{s_{1-b}}$ (q8)
(q8) edge node $\get{p}$ (q9)

(q3) edge [loop below] node $\top$ ()
(q5) edge [loop below] node $\top$ ()
(q9) edge [loop above] node $\top$ ()

Component $C(P,b)$ of process $C$, with $b \in \set{0,1}$

It remains to describe processes $P$ (and $\bP$), see
Figure <ref>.
We describe only $P$, since $\bP$ is symmetric.

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) at (0,0) 0;
[state] (q1) at (6.5,0) 1;
[state] (q2) at (8,2) ;
[state] (q3) at (8,-2) ;

[state, rectangle] (qi) at (3.2,0) $\Init_P$;

(q0) edge (qi)
(qi) edge (q1)
(q1) edge[dashed, bend left] (q2)
(q1) edge[dashed, bend right] (q3)
(q2) edge[bend left] node[right] $B(1)B(0)$ (q1)
(q3) edge[bend right] node[right] $B(1)B(1)$ (q1)

Process $P$, with $\Init_P = \get{p} \,B^\top(0)\,
B^\top(0)$.  The outgoing transitions of state 1 are "controllable".

The initialization sequences of $P$ and $\bP$ are:

\[ \Init_P = \get{p} \,B^\top(0)\, B^\top(0), \quad \Init_{\bP} =
\get{\bp} \,\bB^\top(0)\, \bB^\top(0) \]

They use the (deadlock-free)  component $B^\top(b)$ from
Figure <ref>.
Note that $B^\top(b)$ has the block $B(b)$ from page p:Cb as
main branch, extended by self-loops on the transitions that need to
acquire a lock, so that no deadlock will be possible in this part.
In $\Init_P$ process $P$ first acquires lock $p$, then tries to
synchronize with $C$ twice over bit 0.
After $\Init_P$, process $P$ repeatedly chooses between executing $B(1)B(0)$ or
$B(1)B(1)$, see Figure <ref>.
Process $\bP$ is defined analogously, with lock $\bp$ instead of $p$.

[node distance=1.8cm,auto,>= triangle
initial= [initial by arrow,initial text=,initial
distance=.7cm, initial where=left]
accepting= [accepting by arrow,accepting text=,accepting
distance=.7cm,accepting where =right]

[state,initial] (q0) 0;
[state] (q1) [right of =q0] 1;
[state] (q2) [right of =q1] 2;
[state] (q3) [right of =q2] 3;
[state] (q4) [right of =q3] 4;
[state] (q5) [right of =q4] 5;
[state,accepting] (q6) [right of =q5] 6;

[->] (q0) edge node $\get{s_b}$ (q1)
(q1) edge node $\rel{p}$ (q2)
(q2) edge node $\get{s_{1-b}}$ (q3)
(q3) edge node $\rel{s_b}$ (q4)
(q4) edge node $\get{p}$ (q5)
(q5) edge node $\rel{s_{1-b}}$ (q6)

(q0) edge [loop below] node $\top$ ()
(q2) edge [loop below] node $\top$ ()
(q4) edge [loop below] node $\top$ ()

Component $B^\top(b)$ of process $P$, $b \in \set{0,1}$

Note that in our   no "controllable" action uses
locks. Hence it is always in the system's interest to allow at most one outgoing transition when it controls several, as this will not cause a deadlock and simply amounts to reducing the set of runs the environment can choose.
Hence, if a strategy is "winning" then it remains so  if we
restrict it to allow only one "controllable" action.

In particular, a "strategy" for $P$ and $\bP$, respectively,
corresponds to the choice of a
binary sequence (finite or infinite).

Our  is such that at any time, each of the
processes that has already started its execution (by leaving
the initial state) owns at least one lock.

In particular, if all three processes have started
then at most one lock can be free.

The next lemma describes the main properties of one round of synchronization between
$C$ and $P$, over bit $b$.

Recall that by Remark <ref> we can assume that
$P$'s strategy never allows to do both $B(0)$ and $B(1)$, and
similarly for $\bP$.

Assume that $C$ is in state 0 of $C(P,b)$ (c.f. Figure <ref>), $P$
is in its choice state ready to execute $B(0)$ or $B(1)$, and $\bar{P}$ is in
its choice state ready to execute $\bB(0)$ or $\bB(1)$.
Moreover, $C$ owns $s_0,s_1$, $P$ owns $p$ and $\bP$ owns $\bp$.

If $P$'s strategy does not allow to do $B(b)$
then some execution from the above configuration reaches a deadlock.
Otherwise, in all executions process $C$ either
stays in some  $\top$-labeled loop, or reaches state $6$.
In the latter case, when $C$ has reached state 6: process $P$ has
finished $B(b)$, process $\bP$ did
not move, and the lock ownership is the same as before the execution.

Consider first the case where $P$'s strategy does not allow to
do $B(b)$.
If $\bP$  is not allowed to do $\bB(b)$, then the system is "deadlocked" after $C$ releases $s_b$.
Otherwise we claim that the environment
wins by following the branch $1,7,8$, with $\bP$ doing the
matching operations $\get{}$ and $\rel{}$.
This is because the system is "deadlocked" after $\bP$
releases $s_b$:
$\bP$ needs $\bp$ and $P$ does not require $s_b$, which is the
only free lock.
Moreover, $C$'s transition $8 \act{\get{p}} 9$ is not
possible, since $P$
did not release $p$.

We are left with the case where $P$'s strategy allows to do
$B(b)$ (and not $B(1-b)$).
After $C$ releases $s_b$ the following can happen:

* If $\bP$ takes $s_b$ then $C$'s action
$\get{p}$ in state 1 cannot happen.
The communication along the path $1,7,8$ is
between $C$ and $\bP$. When $\bP$ releases $s_b$ and
$C$ is in state $8$, then the environment has no
choice but to let $P$ acquire $s_b$ and $C$ acquire
$p$ to reach $9$, thus the system does not deadlock.

* Otherwise $P$ takes $s_b$ and $C$ can proceed
until state 3.

We assume now that $C$ is in state 3.
There are two cases:

* Suppose that $P$ took $s_{1-b}$ after $C$ released it.
Next $P$ releases $s_b$, hence
$C$ can take $s_b$, release $p$, and proceed to state 5.
Or $\bP$ takes $s_b$, in which case $C$'s action
$\get{s_b}$ in state 3 can never happen: $\bP$ waits
for $s_{1-b}$ (owned by $P$) and $P$ waits for $p$ (owned by $C$).
In the latter case $C$ will loop forever in state 3.

* Suppose that $\bP$ took $s_{1-b}$ after $C$ released
Then $C$'s action
$\get{s_b}$ in state 3 can never happen because $P$ still owns
So $C$ will again loop forever in state 3.

Assume finally that $C$ is in state 5.
Since $p$ was just released by $C$, process $P$ can take it and release
There are three possible cases:

* If $\bP$ takes $s_{1-b}$ then $C$'s action
$\get{s_{1-b}}$ from state 5
will never happen: $\bP$ waits for $s_b$ (owned by $C$) and $P$
waits either for $s_{1-b}$ or $s_b$, to start the next block
So $C$ will loop forever in state 5.

* The situation is similar if $P$ takes $s_{1-b}$ again
(as part of his next block): $P$ waits for $s_b$ (owned by
$C$) and $\bP$ waits either for $s_{1-b}$ or $s_b$, for his next block.
Again, $C$ will loop forever in state 5.

* If $C$ takes $s_{1-b}$ then she proceeds to state 6, and the lock
ownership is the initial one.

Note that each synchronization round, as described in
Lemma <ref>, is  initiated by $C$, since both $P$ and
$\bP$ need one of the locks $s_b$ or $s_{1-b}$ in order to
start $B(b), \bB(b)$ respectively.
In particular, when $P$ and $\bP$ are ready to execute
the next block ($B(b)$ or $\bB(b)$), they need $C$ to release a lock
in order to start their execution.

Observe also that Lemma <ref> requires the assumption that $P$ owns
$p$, $\bP$ owns $\bp$, and $C$ owns $s_0,s_1$ when a
synchronization round starts.
The encoding $h$ and the initial bits 00 are used in order to
enforce such an initial configuration from the starting configuration,
where all locks are free.

We show now that it is possible to enforce the initial lock ownership
of Lemma <ref> from the initial configuration where all
locks are free.

We denote by $""\Start""$ the configuration where $C$ is in state $1$ of
Figure <ref>, holding the locks $s_0$ and $s_1$, and $P$
and $\bP$ are in state $1$ of Figure <ref>, holding $p$ and
$\bp$, respectively.

We will use a particular vocabulary  in order to shorten the
subsequent proof:
we say that $C$ and $P$ execute $C^\top(P,b)$ and $B^\top(b)$ ""synchronously"" if
they go from state $0$ to $6$ in Figures <ref> and <ref> respectively
while alternating their operations: $C$ releases $s_b$ and $P$ acquires it, then $P$
releases $p$ and $C$ acquires it, etc.
This wording is used similarly for $C^\top(\bP,b)$ and $\bB^\top(b)$.

We say that the initialization phase

is executed
""entirely synchronously"" if the two copies of $B^\top(0)$ and
of $C^\top(P,0)$ are executed synchronously, and
the two copies of  $\bB^\top(0)$ and of
$C^\top(\bP,0)$ are executed synchronously as well.

Assume that processes $C, P, \bP$ all start their execution and the
"initialization phase" is not executed "entirely synchronously".
Then one
of the processes loops forever in its initialization part.
Otherwise, the configuration $"\Start"$ is reached after executing the
"initialization phase".

We distinguish three cases.

Case 1: $C$ starts last.

Let us assume that $C$ does not loop forever in $\Init_C$.
So process $C$ will ultimately execute  execute the first two steps of $\Init_C$,
acquiring  $s_0$ and $s_1$.
Recall that by Remark <ref> at
most one lock is available at this point, so $P$ owns exactly
Next $C$ needs to  execute $C^\top(P,0)$ twice.
If at any moment of this sequence $\bP$ interferes by
acquiring $s_0$ or $s_1$ when $C$ releases it,  then $\bP$ releases
$\bp$, which would become the only free lock.
But since $\get{\bp}$ does not occur in $C^\top(P,0)$, $C$
would then loop forever in
$\Init_C$, which we assumed does not happen.
So $\bP$ does not interfere.

Furthermore, for $C$ not to loop forever in $\Init_C$, it must
be the case that
every time $C$ releases a lock, $P$ acquires it and releases
the lock that $C$ is waiting for next.
As a result, either $C$ loops forever in $\Init_C$, or $C$ and $P$
execute "synchronously" twice $C(P,0)$ and $B(0)$, which is only
possible in $\Init_P$.

After this part of the run
$P$ is in  state $1$ of Figure <ref> and $C$ is ready to
run $C^\top(\bP,0)$ twice.
By the same argument, either $C$ loops forever in $\Init_C$,
or $\bP$ and $C$ synchronize over $0$ twice, bringing
the  to configuration $\Start$.

Case 2: $P$ starts last.

Let us assume that $P$
does not loop forever in $\Init_P$.
When $P$ first acquires $s_0$ in $\Init_P$ and releases $p$, we know by
Remark <ref> that $p$ is the only
free lock at this step.
Hence the next operation must be $C$ acquiring $p$, and then
releasing $s_1$.
Thus $C$ is currently executing "synchronously" with $P$ either $C^\top(P,0)$ or the main
branch of $C(P,0)$.
The two processes must then proceed with the synchronization
over bit 0, since otherwise $P$ would loop forever in $\Init_P$.
Note that $\bP$ cannot interfere by taking  $s_0$ or $s_1$,
since this would again make  $P$ loop forever in $\Init_P$, because
it does not need $\bp$.

After $P$ executed the first $B^\top(0)$ "synchronously" with $C$, it
starts the second  $B^\top(0)$.
For the same reason as before, $C$ has to execute
"synchronously" with $P$ either $C^\top(P,0)$ or the main
branch of $C(P,0)$.
However there was no synchronization between $P$ and $C$ over $1$ in between, as $P$ kept $p$ between the two synchronizations.
As $C$ never executes $C(P,0)$ twice consecutively outside $Init_C$,
$C$ was actually executing $\Init_C$ and is now ready to enter the
second part, the two executions of $C^\top(\bP,0)$.

Just like before, if $P$ interferes in the execution of
$C^\top(\bP,0)$, releasing $p$,
then $C$ will loop forever in $\Init_C$.
We use the same arguments for that part of the run as in case $1$.

So in the end either one of the processes loops forever in its
synchronizations phase, or all three reach the configuration $\Start$.

Case 3: $\bP$ starts last.

We  use similar arguments as in case 2, and consider the
moment after $\bP$ executed its first action $\get{\bp}$.
Next, process $\bP$
needs to execute twice $\bB^\top(0)$.
Assume that $\bP$ does not loop in $\Init_{\bP}$.
This implies that $\bP$ executes the two copies of $\bB^\top(0)$
"synchronously" with $C$  executing twice  $C^\top(0,\bP)$ (for
the same reason as in case 2, $C$ executes here
$C^\top(0,\bP)$, not the main branch of $C(0,\bP)$).
So	$C$ must have executed $C(0,P)$ twice before.

Case 3.1: $P$ started before $C$ first acquires $p$
in $\Init_C$.

After $C$ first acquires $p$
in $\Init_C$ it either executes $C^\top(0,P)$ twice
synchronously with $P$ executing $B^\top(0)$, or $C$ loops
forever in $\Init_C$.

Next, $C$ has to execute the two copies of $C^\top(\bP,0)$.
Similar arguments as in case 2 show that either $\bP$ loops
forever in $\Init_{\bP}$, or $C$ and $\bP$ execute twice
"synchronously" $C^\top(\bP,0)$ and $\bB^\top(0)$.
So in the end either one of the processes loops forever in its
synchronization sequence, or all three processes reach configuration $\Start$.

Case 3.2: $P$ starts after $C$ first acquires $p$ in $\Init_C$.

This means that $P$ has to wait until $C$ first releases $p$ to start.
If $P$ starts before $C$ acquires $p$ for the second time, by similar arguments as before
he has to execute a synchronization over $0$ along with $C$, but needs to wait until the
end of $\Init_C$ to execute its second synchronization over $0$.
If $P$ starts after $C$ releases $p$ for the second time, then it cannot acquire $p$
before the end of $\Init_C$.

In both cases at the end of $C$'s initialization phase $P$ has started
(as $\bP$ has started, and $P$ starts before $\bP$ in this case) but has at least one
synchronization over $0$ left to do from $\Init_P$.
However $C$ has to synchronize with $P$ over $1$ at that point.

We show now that $P$ will loop in any case in $\Init_P$.
Consider Figure <ref>: $C$ releases $s_1$, which can only be acquired by $\bP$, who releases $\bp$.
Then	$C$  releases $s_0$. Next, $\bP$ may acquire it and release $s_1$, which prevents processes to make any other operation, while $P$ is still in its initial part.
Or $P$ may get it, release $p$, which $C$ acquires. Thus process
$P$ again loops in $\Init_P$.

We have considered all cases, and shown that in all of them
either one of the processes loops forever in its initialization
phase, or they  reach
configuration $\Start$.

There is a winning strategy for the  with processes $C,P,\bP$ if and only if the PCP instance has a solution.

Suppose that the system wins.
Consider a maximal run when the "initialization phase" is executed
"entirely synchronously".
According to Lemma <ref> this run goes through

configuration $"\Start"$, after which the processes
follow their "winning strategy".
Note first that $C$'s strategy cannot  stop in
any of the states in which she chooses bits or indices, by
proposing no "controllable" action.
This is because in such states $C$ holds both $s_0$ and $s_1$.
Moreover, as all three processes
started, all of them always hold a lock
(see Remark <ref>), hence $P$ holds  $p$ and
$\bP$ holds $\bp$.
So if $C$'s strategy would block then the entire system would
block, contradicting the "winning strategy".
As a consequence, the strategies of $P$ and $\bP$ cannot stop

By Lemma <ref>, the strategies of $P$ and
$\bP$ produce the same (infinite) binary sequence $b_1 b_2 \dots$,  matching the
one produced by $C$.
This is because although Lemma <ref> refers to a
single synchronization round, such a round cannot interfere
with the subsequent rounds:
recall from  Remark <ref> that if $C$ reaches the
final state of $C(P,b)$, then this
means that $P$ has finished the execution of $B(b)$, and so $P$ waits for
$C$ to initiate the next round.

Thus, if the environment chose to enter $C_{\mathit{letters}}$ in $C$
then absence of deadlock means that all three processes proposed the same infinite binary sequence.
If the environment chose to enter $C_{\mathit{indices}}$,
then absence of deadlock means
the sequence produced by $P$ is $u_{i_1}u_{i_2}\dots$ and the
one produced by $\bP$ is $v_{i_1}v_{i_2}\dots$, for
$i_1i_2\dots$ the index sequence chosen by the winning strategy in $C$.
As the sequences produced by $P$ and $\bP$ are independent of the choice of the
environment, they must be equal, and equal to $u_{i_1}u_{i_2}\dots$ and $v_{i_1}v_{i_2}\dots$.
Hence, the  PCP instance has a solution.

For the other direction assume that PCP has an infinite (unique) solution
$u_{i_1} u_{i_2} \ldots=v_{i_1}v_{i_2}\dots$.
The strategy of $C$ in Figures <ref>
and <ref> consists in choosing the bits/indices
provided by the solution.
If the initialization phases are not executed "entirely synchronously" then the
system wins by having some process loop forever in its initialization
part (Lemma <ref>).
Otherwise, configuration $\Start$ is reached and we use
Lemma <ref> to show that the strategy is winning.

Lemma <ref> completes the proof of Theorem <ref>.

§ CONCLUSIONS

Motivated by a recent undecidability result for distributed control
synthesis <cit.> we have considered a  model for which the
problem has not been investigated yet.
With hindsight it is strange that the well-studied model of lock synchronization
has not been considered in the context of distributed synthesis.
One reason may be the “non-monotone” nature of the synthesis
It is not the case that for a less expressive class of systems the problem is
necessarily easier because the controllers get less powerful, too.

The two decidable classes of lock-sharing systems presented here are rather promising.
Especially because the low complexity results cover already non-trivial problems.
All our algorithms are based on analyzing lock patterns.
While in this paper we consider only finite state processes, the same method
applies to more complex systems, as long as solving the centralized control problem in the style of
Lemma <ref> is decidable.
This is for example the case for pushdown systems.

There are numerous directions that need to be investigated further.
We have focused on deadlock avoidance because this is a central property,
and deadlocks are difficult to discover by means of testing or verification.
Another option is partial deadlock, where some, but not all, processes are
The concept of $Z$-"deadlock scheme" should help
here, but the complexity results may be different.
Reachability, and repeated reachability properties need to be
investigated, too.

We do not know if the upper bound from Theorem <ref> is tight.
The algorithm for verifying if there is a "deadlock" in a given "lock graph",
Algorithm <ref>, is already quite complicated, and
it is not clear how to proceed when a "strategy" is not given.

Another research direction is to consider probabilistic controllers.
It is well known that there are no symmetric solutions to the dining philosophers
problem but there is a randomized one <cit.>.
Symmetric solutions are quite important for resilience issues as it is preferable that
every process runs the same code.
The Lehmann-Rabin algorithm is essentially the system presented in
Figure <ref> where the
choice between $\lft$ and $\rgt$ is made randomly.
This is one of the examples where randomized strategies are essential.
Distributed synthesis has a potential here because it is even more difficult to construct
distributed randomized systems and prove them correct.