======= 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)