======= Review 1 ======= > *** Contributions: What are the major issues addressed in the paper? Do you consider them important? Comment on the novelty, creativity, impact, and technical depth in the paper. The paper focuses on the Byzantine agreement (Byzantine general) problem in a network in which communication links have finite capacity. The main idea of the paper is to combine the techniques developed in the distributed computing community (starting with seminal works by Lamport and others) with the novel technique of network coding. The paper focuses on some special cases (fully connected symmetric networks and networks with less than four nodes) and presents an algorithm that achieves capacity. > *** Strengths: What are the major reasons to accept the paper? [Be brief.] The considered problem is of significant interest and has not been considered before. The authors propose an interesting solution to this challenging problem, leveraging two different existing techniques. > *** Weaknesses: What are the major reasons NOT to accept the paper? [Be brief.] The paper is limited to a special cases of the problem. The presented algorithm is quite complex, and the results are presented in a way which is hard to verify. > *** Detailed Comments: Please provide detailed comments that will help the TPC assess the paper and help provide feedback to the authors. In general, the paper addresses an interesting problem and combines existing technique (Consensus + Network Coding) in a non-trivial way. Unfortunately, the presentation makes it hard to fully verify the correctness of the results. Some of the theorems are in the technical report. The results are limited to the special case of symmetric networks or networks with fewer than four nodes. The authors have published preliminary versions of this work in two places: PODC 2010 "Brief Announcement: Capacity of Byzantine Agreement with Finite Link Capacity - Complete Characterization of Four-Node Networks" Liang, G. and Vaidya, N. 2010. Capacity of byzantine agreement: summary of recent results. In Proceedings of the 2010 ACM Workshop on Wireless of the Students, By the Students, For the Students While it should fine to have a preliminary version in a workshop or as a small announcement, previous publications should be properly cited. > *** Recommendation: Your overall rating (Please try giving as few borderlines as possible). B+ = (top 20% of reviewer's perception of all INFOCOM submissions, but not top 10%) (4) ======= Review 2 ======= > *** Contributions: What are the major issues addressed in the paper? Do you consider them important? Comment on the novelty, creativity, impact, and technical depth in the paper. This paper considers the problem of maximizing the throughput of Byzantine agreement. The existing works implicitly assume the communication links have infinite capacity. This paper discusses the situation where link capacity is finite. It looks the result is new. The technical depth of this paper is strong. > *** Strengths: What are the major reasons to accept the paper? [Be brief.] It extends the existing work from infinite capacity to finite capacity. > *** Weaknesses: What are the major reasons NOT to accept the paper? [Be brief.] The paper itself is basically quite theoretical. Maybe there are better places to publish this paper. > *** Detailed Comments: Please provide detailed comments that will help the TPC assess the paper and help provide feedback to the authors. The paper is well written. However, to me, maybe to many other readers, it is a bit confusing to figure out how this research is related to the networks we are using. If the authors can discuss a bit more how this research can be applied to general network research, this paper will inspire more readers' interest. > *** Recommendation: Your overall rating (Please try giving as few borderlines as possible). A = (top 10% of reviewer's perception of all INFOCOM submissions, but not top 5%) (5) ======= Review 3 ======= > *** Contributions: What are the major issues addressed in the paper? Do you consider them important? Comment on the novelty, creativity, impact, and technical depth in the paper. In this paper, the authors essentially try and characterize the network capacity required in a symmetric network in order to achieve consensus or agreement in a network with Byzantine failures. The authors then present an algorithm that asymptotically achieves this capacity for a four node symmetric network. > *** Strengths: What are the major reasons to accept the paper? [Be brief.] The main strength of this paper is the novelty of the subject matter. While Byzantine agreement protocols have been well studied in the literature for a wide variety of settings, little or no work has been done that studies the required capacity in networks to implement a Byzantine agreement protocol. In particular, the authors are interested in the capacity achievable in the limit, when no correlation between transmitted symbols are assumed, and the agreement protocol runs for t->infinity. The problem is valid and interesting. The authors essentially apply ideas from the classic Byzantine agreement protocol by Pease, Shostak and Lamport, and combine it with ideas from source coding to both characterize the achievable capacity as well as an algorithm that achieves this capacity in the limit. > *** Weaknesses: What are the major reasons NOT to accept the paper? [Be brief.] I have a number of concerns about the paper. My main concern is the hand-waving arguments used when dealing with the duration of time required to execute in extended round 3 of the algorithm. Furthermore, it appears that this step is computationally rather intensive, and may not be a feasible solution in practice. Yet another concern is that the algorithm presented only works for a complete symmetric networks, which may not be realistic in a networking setting. Further, the crucial ideas behind the algorithm seem to be source coding and the classic Byzantine agreement protocol, both of which have been well studied, i.e., there are no novel techniques as presented by the authors. Instead, the presented algorithm applies both techniques in a rather straightforward way. Detailed comments appear below. > *** Detailed Comments: Please provide detailed comments that will help the TPC assess the paper and help provide feedback to the authors. (1) Weakness of the algorithm Extended step 3 is a crucial step in the algorithm, and as the authors themselves acknowledge, it requires a huge overhead in terms of the bits exchanged between nodes. As such, this phase can take a long time to complete. The authors argue, in a somewhat hand-waving manner, that asymptotically this does not matter, since this phase happens at most twice, and in the limit of time, the protocol achieves the stated capacity. While I do not completely disagree with this conclusion, I think this issue deserves more thought and investigation. In a realistic scenario with a limited amount of time, and some X amounts of bits required for agreement, it should be possible to state the capacity achievable as well. Such a characterization will be more complete. (2) Computation time The authors assume computation time to be 0. While this may be a reasonable assumption when talking about network capacity, it is misleading to assume this in other contexts. For example, in extended step 3, when trying to detect a misbehaving node X while labeling edges, it appears that a peer must simulate all computations of round 3 for each peer X, when trying to determine if X detected a misbehaviour or not. This requires decoding every subset of R packets as received by X. It is worth pointing out that this is computationally expensive. (3) Structure of the paper This paper appears to be a shortened version of a longer technical report. While I appreciate the need to leave sections out due to lack of space, I think the structure of the paper can be greatly improved. Since the main presentation concerns the 4 node network, I would start with that, before presenting the generalization in section II. This way, one would not have to push the discussion for general symmetric networks to the appendix. Also, the authors mention "algorithms" multiple times throughout the paper, yet only 1 algorithm is presented. This should be made clear, that only 1 algorithm for 4 nodes is presented, and the rest can be found in the technical report. Also, a flowchart or an algorithm box would have been highly useful to the reader to determine the big picture when trying to understand all the different rounds and modes involved. (4) Typos / Other concerns - pg 2, col 1, para 5, "related works" => "related work" - pg2, col 2, para 8, "an degraded" => "a degraded" - pg2, col 2, para 8, "have been solved" => "has been solved" - pg3, col 1, para 1, the term "generations" is vague and unclear. It is not used again in the paper. The authors should clarify what is meant here. - pg3, col 1, para 3, "code of rate at R" => "code at rate R" - pg3, col 1, para 3, "pretend not receiving anything" => It is unclear what is meant here. - pg5, col 1, para 4, "the label for XY" => what about YX? The scenario here seems symmetric. The authors are either missing YX, or more likely, have failed to explain this case clearly. - pg5, col 1, para 7, "then edge AB" => this should include BA too? - pg6, col 2, para 1, "An slightly" => "A slightly" - pg6, col 2, para 3, "using the packets receives from" => "using the packets received from" - pg 9, col 1, para 2, the proof here seems to require > R, yet NC2 states >= R. Did you mean > R requirement in NC1 - NC3? > *** Recommendation: Your overall rating (Please try giving as few borderlines as possible). B = (top 30% of reviewer's perception of all INFOCOM submissions, but not top 20%) - weak accept (3) ======= Review 4 ======= > *** Contributions: What are the major issues addressed in the paper? Do you consider them important? Comment on the novelty, creativity, impact, and technical depth in the paper. This work considers the capacity of agreement under Byzantine node failure where the links have finite capacity. This is an interesting problem and the work seems to address it in significant depth. > *** Strengths: What are the major reasons to accept the paper? [Be brief.] The problem is new and of fundamental theoretical value. The analysis seems technically detailed. > *** Weaknesses: What are the major reasons NOT to accept the paper? [Be brief.] 1. The work does not set up the problem properly, and does not clearly outline the assumptions and model. As such it is very hard to follow what the authors implicitly assume, and thus quite hard to validate the results. 2. The topic is not well motivated by any realistic scenario. While this is not a fatal weakness, it is definitely not a strength. A realistic scenario would have been useful to set up the problem and its relevance to the INFOCOM community, especially given that this type of problem has been primarily the focus of other research communities (e.g. see the publication venues for prior work cited in the paper). > *** Detailed Comments: Please provide detailed comments that will help the TPC assess the paper and help provide feedback to the authors. This work is potentially of high value, and thus I hate to recommend that it be declined. But the paper presentation lacks significantly, especially the earlier sections, where the problem is first formulated. In particular, the nature of the "networks" being considered is not quite clear, especially regarding the constraints on relaying. For example, in Pease et al. work, the problem considers a set of processors, there is a clear distinction between the cases where faulty processors relay or refuse to relay detected fault information. These details here are somewhat not explicitly visible as the algorithms here rely on network coding which do not seem to explore the variability in the behaviors of relays. Another issue in the model is that the paper assumes each link has a certain asymptotic capacity C, yet the algorithms operate in stages where at each stage it is assumed that a certain rate (capacity) can be achieved. It is not clear at all how that makes sense. Similarl! y, there are constraints given on the max flow and min cut, and it is not clear how the analysis takes care of the dynamism in the network versus the asymptotic capacity of links. The vagueness of the model and the assumptions makes one uneasy about the results and what they really mean. > *** Recommendation: Your overall rating (Please try giving as few borderlines as possible). B = (top 30% of reviewer's perception of all INFOCOM submissions, but not top 20%) - weak accept (3)