Temporal Generalization for Spoken Language Understanding

Spoken Language Understanding (SLU) models in industry applications are usually trained offline on historic data, but have to perform well on incoming user requests after deployment. Since the application data is not available at training time, this is formally similar to the domain generalization problem, where domains correspond to different temporal segments of the data, and the goal is to build a model that performs well on unseen domains, e.g., upcoming data. In this paper, we explore different strategies for achieving good temporal generalization, including instance weighting, temporal fine-tuning, learning temporal features and building a temporally-invariant model. Our results on data of large-scale SLU systems show that temporal information can be leveraged to improve temporal generalization for SLU models.

Introduction
Spoken Language Understanding (SLU) models play an important role in voice-controlled devices, such as Alexa or Google Home. Two common SLU tasks are intent classification (IC) and slot filling (SF). Given a user request, IC aims to extract the user's intent, while SF is a sequence labeling task which assigns a slot label to each of the tokens. For example, the user request "play volbeat" should be classified as PlayMusic by the IC task, while SF should assign the labels O and Artist to "play" and "volbeat", respectively. State-of-the-art approaches typically model the two tasks jointly via DNNs (Do and Gaspers, 2019;Chen et al., 2019).
In deployed industry SLU systems, new data continuously flows into the system, and the underlying data distributions keep drifting over time. In this paper, we focus on the setting of temporal covariate drift, where the distribution of utterances may change, but the correct label for an utterance or token remains fixed (i.e., no concept drift) (Schölkopf et al., 2012). Such data drifts happen, for example, because customer usage patterns change over time, as new movies are being released or new artists and songs become popular. Another cause of data drifts are seasonal changes or changes related to (re-)occurring events. For instance, the utterance "will it snow tomorrow" is more likely to appear during the winter than the summer season, and the utterance "put on the Christmas lighting" is likely uttered around Christmas.
To accommodate for temporal distributional changes, industry SLU models are typically retrained and redeployed over time; in the following sections, we also refer to this process as model release, and we assume that model releases are executed at fixed time intervals, e.g., once per month. We further assume that for each release, new labeled data become available, which were collected since the previous release, yielding data belonging to different time periods.
The common approach to utilize new data is to simply combine them with all previously available data, and subsequently split them into training, validation, and test datasets. We can then build and evaluate a model on these datasets, which we also refer to as offline data in this paper. In industry applications, SLU models are subsequently deployed to customers and have to perform well on incoming customer requests, which we also refer to as online data. Importantly, aiming to provide the best possible experience for our customers, our main goal is building models which perform well on the online rather than the offline data. Since the online data are not available for model building and evaluation, we need to utilize the offline data to build a model which generalizes well to unseen online data from the upcoming time period.
In this paper, we study this temporal generalization task assuming that data from several consecutive time periods, i.e., months in our case, are available, and we aim to build a SLU model which yields high performance on data from an upcoming time period. We aim to improve performance over the common approach of simply combining all offline data, which ignores the temporal nature of the data and implicitly assumes that data from all time periods are equally useful for model training. Instead, relating back to the previous examples, we assume that modeling the temporal nature of the data may be beneficial and that data from certain time periods may be particularly valuable. For instance, data from recent time periods may better reflect upcoming trends, and w.r.t. seasonality patterns, data from the same period in previous years may be particularly valuable.
To tackle the task, we explore four directions: i) instance weighting based on our assumptions about the task, ii) temporal finetuning, iii) learning temporal features and iv) building a temporallyinvariant model. We present extensive experiments on real-world SLU data of German and Portuguese voice-controlled devices. Our results indicate that temporal information can be leveraged to improve temporal generalization of SLU models. We also show that simple temporal fine-tuning is not very effective and in fact leads to performance drop in certain cases.

Related Work
To the best of our knowledge, the temporal generalization scenario studied in this paper has not yet been explored for SLU in the literature, which may be due to the fact that common Academic SLU datasets are rather small and do not have a temporal notation. In general, work addressing the temporal nature of SLU datasets has been limited. Kim et al. (2017) address temporal data drift by adapting from stale to current data with an adversarial domain adaptation approach, treating the stale and current dataset as source and target domain, respectively. Contrasting with our work, they assume the availability of data from the target and they focus on two time periods only. Other work has explored short-term temporal information, e.g., the utterance context provided by a couple of prior utterances to resolve ambiguities (Lin et al., 2021).
In NLP, previous research has explored the significance of temporal drift for several tasks, such as headline generation (Søgaard et al., 2021), sentiment analysis (Lukes and Søgaard, 2018) and named entity recognition (NER) (Rijhwani and Preotiuc-Pietro, 2020), providing evidence that model performance drops when training data age increases compared to the test data. However, despite this evidence, the vast majority of NLP research does not take the temporal nature of data into account for evaluation (Lazaridou et al., 2021). Lazaridou et al. (2021) show that (downstream task) performance of pre-trained language models suffers when performance is measured on future data. Since (re-)training of larger language models is costly, the authors propose to update model parameters by executing few steps of gradient decent on new data. Other approaches to mitigate temporal drift include predictive feature selection for sentiment analysis (Lukes and Søgaard, 2018), and selecting data based on frequent n-grams for NER (Chen et al., 2021). The most similar to our work is the study conducted by Rijhwani and Preotiuc-Pietro (2020) who tackle temporal drift for a smallscale NER task, i.e., including only 3 named entities. They consider data from several consecutive years and aim to build a model which performs well on data of the following year, focusing -in line with the previously described work -on the effects of data receny. The best performance is achieved by using instance weighting of recent data and temporal finetuning for a Bi-LSTM-CRF with Flair and GloVe embeddings, respectively. By contrast, we study temporal generalization in the context of a large-scale SLU production system covering a large numbers of labels. We focus on smaller time periods, i.e., spanning one month instead of a year, and we consider cyclic/seasonal changes in addition to data recency. For this purpose, we include methods which have not yet been explored in temporal generalization tasks, such as building models that leverage temporally-invariant representations.

Method
Given labeled SLU data from several consecutive time periods, our goal is to build a model which generalizes well to unseen data from an upcoming time period. In the following, we first provide a formal definition for our tasks and subsequently present the modeling approaches.

Learning scenario
We assume that labeled data are available, which span N consecutive time periods, i.e., D = , where x i,j 1 , . . . , x i,jn is an utterance with n tokens which was observed during time period D i . For the SF task, a slot label is available for each token in x i,j , and y i,j is a sentence-level intent label for the IC task. In this work, each D i ∈ D comprises data of one month.
The goal is to build a model using [D 1 , . . . , D N −1 ] which generalizes well to the unseen data D N . [D 1 , . . . , D N −1 ] corresponds to the offline data in a release scenario, while D N corresponds to the online data.
Note that this learning scenario corresponds to the task of domain generalization (DG) (Wang et al., 2021) when considering the time periods as individual domains. In DG, one aims to build a model given several different but related domains (datasets) which works well on data of a new (unseen) domain during testing. However, in work addressing DG, typically the domains under consideration are more distant than the datasets of different time periods in our scenario, which are in fact drawn from the same overall source (domain), and contrasting with our scenario, the domain datasets in DG usually do not have a natural order.
Note further that DG differs from domain adaptation (DA) in that DA assumes the availability of some (unlabeled) data of the target domain, which can be utilized for adaptation.

Basic SLU model
Our basic SLU model is a common state-of-the-art SLU architecture for joint intent classification and slot filling. It is comprised of a BERT encoder, an intent decoder and a slot decoder. The BERT encoder's outputs at sentence and token level are used as inputs for the intent and slot decoders, respectively. The intent decoder is a standard feedforward network including two standard dense layers and a softmax layer on top. The slot decoder uses a CRF layer on top of two dense layers to leverage the sequential information of slot labels. As loss we use a weighted sum of the loss of IC L i and the loss of SF L s , i.e.
where λ i and λ s are weights. We use cross-entropy and CRF loss for IC and SF, respectively.

Instance weighting
Instance weighting assigns a weight to each training data instance. In a DA task, a weight may be selected such that it reflects the instance's similarity to the target (Jiang and Zhai, 2007). However, since we do not assume the availability of data from the target time period, we cannot compute such similarity scores. Instead, we simply weight instances based on our assumptions about the task. We assume that recent data, i.e., data from the period prior to the target period, may be particularly valuable, because this period may better reflect recent and upcoming trends, Moreover, instance weighting of data from a recent year has already been shown to improve performance on data of a future year for a small-scale NER task (Rijhwani and Preotiuc-Pietro, 2020). On the other hand, with respect to seasonal changes, data from the same period in previous years could also be of particular value. Thus, taken together, we explore three instance weighting strategies based on recency, seasonality, and combination of both: 1. Reweight each data instance in the period prior to the target period by a weight w > 1 (i.e., reweight D N −1 ), 2. Reweight each data instance from the same calendar month as the target data by w > 1, 3. Reweight all instances from either the same calendar month as the target data or from the period prior to the target data by w > 1.
Given an utterance and a corresponding weight, we weight the losses of both IC and SF. The described instance weighting techniques do not require any temporal information during the application phase and no architectural changes.

Temporal finetuning
We explore temporal finetuning, as it has been previously shown to improve performance on other temporal tasks. In particular, Rijhwani and Preotiuc-Pietro (2020) i) trained Bi-LSTM-CRF models for a small-scale NER task on data from several years, and ii) fine-tuned these models on data of the most recent year, yielding improved performance over the initial models when evaluated on data of a future year. Similarly, we first train a model on all offline data, i.e., on D 1 ∪ . . . ∪ D N −1 , and subsequently we finetune it on data of the most recent offline time period, i.e., on D N −1 . 1 Figure 1: SLU architecture for joint IC and SF with an auxiliary task for predicting the month of an input utterance. While the model is trained by alternating across tasks, during inference only the SF and IC decoders are used.
This technique does not require any temporal information during the application phase and no architectural changes.

Learning temporal features
We hypothesize that learning temporal features could be beneficial for our SLU task and therefore aim to build a temporally-aware model. For this purpose, we explore two established techniques for injecting auxiliary information, i.e., i) via additional input features, and ii) via an auxiliary task. The training of an auxiliary prediction task to improve embeddings is sometimes called selfsupervised learning, and has also been shown to improve generalization in vision tasks (Albuquerque et al., 2020).

Using additional input features
We define a special token for each month, e.g., "[JAN]", . . . "[DEC]". For each utterance, information about the month in which it was observed is added before model training and inference using the corresponding special token. E.g., "[DEC] play Christmas songs" indicates that the utterance "play Christmas songs" was observed in December.
While this technique does not require any architectural changes, temporal information is needed during the application phase, which, however, should be easily accessible in most cases.

Using an auxiliary task
We extend the basic SLU model described in section 3.2 by an auxiliary task which predicts the month given an utterance. Specifically, we apply a multi-task model which is comprised of a joint IC and SF task and an additional classification task; the overall architecture is illustrated in Fig. 1. The auxiliary task decoder is a standard feed-forward network comprising two standard dense layers and a softmax layer on top. We optimize the model by alternating across the two subtasks (joint SF and IC vs month prediction), and we use a combined loss where L i , L s and L t are the losses of the IC, SF and month prediction tasks, respectively, and λ i , λ s and λ i are weights. We use cross-entropy loss for the IC and month prediction tasks and CRF loss for the SF task. For inference, we apply only the joint SF and IC task, and temporal information is not required during the application phase. The intuition is that via the joint training, temporal information is acquired by the model which can then influence the SF and IC predictions during inference.

Building a temporally-invariant model
Relating back to section 3.1, our learning scenario corresponds to the task of DG when considering the time periods as individual domains. We selected a popular direction explored in DG (Wang et al., 2021) and DA (Ramponi and Plank, 2020), i.e., invariant representation learning. The intuition is that by removing information which is specific to individual domains, the model should generalize better to an unseen target domain. Thus, contrasting with the approaches described in the previous section which aim to learn temporal features, in this approach we aim to build a temporally-invariant model by removing features which are specific to certain time periods.
Note that both approaches may be reasonable, as there may be different kinds of temporal features and artifacts related to our data, out of which we may want to leverage some, but abstract away from others. For instance, it may be beneficial if the models learn a notation of seasonality and/or recency, but we may want to abstract away from artifacts related to out-dated trends, annotation inconsistencies across time, etc.
One established approach to domain-invariant representation learning is adding an auxiliary domain classifier to a main task predictor, and then optimizing for an accurate task predictor while applying an adversarial training strategy to confuse the auxiliary domain classifier by making the features from source and target domain indistinguishable, thus yielding domain-invariant features. A gradient-reversal layer can be applied for this purpose (Ganin and Lempitsky, 2015;Ganin et al., 2016). We adapt the approach from Ganin and Lempitsky (2015) to build a temporally-invariant model, i.e., we apply it with our SLU model as the main task predictor and using an auxiliary month classifier instead of the domain classifier (and BERT as the feature extractor).
As in case of learning temporal features using an auxiliary task, for inference we apply only the main task, and thus temporal information or architectural changes are not required during the application phase.

Data
We use data from large-scale industry SLU systems comprising user requests to voice-controlled devices; all requests were de-identified, annotated with intent and slot labels, and marked with a time stamp. We collected data for two languages, i.e. German and Portuguese, and three domains, i.e. Music, Video and Shopping. The data range from May 2019 to December 2020, and we split them into one dataset per month based on timestamps, resulting in 20 datasets D 1 , . . . , D 20 for each domain and language. Thus, one dataset is available per month, domain and language. For each domain and language, D 20 is used for testing, and for D 1 , . . . , D 19 we create training and validation datasets. For German, for each domain we have more than 100,000 data instances available, while for Portuguese for each domain the data amounts are on the order of tens of thousands.
Qualitative data analyses indicate that both gradual and seasonal drifts are indeed present in the data, but there are domain-specific differences. Due to confidentiality reasons, a detailed data analysis is beyond the scope of this paper.

Experimental setup
For each domain and language, we use the D 1 , . . . , D 19 training datasets for model training, and D 20 for testing. Since we do not have access to target period data, we study two options for creating an offline validation dataset: 1. val a comprises the offline validation data from D 1 , . . . , D 19 . This corresponds to the common approach. 2. val r comprises only recent offline validation data, i.e., the validation data of D 19 .
We train and evaluate our modeling approaches on the described setup. As baseline, we train a model, i.e., the basic SLU model described in section 3.2, following the common approach of simply training on the combined offline data (without leveraging any temporal information). In the following, we refer to this approach as concat.
We measure performance using a semantic error rate, which measures intent classification and slot filling jointly and is defined as follow:

Settings
We used pre-trained multilingual BERT (Devlin et al., 2019) (size 768, 110M parameters) 2 , and max-pooling for sentence representations. Each of our decoders has 2 dense layers of size 768 with gelu activation. The dropout values used in IC, SF and month decoders are 0.5, 0.2 and 0.5, respectively. We used equal weights for λ s and λ i (1.0:1.0) and Adam optimizer with a learning rate of 0.1 and a Noam learning rate scheduler. We trained our models for 20 and 25 epochs for German and Portuguese, respectively, with a batch size of 32. These hyper-parameters were used for all models (where they apply). The best models were selected on offline validation data (val all or val rec ). We tried w ∈ [2, 5] and we varied λ t from 0.2 to 0.6. Each model was trained on a single GPU.

Results and discussion
The results on the "online" test data for using either all offline validation data val all or recent validation data val rec to select the best model are shown in Table 1. For confidentiality reasons, we report the relative change in SemER compared to the concat baseline using val all . In the following, we discuss the results w.r.t. different research questions.  Table 1: Results on the "online" test data for using either all offline validation data (val a ) or recent offline validation data (val r ). We report the relative change in SemER compared to the concat baseline using val a .
RQ 1: Can temporal information be leveraged to improve temporal generalization for SLU? Across all domains and languages, improvements in SemER on future data can be achieved by taking the temporal nature of data into account. The best methods differ across domains and languages, which is expected, given that there are domain and language specific differences w.r.t. seasonal and gradual shifts. However, two of the methods yield consistent gains across all domains and languages, i.e., instance weighting of the previous time period and using an auxiliary task yield improved performance compared to the baseline for all considered conditions. Using an auxiliary task achieves the best performance most often.
RQ 2: What is the impact of seasonality and reoccurring events vs recency effects? Previous work in NLP on temporal adaptation and generalization has focused on larger time periods and the effects of data recency, showing strong performance for instance weighting of recent data and temporal finetuning on a small-scale NER task (Rijhwani and Preotiuc-Pietro, 2020). By contrast, our domain datasets cover smaller time periods, with different seasonal effects and re-occruring patterns. On our task, temporal finetuning gives mixed results, with decreasing performance in several cases. We assume that the models may overfit to the recent data, and some previously acquired knowledge related to older time periods might have been forgotten. However, unlike in the NER task which included only the three named entities PER, LOC, and ORG and in which there might be mostly gradual temporal trends, in our task seasonal drifts exist, potentially making certain older knowledge more relevant. By finetuning on recent data, the models may lose too much relevant seasonal knowledge, harming performance for domains with changes related to seasons or re-occurring events. Instance weighting of recent data gives consistent improvements, which is in line with previous findings, while instance weighting of the same time period gives mixed results, i.e., it helps in some cases, but decreases performance in others. To some extent this may be due to domain-specific differences. However, an issue might also be that there can be conflicting seasonal and gradual drifts. In particular, weighting is performed at the dataset level and a dataset from a year ago might include relevant seasonal data instances, but also less useful data instances such as data related to older (already outdated) trends. The negative effects can be mitigated to some extent by selecting the best model on recent validation data, which yields consistent gains in performance across all domains and languages. Future work may explore how to disentangle these effects, and in temporal DA scenarios one may select utterances based on the similarity to the target. However, in our scenario which does not assume the availability of target period data, modeling seasonal and re-occurring patterns indirectly via an auxiliary month prediction task appears to be a better choice in most cases, yielding consistent -and in most cases higher -gains.
How to create a validation dataset without having access to target data? For half of the domain-language pairings, performance is improved by using a recent offline validation dataset. The choice of the best validation dataset may be both method-specific and domain-specific, as drifts differ across domains.
Interestingly, performance of the concat baseline model, which ignores the temporal nature of the data, is consistently improved across domains and languages when using recent validation data. This shows that model performance can also be improved by taking the temporal nature of the data into account for creating a validation dataset in-stead of model building.
Should we aim for a temporally aware or invariant model? In this paper, we have explored both building temporally-aware and temporallyinvariant models, since there may be different kinds of temporal features and artifacts related to our data, out of which we may want to leverage some, but abstract away from others. Our results show consistent gains for temporally-aware models using an auxiliary month classifier as well as gains in all but one case for temporally-invariant models, with temporally-aware models giving better performance in most, but not all cases. Thus, both directions appear to be generally promising.
Future work may explore different approaches to learning temporally aware or invariant models, for instance, by exploring others DG approaches in the latter case. One potentially interesting direction is to learn disentangled representations that separate temporally-invariant and seasonal components.

Conclusion
We studied a temporal generalization task in which we used offline data of time periods spanning one month each to build a model that performs well on future online data. We explored four directions to leverage temporal information which are rather easy to apply in production, i.e., i) instance weighting based on our assumptions about the task, ii) temporal finetuning, iii) learning temporal features and iv) building a temporally-invariant model. Our results on real-world SLU data covering two languages and three domains each show that temporal information can be leveraged to improve temporal generalization for SLU. While several of the explored methods provide consistent gains across all domain-language pairings, the best methods differ, as different domain datasets have different gradual and seasonal drifts. Moreover, our results indicate that methods, such as temporal finetuning, which have been previously shown to provide strong performance on small-scale academic tasks with longer time periods and mostly gradual temporal drifts, do not necessarily yield the best performance in our large-scale SLU task including seasonality patterns.


Alea-BFT: Practical Asynchronous Byzantine Fault Tolerance

Traditional Byzantine Fault Tolerance (BFT) state machine replication protocols assume a partial synchrony model, leading to a design where a leader replica drives the protocol and is replaced after a timeout. Recently, we witnessed a surge of asynchronous BFT protocols that use randomization to remove the assumptions of bounds on message delivery times, making them more resilient to adverse network conditions. However, these protocols still fall short of being practical across a broad range of scenarios due to their cubic communication costs, use of expensive primitives, and overall protocol complexity. In this paper, we present Alea-BFT, the first asynchronous BFT protocol to achieve quadratic communication complexity, allowing it to scale to large networks. Alea-BFT brings the key design insight from classical protocols of concentrating part of the work on a single designated replica, and incorporates this principle in a two stage pipelined design, with an efficient broadcast led by the designated replica followed by an inexpensive binary agreement. We evaluated our prototype implementation across 10 sites in 4 continents, and our results show significant scalability gains from the proposed design.

Introduction
The history of Byzantine fault tolerant (BFT) replication has gone through different stages throughout the years, from the initial exploration of the topic in the 1980s [15], then, in the lates 1990s, the start of a series of practical protocols that achieve good performance [6], and more recently the realworld adoption of this class of protocols in the context of Blockchains [28].
Whenever a BFT protocol is devised, it needs to inevitably face the FLP impossibility result, which states that it is impossible to achieve consensus (or, equivalently, executing a replicated state machine command) in an asynchronous system with even a single fault [9]. For many decades, the almost universally accepted way to circumvent this hurdle was by assuming a partial synchrony model, where the network is assumed to be initially asynchronous, but, after an unknown point in time, to deliver and process messages within a certain time bound [8]. This leads to a class of protocol designs where a leader can drive the execution of the protocol, but, after a timeout that indicates that the protocol is not making progress, all replicas cooperate in picking a new leader.
Recently, researchers picked up a different line of research that had been somewhat dormant for many years: asynchronous BFT protocols [2]. These protocols are safe and live irrespectively of any timing assumptions being met, but at the cost of those guarantees being probabilistic, i.e., they are provided with very high probability. Removing these timing assumptions brings the advantage of allowing the protocol to be more resilient against node and network delays, which may be due to reasons ranging from network problems to malicious activity.
The recently proposed algorithms in this model follow mostly from the work of HoneyBadgerBFT [19], usually regarded as the first practical asynchronous BFT protocol and refined in subsequent work [10]. While these proposals were successful in showing that asynchronous BFT algorithms have reasonable performance and are resilient to adverse network conditions, they also fall short of being practical across a broad range of scenarios. In particular, aspects such as their message complexity being cubic in the number of protocol replicas, the extensive use of threshold encryption, and overall protocol complexity are at odds with deploying these proposals in systems with a large number of replicas. Such scalability limitations prevent these asynchronous protocols from being actively deployed on emerging permissioned blockchain systems that require the system to scale to hundreds or even thousands of participants, for which all suitable solutions assume some level of synchrony [22,28].
In this paper, we present Alea-BFT, the first protocol for asynchronous BFT state machine replication that is practical in real-world scenarios such as wide-area networks or deployments that go beyond a small number of replicas. The main insight in Alea-BFT is that it selectively brings a key design feature from classical partially synchronous protocols, namely the idea of having a per-command designated leader replica that drives the protocol execution for that command. By splitting the command execution in two phases, and placing on this replica the responsibility of the initial broadcast phase that disseminates each command, Alea-BFT can avoid redundant instances of expensive building blocks of asynchronous protocols, while simultaneously avoiding using threshold cryptography to encrypt proposals replicated across all replicas. However, this also introduces new challenges, namely that there is no guarantee that the broadcast by the leader will reach a sufficient number replicas in time for the subsequent agreement phase. We address this challenge by crafting an agreement phase where replicas either agree on the execution of the command in case the command was seen by enough replicas to reconstruct it if needed, or otherwise the command is locally stored in one of the various queues of pending commands that are eventually pushed through the agreement phase.
The resulting protocol is a significant leap forward in the state of the art of asynchronous BFT protocols, namely through the following characteristics.
• It provides optimal resilience for the Byzantine model, tolerating up to f = N−1 3 faulty processes out of N total processes; • It is completely asynchronous, meaning that no assumptions are made regarding the delivery schedule of messages by the network, thus ensuring robustness under adversarial network conditions or attacks that break timing assumptions; • It departs from a design where threshold cryptography is employed to encrypt proposals replicated across all the replicas, followed by an asynchronous common subset protocol and a final round of decrypting the results. Instead, we propose a novel architecture with a two phase pipelined design, based on simple primitives, namely a single broadcast instance followed by a binary agreement.
• It provides significant asymptotic improvements over the state of the art protocols in this model. In particular, both the expected message and communication complexities can be reduced by a factor of up to O(N), while still terminating in constant expected time.
We implemented Alea-BFT and evaluated it in a wide area deployment, comprising replicas spread across 10 sites in 4 continents. Our results show that Alea-BFT brings significant improvements over the state-of-the-art protocols for asynchronous BFT, at the cost of a modest increase in latency due to leader rotation.
The remainder of the paper is organized as follows. Section 2 surveys related work. Section 3 describes the system model and key building blocks. Section 4 presents the design of Alea-BFT. Section 5 analyses its asymptotic complexity. Section 6 describes our implementation, which is evaluated in Section 7. We conclude in Section 8.

Related Work
The Byzantine consensus problem was formulated by Lamport et al. [15], and led to a series of proposals for Byzantine fault tolerant replication protocols [12,18,24]. More recently, several proposals appeared that made BFT protocols more efficient, namely avoiding the use of expensive cryptographic signatures in the normal case [1,6,13]. BFT then gained a real-world adoption in the context of cryptocurrencies and blockchains, with several new protocols for that context [28].
From these proposals, the subset that implement a form of consensus -namely state machine replication protocols [25] are faced with the FLP impossibility result [9], which states that there is no deterministic solution for the consensus problem in an asynchronous system, even with a single crash fault. To circumvent this result, almost all modern BFT systems, rely on timing assumptions such as partial synchrony [8] in order to ensure liveness. This is the case, for instance, of systems such as PBFT [6] and also more recent proposals such as HotStuff [28] or Kauri [22].
As shown by Singh et al. [26] through simulations where replicas are correct but the network is unreliable, protocols in this model are sensitive to variations in message delivery performance, with the throughput dropping to zero under certain conditions, thus highlighting the need for protocols to take the network behavior into account.
As an alternative to protocols for the partially synchronous model, randomized protocols circumvent FLP by only guaranteeing the liveness property with high probability. The design for this class of protocols runs the main algorithm through multiple rounds until its non deterministic nature allows the probability of not having liveness to be irrelevant. These protocols are then able to operate over a fully asynchronous model, therefore eliminating the need for timing assumptions and the consequences in terms of the fragility of the protocols in the presence of network unreliability. Despite that fact that these properties make the protocols very interesting from a theoretical standpoint, asynchronous BFT protocols [3,4,20,23] have usually been considered impractical due to their high communication costs and expected termination time. Very recently, several new randomized protocols appeared. At the core of this new line of proposals is the use of an asynchronous binary agreement (ABA) primitive, in which processes decide on the value of a single bit. These ABA protocols are then used as building blocks for a solution to atomic broadcast and state machine replication. We next describe these new protocols, which form the most closely related work.
HoneyBadgerBFT [19] is based on the observation that atomic broadcast can be built on top of an asynchronous com- Figure 1: The structure of ACS subprotocol used by Honey-BadgerBFT [19]. Each of the blue boxes corresponds to an instance of a distributed protocol, whose message exchanges are not depicted. mon subset (ACS) framework by combining it with a threshold encryption scheme. In ACS every party proposes an input value, and outputs a common vector containing the inputs of at least N − f distinct parties. As illustrated in Figure 1, Hon-eyBadgerBFT constructs ACS from the composition of two phases, namely reliable broadcast (RBC) and asynchronous binary agreement (ABA). During the broadcast phase, every replica starts an RBC instance in order to disseminate its proposal to all other replicas. Then, in the agreement phase, N parallel ABA instances are invoked in order to decide on a N-bit vector, where the i-th value indicates whether or not to include the proposal from replica P i in the final ACS output. Here, the use of threshold encryption prevents an adversary from selectively censoring transactions, by selecting which proposals to include in the ACS output vector.
HoneyBadgerBFT significantly outperformed previous protocols, which constructed atomic broadcast directly from multi-valued Byzantine agreement (MVBA) [4]. This then led to the development of new protocols improving on it. BEAT [7] presents a series of techniques aimed at optimizing HoneyBadgerBFT and explores the trade-offs associated with using different broadcast and threshold cryptography subprotocols. EPIC [16] is an extension to BEAT that provides security under the adaptive corruption model, meaning the adversary can adaptively decide whose replicas to corrupt at any moment during the execution of the protocol. Finally, the Dumbo [10] protocols present alternative ACS constructions aimed at reducing the number of ABA executions per command delivered. Dumbo1 reduces this number to a value k independent of N by selecting a committee of aggregators that nominate which subset of proposals to output, while Dumbo2 further reduces it to a constant by instantiating ACS based on a MVBA execution over reduced size inputs.

Basics
In this section, we present the system model and precisely define the basic blocks upon which our proposal is built.

System model
We consider a distributed system composed of N processes, uniquely identified from the set S = {P 0 , ..., P N−1 }, as well as an arbitrary number of clients. We assume a Byzantine failure model where up to f = N−1 3 processes can fail during the execution of the protocol. The adversary is given full control over the behavior of a static set of these faulty processes meaning that they can deviate arbitrarily from the protocol specification and even collude among each other in order to subvert the properties of the protocol. The remaining processes that do not fail during protocol execution are referred to as correct. The system is asynchronous, with the delivery schedule of messages being delegated under adversarial control, and without bounds on communication delays or processing times. We consider the processes to be fully connected by channels providing guarantees that messages are not modified in transit and are eventually delivered. In practice, this requires message retransmission and point to point authentication, but by considering this network model we can omit these from the protocol description. Lastly, the adversary is assumed to be computationally bound and therefore unable to subvert the cryptographic primitives employed.

Specification
We developed Alea-BFT as an atomic broadcast protocol, which is a commonly used abstraction for implementing state machine replication. Intuitively, this allows a process (e.g., a proxy replica) to broadcast a message (e.g., a state machine command) to all processes, ensuring that all processes deliver all messages in the same order (executing all commands in the same order and therefore transitioning through the same sequence of states). Formally, atomic broadcast is defined as follows [11]: • Validity: If a correct process broadcasts a message m, then some correct process eventually delivers m.
• Agreement: If any correct process delivers a message m, then every correct process delivers m.
• Integrity: A message m appears at most once in the delivery sequence of any correct process.
• Total Order: If two correct processes deliver two messages m and m , then both processes deliver m and m in the same order.

Building blocks
Similarly to other asynchronous replication protocols, Alea-BFT is designed in a highly modular way, by reusing several sub-protocols to carry out certain tasks. In this modular, layered architecture, upper level protocols can provide inputs and receive outputs from sub-protocols at the lower layers of the stack. Next, we present the precise specification of the underlying primitives that are used as building blocks for the Alea-BFT protocol.

Verifiable Consistent Broadcast Protocol
Verifiable consistent broadcast (VCBC) is a protocol to deliver a payload message from a distinguished sender to all replicas. It can only provide guarantees that all correct replica processes deliver the broadcast value if the sender is correct; however, it always ensures that no two correct processes deliver conflicting messages. Additionally it allows any party P i , that has delivered the payload message m, to inform another party P j about the outcome of the broadcast execution, allowing it to deliver m immediately and terminate the corresponding VCBC instance. More formally, a VCBC protocol ensures the following properties [4]: • Validity: If a correct sender broadcasts m, then all correct parties eventually deliver m.
• Consistency: If a correct party delivers m and another party delivers m , then m = m .
• Integrity: Every correct party delivers at most one message. Additionally, if the sender if correct, then the message was previously broadcast by it.
• Verifiability: If a correct party delivers a message m, then it can produce a single protocol message M that it may send to other parties such that any correct party that receives M can safely deliver m.
• Succinctness: The size of the proof σ carried by M is independent of the length of m.
In Alea-BFT we use a VCBC implementation consisting of a slightly modified version of an echo broadcast protocol [4] using threshold signatures to generate and validate a proof σ associated with M. This allows the message size to be kept constant, ensuring succinctness. The message complexity of the VCBC protocol used is O(N) and its communication complexity is O(N(|m|+λ)), assuming the size of a threshold signature and share is at most λ bits.

Asynchronous Binary Agreement
An asynchronous binary agreement (ABA) protocol allows correct processes to agree on the value of a single bit. Each process P i proposes a binary value b i ∈ {0, 1} and decides for a common value b from the set of proposals by correct processes. Formally, a binary agreement protocol can be defined by the following properties: • Agreement: If any correct process decides b and another correct process decides b , then b = b .
• Termination: Every correct process eventually decides.
• Validity: If all correct processes propose b, then any correct process that decides must decide b.
Given the FLP impossibility result [9], there is no deterministic algorithm capable of satisfying all the previous proprieties in the asynchronous model of Alea-BFT. A solution to this is problem is resort to a randomized solution that guarantees termination in a probabilistic way. As a result, the termination property is replaced with the following: • Termination: The probability that a correct process is undecided after r rounds approaches zero as r approaches infinity.
This way, even though the total number of rounds required to reach agreement is unbounded, the probability that the protocol does not terminate converges to zero. We instantiate this primitive via the Cobalt ABA [17] protocol, a modified version of the protocol by Mostefaoui et al. [21] to include a fix for a liveness issue present in the original protocol. The protocol relies on a common source of randomness, a "common coin", realized from a threshold signature scheme by signing a unique bit string, corresponding to the name of the coin, and combining the signature shares to generate a random seed [5]. It provides optimal resilience, O(N 2 ) message complexity, O(λN 2 ) communication complexity and terminates in O(1) expected time.

Alea-BFT
In this section, we present the design of Alea-BFT, a new protocol that substantially improves the performance and scalability of asynchronous BFT replication. In addition to designing and implementing Alea-BFT, we also conducted a full correctness proof, which we present in Appendix A.

Motivation
We start by presenting in a systematic way the characteristics of state of the art proposals [7,10,16,19] that may represent scalability barriers: • Message and communication complexity: All the previously cited proposals employ an instance of ACS, where every replica must propose a candidate value out of which a subset is selected to be included in the final output vector. This requires all replicas to execute an all to all communication phase to disseminate their proposals. By itself, this step incurs a cubic message and communication costs due to the N executions of reliable broadcast (RBC).
• Number of ABA instances: Since the agreement protocol (ABA) is randomized, it may take several attempts based on different random values to terminate. Previous work [10] showed that, despite the expected number of rounds per ABA being constant, the overhead of running multiple ABA instances presents one of the major bottlenecks for existing protocols. The same work shows that it is possible to reduce the number of ABA executions to a constant value at the cost of extra communication steps, but we argue that this value could be further reduced to a single execution.
• Bandwidth usage: The strategy of sequentially executing independent ACS instances implies that some of the broadcast instances were effectively "wasted" as their values were not included in the final output and therefore must be broadcast again in a subsequent ACS execution. This results in unnecessary bandwidth usage.
• Byzantine performance faults: The adversary has absolute control over which replicas proposals are included in the final output, only constrained by the validity property of ACS. This means that up to f proposals that originate from Byzantine replicas can be invalid, resulting in serious performance degradation.
• Threshold encryption: A reduction from ACS to atomic broadcast requires threshold encryption for the entire set of proposals, to ensure fairness. This also adds an extra all to all communication step, for broadcasting decryption shares for the proposals included in the ACS output vector.

Overview and Intuition
Despite these drawbacks, asynchronous protocols based on an ACS framework showed that there is potential for asynchronous protocols to become practical, if we overcome the above limitations. A key idea that we leverage in Alea-BFT to achieve this is to have a single replica propose a value per consensus instance, similarly to what happens in leader based protocols in the partially synchronous model, while all others simply agree on whether to deliver it or not. By itself, this enables us to both remove an all to all communication phase and only have a single ABA execution per command (or batch of commands).
Strawman Proposal. This insight leads us to a strawman proposal, consisting of adapting the ACS construction of Hon-eyBadgerBFT, but instead of having all replicas simultaneously propose candidate values, a single replica is selected as the proposer for each consensus round. The role of the proposer is to select from its buffer of pending commands a value (or batch of values) to serve as a proposal and broadcast it to all replicas, using a broadcast primitive that ensures that all replicas receive the same value (or no value at all). Correct replicas would then proceed to execute a single ABA to determine whether to deliver the proposed value for that round (if enough replicas have received it) or not deliver anything. Additionally, the proposer could be deterministically rotated upon every ABA execution, in order to address the scenario where the proposer is faulty without introducing a fail-over sub protocol, similarly to what happens in other BFT protocols for the partially synchronous model [27] that incorporate leader rotation into the normal operation such that it is constantly changing. This strawman protocol, however, raises an immediate problem. In previous protocols based on an ACS framework, replicas are guaranteed to receive proposals from at least N − f correct replicas, and therefore they can wait until this threshold is met before deciding which values to input for the subsequent agreement stage. In contrast, in our strawman protocol, only a single replica takes the role of the proposer at any given time, so there is no way to determine whether the current proposer is faulty or not, thus making it difficult to decide which value to input into the ABA without resorting to some sort of timeout, which contradicts the asynchronous model.
Final design. The impossibility of waiting for a specific threshold to be met before deciding the value to input to the ABA stage, leads us to the insight of not waiting at all, and instead allowing undelivered proposals to exist, which are then carried across rounds. In other words, every time a particular replica is reelected as the proposer, the corresponding ABA execution will decide over its backlog of pending proposals instead of a single newly proposed value (or batch of values). This way, replicas can submit their input to start the ABA for a new round as soon as they conclude the previous round, since even if the decision is 0 (i.e., not deliver any proposal in the round), the same proposal will be eventually revisited when the same replica becomes the leader and a larger threshold of replicas become aware of the proposal, guaranteeing a convergence for an ABA decision of 1 over time. The ABA execution also serves a synchronization mechanism between replicas, since no replica can progress to a round until it has participated and terminated all ABA instances for previous rounds.
In Alea-BFT, we leverage this idea to decompose the monolithic architecture of previous ACS-based protocols, in which a binary agreement instance actively waits for the corresponding broadcast to terminate, into a two stage pipeline, where the results of the first phase (broadcast component) are queued to be eventually processed, either by the current or by a subsequent execution of the second phase (agreement component), which is being executed in parallel.
The resulting overall protocol flow is depicted in Figure 2. It starts with the the broadcast component of the Alea-BFT pipeline, where replicas receive client commands, store these in a pending buffer of size B, and, when the buffer is full, Figure 2: Overview of Alea-BFT. Each request goes through a single instance of a broadcast primitive (VCBC), whose output is inserted in a priority queue structure at each replica, which determines the input to the final ABA protocol instance. disseminate its contents via a VCBC primitive tagged with an incremental sequence number s. The output of VCBC at each replica is stored in a buffer, and only removed upon a decision of 1 in the subsequent phase. This stage produces an instance of an ordered backlog of undelivered proposals at each replica. These instances are then used as input to the next component of the pipeline. Note that every replica maintains N backlogs of undelivered proposals, one for each replica in the system, and these grow and shrink over time depending on how efficiently the agreement component can process them.
The next stage is the agreement component, which iteratively selects one of the backlogs and decides whether to deliver the oldest proposal contained in it. To do so, replicas participate in a single ABA execution, voting 1 if their backlog contains this proposal, or 0 otherwise. If the decision is 1, this indicates that a sufficient threshold of correct replicas are aware of the proposal and may safely deliver it, as all other replicas are guaranteed to be able to actively fetch it if needed, via a recovery mechanism. Otherwise, in case of a decision for 0, the agreement component simply moves on to the next backlog, repeating the same process all over again.
As we mentioned, since the VCBC primitive of the broadcast component does not guarantee termination, we need to address the scenario where a correct process ouputs an ABA decision for 1, but does not yet know the corresponding proposal. In this scenario, that correct process requests the missing proposal from the other processes that voted 1. This is guaranteed to work for the following reason: since ABA decided a value of 1, this implies that at least one correct process voted for 1, and is therefore this process is able to compute a VCBC proof for the pending proposal and forward it to the requesting process.

Description
Now we explain the Alea-BFT protocol in greater detail. Processes maintain two state variables shared between the two components of the pipeline: variable S i , consisting of the set of all messages delivered by the protocol, which is initialized as empty upon a call to the START procedure, and updated during the execution of the agreement component; and variable queues i , comprising an array of N priority queues, each corresponding to a distinct replica P x , ∀x ∈ {0, ..., N − 1}. Algorithm 1 is responsible for initializing the shared state variables and starting the pipeline components upon a to call to the START procedure. In the remainder of this section, we start by specifying the data structure of the priority queues, and then describe the two components of the pipeline in turn.

Priority queues
A priority queue is a custom data structure for storing elements, sorted according to their priority values. We refer to each position in a priority queue as a slot, uniquely identified by a priority value associated with it, where the lowernumbered priority values represent the elements that must be processed first. Only a single element can ever be inserted in a given slot, even after being removed, as the slot is permanently labeled as used and cannot store another element. There is a special slot called the head slot, that always points to the lowest priority slot whose value has not been removed yet. The pointer to the head slot progresses incrementally, conditioned by the insertion and removal of elements from the queue. A priority queue exposes the following attributes: • id: The unique identifier of the queue (static).
• head: The priority value associated with the head slot of the queue (dynamic).
Additionally, a priority queue provides an interface for accessing and modifying its contents as described below: • Enqueue (v, s): Add an element v with a given priority value s to the queue (ignored if the corresponding slot is not empty).
• Dequeue (v): Removes all instances of the specified element v from the queue, if it is present.
• Peek () → {v, ⊥}: Retrieve, without removing, the element v in the head slot of the queue, or ⊥ if the slot is empty.
As we will see, Alea-BFT leverages the proprieties of this structure to mediate the communication between the broadcast and agreement components of the protocol pipeline. In particular, each of the N priority queues maintains the undelivered proposals coming from the other replicas, ordered by the priority value assigned to those proposals.

Broadcast Component
The broadcast component is responsible for establishing an initial local order over the client updates received and propagating that order to other replicas. Every replica process maintains a two local state variables, a buffer of pending commands bu f i , and an integer value priority i , indicating the next sequence number it should assigned to a proposal. The main logic of this component, illustrated in Algorithm 2, is split between two upon rules: Upon rule 1 (lines 9 to 15): The first rule is triggered, by any correct process P i , upon the reception of a client message m to be totally ordered by the protocol. It is responsible for selecting a batch of B transactions from the pending buffer, attributing a local sequence number to it and broadcasting this pre-ordered proposal to all replicas. Process P i then proceeds as follows: • If the set of delivered messages S i does not contain the client message m, append it to the buffer bu f i , or ignore it otherwise (lines 10 to 11).
• If the size of the buffer reached a threshold B, input bu f i into a VCBC instance tagged with ID (i, priority i ) indicating that process P i assigned the local priority value priority i to a proposal consisting of the current buffer contents (lines 12 to 13).
• Increment the value of priority i , so that it can be assigned to the next proposal from P i and clear the buffer. (lines 14 to 15).

Upon rule 2 (lines 16 to 20):
The second rule is triggered, by any correct process P i , upon the delivery of a proposal m for a given VCBC instance tagged with ID ( j, priority j ), where j corresponds to the identifier of the replica P j that proposed m, and priority j to the sequence number assigned to it by P j . Process P i proceeds as follows: • Insert the delivered proposal m into the slot priority j of the priority queue Q j , mapping to P j . This corresponds to adding the m to the backlog of P j in P i , with the priority value priority j (lines 17 to 18).
• If the set S i contains m, indicating that it had already been delivered, then process P i immediately removes it from Q j in order to avoid ordering duplicate messages, effectively deleting m and progressing through the backlog (lines 19 to 20).
Our protocol relies on batching to improve on performance and bandwidth utilization. In particular, in the implementation described in Algorithm 2, replicas aggregate a fixed number of commands, configurable by B, before assigning a priority value to the batch and forwarding to other replicas.

Agreement Component
The agreement component, presented in Algorithm 3, is responsible for establishing a total order among client commands. This is done through a succession of agreement rounds that iterate through the various priority queues, and decide whether to insert the head of that queue in the total order or skip it. Processes maintain a single state variable r i , serving as a unique identifier for the current agreement round. The execution of the agreement component starts with a call to the AC-START procedure (line 3), which initializes the local variable r i to 0 and begins executing the agreement loop.
Agreement loop (lines 5 to 16): For each iteration r i of the agreement loop the backlog of proposals pertaining to a certain replica is selected. This replica is a designated round leader, chosen through a deterministic function of the round number F (e.g., by rotating through all replicas). Let P a denote the current round leader, such that all replicas operate over the priority queue Q a for r i . A correct process P i proceeds as follows: • Run an ABA instance tagged with ID (r i ) to determine whether the value in the head slot of Q a should be delivered for this round. Process P i , inputs 1 into the ABA if its local Q a contained a value in the head slot, or 0 otherwise (lines 6 to 9).
• If the ABA execution decided for 0, indicating that no proposal should be delivered for the current round r i , simply proceed to the next loop iteration, otherwise: -If process P i input 0 into the ABA send a FILL-GAP message to all processes that voted for 1. This is required because at this point in time P i is unaware of the value to deliver for r i and therefore must request it from another process (lines 12 to 13).
-Block execution until the head slot of Q a contains a value to be delivered via a call to the AC-DELIVER procedure. The value of the head slot can be updated by the delivery by a pending VCBC instance, either through "normal" execution or as result of the reception of a FILLER message (line 14).
In addition to the main agreement loop, the agreement component also defines two upon rules, associated with the recovery sub-protocol, to handle the reception of valid FILL-GAP and FILLER messages: Upon rule 1 (lines 17 to 21): The first rule is triggered, by any correct process P i , upon the reception of a valid FILL-GAP, q, s message from P j , where q identifies a priority queue Q q , and s specifies the current head slot of Q q in P j . Process P i then proceeds as follows: • Check if its local backlog pertaining to P q is more advanced than the one of P j , by comparing the head pointer of its Q q against s (line 19). If it's lower this indicates that P i cannot satisfy the FILL-GAP request thus ignoring it, otherwise: -Compute and store in entries a verifiable message M, for all VCBC instances originating from P q tagged with a priority compromised between the value s requested by P j and current head slot of Q q in P i (line 20).
-Send a FILLER message to P j containing all the VCBC verifiable messages M, computed in the previous step (line 21).

Upon rule 2 (lines 22 to 24):
The second rule is triggered, by any correct process P i , upon the reception of a valid FILLER, entries message. This message is received as a response to a FILL-GAP request and contains the required information necessary for P i to progress in the execution of the protocol, by completing pending VCBC instances, after blocking in line 14. Process P i proceeds as follows: • Deliver all M messages in entries to the corresponding VCBC instances. Note that the verifiability property of VCBC ensures that it immediately terminates upon the reception of M, therefore triggering the second upon rule of the broadcast component.
Finally the AC-DELIVER procedure (line 25), called during the execution of the agreement loop, is responsible for delivering the contents of values, a batch of totally ordered messages m, to the application layer (line 31). Additionally, this procedure also removes value from all priority queues and appends its contents to the set of delivered requests S.

Analysis
In this section we analyse the asymptotic efficiency of the Alea-BFT protocol, according to time, message and commu-nication complexity metrics. The results of this analysis are summarized in Table 1.
To analyze Alea-BFT we observe that, for every particular proposal payload to be delivered, message exchanges occur in three different places. First, during the execution of the broadcast component, a replica initiates a VCBC instance to disseminate the locally ordered proposal to all replicas, which is then queued in a priority queue slot according to the priority value assigned to it. Second, all replicas participate in successive ABA executions, to decide whether or not to deliver the proposal in a particular slot. Here, we denote by σ the average number of ABA instances executed over a single slot before it decides for 1 and its contents are scheduled for delivery. Finally, a fallback sub-protocol is triggered by replicas that did not VCBC-deliver the proposal before the corresponding ABA execution decided for 1, in order to actively fetch it from the other replicas.

Time Complexity
Time complexity is defined as the expected number of communication rounds before a protocol terminates, or, when we consider a continuously running protocol such as atomic broadcast, from a command proposal to its output. In the case of Alea-BFT, the first and third steps terminate in constant time O(1), whereas the total number of rounds required for the agreement component to decide depend on the value of σ, therefore bounding the overall time complexity of Alea-BFT as O(σ).

Message Complexity
Message complexity is the expected number of messages generated by correct replicas during the execution of the protocol. In Alea-BFT, the VCBC instance from the broadcast phase generates O(N) messages; then, every ABA instance exchanges O(N 2 ) messages; and finally the third recovery phase incurs an overhead of O(N) messages per replica that triggers this fallback protocol. Hence, the message complexity of Alea-BFT is O(σN 2 ), due to the σ ABA instances that are executed per priority queue slot prior to delivery.

Estimating σ
As previously mentioned, Alea-BFT does not guarantee a constant time execution, which ultimately could negatively affect the protocol latency. In particular, this is because multiple zero-deciding ABA instances could be executed over the same priority queue slot until its contents are considered to be totally ordered. However, we argue that, despite being theoretically unbounded, the value of σ (the number of ABA instances required for a decision) is in practice a very small constant, which ultimately is very close to the optimal value of 1. This statement is justified by the observation that, given a round-robin queue mapping function F, the same queue is revisited every N epochs, meaning that N − 1 other sequential ABA instances must have been executed by the time a particular queue is revisited. Considering the validity property of ABA, which states that the decided value must have been proposed by a correct process, then the termination of a VCBC instance by N − f correct replicas guarantees that the next ABA execution pertaining to it will decide for 1. Therefore, for the value of σ to increase by a single unit, correct replicas would, on average, have to complete N sequential ABA executions for every single VCBC instance, corresponding to the number of rounds after which a queue is revisited, an unlikely scenario given that ABA is a randomized protocol and consequently more expensive than a single deterministic execution of VCBC. In Section 7, we present practical results that further corroborate the hypothesis that the expected value of σ is a small constant close to 1.

Implementation
We implemented a prototype version of Alea-BFT, consisting of 5,000 lines of Java code. The source code is organized in a modular manner, with the main Alea-BFT outer protocol leveraging sub protocols (namely broadcast and binary agreement) as building blocks. Reliable point-to-point links were implemented using TCP streams, authenticated using HMAC with SHA-256 and 32 Byte keys shared by each replica pair. Additionally, we implemented HoneyBadgerBFT and Dumbo1/2, which were used as comparison baselines for our experimental evaluation.

Evaluation
In this section, we present the experimental evaluation of Alea-BFT. We are interested in comparing the overall performance of Alea-BFT against state-of-the-art protocols in the same model for varying system sizes, loads and fault scenarios. Additionally, we attempt to more precisely determine the analytical complexity of Alea-BFT by measuring the value taken by σ under realistic deployment scenarios.

Experimental setup
For our experiments, we deployed Alea-BFT, Dumbo1/2 and HoneyBadgerBFT on N = 4, 8, 16, 32, 64 and 128 Amazon EC2 t2.medium instances, uniformly distributed across 10 different regions (Paris, London, Frankfurt, Singapore, Tokyo, Mumbai, California, Virginia, Central Canada, and São Paulo) therefore spanning four continents. Each instance was equipped with 2 virtual CPUs, 4GB of memory and running Amazon Linux 2. We split our experiments in test groups based on the system scale N and a varying batch size B ranging from 4 up to 10 6 transactions. We used a fixed transaction size of 250 bytes across all our experiments. As baselines, we used HoneyBadgerBFT and the Dumbo family of protocols, thus capturing both the initial proposal in this new generation of asynchronous BFT protocols, and the state of the art proposals that were shown to outperform HoneyBadgerBFT. We excluded the BEAT protocols from our experimental evaluation, as their work keeps the structure of HoneyBadgerBFT intact and most of the methods presented in it are orthogonal and compatible with the other ACS based protocols.

Measuring σ
In Section 5, we presented a theoretical analysis of the complexity of Alea-BFT. The analysis showed that all complexity metrics are dependent on the value of a variable σ, corresponding to average the number of ABA executions per delivered proposal, which is theoretically unbounded. In an attempt to quantify the actual value of σ under realistic network conditions, we measured the number of messages generated by correct processes during protocol execution for different system sizes using a batch size of 1, 000 transactions, and in a scenario where all replicas constantly have requests to be executed, thus maximizing the load on the system. Figure 3 compares the average number of messages generated by each correct process during the execution of Alea-BFT, in order to deliver a single proposal, against an analytical computation of this value for different σ values. As we can see, the experimental measurements follow very closely the computed values for σ = 1, independently of the system scale.
A follow-up question is how does this translate, in practice, in terms of relative message complexity when compared to the state of the art. To this end, we measured experimentally the message complexity per replica and per request batch of Alea-BFT in comparison with HoneyBadgerBFT and Dumbo1/2. As we can see in Figure 8, this metric grows exponentially for the protocols based on ACS, but stays linear for Alea-BFT. This is expected since, in an ACS framework, every replica must reliably broadcast its proposals for that batch, which incurs O(N 2 ) messages per replica. In contrast, in Alea-BFT the broadcast primitive used has a message complexity of O(N).
The previous experiments support our hypothesis that, despite being theoretically unbounded, under a wide-area deployment with substantial request load, the value of σ does in fact approximate the optimal value of 1. In light of this, we present in Table 2 the expected complexities of Alea-BFT, HoneyBadgerBFT and Dumbo1/2 when setting σ = 1. As the table highlights, the gains are significant in terms of both message and communication complexity, allowing us to underline the importance of our proposal to the practicality of asynchronous BFT.

Throughput
Next, we measure the consequences of the previously studied protocol characteristics on their end to end performance, starting with the protocol throughput. Throughput is defined as the rate at which commands are serviced by the system, or, from the perspective of a Blockchain system, the number of transactions committed by unit of time. In our experiments, we measured the throughput by launching multiple replicas executing the protocol at the maximum possible rate (i.e., always having pending client requests to process) and periodically registering the number of transactions committed during the last time interval. Figure 4, compares the throughput of Alea-BFT, HoneyBadgerBFT and Dumbo1/2, for different system scales, as the batch size increases. The results show that the positive slope of the Alea-BFT throughput curve is maintained for a wider range of batch sizes than with all the other protocols. This leads to a resulting peak throughput of Alea-BFT that is about one order of magnitude higher than the state of the art in asynchronous BFT. This result is explained by the differences in communication complexity between the protocols, as presented in Table 2. Next, we fix the batch size to a value of 5000 transactions, and evaluate how the resulting throughput scales with the replica group size. Note that this is a conservative experiment for Alea-BFT since our protocol would allow for further throughput gains than the other protocols by increasing the batch size, as previously shown.
The results in Figure 5 show that Alea-BFT not only outperforms all other protocols for all system sizes, but this discrepancy in performance actually increases with the number of replicas in the system, thus showing better scalability. This is again expected since Alea-BFT presents lower message and communication complexities than its counterparts. Another interesting remark is that for smaller values of N, HoneyBad-gerBFT actually outperforms both Dumbo protocols despite being theoretically more expensive, showing that the benefit of reducing the number of ABA executions does not outweigh the overhead of the mechanisms required to achieve so for small system scales.

Latency
Next, we compare the latency of the various protocols, by measuring the time interval between the instant the first correct replica starts the protocol (i.e., selects the transaction from its pending buffer of client requests) until (N − f ) replicas deliver the result. In HoneyBadgerBFT and Dumbo1/2 this corresponds to an instance of ACS plus the threshold decryption round, whereas in Alea-BFT it encompasses the full pipeline, including the period during which a transaction is waiting in the priority queues for the agreement component to select it for delivery. In Figure 6, we examine the average latency of the protocols for different system sizes under no contention, i.e., having each node propose a single transaction at a time while no other proposals are being processed. As we can see, for small values of N, the basic latency of all four protocols is very similar. However, as the system size increases, we start to observe some differences, with the av- erage latency of HoneyBadgerBFT increasing faster than the remaining protocols. This discrepancy can be explained by the latency overhead associated with running multiple ABA instances, a factor that is greatly reduced in both Alea-BFT and the Dumbo protocols. The average latency of Alea-BFT grows faster than that of Dumbo1 and Dumbo2. This is because the latency of Alea-BFT is visibly influenced by the choice of replica that proposes the transaction, since the priority queues containing ordered proposals are traversed in a round robin manner, based on replica id. In particular, if the current leader is replica 0, then a proposal from a replica with a lower id will result in a lower latency measurement than if the proposal originated from a replica with a higher id. Note that, for fairness, the proposer was randomly selected and the results averaged across multiple runs. To gain an overall view of the tradeoff between latency and throughput for the various protocols, we show in Figure 7 how the latency evolves as the system load increases for a medium system scale of 32 replicas. Each point corresponds to measuring the throughput and latency of a given protocol for a fixed batch size, and the various points along a line correspond to varying the batch size and therefore increasing both latency and throughput as the batch size increases. For all protocols, initially the latency stays relatively stable, only presenting small increases as the system load grows. However, as we reach the nominal capacity of each protocol, we see a very steep increase in latency as the system resources stop being able to keep up with the increase in system load. Note that Alea-BFT is able to sustain a stable latency for much higher system loads than all the other protocols, and this is due to its asymptotic complexity, which leads to a more optimized bandwidth usage.

Performance under adversarial conditions
Finally, we evaluate the the performance of Alea-BFT under adversarial conditions, particularly in the presence of a malicious network scheduler and faulty replica processes.
In the first experiment, we aim to understand how an adversary that controls the delivery of network messages can influence the value of σ, and consequently the performance of Alea-BFT. To this end, we conducted an experiment using a malicious scheduler that purposely delayed the delivery of VCBC instances by N − f replicas, in order to artificially increase the value of σ to a value that is closer to N. As illustrated in Figure 8, even under adversarial network conditions, Alea-BFT still requires fewer message exchanges than HoneyBadgerBFT, although it requires more messages than both Dumbo protocols. This is explained by the fact that, in a scenario where σ = N, both Alea-BFT and HoneyBad-gerBFT require N ABA executions per consensus instance, whereas Dumbo1 and 2 reduce this number to a small value k (independent of N) and a constant value, respectively.
Additionally, we compare the performance of Alea-BFT and HoneyBadgerBFT in three different replica fault scenarios: failure-free, crash failure and Byzantine. In the crash failure scenario, we configure f replicas to completely ignore all external events. In the Byzantine fault scenario, we simulate the attack described in Section 4.1, in which an attacker purposely submits invalid proposals to be ordered that despite consuming resources do not count for the overall throughput of the protocol. For all experiments, the system scale was set to 4 replicas, with f = 1, and the batch size to 1, 000 transactions.  decrease by about 30% and 24%, respectively. These results are directly related with how often the proposal from a Byzantine replica is delivered by the protocol. In HoneyBadgerBFT, this corresponds to the threshold of proposals originating from Byzantine replicas that are included in the final output vector of ACS, which, under a fair network scheduler, follows a hypergeometric distribution over a population of size N and N − f draws. In contrast, under an adversarial network scheduler, the output of ACS will always contain f Byzantine proposals, since it can be influenced by the delivery order of messages. In Alea-BFT, the performance decay that occurs under the fault scenarios presented above follows directly from the queue selection function. In particular, the round robin strategy used in our implementation results in faulty replicas being selected periodically. A possible improvement over our baseline implementation could explore the impact of using adaptive queue selection functions. Additionally, for the Byzantine fault scenario, it would be possible for Alea-BFT to ignore invalid proposals during the broadcast phase. In contrast, ACS based protocols cannot follow this approach since the commit of which proposals to include happens before the threshold decryption round revealing its contents.

Conclusion
In this paper, we presented Alea-BFT, the first practical asynchronous BFT protocol to scale to large networks. Alea-BFT follows a principled design that splits the execution across two stages, and brings the idea of having a designated single replica drive the execution of the more expensive broadcast phase -to avoid redundant communication and computation that negatively affects the scalability of previous protocolsfollowed by a less expensive binary agreement phase. Our experimental evaluation shows that Alea-BFT is significantly more scalable than state of the art protocols, paving the way to the practical adoption of asynchronous BFT at scale. Definition 2 A correct process P i is said to be Prepared (i, s) for m on round r when it has delivered all VCBC (i, s ) instances tagged with a priority s ≤ s, where s corresponds to the lowest priority assigned by P i to a message m / ∈ S (i) r . The value of m corresponds to the result of VCBC (i, s).
Note that stating that a process is Prepared(i, s) for m, is the equivalent of invoking the Peek operation over the priority queue Q i and obtaining the value m = ⊥, located in its head slot of index s.

A.1 Agreement
The proof of agreement is structured as Lemma 1 and Theorem 1. Lemma 1 is used to prove agreement on the value of Prepared(i, −) for any agreement round where consensus holds at entry and Theorem 1 uses the previous lemma as support to conclude the reasoning.
Lemma 1 If some correct process has Prepared(i, −) for value m on round r, then no other correct process can have Prepared(i, −) for m , on the same agreement round, where consensus holds at entry, such that m = m .
For this proof we assume that two correct processes P and P are Prepared(i, −) for values m and m respectively, on round r where consensus holds at entry, and proceed to demonstrate that m = m leads to a contradiction due to a violation the consistency property of VCBC. 4.2.2. Process P c was Prepared(F(r), s) at the start of round r.
PROOF: By 4.2.1 and the assumption that P c is correct.
PROOF: By 4.2.2 and definition 2, the correct process P c must have VCBC delivered all proposals from P F(r) tagged with a priority value s ≤ s. Therefore, by the verifiability of VCBC, process P c , can produce a FILLER message that completes all VCBC instances whose result P is unaware.

A.2 Integrity
Theorem 2 (Integrity) Every correct process delivers any message m at most once.
For this proof we assume, without loss of generality, that a correct process P i has delivered a message m for a given agreement round r, and proceed to demonstrate that it cannot deliver m for any subsequent round due to its inability to become Prepared(−, −) for m, which is a prerequisite for delivery according to the protocol spec.
1. ASSUME: 1. Process P i is correct. 2. Process P i invoked DELIVER(m) for round r. PROVE: Process P i cannot deliver m for any round r > r.

S
(i) r+1 = S (i) r + {m}. PROOF: By assumptions 1 and 2, process P i is correct and has delivered m for round r. Therefore, updating its delivered set for the next round to include m.
3. Process P i cannot have Prepared(F(r ), −) for value m, for any round r > r.
PROOF: By 2 and Definition 2, it is impossible for a correct process P i to prepare for any value m during r if m ∈ S PROOF: To deliver m for a round r , the correct process P i must have Prepare(F(r ), −) for the value m during r . By 3, this is impossible if P i has delivered m for a prior round since m ∈ S (i) r , thereby proving the theorem.

A.3 Validity
The proof of validity is structured as Lemma 2 and Theorem 3. Lemma 2 formalizes an upper bound on the number of agreement rounds required to deliver a message when certain preconditions are met. Theorem 3 builds upon this lemma to conclude the proof.
Lemma 2 If 2 f + 1 correct processes have Prepared(i, s) for value m by the time they enter round r, then m is guaranteed to be delivered by the next round r ≥ r, such that F(r ) = i.