Review #197A =========================================================================== Overall merit ------------- 3. Weak accept Reviewer expertise ------------------ 3. Knowledgeable Paper summary ------------- Summary: The paper presents an algorithm for solving Approximate Byzantine Consensus. The underlying communication network is more general than commonly considered. It considers networks that are represented by an incomplete directed graph. In this more general model, the proposed algorithm is the first to achieve optimal resilience. Comments for author ------------------- Evaluation: Strengths: + The proposed algorithm answers an open question. It solves the Approximate agreement problem in the more general model of incomplete directed graphs, and it does so with optimal resilience. + The paper has technical depth and uses interesting techniques. Weaknesses: - This paper considerably overlaps a work by Tesng and Vaidya from 2015 (quoted in the paper). Three out of four Theorems, that are stated in the “main results”, are reformulations of theorems from the above mentioned work. In addition, the techniques seem to be similar. - Large segments of the work are presented only in the Appendix. These include essential parts of the main results. - The writing ends abruptly without discussing general insights. (Perhaps I missed something, but I did not conclude any immediate insights alone.) Issue: ** The paper claims to generalize the algorithm of Abraham et al. from 2004. However, in the proposed algorithm here, termination is achieved by an assumption that appears in the Appendix. I.e., that the range of input values is a priori known. This is a strong assumption that does not appear in the algorithm of Abraham et al., thus, the proposed algorithm does not generalize it exactly. Q: The algorithm’s computation complexity is exponential. Is this an inherent part of having optimal resilience? A list of minor writing comments: 1. Page 5, before section 3 - not === that. 2. P6, 2nd line - redundant paths: … and may have a cycle. === and may have cycles. 3. P6, DEF4 - a f-cover === an f-cover. 4. P6, 6th line of SEC4 - to collection information === to collect information. 5. P6, pre-last line - time that the === time than the 6. P8, 3rd parag. 2nd line - is still be able === is still able 7. P8, last parag. 4th line - BW is proved hold for… === BW are proved for… 8. Appendix A, DEF20 - something in this definition is wrong. 9. P19, after DEF20 - ...and 3-reach prove are… === ...and 3-reach are… * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Review #197B =========================================================================== Overall merit ------------- 4. Accept Reviewer expertise ------------------ 3. Knowledgeable Paper summary ------------- This submission considers the task of approximate agreement in arbitrary directed networks with Byzantine faults. The network is known to all nodes, there are no signatures, and each node is given a real input from the range [0,K] (where K is known as well). Each node then computes an output such that the outputs span an interval [x,x+eps], which is subset of the interval spanned by the inputs to correct nodes. For this setting, the authors present a necessary and sufficient condition for solving this task, and a generalization is given showing a relation to other consensus tasks. The algorithm showing the upper bound takes ceil(log K/eps) iterations, which take Theta(n) rounds each, and requires exponential message size and computations. Comments for author ------------------- strengths: - considers well-motivated key problem - result precisely fills in an important blank spot in our understanding - clearly structured presentation weaknesses: - algorithm is inefficient - proving the correctness of the algorithm takes a lot of effort and notation; while I don't feel in a position to judge whether this is necessary, it makes it challenging to extract intuition and understanding I believe this to be an important and non-trivial result, and I am under the impression that the presentation is well done (with the caveat that I would hope for a simplified reasoning). Accordingly, I think it is suitable for the conference. minor comments: - For my taste, you mention that you solve the \emph{open problem} a couple of times more often than necessary - I suggest to mention signatures (a.k.a. authenticated messages) in the related work and briefly summarize how they change the picture. - The system model should mention that the graph is known a priori. Also, if there's anything known about settings with less initial knowledge on the topology, it should be mentioned in the related work (otherwise, please mention the absence of such work). - "1-reach, 2-reach, and 3-reach are equivalent with" -> equivalent to (I think) - "that each of their conditions to be equivalent to" -> is equivalent to - Theorems 1 to 3: "satisfies 1/2/3-reach condition" -> the 1/2/3-reach condition - "it cannot wait for messages not might never arrive" -> that might never arrive - "(i.e., messages tampered by faulty nodes)" -> tampered with (maybe rather dropped by?) - "(A,v)-paths: [...] p' = " - typesetting off, I think you should \langle and \rangle here as well? - "has set of vertices V" -> has vertex set V - "[...] by a node through different paths" - missing . - underlining: It's of course a matter of taste, but ordinary emphasis should be enough (I think that most style guides discourage underlining etc.) - "The properties of Algorithm BW is proved hold for [...]" - please fix - "a message not intended for i or contains a false path information" -> containing false path information - "For efficiency, we only use RFlood to propagate state values [...]" - The algorithm is not efficient in any typical sense of the word, as it has a very high message and computational complexity, and also is not particularly fast (as in all topologies paths of length Omega(n) are considered). Against this background, I find this statement rather confusing. - "only one parallel thread for some F_v" -> for each F_v (?) - "We first remind the reader that S_{F_1,F_1} [...]" -> S_{F_1,F_2} - "defined in Definitions 6 and 5" -> 5 and 6 - "set A is said to propagate in C to set B if either (i) B=\emptyset or (ii) for each node b in B, [...]" - the second condition is trivially satisfied if B = \emptyset, so this is redundant (and I don't think being explicit here for clarity is actually necessary) - Theorem 5: Why is it required that F_2 \subseteq \bar{F_1}? Is this restriction required? Doesn't this restriction get (partially) in the way when applying Theorem 5 later? - "Hence, it is possible that the value sent by node w is x_w', but themessage(s) propagated [...]" - I found this misleading, as it is actually not possible. You clear this up by proving exactly that right afterwards, but way stating this possibility in the first place, rather than providing the argument excluding it? - "by assumption.Let" - insert space - "By the 3-reach condition of Definition 15" -> Definition 3 - Why is F' subseteq V\setminus S_{F_u,F_w'} here? Again, it's unclear to me why this restriction is necessary, and it means that the other case later has to be treated separately. - "this would contradict with Equation (1)" - remove "with" - "Let any pair of nonfaulty nodes v,u which execute" -> Let v,u be a pair of nonfaulty nodes executing/which execute - "Note that both nodes v,u will only satisfy [...] only" - remove first only - "are averaged as is usual" - taken literally this would mean to take the average of the remaining values; please choose a less ambiguous formulation (e.g., "average of the extremal remaining values" or "midpoint of the interval spanned by the remaining values") * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Review #197C =========================================================================== Overall merit ------------- 3. Weak accept Reviewer expertise ------------------ 3. Knowledgeable Paper summary ------------- The paper characterizes directed graphs for which asynchronous approximate agreement is solvable, despite a bounded number f of faulty nodes. Approximate agreement is a fundamental problem in fault-tolerant distributed computing, whose has been studied since the early days of the field. The submission closes one of the few remaining open questions regarding this problem. A condition named 3-reach is introduced and it shown that in every directed network in which it is satisfied, approximate agreement can be solved. Intuitively, this condition requires that for every pair of nodes u and v,  every set of faulty node $F$, every set of suspected faulty nodes $F_u$, $F_v$, there is a node w that has directed path to $u$ ($v$) avoiding  $F \cup F_u$ ($F \cup F_v)$. Interestingly, this necessary and sufficient condition is the same for synchronous and asynchronous cases. The algorithm description is hard to follow. High level principles of the algorithm should clearly appear.  The purpose and specification of each component should be clearly spelled out. - The notion of asynchronous round should be defined. When does a   round ends for a particular node? - Besides intuition, please specify what algorithms BW and FA are doing, in terms of   inputs, outputs or the invariants they maintain for each round. - From the text on page 9, one cannot understand what the function   completeness does,  what is its purpose, and what are its   parameters. - A crucial part of the algorithm seems to be line 5 in Algorithm 2. I   cannot find explanation about this part of the code. The paper makes a fair contribution on a fundamental problem in fault-tolerant distributed computing, but its main part, it would benefit form a better exposition of the approximate agreement algorithm. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Review #197D =========================================================================== Overall merit ------------- 2. Weak reject Reviewer expertise ------------------ 1. No familiarity Paper summary ------------- The paper presents a solution to the approximate consensus problem in an asynchronous setting when the communication graph is directed. They show that a '3-reach' condition is necessary and sufficient in this setting, and hence their protocol works when the 3-reach condition is satisfied. Comments for author ------------------- The terminology and the protocol in the paper are clearly defined and well-constructed. Also, the solution seems non-trivial. My key concern is wrt the practicality of the solution -- the Byzantine Witness algorithm requires maintaining an exponential number of threads which is clearly not feasible. I understand that this is meant to be a theoretical feasibility result, but maintaining exponential threads for each round seems like far too much to pay.