Coordination-Free Byzantine Replication with Minimal Communication Costs
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Hellings, Jelle
Sadoghi, Mohammad
State-of-the-art fault-tolerant and federated data management systems rely on fully-replicated designs in which all participants have equivalent roles. Consequently, these systems have only limited scalability and are ill-suited for high-performance data management. As an alternative, we propose a hierarchical design in which a Byzantine cluster manages data, while an arbitrary number of learners can reliable learn these updates and use the corresponding data. To realize our design, we propose the delayed-replication algorithm, an efficient solution to the Byzantine learner problem that is central to our design. The delayed-replication algorithm is coordination-free, scalable, and has minimal communication cost for all participants involved. In doing so, the delayed-broadcast algorithm opens the door to new high-performance fault-tolerant and federated data management systems. To illustrate this, we show that the delayed-replication algorithm is not only useful to support specialized learners, but can also be used to reduce the overall communication cost of permissioned blockchains and to improve their storage scalability.
 Hello, I am Neil Allenx and I will present our research on coordination-free Byzantine replication. This is joint work with Mohamed Sarobi of the Exploratory Systems Lab in Davis. The aim of our ongoing research is to achieve fault-tolerant data processing that can even deal with malicious Byzantine behavior. At the same time, we also want to achieve high performance. Unfortunately, fault-tolerance is typically provided via full replication, and full replication requires a heavy amount of communication between replicants, this to coordinate data updates. Moreover, this communication increases when we add replicants, making full replication unscathable. Likewise, full replication also rules out the use of sharding, of geo-replacement of data and specializing the roles of replicants. A search fault-tolerant seems to be at odds with the typical techniques used for high performance data processing. Hence, we need to step away from full replication if we want to combine high performance with fault-tolerance. As a first step towards this goal, we propose a design in which data is stored in a Byzantine fault-tolerant cluster, while complex read-only workloads are handled off-site. To do so, we manage the data in a reliable Byzantine fault-tolerant cluster, and this cluster will handle data updates by processing incoming wide transactions of clients. As this cluster uses full replication, it can even deal with some malicious replicants that try to subvert these updates. Now if a party wants to perform a heavy read-only workload, such as data analytics, data provenance, machine learning or visualization, it can set up its own trusted environment under its own control to do so. After setting up this environment, the party measures itself as a learner with the fault-tolerant cluster, and in response, the cluster will forward all data updates to its party. After a learner receives data updates, it can then start to perform its own read-only workloads. It can do so without cooperation of the cluster or any other participants, and thereby reducing the overload on the system and increasing scalability. To enable this design, we need a highly efficient way to stream all transactions from our fault-tolerant cluster to the learners. Moreover, we want to do so with minimal cost for all the replicas involved. We formalize this problem as the Byzantine learner problem, the problem of sending the right transaction managed by a cluster to our learner. We need to do so in a reliable Byzantine fault-tolerant manner. This means that the learner will eventually learn all decided transactions, while ruling out that malicious webcasts can convince the learner to learn any other transactions. Furthermore, to support our design, any solution needs to minimize overall communication and minimize the cost for each replica in the cluster. To provide efficient Byzantine learning, we will adapt traditional information dispersal techniques to the setting of Byzantine fault-tolerant systems. Consider we have a value v of s-binds. An information dispersal algorithm can break up this value v into n distinct pieces, such that v can be reconstructed from any subset that misses at most f-pieces. To apply this to the setting of Byzantine fault-tolerant systems, we choose n to be the number of replicas and f to be an upper bound on the number of Byzantine faulty replicas. By result of Rabin, we know that a space optimal algorithm for information dispersal exists, namely edel. It guarantees that individual pieces have size proportional to n-f and that any subset of pieces from which we can reconstruct v as approximately the same size as v. Next we look at the delayed replication algorithm that uses ERA to send a journal of transactions from our Byzantine cluster to our learner. As the first step, each replica will partition its journal into sequences s of n transactions. Then the ERA computes the ERA piece of s, and next the ERA also computes a checksum of s and the checksum will be used by the learner to deal with malicious behavior. Finally, the ERA sends the checksum together with its ERA piece to the learner. Eventually, the learner will receive distinct ERA pieces from the non-faulty replicas, and as there are n-f non-faulty replicas, the learner can reconstruct s from these ERA pieces. We notice that this algorithm does low balancing. All replicas send the same amount of data, and each replica sends only a minimum fraction of the data. At the same time, the learner will receive data proportional to the size of the original journal. Next, we illustrate the working of the delayed replication algorithm. Initially, none of the four replicas can send data, as sending starts only after sufficient updates are made. After four updates, each replica can compute its ERA piece and the checksum and send these to the learner. During this process, the Byzantine replica B might try to disturb the algorithm by sending invalid data or sending no data at all. Fortunately, after receiving the three ERA pieces of non-faulty replicas, the learner is always able to reconstruct the first four updates. Finally, after the next four updates have been made, the sending process recommences. Next, we look at how learners can reconstruct the transactions it receives. To do so, we first consider checksums consisting of a simple hash-based fingerprint of the original sequence s of transactions. We notice that each non-faulty replica will send correct ERA pieces and correct checksums. Moreover, these checksums will be identical. Hence, if the learner receives x-hashes, then the most f of these hashes come from faulty replicas and the other x-hashes come from non-faulty replicas. And consequently, the learner only has to wait until it receives more than f identical hashes. After this, the learner has the guarantee that it knows the correct checksum as one of these checksums must be sent by a non-faulty replica. These checksums can then be used to determine whether a reconstructed sequence of transactions s' matches the original sequence. Unfortunately, this process is very compute-intensive for the learner. In the worst case, the learner must try to reconstruct s from every set of n-f pieces as only one of these sets is guaranteed to be correct. To reduce the computation cost for the learner, we consider checksums based on merkle trees. These checksums can be used to identify faulty pieces before they are used to reconstruct s. To illustrate how merkle tree checksums work, consider eight replicas and a sequence s. Each replica first computes the eight eta pieces of s, and then constructs a binary tree in which leaf nodes hold a hashes of an eta piece, and internal nodes hold hashes of their child values. To construct a checksum for a piece s5, the cost-preventing replica first determines the part from the root to this piece s5. Then it takes the root hashes of the tree and the neighbors on this part as a checksum. We notice that the root value is equivalent in all checksums, and hence the learner can determine the correct root value. Using a checksum and the correct root value, the learner can then determine whether the provided piece s5 is correct. The learner does so by first computing the hashes of s5, and then it can use the neighbor information in the checksums to reconstruct a path to the root. This yields a new root value, and the learner can then use this new root value to determine whether it matches the original correct root value. If this is the case, the provided piece s5 is correct, and otherwise the provided piece can be discarded as it is faulty. This process only costs log n hashes operation, and this is rather cheap on modern hardware. Combining the delayed application algorithm with Merkle Tree checksum yields a highly efficient solution to the Byzantine learner problem. More specifically, this combination guarantees that the learner will learn all transactions that are decided. Furthermore, the learner will only receive a linear number of messages with a size proportional to the journal size. Lastly, the learner will only have to perform a single decode step per end transaction. For replicas, this solution guarantees that each replica only sends a single message to the learner per end transaction. Moreover, each replica will send an equal and minimal amount of data to the learner. Next, we look at an application of the delayed replication algorithm within a Byzantine classroom. We notice that replicas typically do not need the full history of transactions to decide whether a proposed update is valid. Often, they only need a small current view of the data. Indeed, the full journal of all update decisions is typically only needed for recovering replicas. Hence, we treat a recovering replica as a learner and use the delayed replication algorithm to bring the recovering replica up to date. By doing so, each replica only has to store a fraction of the journal. This partially replicated approach can still deal with faulty replicas while making storage scalable. Indeed, adding more replicas to the cluster will even reduce the storage cost per replica. We conclude that efficient Byzantine learning is possible and we provide the delayed replication algorithm to do so. This opens up new designs for high-performance fault-solving data processing. In the paper, we also discussed several ways in which our delayed replication algorithm can be used to provide low-cost checkpoints and scalable storage for permissioned blockchain systems. High-performance fault-solving data processing remains ongoing work and more results can be found on our websites.
 Hello, I am Neil Allenx and I will present our research on coordination-free Byzantine  replication.  This is joint work with Mohamed Sarobi of the Exploratory Systems Lab in Davis.  The aim of our ongoing research is to achieve fault-tolerant data processing that can even  deal with malicious Byzantine behavior.  At the same time, we also want to achieve high performance.  Unfortunately, fault-tolerance is typically provided via full replication, and full replication  requires a heavy amount of communication between replicants, this to coordinate data  updates.  Moreover, this communication increases when we add replicants, making full replication  unscathable.  Likewise, full replication also rules out the use of sharding, of geo-replacement of  data and specializing the roles of replicants.  A search fault-tolerant seems to be at odds with the typical techniques used for high  performance data processing.  Hence, we need to step away from full replication if we want to combine high performance with  fault-tolerance.  As a first step towards this goal, we propose a design in which data is stored in a Byzantine  fault-tolerant cluster, while complex read-only workloads are handled off-site.  To do so, we manage the data in a reliable Byzantine fault-tolerant cluster, and this  cluster will handle data updates by processing incoming wide transactions of clients.  As this cluster uses full replication, it can even deal with some malicious replicants  that try to subvert these updates.  Now if a party wants to perform a heavy read-only workload, such as data analytics, data provenance,  machine learning or visualization, it can set up its own trusted environment under its  own control to do so.  After setting up this environment, the party measures itself as a learner with the fault-tolerant  cluster, and in response, the cluster will forward all data updates to its party.  After a learner receives data updates, it can then start to perform its own read-only workloads.  It can do so without cooperation of the cluster or any other participants, and thereby reducing  the overload on the system and increasing scalability.  To enable this design, we need a highly efficient way to stream all transactions from our fault-tolerant  cluster to the learners.  Moreover, we want to do so with minimal cost for all the replicas involved.  We formalize this problem as the Byzantine learner problem, the problem of sending the  right transaction managed by a cluster to our learner.  We need to do so in a reliable Byzantine fault-tolerant manner.  This means that the learner will eventually learn all decided transactions, while ruling  out that malicious webcasts can convince the learner to learn any other transactions.  Furthermore, to support our design, any solution needs to minimize overall communication and  minimize the cost for each replica in the cluster.  To provide efficient Byzantine learning, we will adapt traditional information dispersal  techniques to the setting of Byzantine fault-tolerant systems.  Consider we have a value v of s-binds.  An information dispersal algorithm can break up this value v into n distinct pieces, such  that v can be reconstructed from any subset that misses at most f-pieces.  To apply this to the setting of Byzantine fault-tolerant systems, we choose n to be  the number of replicas and f to be an upper bound on the number of Byzantine faulty replicas.  By result of Rabin, we know that a space optimal algorithm for information dispersal  exists, namely edel.  It guarantees that individual pieces have size proportional to n-f and that any subset  of pieces from which we can reconstruct v as approximately the same size as v.  Next we look at the delayed replication algorithm that uses ERA to send a journal of transactions  from our Byzantine cluster to our learner.  As the first step, each replica will partition its journal into sequences s of n transactions.  Then the ERA computes the ERA piece of s, and next the ERA also computes a checksum  of s and the checksum will be used by the learner to deal with malicious behavior.  Finally, the ERA sends the checksum together with its ERA piece to the learner.  Eventually, the learner will receive distinct ERA pieces from the non-faulty replicas, and  as there are n-f non-faulty replicas, the learner can reconstruct s from these ERA pieces.  We notice that this algorithm does low balancing.  All replicas send the same amount of data, and each replica sends only a minimum fraction  of the data.  At the same time, the learner will receive data proportional to the size of the original  journal.  Next, we illustrate the working of the delayed replication algorithm.  Initially, none of the four replicas can send data, as sending starts only after sufficient  updates are made.  After four updates, each replica can compute its ERA piece and the checksum and send these  to the learner.  During this process, the Byzantine replica B might try to disturb the algorithm by sending  invalid data or sending no data at all.  Fortunately, after receiving the three ERA pieces of non-faulty replicas, the learner  is always able to reconstruct the first four updates.  Finally, after the next four updates have been made, the sending process recommences.  Next, we look at how learners can reconstruct the transactions it receives.  To do so, we first consider checksums consisting of a simple hash-based fingerprint of the  original sequence s of transactions.  We notice that each non-faulty replica will send correct ERA pieces and correct checksums.  Moreover, these checksums will be identical.  Hence, if the learner receives x-hashes, then the most f of these hashes come from faulty  replicas and the other x-hashes come from non-faulty replicas.  And consequently, the learner only has to wait until it receives more than f identical  hashes.  After this, the learner has the guarantee that it knows the correct checksum as one of these  checksums must be sent by a non-faulty replica.  These checksums can then be used to determine whether a reconstructed sequence of transactions  s' matches the original sequence.  Unfortunately, this process is very compute-intensive for the learner.  In the worst case, the learner must try to reconstruct s from every set of n-f pieces  as only one of these sets is guaranteed to be correct.  To reduce the computation cost for the learner, we consider checksums based on merkle trees.  These checksums can be used to identify faulty pieces before they are used to reconstruct  s.  To illustrate how merkle tree checksums work, consider eight replicas and a sequence s.  Each replica first computes the eight eta pieces of s, and then constructs a binary  tree in which leaf nodes hold a hashes of an eta piece, and internal nodes hold hashes  of their child values.  To construct a checksum for a piece s5, the cost-preventing replica first determines the  part from the root to this piece s5.  Then it takes the root hashes of the tree and the neighbors on this part as a checksum.  We notice that the root value is equivalent in all checksums, and hence the learner can  determine the correct root value.  Using a checksum and the correct root value, the learner can then determine whether the  provided piece s5 is correct.  The learner does so by first computing the hashes of s5, and then it can use the neighbor  information in the checksums to reconstruct a path to the root.  This yields a new root value, and the learner can then use this new root value to determine  whether it matches the original correct root value.  If this is the case, the provided piece s5 is correct, and otherwise the provided piece  can be discarded as it is faulty.  This process only costs log n hashes operation, and this is rather cheap on modern hardware.  Combining the delayed application algorithm with Merkle Tree checksum yields a highly  efficient solution to the Byzantine learner problem.  More specifically, this combination guarantees that the learner will learn all transactions  that are decided.  Furthermore, the learner will only receive a linear number of messages with a size proportional  to the journal size.  Lastly, the learner will only have to perform a single decode step per end transaction.  For replicas, this solution guarantees that each replica only sends a single message to  the learner per end transaction.  Moreover, each replica will send an equal and minimal amount of data to the learner.  Next, we look at an application of the delayed replication algorithm within a Byzantine classroom.  We notice that replicas typically do not need the full history of transactions to decide  whether a proposed update is valid.  Often, they only need a small current view of the data.  Indeed, the full journal of all update decisions is typically only needed for recovering replicas.  Hence, we treat a recovering replica as a learner and use the delayed replication algorithm  to bring the recovering replica up to date.  By doing so, each replica only has to store a fraction of the journal.  This partially replicated approach can still deal with faulty replicas while making storage  scalable.  Indeed, adding more replicas to the cluster will even reduce the storage cost per replica.  We conclude that efficient Byzantine learning is possible and we provide the delayed replication  algorithm to do so.  This opens up new designs for high-performance fault-solving data processing.  In the paper, we also discussed several ways in which our delayed replication algorithm  can be used to provide low-cost checkpoints and scalable storage for permissioned blockchain  systems.  High-performance fault-solving data processing remains ongoing work and more results can  be found on our websites.
HellingsSadoghi_0_299.png HellingsSadoghi_300_1427.png HellingsSadoghi_1428_3359.png HellingsSadoghi_3360_3671.png HellingsSadoghi_3672_4451.png HellingsSadoghi_4452_5747.png HellingsSadoghi_5748_7235.png HellingsSadoghi_7236_8303.png HellingsSadoghi_8304_10019.png HellingsSadoghi_10020_10823.png HellingsSadoghi_10824_11075.png HellingsSadoghi_11076_12467.png HellingsSadoghi_12468_13463.png HellingsSadoghi_13464_14675.png HellingsSadoghi_14676_15359.png HellingsSadoghi_15360_15384.png