:
LEAVE UNSET 2023 LEAVE UNSET LEAVE UNSET Machine Learning for Health (ML4H)
2023

# ML4H 2023 Template: Proceedings Track

Hung, Le Nhat<EMAIL_ADDRESS>
University of Surrey  United Kingdom  Ong<EMAIL_ADDRESS>
University of Surrey  United Kingdom  Bober, Miroslaw<EMAIL_ADDRESS>
University of Surrey  United Kingdom

#  SurvTimeSurvival: Survival Analysis On The Patient With Multiple
Visits/Records

Hung, Le Nhat<EMAIL_ADDRESS>
University of Surrey  United Kingdom  Ong<EMAIL_ADDRESS>
University of Surrey  United Kingdom  Bober, Miroslaw<EMAIL_ADDRESS>
University of Surrey  United Kingdom

###### Abstract

_The accurate prediction of survival times for patients with severe diseases
remains a critical challenge despite recent advances in artificial
intelligence. This study introduces ”SurvTimeSurvival: Survival Analysis On
Patients With Multiple Visits/Records,” utilizing the Transformer model to not
only handle the complexities of time-varying covariates but also covariates
data. We also tackle the data sparsity issue common to survival analysis
datasets by integrating synthetic data generation into the learning process of
our model. We show that our method outperforms state-of-the-art deep learning
approaches on both covariates and time-varying covariates datasets. Our
approach aims not only to enhance the understanding of individual patient
survival trajectories across various medical conditions, thereby improving
prediction accuracy, but also to play a pivotal role in designing clinical
trials and creating new treatments. 111The source code associated with the
methodologies and results presented in this manuscript will be made publicly
available and can be accessible at:
https://github.com/davidlee1102/Surtimesurvival. _

##  1 Introduction

Survival analysis, called time-to-event, is concerned with predicting event
occurrence times and is indispensable in medicine Friedman et al. (2015),
social sciences Box-Steffensmeier et al. (2015), and economic Davidson-Pilon
(2019), enabling researchers to compute survival probabilities and hazard
functions and compare diverse groups or conditions. Traditional models such as
the Cox (1972) and Kaplan-Meier Bland and Altman (1998) estimators have
foundational significance but are limited due to the restrictive assumption
made. In particular, these limitations are relaxed on recent AI-based
solutions like DeepSurv Katzman et al. (2018), Deep-Hit Lee et al. (2018),
Dynamic Deep-Hit Lee et al. (2019), and Deep Survival Machines Nagpal et al.
(2021) symbolize evolution in this domain. Notably, the SurvTrace model Wang
and Sun (2022), employing deep learning with the Transformer-based
architecture Vaswani et al. (2017); Devlin et al. (2018), has shown promising
predictive accuracy. However, some limitations still remain, affecting
survival prediction accuracy.Specifically, it appears that SurvTrace does not
adequately incorporate time-varying covariates (time-cov) in each patient’s
records, potentially impacting the robustness of this method. On another
front, Dynamic Deep-Hit’s dependence on LSTM architecture Hochreiter and
Schmidhuber (1997) may constrain its predictive prowess due to a ”long-term
dependency problem” Zhao et al. (2020).

Contribution. In this work, we propose ”SurvTimeSurvival: Survival Analysis On
The Patient With Multiple Visits/Records” deep-learning with the Transformer-
based method that not only leverages the SurvTrace strength but also utilizes
time-varying covariates adaptation to more accurately model and comprehend
each individual patient’s data, enhancing the precision of survival
predictions. A more granular exposition of SurvTimeSurvival is elaborated on
three different points:

  1. (a)

We develop a new approach that facilitates the management of both covariates
and time-varying covariates data by utilizing the advantages of Transformers
architecture Vaswani et al. (2017) with multiple related visits/records,
thereby augmenting the comprehension of dependent visits/records that relate
to each identified patient.

  2. (b)

We design a new architecture that combines our proposed model (a) with
SurvTrace Wang and Sun (2022) method to not only optimize learning across a
variety of data and emphasize essential features that influence patient
survival duration but also utilize the advantages of SurvTrace.

  3. (c)

We proposed SurvTimeSurvival, a novel approach that strategically combines our
integration model (b) with the SurvivalGan technique Norcliffe et al. (2023)
to harness the benefits of synthetic data during training, thereby enhancing
survival prediction accuracy.

We have performed comprehensive experiments on SurvTimeSurvival using three
different public time-varying covariates and covariates medical datasets. The
resulting experimental results demonstrate that our method markedly surpasses
the state-of-the-art baselines.

##  2 Related Work

In longitudinal survival analysis in healthcare, ”time-varying covariates”
(time-cov) encapsulate dynamic changes to patient data across visits/records,
improving comprehension of evolving health trends and event risks, such as
relapse or death. Contrasted with ”time-varying covariates”, the covariates
data is ”non-time-varying covariates” data or ”time-invariant covariates”
data, meaning each patient has one record/visit only. Time-varying covariates
data helps to reveal intricate temporal relationships, enhancing prediction
accuracy and clarifying key risk factors Pourjafari et al. (2022).

The Cox PH model Cox (1972) is fundamental in survival analysis in biomedical
research, clarifying how covariates affect survival. However, its assumptions,
such as expecting proportionality and linear relationships among covariates,
might limit its usefulness in situations where there are complex non-linear
interactions. Contemporary methodologies like Katzman et al. (2018); Nagpal et
al. (2021); Lee et al. (2019, 2018) offer advanced analytical prowess,
although they are not immune to pitfalls. The prevalent use of RNN Schmidt
(2019) and LSTM Hochreiter and Schmidhuber (1997) networks may not be suited
for survival analysis since the ”long-term dependency problem” Zhao et al.
(2020).

The Transformer architecture Vaswani et al. (2017) and BERT Devlin et al.
(2018) have improved sequential medical data processing Hu et al. (2021), with
BERT using pre-trained models for bidirectional clinical contexts. Moreover,
SurvTRACE Wang and Sun (2022) is a Transformer-based model integrating
numerical embedding, attentive encoding, and an alignment module for tasks
like survival analysis, mortality prediction, and length-of-stay prediction.
It uses discrete-time hazard rates, PCH loss, and IPS-based PCH loss to
improve the prediction of survival outcomes. However, SurvTrace just only
deals with covariates (cov) in each patient’s records, potentially impacting
the results’ robustness. Based on that, our research capitalizes on
Transformer features for time-varying covariates adaptation handling,
optimizing feature interpretation, and enriching SurvTrace strength.

Synthetic data Lu et al. (2023), created to mimic real-world data
statistically, helps in maintaining patient privacy. SurvivalGAN Norcliffe et
al. (2023) is a GAN Creswell et al. (2018) variant sculpted capable of
synthesizing time-to-event data, crucial for survival analysis— a domain
concentrating on durations preceding pivotal events. By being implemented in
the Synthcity framework Qian et al. (2023), SurvivalGAN engenders datasets
mirroring authentic data characteristics but sans personal identifiers. Thus,
synthetic data is pivotal in tackling the training challenges arising from
data insufficiency, a situation often precipitated by privacy issues and
technology limitations.

Figure 1: In the SurvTimeSurvival framework, raw data comprising both
categorical and numerical covariates is encoded and partitioned into training
and test sets. The training set is augmented with synthetic data generated by
SurvivalGan Norcliffe et al. (2023) and subsequently processed to adapt time-
varying covariates structure. By adding the masking, it allows the attention
mechanism of our model to ignore the padded components of our input. After
implementing masking and padding, the data is fed into the SurvTimeSurvival
framework, a hybrid model that integrates our Transformer-based model Vaswani
et al. (2017)—designed to handle both data types—and the SurvTrace module Wang
and Sun (2022), which utilizes $N$ features from our module for survival
outcomes predictions. The model’s performance is then evaluated on the test
data. This evaluation is conducted after the data has been processed to adapt
time-varying covariates and apply masking and padding functions (phase 2). The
evaluation metrics used for this assessment are the Concordance Index and the
Brier score.

##  3 Model Architecture

An overview of our SurvTimeSurvival architecture is shown in Figure 1. Its
architecture consists of three main components: ”Our Transformer-based
temporal aggregation method”, ”SurvTrace ”, and ”SurvivalGan”.

Specifically, the combination of our temporal aggregator and SurvTrace allows
our model to deal with two types of survival analysis data (time-varying
covariates and covariates) whilst simultaneously leveraging the strength of
SurvTrace Wang and Sun (2022). Moreover, the integration of SurvivalGan
Norcliffe et al. (2023) for synthetic data generation into our learning
process allows us to tackle the issue of data sparsity in survival analysis
data. We show in Section 4 that this results in a noticeable improvement in
the accuracy of survival predictions.

###  3.1 Problem Definition

We define the structure of our survival data as follows:

$D=\\{(\bm{X}_{i},\bm{Z}_{i},\bm{t}_{i},e_{i})\\}_{i=1}^{n}$

The total number of patients is $n$. Each patient (say $i^{th}$ patient), has
$N_{i}$ number of records, where $\bm{X}_{i}\in\mathbb{R}^{N_{i}\times
n_{num}}$ represents the $n_{num}$ numerical  covariate features,
$\bm{Z}_{i}\in\mathbb{Z}^{N_{i}\times n_{cat}}$ represents the $n_{cat}$
categorical  covariate features. The vector of event times is given as
$\bm{t}_{i}\in\mathbb{R}^{N_{i}}$. The indicator $e_{i}$ differentiates
whether $\bm{t}_{i}$ is an actual event or censored. For single events,
$e_{i}$ is binary, but for competing events, $e_{i}\in\\{0,1,\ldots,K_{E}\\}$
specifies the event at $\bm{t}_{i}$. A value of $e_{i}=0$ denotes right-
censoring for the $i$-th patient, meaning no events were observed by the
study’s end Wang and Sun (2022). Note that in the event of covariates data
(i.e. non time-varying covariates), we set $N_{i}=1$. Central to survival
analysis is understanding the hazard and survival functions, with the survival
function $S(t)$ representing the probability a subject is event-free until
time $t$, defined as $S(t)\equiv\Pr(T>t)$. Meanwhile, the hazard function,
symbolized as $\lambda(t)$, provides a momentary rate at which events
transpire, conditional on the absence of prior events. It is defined by the
following limit:

$\lambda(t)\equiv\lim_{{\Delta t\to 0}}\frac{\Pr(t\leq T<t+\Delta t\,|\,T\geq
t)}{\Delta t}$

The hazard function, $\lambda(t)$, fundamentally represents the instantaneous
risk of event occurrence at time $t$, given that the subject has remained
event-free up to and including time $t$. In a similar vein, the probability
mass function (PMF) associated with the event time is denoted as $g(t)$, where
$g(t)=\Pr(T=t)$ explicitly characterizes the probability that the event
transpires precisely at time $t$.

###  3.2 Survival Data: An Overview of Processing & Generating Synthetic Data

Our model follows the common pre-processing step of normalizing numerical
features and encoding categorical features. With the numerical data
$\bm{X}=\\{((x_{j})_{j=1}^{n_{num}})_{i}\\}_{i=1}^{n}$ with
$x_{j}\in\mathbb{R}$, we normalize as
$\bm{X}^{\prime}=\\{((x_{j}^{\prime}=\frac{x_{j}}{M})_{j=1}^{n_{num}})_{i}\\}_{i=1}^{n}$
where $M$ is $\bm{X}$’s maximum. For categorical data
$\bm{Z}=\\{((z_{j})_{j=1}^{n_{cat}})_{i}\\}_{i=1}^{n}$ with
$z_{j}\in\mathbb{N}$ undergoes one-hot encoding Xu et al. (2019), producing
$\bm{Z}^{\prime}=\\{((O(z_{j}))_{j=1}^{n_{cat}})_{i}\\}_{i=1}^{n}$. The
unified dataset $\bm{Y}$ combines $X^{\prime}$ and $Z^{\prime}$, represented
as
$\bm{Y}=\\{\left((x_{1}^{\prime},\ldots,x^{\prime}_{n_{num}},O(z_{1}),\ldots,O(z_{n_{cat}})\right)_{i}\\}_{i=1}^{n}$,
with $n$ being total visits/records and $n_{num},n_{cat}$ are the number of
numerical and category features.

After the above pre-preprocessing, the dataset is partitioned into a part for
training/validation and the remaining as the test subset. We have ensured that
the test subset is not involved in either the model training nor the synthetic
data generation. Subsequently, the training data undergoes synthesis using the
SurvivalGan paradigm Norcliffe et al. (2023). This framework leverages the
power of the Generative Adversarial Network (GAN) Creswell et al. (2018),
facilitating the proficient generation of synthetic covariates data. The main
target of SurvivalGAN is finding the result of the ”optimism” equation.
Mathematically, its formula is delineated:

$\text{Optimism}=\int_{0}^{\infty}f(t)[p_{\text{Syn}}(t)-p_{\text{Real}}(t)]\,dt.$

Where $f(t)$ is defined as a function for piecewise. If the time interval
$0\leq t\leq T$, $f(t)$ takes on the value of $t/T$, while times greater than
$T$, $f(t)$ is simply 1. Moreover $p_{\text{Syn}}(t)$, and
$p_{\text{Real}}(t)$ represent the survival function of the synthetic data and
the real data at time $t$, respectively. Thus, the measure ”optimism”
quantifies deviations between synthetic and real survival datasets. This
promotes a data representation, counteracting biases and enhancing model
reliability and prediction accuracy across diverse scenarios.

Post-generation of synthetic data, we add it to the previous
training/validation set. The combined data is then transformed to a time-
varying covariates format. Should the data already be in time-varying
covariates format, each patient’s series of visits/records are amalgamated
into a structured sequence, akin to sequence processing approaches in NLP
Devlin et al. (2018); Liu et al. (2019). Moreover, let ST represent the
synthetic feature; the generated and original data will be represented as
follows:

$\displaystyle\bm{G}$
$\displaystyle=\left\\{\left(\\{(O(z_{ST_{v}}))\\}_{v=1}^{n_{cat}},\\{(x_{ST_{j}}^{\prime})\\}_{j=1}^{n_{num}}\right)_{i}\right\\}_{i=1}^{m}$
$\displaystyle\bm{Y}$
$\displaystyle=\left\\{\left(\\{(O(z_{v}))\\}_{v=1}^{n_{cat}},\\{(x_{j}^{\prime})\\}_{j=1}^{n_{num}}\right)_{i}\right\\}_{i=1}^{n}$

where $m$ is the number of visits/records generated, with $n$ being the total
visits/records in original data and $n_{num},n_{cat}$ is the number of
numerical and category features respectively, encompassing both original and
synthesized data. We denote the combined dataset of data in $\bm{G}$ and
$\bm{Y}$ as $\bm{Y}^{\prime}$.

Moreover, given a maximum number of visits/records of the patient is $V$, the
number of visits/records equal to V truncates to the $V$ visits/records, while
those with fewer V will be padded as $<\textbf{{pad}}>$ for uniformity.
Specifically, for patient id_1 with $n<V$ visits/records, the sequence is
represented as
$\text{id\\_1\\_sequence}=\\{\text{{{v}}}_{i}\\}_{i=1}^{n}\cup\\{<\textbf{{pad}}>\\}_{i=n+1}^{V}$,
where $\mathbf{v}_{i}$ is the $i$-th visit/record, containing
$n_{num},n_{cat}$ features at time $i$.

###  3.3 Temporal Attention-based Aggregation Model

In this section, we describe our temporal aggregation design that leverages
the strength of the Transformer architecture to deal with two different data
types: time-varying covariates data and covariates data. Our design is split
into 3 main parts: Input representation & Positional encoding, Transformer
encoder layer, and Features extraction through the embedding layer.

####  3.3.1 Input Representation & Positional Encoding On Patient Data

Given a time-varying covariates sequence of a patient, denoted as $\bm{x}$, it
is transformed as:

$\displaystyle E(\bm{x})$ $\displaystyle=\bm{xW}_{\text{emb}}+b_{\text{emb}}$
(1) $\displaystyle P_{\text{pos},2i}$
$\displaystyle=\sin\left(\frac{\text{pos}}{10000^{2i/d_{\text{model}}}}\right)$
(2) $\displaystyle P_{\text{pos},2i+1}$
$\displaystyle=\cos\left(\frac{\text{pos}}{10000^{2i/d_{\text{model}}}}\right)$
(3) $\displaystyle\bm{x}^{\prime\prime}$ $\displaystyle=E(\bm{x})+P$ (4)

Given the set of equations, the parameters $\bm{W}_{\text{emb}}$ and
$b_{\text{emb}}$ are representative of the weight and bias terms for the
embedding layer, respectively. Specifically, equation (1) delineates the
computation for $E(\bm{x})$, which serves as an embedding containing salient
information. This embedding is subsequently enhanced with the integration of
positional encodings, as defined by the functions $P_{\text{pos},2i}$ and
$P_{\text{pos},2i+1}$. The culmination of this process is
$\bm{x^{\prime\prime}}$, a sophisticated representation encapsulating a
patient’s comprehensive medical history, amalgamating both categorical and
numerical data from their records or visits. Such intricate representations
are pivotal in the domain of survival models, where they are employed to
prognosticate temporal outcomes related to specific events.

####  3.3.2 Transformer Encoder Layers

After having the enriched representation $\bm{x}^{\prime\prime}$, it will be
processed through the Transformer encoder layers Devlin et al. (2018).
Mathematically, for each layer:

$\displaystyle\text{Attention}(Q,K,V)$
$\displaystyle=\text{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)V$ (5)
$\displaystyle\bm{x}^{\prime\prime\prime}_{1}$
$\displaystyle=\text{LayerNorm}(\bm{x^{\prime\prime}}+\text{Attention}(Q,K,V))$
(6) $\displaystyle\text{FFN}(\bm{x})$
$\displaystyle=\max(0,\bm{xW}_{1}+b_{1})\bm{W_{2}}+b_{2}$ (7)
$\displaystyle\bm{x}^{\prime\prime\prime}_{2}$
$\displaystyle=\text{LayerNorm}(\bm{x}^{\prime\prime\prime}_{1}+\text{FFN}(\bm{x}^{\prime\prime\prime}_{1}))$
(8)

From Eq. (5), the attention scores are computed through the dot product of the
Query (Q) and Key (K) matrices, scaled down by a factor of $\sqrt{d_{k}}$.
These scores dictate the weighting for each component in the Value (V) matrix.
Moreover, the query/key/values in Eq. (7) indeed are from the multi-headed
self-attention mechanism of the transformer architecture. In our work, we
perform attention-based aggregation across time in our time-varying covariate
features described in Section 3.3.2. Moreover, the attention mechanism is
particularly adept at capturing and emphasizing the interrelations in a
patient’s historical events. Moreover, Layer Normalization acts to stabilize
the model’s activations, whereas the Feed-Forward Network (FFN) introduces
necessary non-linearity, as formalized in Eq. (7). The intermediary
representation, $\bm{x}^{\prime\prime\prime}_{1}$, can be viewed as an
enriched perspective of a patient’s medical history, vital for subsequent
survival analysis tasks. Once processed through the encoder layers, the final
output is represented by $\bm{x}^{\prime\prime\prime}_{2}$, which encapsulates
the combined effects of the initial embedding, attention mechanism, and the
FFN transformations.

####  3.3.3 Pooling and Feature Extraction

We employ global average pooling to aggregate the temporal dimension. This is
then projected into an $N$-dimensional feature vector, aligning it with the
SurvTrace input defined as numerical input:

$\displaystyle
y=F(Gl(\bm{x}_{2}^{\prime\prime\prime}))=[f_{1},f_{2},f_{3},\ldots,f_{N}]$

Where $Gl$ denotes the global average pooling function, which essentially
reduces the spatial dimensions of the input by computing the average over the
entire feature map. $F$ represents the feed-forward transfer function,
typically introducing non-linearity and transforming the data for subsequent
processing. In addition, originally sourced from individual patient records,
the data has now been distilled into $N$ salient features. This dimensionality
reduction ensures computational efficiency and captures the most informative
patterns from the patient records.

###  3.4 Modified SurvTrace Module

In SurvTrace Wang and Sun (2022), we have modified its architecture to
transition from an initial dual-type input (both numerical and categorical) to
exclusively accepting our model’s embedding output. This enhancement leverages
the Transformer architecture, facilitating not only the management of static
covariates as seen in the traditional SurvTrace but also dealing with time-
varying covariates data, which contain more meaningful information that can
bolster prediction accuracy. In addition, while retaining the beneficial
features of the original SurvTrace, our model demonstrates enhanced
performance and yields improved results compared to its predecessor.

Moreover, by integrating our method into SurvTrace, we have the capability to
enhance its existing loss functions, as detailed as follows:

$\mathcal{L}=\mathcal{L}_{\text{IPS}}+\gamma_{1}\mathcal{L}_{\text{MP}}+\gamma_{2}\mathcal{L}_{\text{LS}}.$

where ${L}_{LS}$, ${L}_{MP}$ and ${L}_{IPS}$ is the loss for length-of-stay,
mortality, and leverage the inverse propensity score, respectively. Two hyper-
parameters, $\gamma_{1}$ and $\gamma_{2}$, can initially be set to 1 and
subsequently annealed during training.

Table 1: Descriptive statistics of three public medical datasets. Dataset | Events (%) | Censored (%) | Covariates | Event Duration | Censoring Time
---|---|---|---|---|---
|  |  | (num., cat.) | min | max | mean | min | max | mean
METABRIC | 57.9 | 42.1 | 5, 4 | 0.1 | 355.2 | 99.9 | 0 | 337 | 159.5
SUPPORT | 68.0 | 32.0 | 8, 6 | 3 | 1944 | 205.4 | 344 | 2029 | 1059.8
PBC2 | 44.87 | 55.12 | 8, 7 | 41 | 5071 | 2219 | 533 | 5222 | 3368

##  4 Experiments

In this section, we detail experiments that are aimed at showing the
following:

  1. 1.

Our proposed method “SurvTimeSurvival” achieves performance that exceeds state
of the art approaches on both covariates and time-varying covariates datasets.

  2. 2.

We provide experimental evidence that the ability to utilise time-varying
covariates data within Transformer architectures results in improved
predictions of survival curves.

  3. 3.

We also show the contribution of the inclusion of synthetic data to our
learning process in obtaining the final results for our novel method.

###  4.1 Environment Configuration

In our experimental framework, we employed the Adam optimization algorithm
Kingma and Ba (2014). Our module was architectured to yield a vector of
dimensions ranging from 15 to 30 features, which subsequently served as input
to the SurvTrace model Wang and Sun (2022). For hyper-parameter tuning, we
calibrated learning rates between $1\times 10^{-4}$ and $1\times 10^{-3}$,
weight decay from $1\times 10^{-3}$ to $0$, transformer layer depths of 2 to
4, embedding dimensions set at 16, intermediate layers of sizes 32 and 64, and
evaluated multi-head attention configurations with heads numbering 1, 2, and
4.

Both the cause-specific and task-specific subnetworks were structured as
multi-layer perceptrons (MLPs), encompassing one or two layers. They were
dimensionally harmonized with the primary transformers. The ReLU activation
functions schmidt2020nonparametric were integrated, aligning with the
intrinsic design of the SurvTrace model.

###  4.2 Dataset Setup

Our study analyzes the event using three different public medical time-varying
covariates/ covariates dataset. With covariates data, Study to Understand
Prognoses Preferences Outcomes and Risks of Treatment(SUPPORT2) Knaus et al.
(1995) and Molecular Taxonomy of Breast Cancer International Consortium
(Metabric) Curtis et al. (2012) dataset from the Pycox library Kvamme and
Borgan (2019) is used. For time-varying covariates data, we employ the Mayo
Clinic Primary Biliary Cirrhosis (PBC2) dataset Lindor et al. (1996) from the
Auton library Nagpal et al. (2021). Also, our data preparation steps lean
heavily not only on our proposed method (Section 3.2) but also on tools from
the Auton library Nagpal et al. (2021). The statistics of our experimented
datasets are available in Table 1.

Regarding synthetic data generation in training/ validation, for SUPPORT2
Knaus et al. (1995) and Metabric Curtis et al. (2012) covariates datasets, we
employ ’survival_gan’ Qian et al. (2023); Norcliffe et al. (2023) approach.
The ’time_gan’ module Yoon et al. (2019); Norcliffe et al. (2023) is employed
for training and generating the data for time-varying covariates synthetic
data.

Regarding the proportion of data for training/validating and generating, for
the covariates datasets, we adopt a strategy wherein 80% of the original data
is used for training and subsequent synthetic data generation, drawing
inspiration from the methodology delineated in Gowal et al. (2021). When
addressing the time-varying covariates, PBC2, we generate 799 synthetic
entries pertinent to 188 patients employing the ’time_gan’ model Yoon et al.
(2019). This corresponds to 50% of the training dataset. The rationale behind
this particular proportion for the time-varying covariates dataset is to
encapsulate half of the meaningful temporal patterns, thus facilitating an
exploration into the model’s adaptability and sensitivity to such intricate
information dynamics.

###  4.3 Baselines & Evaluation Metrics

To assess the efficacy of our proposed method, we conducted benchmark
comparisons against state-of-the-art models, including DeepSurv Katzman et al.
(2018), Deep-Hit Lee et al. (2018), Dynamic Deep-Hit Lee et al. (2019), and
SurvTrace Wang and Sun (2022). For a fair comparison, we obtained the
implementation of these methods from their respective authors and applied them
to our training and test datasets. In order to analyze the contribution of
synthetic data use in our method, we also perform experiments with and without
their inclusion.

We also employed five-fold cross-validation (CV) for a comprehensive
evaluation, reporting metrics as the mean values, ensuring precision and
uniformity in the comparative analysis. Furthermore, for the $k$-th event
evaluation, we employed the time-dependent Concordance index $C_{\text{td}}$
and Brier score:

$\displaystyle C_{\text{td}}(\tau,k)$
$\displaystyle=\Pr\left\\{S_{k}(\tau|\bm{x}_{i})>S_{k}(\tau|\bm{x}_{j})\mid
e_{i}\right.$ (9)
$\displaystyle\quad\left.=k,t_{i}<t_{j},t_{i}\leq\tau,k>0\right\\},$

Figure 2: Means of $C_{td}$ on medical datasets with/without synthetic data on SurvTimeSurvival (CV $K$=5) Table 2: Means of $C_{td}$ for different models on covariates datasets (CV $K=5$); The means of standard deviation on five runs shown in the bracket. Approaches | SUPPORT2 | METABRIC
---|---|---
| 0.25Q | 0.5Q | 0.75Q | 0.25Q | 0.5Q | 0.75Q
DeepSurv | 0.60(0.015) | 0.57(0.011) | 0.59(0.007) | 0.66(0.019) | 0.64(0.025) | 0.64(0.022)
Deep-Hit | 0.62(0.011) | 0.57(0.010) | 0.55(0.012) | 0.70(0.028) | 0.65(0.023) | 0.59(0.023)
Dynamic Deep-Hit | 0.63(0.009) | 0.58(0.010) | 0.55(0.010) | 0.71(0.021) | 0.65(0.015) | 0.61(0.016)
SurvTrace | 0.65(0.010) | 0.62(0.009) | 0.59(0.011) | 0.72(0.023) | 0.71(0.020) | 0.66(0.019)
Ours | 0.74(0.009) | 0.71(0.011) | 0.70(0.011) | 0.80(0.019) | 0.78(0.015) | 0.75(0.015)
Table 3: Means of $C_{td}$ and Brier score across models on PBC2 time-varying covariates dataset (CV $K=5$); The means of standard deviation on five runs shown in the bracket.  Approaches | Concordance Index | Brier Score
---|---|---
0.25Q | 0.5Q | 0.75Q | 0.25Q | 0.5Q | 0.75Q
DeepSurv | 0.56(0.020) | 0.54(0.026) | 0.55(0.018) | 0.163(0.002) | 0.312(0.004) | 0.322(0.004)
Deep-Hit | 0.59(0.030) | 0.57(0.026) | 0.57(0.024) | 0.127(0.002) | 0.296(0.003) | 0.331(0.003)
Dynamic Deep-Hit | 0.69(0.010) | 0.65(0.009) | 0.64(0.008) | 0.061(0.002) | 0.211(0.003) | 0.223(0.003)
SurvTrace | 0.69(0.015) | 0.64(0.017) | 0.64(0.012) | 0.058(0.002) | 0.210(0.002) | 0.212(0.002)
Ours - W/o $G$ | 0.73(0.012) | 0.76(0.010) | 0.80(0.006) | 0.054(0.001) | 0.139(0.002) | 0.189(0.002)
Ours | 0.77(0.010) | 0.77(0.009) | 0.80(0.005) | 0.051(0.001) | 0.135(0.002) | 0.189(0.001)

Brier Score $\displaystyle=\frac{1}{N}\sum_{i=1}^{N}(f_{i}-o_{i})^{2}.$ (10)

From (9), $S_{k}(t|x_{i})$ signifies the survival function for $k$-th event at
time $\tau$. Adjustments were made using IPCW Uno et al. (2011), and
consistent with Nagpal et al. (2021), reported $C_{\text{td}}$ at the 25%,
50%, 75% quantiles. From (10), Brier score with $N$ predictions, forecasted
probability $f_{i}$, and actual outcome $o_{i}$, the score ranges from 0
(perfect) to 1 (worst), reflecting the squared discrepancy between forecasts
and outcomes.

Regarding the experimentation on methods not inherently designed for handling
time-varying covariates data Wang and Sun (2022); Katzman et al. (2018); Lee
et al. (2018), we transformed the dataset into a covariates-only dataset. By
testing their proposed methods, we highlight the advantages of addressing
time-varying covariates over covariates data.

###  4.4 Experiment Results

The experimental results in terms of $C_{td}$ values comparing our method
“SurvTimeSurvival” against SOTA approaches can be seen in Tables 2 & 3 for the
covariates and time-varying covariates datasets respectively.

It can be seen that our methods have performances that exceed every method
that we compare against across all datasets. In the SUPPORT2 dataset, our
concordance indices surpassed those of the SurvTrace method by margins of
0.09, 0.09, and 0.11 for the 0.25, 0.5, and 0.75 quantiles, respectively.
Similarly, for the Metabric dataset, we observed improvements of 0.08, 0.07,
and 0.09 across the corresponding quantiles, as described in Table 4.
Additionally, compared with SurvTrace, SurvTimeSurvival exhibits advanced
capabilities by generating synthetic data and managing time-varying covariates
efficiently, highlighting its broad adaptability.

For the PBC2 dataset (Table 3), our method also obtains the highest
concordance index values of 0.77, 0.77, and 0.80 across quantiles 0.25, 0.5,
and 0.75, respectively. This is an improvement over the next highest performer
of Dynamic Deep-Hit of 0.08, 0.12, and 0.16, respectively. Furthermore,
considering the Brier Score—a metric to measure the accuracy of probabilistic
predictions—our method consistently exhibits commendable results.
Specifically, at the 0.25 quantile, our model yielded a score of 0.051, which
declined to 0.135 at the 0.5 quantile and remained stable at 0.189 for the
0.75 quantile. Compared with other methods, these scores clearly underscore
our approach’s efficacy and robustness in predicting survival outcomes,
especially compared to the benchmark techniques listed.

####  4.4.1 Importance of Time-Varying Covariates and Transformers

Table 3 shows that explicit use of time-varying covariates data can improve
prediction accuracy instead of treating each time visit in patient records as
discrete. This observation is further supported when contrasting our method
with the SurvTrace Wang and Sun (2022) model when it deals only with
covariates data. By capitalizing on the strengths of the Transformer
architecture, both our and SurvTrace models register improved performance
metrics. Notably, our method outstrips SurvTrace by margins of 0.08, 0.13, and
0.16 in the 0.25, 0.5, and 0.75 quantiles, respectively, as evidenced by the
Concordance Index since applying time-varying covariates dataset. Moreover, we
also instigated a comparison with Dynamic Deep-Hit Lee et al. (2019) and
recognized that the Transformer architecture has more advantages than the
LSTM.

####  4.4.2 Contribution of Synthetic Data

Table 3 presents the Concordance Index ($C_{td}$) comparison of various
survival prediction methodologies on the PBC2 dataset. Notwithstanding the
absence of synthetic data (w/o $G$), our method, SurvTimeSurvival, manifests
remarkable performance when benchmarked against methods like Katzman et al.
(2018); Lee et al. (2018, 2019); Wang and Sun (2022). Remarkably,
incorporating synthetic data during the training phase augments the predictive
accuracy of SurvTimeSurvival. At specified quantiles of 0.25, 0.5, 0.75,
SurvTimeSurvival enhanced its $C_{td}$ scores to 0.77, 0.77, and 0.80,
respectively, after including the synthetic data. The contribution of
synthetic data use in our method can be seen in Figure 2. We can see an
increase in the $C_{td}$ values in all datasets across all quantiles.
Therefore, this experiment highlights the importance of using synthetic data
in training, improving accuracy, and potentially addressing situations with
limited data due to privacy and technical challenges.

Description | SurvTrace | Ours
---|---|---
Apply synthetic data |  | $\checkmark$
Dealing w/ ”cov” data | $\checkmark$ | $\checkmark$
Dealing w/ ”time-cov” data |  | $\checkmark$
Dealing w/ multiple events | $\checkmark$ | $\checkmark$
Predict survival, risk, hazard | $\checkmark$ | $\checkmark$
Table 4: Comparison between SurvTrace & Our methodology

##  5 Conclusion

In conclusion, the SurvTimeSurvival methodology advances survival analysis by
handling both time-varying covariates and covariates data and integrating data
synthesis for better accuracy. Building upon the strengths of the Transformer
architecture and integrating features from the SurvTrace model, our approach
outclasses earlier strategies in precision. It bridges the analytical divide
between different data types, promising significant implications not only for
healthcare research but also for the engineering and economics domains. In
comparison, we find the next highest performing method of SurvTrace only
contains a subset of the above capabilities (Table 4). Future directions
include integrating knowledge distillation for even greater accuracy.

## References

  * Bland and Altman (1998) J Martin Bland and Douglas G Altman.  Survival probabilities (the kaplan-meier method).  _Bmj_ , 317(7172):1572–1580, 1998.
  * Box-Steffensmeier et al. (2015) Janet M Box-Steffensmeier, Raphael C Cunha, Roumen A Varbanov, Yee Shwen Hoh, Margaret L Knisley, and Mary Alice Holmes.  Survival analysis of faculty retention and promotion in the social sciences by gender.  _PloS one_ , 10(11):e0143093, 2015.
  * Cox (1972) David R Cox.  Regression models and life-tables.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 34(2):187–202, 1972.
  * Creswell et al. (2018) Antonia Creswell, Tom White, Vincent Dumoulin, Kai Arulkumaran, Biswa Sengupta, and Anil A Bharath.  Generative adversarial networks: An overview.  _IEEE signal processing magazine_ , 35(1):53–65, 2018.
  * Curtis et al. (2012) Christina Curtis, Sohrab P Shah, Suet-Feung Chin, Gulisa Turashvili, Oscar M Rueda, Mark J Dunning, Doug Speed, Andy G Lynch, Shamith Samarajiwa, Yinyin Yuan, et al.  The genomic and transcriptomic architecture of 2,000 breast tumours reveals novel subgroups.  _Nature_ , 486(7403):346–352, 2012.
  * Davidson-Pilon (2019) Cameron Davidson-Pilon.  lifelines: survival analysis in python.  _Journal of Open Source Software_ , 4(40):1317, 2019.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Friedman et al. (2015) Lawrence M Friedman, Curt D Furberg, David L DeMets, David M Reboussin, and Christopher B Granger.  _Fundamentals of clinical trials_.  Springer, 2015.
  * Gowal et al. (2021) Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A Mann.  Improving robustness using generated data.  _Advances in Neural Information Processing Systems_ , 34:4218–4233, 2021.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Hu et al. (2021) Shi Hu, Egill Fridgeirsson, Guido van Wingen, and Max Welling.  Transformer-based deep survival analysis.  In _Survival Prediction-Algorithms, Challenges and Applications_ , pages 132–148. PMLR, 2021.
  * Katzman et al. (2018) Jared L Katzman, Uri Shaham, Alexander Cloninger, Jonathan Bates, Tingting Jiang, and Yuval Kluger.  Deepsurv: personalized treatment recommender system using a cox proportional hazards deep neural network.  _BMC medical research methodology_ , 18(1):1–12, 2018.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Knaus et al. (1995) William A Knaus, Frank E Harrell, Joanne Lynn, Lee Goldman, Russell S Phillips, Alfred F Connors, Neal V Dawson, William J Fulkerson, Robert M Califf, Norman Desbiens, et al.  The support prognostic model: Objective estimates of survival for seriously ill hospitalized adults.  _Annals of internal medicine_ , 122(3):191–203, 1995.
  * Kvamme and Borgan (2019) Håvard Kvamme and Ørnulf Borgan.  Continuous and discrete-time survival prediction with neural networks.  _arXiv preprint arXiv:1910.06724_ , 2019.
  * Lee et al. (2018) Changhee Lee, William Zame, Jinsung Yoon, and Mihaela Van Der Schaar.  Deephit: A deep learning approach to survival analysis with competing risks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32, 2018.
  * Lee et al. (2019) Changhee Lee, Jinsung Yoon, and Mihaela Van Der Schaar.  Dynamic-deephit: A deep learning approach for dynamic survival analysis with competing risks based on longitudinal data.  _IEEE Transactions on Biomedical Engineering_ , 67(1):122–133, 2019.
  * Lindor et al. (1996) KEITH D Lindor, TERRY M Therneau, ROBERTA A Jorgensen, MICHAEL Malinchoc, and E ROLLAND Dickson.  Effects of ursodeoxycholic acid on survival in patients with primary biliary cirrhosis.  _Gastroenterology_ , 110(5):1515–1518, 1996.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Lu et al. (2023) Yingzhou Lu, Huazheng Wang, and Wenqi Wei.  Machine learning for synthetic data generation: a review.  _arXiv preprint arXiv:2302.04062_ , 2023.
  * Nagpal et al. (2021) Chirag Nagpal, Xinyu Li, and Artur Dubrawski.  Deep survival machines: Fully parametric survival regression and representation learning for censored data with competing risks.  _IEEE Journal of Biomedical and Health Informatics_ , 25(8):3163–3175, 2021.
  * Norcliffe et al. (2023) Alexander Norcliffe, Bogdan Cebere, Fergus Imrie, Pietro Lio, and Mihaela van der Schaar.  Survivalgan: Generating time-to-event data for survival analysis.  In _International Conference on Artificial Intelligence and Statistics_ , pages 10279–10304. PMLR, 2023.
  * Pourjafari et al. (2022) Ebrahim Pourjafari, Navid Ziaei, Mohammad R Rezaei, Amir Sameizadeh, Mohammad Shafiee, Mohammad Alavinia, Mansour Abolghasemian, and Nick Sajadi.  Survival seq2seq: A survival model based on sequence to sequence architecture.  In _Machine Learning for Healthcare Conference_ , pages 79–100. PMLR, 2022.
  * Qian et al. (2023) Zhaozhi Qian, Bogdan-Constantin Cebere, and Mihaela van der Schaar.  Synthcity: facilitating innovative use cases of synthetic data in different data modalities.  _arXiv preprint arXiv:2301.07573_ , 2023.
  * Schmidt (2019) Robin M Schmidt.  Recurrent neural networks (rnns): A gentle introduction and overview.  _arXiv preprint arXiv:1912.05911_ , 2019.
  * Uno et al. (2011) Hajime Uno, Tianxi Cai, Michael J Pencina, Ralph B D’Agostino, and Lee-Jen Wei.  On the c-statistics for evaluating overall adequacy of risk prediction procedures with censored survival data.  _Statistics in medicine_ , 30(10):1105–1117, 2011\.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang and Sun (2022) Zifeng Wang and Jimeng Sun.  Survtrace: Transformers for survival analysis with competing events.  In _Proceedings of the 13th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics_ , pages 1–9, 2022\.
  * Xu et al. (2019) Lei Xu, Maria Skoularidou, Alfredo Cuesta-Infante, and Kalyan Veeramachaneni.  Modeling tabular data using conditional gan.  _Advances in neural information processing systems_ , 32, 2019.
  * Yoon et al. (2019) Jinsung Yoon, Daniel Jarrett, and Mihaela Van der Schaar.  Time-series generative adversarial networks.  _Advances in neural information processing systems_ , 32, 2019.
  * Zhao et al. (2020) Jingyu Zhao, Feiqing Huang, Jia Lv, Yanjie Duan, Zhen Qin, Guodong Li, and Guangjian Tian.  Do rnn and lstm have long memory?  In _International Conference on Machine Learning_ , pages 11365–11375. PMLR, 2020.


# Nearly-Optimal Consensus Tolerating Adaptive Omissions:
Why is a Lot of Randomness Needed?

Mohammad T. Hajiaghayi
University of Maryland, Maryland, USA  Dariusz R. Kowalski
School of Computer and Cyber Sciences, Augusta University, Georgia, USA  Jan
Olkowski
University of Maryland, Maryland, USA.

###### Abstract

We study the complexity of the problem of reaching agreement in a synchronous
distributed system, also called consensus, by $n$ autonomous parties, when the
communication links from/to faulty parties can omit messages. The faulty
parties are selected and controlled by an adaptive, full-information,
computationally unbounded adversary. We design a randomized algorithm that
works in $O\left(\sqrt{n}\log^{2}n\right)$ rounds and sends
$O\left(n^{2}\log^{3}n\right)$ total number of communication bits, where the
number of faulty parties can be $\Theta(n)$. When the number of faulty parties
is linear in $n$, our result is simultaneously tight for both these measures
within polylogarithmic factors: due to the $\Omega(n^{2})$ lower bound on the
number of messages send by any Monte Carlo solution, by Abraham et al.
(PODC’19), and due to the $\Omega(\sqrt{n/\log{n}})$ lower bound on the number
of rounds of any Las Vegas solution by Bar-Joseph and Ben-Or (PODC’98).
Thereby, this work settles the landscape of the consensus problem in the
omission failures model, which stood as an open question since the work of
Dolev and Strong (SICOMP’83).

Additionally, we strictly quantify how much randomness is necessary and
sufficient to reduce time complexity to a certain value, while keeping the
communication complexity optimal wrt to polylogarithmic factors. We prove that
no Monte Carlo algorithm can work in less than
$\Omega\left(\frac{n^{2}}{\max\\{R,n\\}\log{n}}\right)$ rounds if it uses less
than $O(R)$ calls to a random source, assuming a constant fraction of all
parties is faulty. This result should be contrasted with a long line of work
on consensus algorithms against an adversary limited to polynomial computation
time, thus unable to break cryptographic primitives, culminating in a work by
Ghinea et al. (EUROCRYPT’22), where an optimal $O(r)$-round solution reaching
consensus with probability $1-(cr)^{-r}$ is given. Our lower bound strictly
separates these two regimes, by excluding such results if the adversary is
computationally unbounded.

On the upper bound side, we show that for
$R\in\tilde{\mathcal{O}}\left(n^{3/2}\right)$ there exists a randomized
algorithm solving consensus in
$\tilde{\mathcal{O}}\left(\frac{n^{2}}{R}\right)$ rounds, with probability
polynomially close to $1$ (whp), where tilde notation hides a poly-logarithmic
factor. The communication complexity of the algorithm does not depend on the
amount of randomness $R$ and stays (universally) optimal within
polylogarithmic factors. As a consequence, we give a spectrum of solutions
that interpolates between optimal results in the deterministic regime ($R\in
O(n)$; $O(1)$ entropy per party) and the randomized regime ($R\in O(n^{3/2})$
random bits).

##  1 Introduction

In any distributed system, reaching agreement (consensus) is essential for
coordinating actions of the participating $n$ parties (also called processes),
out of which up to $t$ could be faulty. The hardness of the task primarily
depends on the type of fault present in the system. The classical hierarchies
[Attiya-Welch-book2004, Lynch-book96] for synchronous message-passing models
distinguish the following types of faults, in the order of increasing
hardness: crash failures, omission failures, authenticated Byzantine failures,
and Byzantine failures. In this work, we focus on the second type of failures
in this list, the omission failures. Precisely, we assume that a
computationally unbounded and malicious adversary can observe the system
during the computation and omit an arbitrary subset of messages send to /
received from selected faulty processes in an online, adaptive fashion. The
adversary can also, based on the history of the computation, corrupt new
processes if the number of corrupted stays within a fixed limit $t$. The
adversary, however, cannot see the future random bits.

Despite of huge volume of research on the performance of consensus algorithms,
the proper assessment of the hardness of consensus under this type of failure
has been elusive. There is no theoretical evidence that omissions failures are
weaker than the next model in the hierarchy, authenticated Byzantine, even if
such a hypothesis seems compelling. Compared to the weaker model of crash
failures, there is a strict hardness barrier following from the existence of
an algorithm using $O(n^{3/2}\log^{13/2}{n})$ messages by Hajiaghayi et al.
[DBLP:conf/stoc/HajiaghayiKO22] (STOC’22) in the case of crash failures and
the $\Omega(n^{2})$ lower bound on the number of messages in the model with
omission failures, proved by Dolev and Reishuk [DolevR85] (JACM’85) for
deterministic solutions and by Abraham et al. [AbrahamCDNPRS19] (PODC’19) for
the randomized ones, all results assuming $\Theta(n)$ faulty parties. However,
if the space of solutions is categorized based on the round complexity of a
solution, even for these two models (i.e., crashes and omissions) the picture
is not clear. Both models admit an $\Omega(\sqrt{n/\log{n}})$ lower bound for
Las Vegas solutions, due to the work of Bar-Joseph and Ben-Or [Bar-JosephB98]
(PODC’98) (when the number of faulty parties is linear in the system size). In
the case of crashes, the lower bound is matched by an algorithm of the same
authors [Bar-JosephB98], while in the case of omissions – the best previous
solution is 40 years old result of Dolev and Strong [DolevS83] (SICOMP’83)
that works in $O(n)$ rounds! Hence, our first goal is to fully understand the
hardness of omission failures in reaching consensus:
Question 1: Is there a consensus algorithm, possibly randomized, that at the
same time matches both lower bounds with respect to poly-logarithmic factor?
That is, is there an algorithm that solves consensus in $\tilde{O}(\sqrt{n})$
rounds with $\tilde{O}(n^{2})$ total number of sent communication bits even if
a linear number of omission failures occur in the network?

We answer this question affirmatively and give a new algorithm that is almost-
optimal111In this work, almost-optimal means optimal within a poly-logarithmic
factor. with respect to, simultaneously, the number of rounds and the total
number of sent communication bits when the number of faults is $\Theta(n)$.

Then, we focus on the aspect of how much randomness is necessary to break the
$\Omega(n)$ lower bound on the number of rounds for deterministic solutions
[FischerL82] (again, assuming $\Theta(n)$ faults):
Question 2: What is the impact of the amount of randomness available at
processes on the efficiency of consensus algorithms? In particular, could
pseudo-random generators be used efficiently?

We quantify the number of random bits that is sufficient and necessary to
achieve a given time $\in\tilde{\Omega}(\sqrt{n})$222We use tilde notation to
hide a polylogarithmic factor., while keeping almost-optimal communication
complexity. In particular, we prove that using pseudo-random generators with
small seeds may delay reaching consensus nearly quadratically, which may have
severe consequences in distributed ledger implementations and distributed
database applications based on consensus. Even more interestingly, our lower
bounds apply to Monte Carlo algorithms. This makes a surprising distinction
between a parallel line of work on consensus protocols in the case of
authenticated Byzantine failures governed by a computationally-bounded
adversary [abraham2019synchronous, fitzi2003efficient, ghinea2022round,
katz2006expected], done by the cryptography community. In this model, the
adversary is still adaptive, but the algorithm has a trusted setup for unique
threshold signatures and an unforgeable public-key infrastructure; thus, the
view of the adversary is limited to the history of the faulty processes and
all messages send to them. Nevertheless, the adversary can adaptively corrupt
new parties based on its view and has the priority over messages being
delivered in the round it corrupts. In this setting, the result of Ghinea et
al. [ghinea2022round] (EUROCRYPT’22) shows an algorithm that terminates in $r$
rounds with probability at least $1-cr^{-r}$, for any $r$ and some absolute
constant $c>0$. Our lower bound excludes such results in the model with a
computationally unbounded adversary, showing that not only many random bits
but also strong cryptography could be necessary for some applications of
consensus protocols.

### Summary of results and the paper structure.

As mentioned earlier, we focus on the classical message-passing model in which
processes are autonomous, synchronous and can exchange messages via point-to-
point communication channels. The adversary corrupts and controls at most $t$
processes, causes omission failures at them, and is (full-information)
strongly adaptive. In Sections 3, LABEL:sec:overview-lower and
LABEL:sec:overview-randomness, we present an extended overview of the three
main results and novel techniques obtained in this work; for the sake of
overview, we typically assume $t=\Theta(n)$. A summary of them can be found in
Table 1. In Section LABEL:sec:related we discuss the related work in more
details. Section 2 presents detail formal description of the model. Sections
LABEL:sec:main-algo, LABEL:sec:proof-lower and LABEL:sec:tradeoff-upper
contain the full and formal analysis of our main results. Section
LABEL:sec:future states major research directions opened by our work.

| result | time | comm. bits | random bits | comments
---|---|---|---|---|---
algo- | Thm 1 | $O\left(\sqrt{n}\log^{2}{n}\right)$ | $O(n^{2}\log^{3}n)$ | $O\left(n^{3/2}\log^{2}{n}\right)$ |
rithms | Thm LABEL:thm:trade-off-res | $O\left(\frac{n^{2}}{R}\log^{2}{n}\right)$ | $O\left(n^{2}\log^{5}{n}\right)$ | $O\left(R\log^{2}{n}\right)$ | $\forall R\in O\left(n^{3/2}\right)$
lower | [Bar-JosephB98] | $\Omega\left(\frac{t}{\sqrt{n\log n}}\right)$ | - | - | correct prob. $=1$
bounds | [AbrahamCDNPRS19] | - | $\Omega\left(\epsilon t^{2}\right)$ | - | correct prob. $\geq\frac{3}{4}+\epsilon$
| Thm LABEL:thm:lower-randomness-res | $T$ | - | $R$ | $T\times(R+T)=\Omega\left(\frac{t^{2}}{\log{n}}\right)$
|  |  |  |  | correct prob. $\geq 1-\frac{1}{n^{3/2}}$
Table 1: Our main results presented for three metrics: time complexity, total
number of used communication bits and total number of used random bits. All
our algorithms are subject to their complexity bounds whp, i.e., with
probability polynomially close to $1$, see Section 2. $T$ and $R$ are random
variables denoting, respectively, the number of rounds and the cumulative
number of random bits used by all processes in a run of an algorithm. The
“correct prob.” denotes the probability of correctness of the class of
algorithms to which the lower bound applies. The new results are underlined in
column “result”. Extended versions of Theorems 1 and LABEL:thm:trade-off-res,
with explicit dependency on the parameter $t$, are given in Sections
LABEL:sec:main-algo and LABEL:sec:tradeoff-upper, resp.

##  2 Model Details and Definitions

We consider the classical synchronous message-passing distributed system with
omission faults, cf., [Attiya-Welch-book2004, Lynch-book96,
raipin2010strongly]. The system contains $n$ processes, also called parties.
Each process has a unique ID in $\mathcal{P}=[n]=\\{1,\ldots,n\\}$. For
simplicity, we will use $p$ to refer to a process with ID $p\in\mathcal{P}$.
Both $\mathcal{P}$ and $n$ are known to all process. Processes operate in
synchronized rounds. Without loss of generality,333See [Attiya-Welch-book2004,
Bar-JosephB98] for the discussion on generality of our assumptions and related
settings – crash and Byzantine faults. we assume that each round consists of
the following two phases:

  1. 1.

Local computation phase: Each process performs a local computation (i.e.,
autonomously from other processes) in order to change its state. The
computation can be any function of the current state, of all messages received
prior to this phase, and of a sequence of uniformly distributed and
independent random bits of an arbitrary, but finite, length that can be
reached by a process at the beginning of the phase. More precisely, for the
last parameter of the function, we assume that there exists a random source
that, when called, can provide a process and its state-changing function with
a 0-1 sequence, of requested length, containing uniform and independent
distributed random bits.

  2. 2.

Communication phase: During this phase, each process can send messages to any
other processes in the system. The content of a message is a function of the
current state computed in the preceding local computation phase, and is not
limited by the model. In particular, the length and content of messages is not
restricted by the model, although our algorithms are designed in a way to use
short messages. Each message sent is delivered to its destination at the end
of the same phase, and is ready to be processed in the next round, unless an
omission failure occurs.

### Processes’ omission failures and adversaries.

Not all processes are reliable. Up to some $t=O(n)$ processes may become
(omission) faulty during the execution – once a process becomes faulty, it
stays faulty through the end of computation and some of its incoming/outgoing
messages could be lost. We assume that $t$ is a part of the problem input and
thus known up-front to all processes. The decision which process becomes
faulty and when, as well as the control over the faulty processes, is governed
by an adversary. We consider an adaptive full-power full-information adversary
that

  * •

has unlimited computational power, knows the algorithm and input parameters
and can see the states (and thus also the current random bits used) of all
processes, as well as the content of all arriving messages, at any time, and

  * •

can select online which (non-faulty) processes to fail and when, and with
respect to faulty processes – it can omit any subset of messages
incoming/outgoing to/from the faulty processes (i.e., such messages are not
delivered to their destinations, having the same effect as no message sent).

Consequently, an adversarial strategy is a deterministic function, which
assigns to each possible history that may occur in any execution some
adversarial action for the subsequent phase of the execution, i.e., which
processes to fail in that phase and in which moment and which messages sent
by/to them would reach their destinations. Note, that in the above definition,
the adversary has flexibility to adapt its actions between any two phases of
the algorithm (not only between consecutive rounds). In the remainder, we will
be referring to this adversary simply by adaptive adversary.

We remark that crash failures of processes can be viewed as omission failures
– the adversary simply bans all their incoming and outgoing messages after the
failure round (while in the round of a crash, the adversary could allow any
subset of outgoing messages to reach their destinations).444In case of
crashes, incoming messages are not relevant, because the faulty process could
not influence correct processes any more and it is not required from them to
satisfy any of the consensus properties.

### Consensus problem.

A randomized algorithm for processes $\mathcal{P}=\\{1,\ldots,n\\}$, where
each process $p\in\mathcal{P}$ holds initial input $b_{p}\in\\{0,1\\}$, is a
consensus protocol tolerating $t$ faulty processes if all the three following
conditions hold with probability $1$ in the presence of an adaptive adversary
failing/controlling at most $t$ processes:

Agreement. All non-faulty processes output the same value.

Validity. If all non-faulty processes begin with the same input value $b$,
then all of them output $b$.

Termination. Non-faulty processes have to decide and terminate.

Consider a randomized consensus algorithm against a fixed adversarial
strategy. The following metrics determine the quality of the execution against
that strategy:

  * •

_Time of an execution_ of the algorithm is defined as the smallest number
$\tau_{1}$ such that the number of rounds that occur by termination of the
last non-faulty process is at most $\tau_{1}$;

  * •

_The number of communication bits in an execution_ of the algorithm is the
smallest number $\tau_{2}$ such that the total number of bits sent by all
processes in point-to-point messages by termination of the last non-faulty
process is at most $\tau_{2}$;

  * •

_Randomness of an execution_ of the algorithm is defined as the smallest
number $\tau_{3}$ such that the number of (independent and uniform) random
bits used by all processes by termination of the last non-faulty process is at
most $\tau_{3}$; when describing the lower bound result, we abuse the notation
slightly, and define randomness of an execution as the total number of times
when processes access their random sources during the local computation phase.
Complying to the definition of the local computation phase, in each such
access a process can use a sequence of random bits of finite length. Observe
that such definition makes a lower bound result even stronger.

We define time/communication/randomness complexity of a (distributed)
algorithm as a supremum of time, the number of communication bits, and the
number of random bits, respectively, taken over all adversarial
strategies.555Note that the supremum for different measures could be achieved
by sequences of different strategies – nevertheless, each of the complexities
of our solutions is still close to optimal. Finally,
time/communication/randomness complexity of a distributed problem is an
infimum of all algorithms’ time/communication/randomness complexities,
respectively. In our paper, we are interested in studying almost-optimal
solutions, i.e., optimal within a polylogarithmic factor, wrt the
abovementioned complexities. The bounds on the complexities should hold with
high probability. We say that a random event occurs _with high probability_
(whp for short), if its probability could be made $1-O(n^{-c})$ for any
positive constant $c$ by linear scaling of parameters of the considered random
process.666We would like to note that, after ignoring polylogarithimic
factors, all our upper bounds hold with the same asymptotic complexities in
even stronger regime where the probabilities are of form $1-O(n^{\omega(1)})$.

##  3 Main consensus algorithm

Our first and main result is a new consensus algorithm which is almost-optimal
with respect to time complexity, bit complexity and randomness complexity, if
the number of faulty parties is $\Theta(n)$.

######  Theorem 1.

There is a randomized algorithm solving consensus with probability $1$ against
the adaptive omission adversary that can control $t<\frac{n}{30}$ processes,
which terminates in $O\left(\sqrt{n}\log^{2}{n}\right)$ rounds and uses
$O\big{(}n^{2}\log^{3}n\big{)}$ bits of communication and
$O\left(n\cdot\sqrt{n}\log^{2}{n}\right)$ random bits, whp.

For the ease of presentation, and for the sake of space constraints, in this
section, we assume that $t=\frac{n}{30}-1$ and we provide a more high-level
overview of techniques used to obtain the result. A self-contained and fully
formal derivation of this theorem, incorporating the upper bound $t$ on the
number of faulty processes into the time and communication complexities and
containing all the omitted proofs, is deferred to Appendix LABEL:sec:main-
algo, where the above Theorem is restated as Theorem LABEL:thm:main-algo.

In the case when $t=\Theta(n)$, the almost-optimality of the running time
follows from the $\Omega\left(\sqrt{n/\log{n}}\right)$ lower bound showed in
[Bar-JosephB98]. The almost-optimality of the communication bit complexity is
due to the result of Abraham et al. [AbrahamCDNPRS19] who showed that any
randomized algorithm solving consensus with at least a constant positive
probability against the adaptive omission-causing adversary requires
$\Omega(n^{2})$ messages (each message carries at least one bit). The almost-
optimality of the randomness complexity follows from Theorem LABEL:thm:lower-
randomness-res presented in the later part of the paper. We next give an
overview of the algorithm. The pseudocode can be found in Algorithm 1.

input: $\mathcal{P}$, $p$, $b_{p}$, t

1 $\texttt{operative}_{p}\leftarrow true$, $\texttt{decided}_{p}\leftarrow
false$;

2 $V_{p}\leftarrow$ a set of neighbors of $p$ in a predetermined graph $G$
guaranteed by Theorem LABEL:thm:random-graph-properties;

3 $W_{1},\ldots,W_{\left\lceil\sqrt{n}\right\rceil}\leftarrow$ a pre-defined
partition of $\mathcal{P}$ into $\left\lceil\sqrt{n}\right\rceil$ disjoint
sets of size $\leq\left\lceil\sqrt{n}\right\rceil$ each;

4 let $\ell$ be such that $p\in W_{\ell}$;

5 for  _$\frac{t}{\sqrt{n}}\log n$ epochs_ do

6
$\texttt{g\\_ones}_{p},\texttt{g\\_zeros}_{p},\texttt{operative}_{p}\leftarrow\textsc{GroupBitsAggregation}(W_{\ell},p,\texttt{operative}_{p};b_{p})$;

7 if  _$\texttt{operative}_{p}=false$_ then stay idle until the end of the
epoch;

8

9
$\texttt{ones}_{p},\texttt{zeros}_{p},\texttt{operative}_{p}\leftarrow\textsc{GroupBitsSpreading}(V_{p},p,\ell,\texttt{operative}_{p};\texttt{g\\_ones}_{p},\texttt{g\\_zeros}_{p})$;

10

11 if  _$\texttt{ones}_{p}
>\frac{18}{30}(\texttt{ones}_{p}+\texttt{zeros}_{p})$_ then $b_{p}\leftarrow
1$;

12 else if  _$\texttt{ones}_{p}
<\frac{15}{30}(\texttt{ones}_{p}+\texttt{zeros}_{p})$_ then $b_{p}\leftarrow
0$;

13 else set $b_{p}$ to $0$ or $1$ uniformly at random;

14

15 if  _$\texttt{ones}_{p}
>\frac{27}{30}(\texttt{ones}_{p}+\texttt{zeros}_{p})$ or
$\texttt{ones}_{p}<\frac{3}{30}(\texttt{ones}_{p}+\texttt{zeros}_{p})$_ then
$\texttt{decided}_{p}\leftarrow true$;

16

17 end for

18

19if  _$\texttt{operative}_{p}=true$ and $\texttt{decided}_{p}=true$_ then
send $b_{p}$ to all processes in $\mathcal{P}$;

20 else if  _any message $b_{q}$ received from some process $q$_ then
$b_{p}\leftarrow b_{q}$;

/* in the above, $q$ can be chosen arbitrarily from the received messages */

21 if  _$\texttt{decided}_{p}=true$ or $(\texttt{operative}_{p}=false$ and $p$
received a message in the previous round$)$_ then decide $b_{p}$;

22 else

23 if  _$\texttt{operative}_{p}=true$_ then $p$ participates in the
deterministic synchronous Consensus algorithm given in Theorem 4 in [DolevS83]
with the input bit $b_{p}$; if $p$ reaches agreement in that protocol, it
broadcasts the decision to all processes in $\mathcal{P}$ and it decides on
the algorithm’s decision;

24 else $p$ remains idle until a decision is sent to it; upon receiving a
decision, it decides on this value;

25

26 end if

Algorithm 1 OptimalOmissionsConsensus

### Universal idea: Local and dynamic partitioning of processes into operative
/ inoperative and implementing time- and communication-efficient biased-
majority-voting only by the operative ones.

We introduce a new partitioning of processes into operative and inoperative,
based on the communication received by each process from a certain pre-defined
set of other processes which maintain their operative status (this set may
vary, depending on what procedure is executed – it will be emphasized later).
This partition is not equivalent to the standard classification into faulty /
non-faulty ones. With our partition, we can guarantee that faulty processes
either communicate well enough to contribute to the progress towards a unified
decision (i.e., stay operative) or become excluded from the set of operative
processes, having no impact on the final decision. Our partition also avoid a
major performance problem in omission-tolerant or Byzantine-tolerant
computation – identifying a single faulty process may require at least
quadratic number of messages, cf., [AbrahamCDNPRS19], which makes it fast,
local and incorporated in efficient communication schedules.

Then, we employ the idea of reaching consensus by applying the biased-
majority-voting rule, as proposed in [Bar-JosephB98], but with a novel twist –
only the operative processes implement the vote protocol to agree on a
consensus decision. It uses $O(\sqrt{n}\log{n})$ repetitions of the single
vote subroutine, called epochs in the pseudo-code, see lines 1-1 in Algorithm
1. Each repetition/epoch consists of $O\left(\log n\right)$ rounds of
communication-efficient counting, see the description below), however it
succeeds in unifying the votes only if the number of newly failed processes is
$O(\sqrt{n})$ and only with a constant probability (this is why we need
$O(\sqrt{n}\log{n})$ epochs). Only after the part implementing the biased-
majority-voting rule ends, the operative processes communicate the decision to
the remaining parties. We first describe how we implement a single epoch,
based on two technical advancements, and conclude with more details on how the
overall consensus protocol (based on the biased-majority-voting rule) is
designed.

### An implementation of a single biased-majority-vote subroutine (epoch).

In our case, a single epoch (i.e., a single repetition of the biased-majority-
vote subroutine, lines 1-1) heavily relies on counting, collaboratively by
every operative process, the number of operative processes that have candidate
decision value $0$ and, separately, value $1$. These numbers must be
approximate, up to an additive factor linearly dependent on the number of
processes that become inoperative, as the operative status may change
dynamically – some processes can lose it before the calculation finishes and,
in consequence, their candidate values might not be properly counted by
others. Moreover, this calculation has to consider the fact that some
operative processes can be controlled by adversary, thus it must, regardless,
exploit the property that the operative processes communicate with enough
other processes. A protocol performing this calculation in $O(\log{n})$ rounds
and using $O(n^{3/2}\log^{2}{n})$ communication bits, in total, is the main
technical advancement of this algorithm and we present it next in a form of
two technical advancements.

### Technical advancement 1: $\sqrt{n}$-decomposition into groups and binary-
tree-like intra-group calculations of operative processes for communication
saving.

As mentioned above, there are some inherit difficulties in the omission
failure model that complicate the time- and communication-efficient counting
of the number of candidate values (i.e., votes) $0$ and $1$ among the
operative processes. Here, we present the techniques we use to mitigate them.
We pre-define fixed partition of the set of processes into
$\left\lceil\sqrt{n}\right\rceil$ groups of size
$\left\lfloor\sqrt{n}\right\rfloor$ or $\left\lceil\sqrt{n}\right\rceil$ each
(see line 1 of Algorithm 1 and example in Figure 1), and first require the
operative processes to count the number of operative $0$’s and $1$’s only
within the groups (executed procedure GroupBitsAggregation in line 1). In this
part, we use a virtual sparse data structure on some subsets of processes,
structured into a balanced binary tree, which is used to aggregate the counts.

$W_{1}$$W_{2}$abcde$W_{3}$$W_{4}$$W_{5}$$W_{6}$ Figure 1: A schematic picture
of two different techniques used for communication between processes.
Different colors represent different groups in the $\sqrt{n}$-decomposition of
the processes. The links represent the overlaying communication resembling a
sparse random graph used for exchanging operative counts of different groups.
The choice of links is independent of the $\sqrt{n}$-decomposition.

Vertices of the binary tree correspond to specific subsets of processes in the
group: leaves of the binary tree are singletons in the group, and each vertex
in a higher layer corresponds to the union of the subsets that are already
identified with the children of that vertex in the tree. The root of the
binary tree corresponds to the set of all processes in the group. Processes
calculate the number of operative $0$’s and $1$’s, called operative counts,
starting from the leaves of the tree (i.e., singletons) and then keep moving
up the tree. At each vertex in a higher layer, the processes in the subset
corresponding to that vertex work together to relay and sum up the operative
counts from the lower layer. In this relay-and-aggregation procedure, all
operative processes in the group exchange messages, not only to relay and
aggregate values from children to parents in the virtual tree, but also to
keep track who remains operative in the whole group. More precisely, if a
process receives information from less than half of the other processes from
the group, during the procedure of relaying and aggregating the operative
counts of $0$’s and $1$’s from the lower layer, it becomes inoperative. See
example in Figure 2. After $O(\log{n})$ rounds, corresponding to the height of
the binary tree, the operative counts for the entire group – corresponding to
the root of the tree – can be calculated. Complying with the rule of receiving
enough number of messages in order to maintain an operative status, only the
processes of the group that remain operative use the operative counts further
in the protocol. In the analysis, we will be able to prove that, regardless of
the omission failures’ pattern, there is a group of $\Theta(n)$ operative
processes whose counts of operative $0$’s and $1$’s differ by, at most, the
number of processes who have become inoperative. Taking the advantage of the
binary-tree-structured communication, we can guarantee that processes of each
group exchange at most $\tilde{O}(n)$ bits in total and that the procedure of
operative counting $0$’s and $1$’s takes only $O\left(\log{n}\right)$ rounds.
Summarizing, we prove the following result about a single execution of the
procedure GroupBitsAggregation. Detailed description can be found in Appendix
LABEL:subsec:comm-patterns and in Algorithm LABEL:alg:bits-agreg; the formal
analysis is in Appendix LABEL:subsec:analysis-main.

######  Lemma (Lemma LABEL:lem:bits-agg-contr and LABEL:lem:msg-aggr in
Appendix LABEL:subsec:analysis-main).

A single execution of the procedure GroupBitsSpreading works in $O(\log{n})$
rounds and guarantees that every operative process in a single group knows an
approximate number of other operative processes in the group having candidate
value $0$ and $1$. The numbers in different operative processes differ by at
most the number of processes of the group that became inoperative during the
execution of the procedure. Processes in a single group use at most
$O(n\log^{2}{n})$ bits of communication, in total, during the execution.

a,b,c,d,ea,b,c,da,babc,dcde$a,b,c,d,e$${\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}1}$${\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}2}$${\color[rgb]{1,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{1,.75,.75}3}$$\\{a,b,d,e\\}$$\\{a,b,d,e\\}$
Figure 2: Visualization of the $\sqrt{n}$-decomposition of the blue group from
Figure 1. The processes $a,b,c,d,e$ in the group are logically decomposed into
a binary tree. The pink arrows visualize the three-round process of relaying
operative counts of the two children of the root to the root itself. First,
the counts are relayed to all processes in the group (arrow #1), then the
processes send a confirmation if they received the counts (arrow #2), finally,
all in the group transmit the received counts to the higher layer – the root
in this case (arrow #3). Some processes can be faulty (process $c$ does not
communicate, only $\\{a,b,d,e\\}$) and their values are not guaranteed to be
accumulated accurately.

### Technical advancement 2: Fast inter-group communication and status
maintenance between operative processes.

After the tree-based communication, the operative processes in each group have
a shared knowledge about the count of operative $0$’s and $1$’s within their
group. Since there are $\left\lceil\sqrt{n}\right\rceil$ different groups, the
number of logically different counts is $O(\sqrt{n})$. To exchange these
$O(\sqrt{n})$ counts between the groups, the operative processes communicate
along the links in a sparse, but well-connected, graph – neighborhoods of
which are pre-selected locally in line 1 – that underlays the entire network;
see the executed procedure GroupBitsSpreading in line 1 of Algorithm 1 and the
illustration of the graph on the top of the group partition in Figure 1. The
graph used by the operative processes is selected as follows. We consider a
random graph, where each edge is selected independently at random with
probability $\Theta(\log{n}/n)$. Next, we use the probabilistic analysis to
show that the following event holds whp: a random graph with such edge density
has the property that every subgraph of a constant-fraction size is dense and
shallow – see Theorem LABEL:thm:random-graph-properties in Appendix
LABEL:subsec:analysis-main. The “dense” property refers to the fact that
removing an arbitrary but at most $\alpha$-fraction of edges incident to any
vertex from a linear number of vertices, allows to find a connected subgraph
of this linear number of vertices such that every vertex has degree at least
$\beta\log{n}$ within this subgraph. The “shallow” property refers to the fact
that the latter subgraph has logarithmic diameter (asymptotically). These two
properties justify our partition into operative and inoperative classes, from
perspective of the inter-group communication: as long as the process has more
than $\beta\log{n}$ active links, intuitively it belongs to the connected
shallow subgraph and thus it is capable of exchanging information with any
other process with this property in $O(\log{n})$ rounds. This holds regardless
of the factual faulty / non-faulty state of the processes. Therefore, the
operative processes can spread among themselves the operative counts of the
$\left\lceil\sqrt{n}\right\rceil$ different groups, yielding the property that
as long as a process remains operative it knows some operative counts of any
group with at least one operative process. More specifically, every operative
process stores a data structure memorizing the operative counts of each of the
$\left\lceil\sqrt{n}\right\rceil$ groups present in the system. Initially, it
knows only the counts of the group it belongs to. In $\Theta(\log{n})$ rounds
of communication it keeps sending these counts along every edge determined by
the underlying graph, maintaining the fact that operative counts of a
particular group are sent only once via each edge; at the same time it
receives counts of other groups and updates the data structure based on this
information. In case a process receives two or more different count values of
some group, it can choose arbitrarily any of them – as argued earlier, all of
them could differ by at most the number of processes that have become
inoperative in that group. To summarize, the procedure GroupBitsSpreading has
the following outcome (the formal description is given in Algorithm
LABEL:alg:bits-spread and in Appendix LABEL:subsec:comm-patterns; the formal
analysis is provided in Appendix LABEL:subsec:analysis-main).

######  Lemma (Lemmas LABEL:lem:spreading-reaching, LABEL:lem:operative-
contribution and Theorem LABEL:thm:main-algo in Appendix
LABEL:subsec:analysis-main).

Assume that processes run the procedure GroupBitSpreading with $O(\sqrt{n})$
different logical input values (which are the operative counts of candidate
values $0$ and $1$ of each group). At the end of the procedure, each operative
process knows at least one copy of the logical value, provided that at least
one process starting with this logical value remains operative. The procedure
uses $O(\log{n})$ communication rounds and $O(n\sqrt{n}\log^{2}{n})$
communication bits in total.

The combination of the two above technical advancements lead to calculating
the number of candidate values 0 and 1 among the operative processes. Although
these numbers are approximate, as they can differ by the number of processes
that have become inoperative, this difference is acceptable to still employ a
variant of the biased-majority-voting consensus, as we discuss in the next
part.

### Putting them all together: consensus protocol based on biased-majority-
voting adjusted to the new efficient voting implementation in an epoch.

Assuming that each operative process has the approximate numbers of other
operative processes having a candidate value $1$ and $0$, we explain the
modification to the consensus framework based on the biased-majority-voting by
Bar-Joseph and Ben-Or [Bar-JosephB98] in order to adapt to the dynamic
characteristic of the operative set of processes and to the properties that
our new efficient single-epoch implementation of a voting has. Our
modification takes into account that, in our case, the counts of operative
$0$’s and $1$’s are not the same in every operative process. The communication
protocols guarantee only that a candidate value of an operative process is
accounted by any other operative process, however, it gives no guarantee
regarding the candidate values of the processes that become inoperative during
the calculation and communication. Also, in our implementation of a single
biased-majority-voting subroutine (epoch), described earlier, the operative
processes do not assign any default values to the candidate values of the
inoperative processes. Thus, any operative process estimates the number of all
operative processes simply by adding the operative counts of $0$’s and $1$’s.
Based on the above estimates, the algorithm employs the procedure of
converging the candidate values of the operative processes to the final
decision value according to the following: if an operative process has an
operative count of $1$’s (meaning the candidate values of operative processes
assigned to $1$) at least $\frac{18}{30}$ of the estimated total of all
operative processes, it sets the candidate value to 1. If the operative count
is less than half of the estimated total, it sets the candidate value to 0. In
all other cases, the candidate value for the next step is a uniformly chosen
random bit. See lines 1-1 and Figure LABEL:fig:random-coin for an
illustration.