----------------------- REVIEW 1 ---------------------
PAPER: 27
TITLE: Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding
AUTHORS: Guanfeng Liang and Nitin Vaidya
In this paper the authors consider the problem of Byzantine Broadcast in the context of a synchronous network where at most f nodes are byzantine. They propose an algorithm (called NAB for Network-Aware Byzantine) that aims at achieving the best throughput (at least 1/3 of the capacity and 1/2 when an additional property is satisfied). The algorithm is made of 3 consecutive phases: Unreliable Broadcast, Failure Detection, and Dispute Control. The last phase is not always executed.
The Equality Check algorithm executed at the beginning of phase 2 is the most original part of this work. It is described in Section 3. During this phase each node uses a local linear coding to send informations about the value received during phase 1. If two correct nodes have not received the same value, at least one of them must detect the problem. Theorem 1 is at the core of the correctness proof. Unfortunately, due to space limitation, the authors only provide the proof sketch within the paper. The whole proof is provided in Annex. The proof relies on the following property: when A is a square matrix that is invertible, the equation Ax = 0 has only one trivial solution x=0. During the proof, the authors show that, based on the set of (random) coding matrices used by the nodes, they can always obtain an invertible matrix with a non-zero probability.
The paper is clear and well written. Unfortunately, important parts are contained in Appendices (especially the complete proof of theorem 1). Results about the throughput are presented as a main result in the abstract but they are just mentioned in Section 5.2. The explanation appears only in Appendices. The fact that the propagation delays are not taken into account is mentioned in the main paper (to simplify the analysis). Technics to cope with these delays (pipeline) are also only mentioned in the Appendices.
The authors have to move some informations contained in the Appendices within the paper.
A mistake appears page 7. The second subgraph is not {1, 3, 4} but {1, 2, 4}.
typos:
- page 6 "identified as fault" has to be replaced by "identified as faulty"
- page 8 - requirement (EC) : "x_i = x_j" has to be replaced by "x_i different from x_j"
- page 8 "possibly source node" has to be replaced by "possibly the source node"
- page 8 "there exist of coding matrices" has to be replaced by "there exist a set of coding matrices"
----------------------- REVIEW 2 ---------------------
PAPER: 27
TITLE: Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding
AUTHORS: Guanfeng Liang and Nitin Vaidya
The paper considers the broadcast problem in a point-to-point network with faulty nodes.
As pointed out by the authors, the main contribution of the work is the second phase of their proposed algorithm, in which failures are detected through an equality check procedure. Improving the performance of this stage is the key point in improving the overall throughput. As such, the authors use linear codes to achieve fast equality check.
I consider myself somewhat familiar with linear codes, and to me Theorem 1 (which is perhaps the major contribution of the work) is intuitive. To make Theorem 1 easier to understand for the readers, I think the authors could provide a simple intuition instead of putting a proof sketch. For example, they could explain the correctness of their equality check for a graph with only two nodes, and then explain why the same idea works in a general graph.
Overall, although the paper sheds some light on how linear codes can be used to achieve higher throughput, it is open to debate whether its contribution may be enough for PODC.
Some minor comments:
- It may be good to emphasize that the correctness of a set of coding matrix is independent of messages x_i. That is, in a given network, there is a set of coding metrics that is always correct, irrespective of messages x_i.
- Typo on page 8, line 8: (i.e. xi=xj) should be (i.e. xi != xj)?
- Typo on page 10, in definition of set Gama {H|J is a ¡K} should be {H|H is a ¡K}?
----------------------- REVIEW 3 ---------------------
PAPER: 27
TITLE: Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding
AUTHORS: Guanfeng Liang and Nitin Vaidya
This paper gives an algorithm to reliably broadcast messages of length L through a network of a given topology with given link capacities with throughput at least 1/3 of capacity. The throughput is measured by the lim as the number of messages goes to infinity, of the number of bits broadcast/total time. The correctness proof seems to work only on sufficiently large L though a lower bound of L is not stated in the description of the result in the intro.
Much relies on the fact that costs are amortized over large L and large Q. For example, the standard Byzantine agreement protocol for one bit is used as a subroutine.
The techniques here are based on a technique previously used by one of the authors. The new part of the work is tuning the coding matrix for the particular capacities of the particular links.
A probabilistic argument is used to show that good coding matrices exist.
This paper is beautifully written. However, my feeling is that the work is somewhat incremental.
Note to authors: example towards bottom of page 7 seems to have a mistake.