===========================================================================
COMSNETS 2012 Review #155A
Updated Monday 17 Oct 2011 2:40:56am CDT
---------------------------------------------------------------------------
Paper #155: Capacity of Byzantine Consensus in Capacity Limited
Point-to-Point Networks
---------------------------------------------------------------------------
Overall merit: 2. Weak reject
Reviewer expertise: 2. Some familiarity
===== Paper summary =====
This paper deals with modeling capacity of a network where consensus among nodes is considered as an explicit constraint. The authors provide a heavy modeling effort to prove bounds on the capacity of a 4-node network with Byzantine consensus, which is a terminology from distributed systems. A weaker model for a probabilistic model of capacity of networks with consensus is also developed. Overall, the paper does not relate well to the networking community.
===== Comments for author =====
The paper tackles the important problem of finding closed-form bounds on the capacity of a network under failures. The problem relates to what-if analysis in general; however, the paper does not do justice on covering enough grounds to make the relation to the traditional networking problems.
The major issue with this paper is that it is highly cryptic. First, it does not really define the problem clearly. A simple network example illustrating what exactly "consensus capacity" means would be a good start for making the paper reach out to the reader. Again, since no clear examples are provided, the paper does not motivate the problem well. Many critical questions remains unanswered about the motivation and context: What exactly consensus refers to in a network? Are we talking about routing consensus? Why do you model the consensus as a "bit stream"? How does that relate to a network setting?
Beyond all these, the paper is not a significant enough step on top of the authors' recent publication: "Capacity of byzantine agreement with finite link capacity" INFOCOM'11, where the authors make a better job of explaining how the "consensus/agreement capacity" problem relates to the networking community.
page 1: Byzantine Fault-Tolerant -> Byzantine Fault-Tolerance
page 1: a underlying -> an underlying
page 1: available resource of the network -> available resources of the network
page 1: are assume -> assume
page 1: fashions -> fashion
Section II: theory and practice both -> both theory and practice
page 7: and compute -> and computes
===========================================================================
COMSNETS 2012 Review #155B
Updated Monday 24 Oct 2011 12:14:43am CDT
---------------------------------------------------------------------------
Paper #155: Capacity of Byzantine Consensus in Capacity Limited
Point-to-Point Networks
---------------------------------------------------------------------------
Overall merit: 4. Accept
Reviewer expertise: 2. Some familiarity
===== Paper summary =====
The paper considers the Byzantine consensus problem but where the n participating nodes are communicating over a capacitated network (point-to-point). The paper looks at the communication aspect of this problem; more specifically, what is the maximum achievable consensus throughput over this network for Byzantine consensus. The paper derives an upper bound on the consensus capacity, and then shows that the bound is tight for a special case of complete 4-node network with at most one faulty node.
===== Comments for author =====
The consideration of the well-known Byzantine consensus problem over a capacitated network, and looking at the"consensus capacity", is interesting and seems novel. The definition of the capacity in this context makes sense, and while I did not verify all the analysis, the results at a high level are intuitive. The upper bound on the consensus capacity (Theorem 1) seems quite natural.
The tightness argument (high probability argument) is for a very restricted case of 4-node complete network with at most one faulty node, although it considers arbitrary capacity links. The analysis of this special case, as provided by the authors, seems non-trivial however.
The authors need to distinguish better with their earlier work [12,[13]. The authors do say that in these previous work they consider "broadcast", but some more details on the technical differences are necessary. These should also be discussed in the related work section.
===========================================================================
COMSNETS 2012 Review #155C
Updated Monday 24 Oct 2011 4:19:15am CDT
---------------------------------------------------------------------------
Paper #155: Capacity of Byzantine Consensus in Capacity Limited
Point-to-Point Networks
---------------------------------------------------------------------------
Overall merit: 3. Accept if room
Reviewer expertise: 2. Some familiarity
===== Paper summary =====
Mathematical analysis to determine to the upper bound for the capacity Byzantine network is presented. Section 4 contains a description of the algorithm for a 4- node network and has been generalized. A motivation for the application of the results can be included if it is not already discussed in other papers on this topic.
For an applied conference such as COMSNETS, that would be useful.
===========================================================================
COMSNETS 2012 Review #155D
Updated Saturday 29 Oct 2011 12:39:52pm CDT
---------------------------------------------------------------------------
Paper #155: Capacity of Byzantine Consensus in Capacity Limited
Point-to-Point Networks
---------------------------------------------------------------------------
Overall merit: 3. Accept if room
Reviewer expertise: 1. No familiarity
===== Paper summary =====
This paper investigates the problem of maximizing throughput for Byzantine consensus in point-to-point networks, where each link as some capacity constraint. The performance of BFT algorithms depend strongly on the performance of underlying networks, yet little is known about the relationship between the performance of the underlying network and the efficiency of the BFT algorithms that operate on top of the underlying network. The authors introduce a structure and algorithm for achieving consensus with high probability in larger networks.
===== Comments for author =====
This paper is a theoretical paper that examines the relationship between the efficiency of BFT algorithms and the capacity of the underlying network. Although the results and proofs seem solid, for the COMSNETS audience, the paper needs to be revised to better explain the implications of the results. Most readers of this paper will not be experts in BFT systems, although perhaps they will design networks on which BFT systems may operate. What do the results imply for how a network should be provisioned for real-world communications networks?
Some of the results that show tighter bounds are for extremely small networks (e.g., four nodes), which seems extremely impractical for any real-world setting for where BFT may operate, such as in a cluster of thousands of servers. The later parts of the paper deal with this limitation by showing more probabilistic results, but in practice, system designers may not find probabilistic notions of consensus acceptable, particularly for critical systems. I couldn't actually find the statement of a result for the probabilistically correct algorithms; is there a result that provides some guarantee on correctness or consensus?
Overall, exploring the interactions between BFT algorithms and underlying network properties is an interesting twist, but the paper seems slightly out of scope for the audience, especially without some tighter and more explicit connection to practice.