From: ICDCN 2013 Subject: ICDCN 2013 notification for paper 82 Date: September 12, 2012 10:52:33 AM CDT To: Nitin Vaidya Dear Nitin Vaidya, we are pleased to inform you that your submission #82 entitled "Iterative Approximate Byzantine Consensus under a Generalized Fault Model" has been accepted for publication as a regular paper in the Distributed Computing track of ICDCN 2013.   Within the Distributed Computing Track, we received 67 submissions, accepted 18 as full papers and an additional 3 as concise papers. Decisions on each paper were based on multiple reviews by PC members, discussions among  PC members,  as well as additional input when needed. As the author of an accepted paper you will have to submit a camera-ready version as well as a signed copyright form by Saturday October 13, 2012.   Detailed instructions on how to prepare your camera-ready version and copyright form are available on the Springer LNCS website at:   http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0. Please submit the files belonging to your camera-ready paper using your EasyChair author account. Follow the instructions after the login for uploading three files: (a) either a zipped file containing all your LaTeX sources or    a Word file in the RTF format, (b) PDF version of your camera-ready paper, and (c) the signed copyright form. The page limit is *15 pages* (including everything) and is strict. Please follow strictly the author instructions of Springer-Verlag when preparing this final version. In order for your paper to be included in the conference proceedings, at least one author must register (see the ICDCN Web page) to the conference  and present the paper. Reviews and comments on your paper are appended to this email. Please take them into account while preparing your camera-ready version. This will be your way to thank the reviewers for their work. We thank you for submitting a paper to ICDCN 2013 and we look forward to a very exciting conference with your active participation. Michel Raynal & Davide Frey ----------------------- REVIEW 1 --------------------- PAPER: 82 TITLE: Iterative Approximate Byzantine Consensus under a Generalized Fault Model AUTHORS: Lewis Tseng and Nitin Vaidya Summary of the paper The paper addresses the problem of approximate agreement in a synchronous directed network  with non-uniform Byzantine failures. The adversary specifies a set of possible "fault sets": in every execution, the set of faulty processes must be specified by the adversary. Necessary and sufficient conditions on the communication graphs for the problem to be solvable are determined for each given adversary. Upsides The paper considers an interesting problem. It is a priori hard to say what assumption about the generalized Byzantine adversary allow for a solution to approximate agreement.    The paper is generally well-written and the solution looks sound (did not mange to go through all the detail). Downsides The part relating to transition matrices is not very welcoming to the readers unfamiliar with the earlier work. The problem statement is slightly ambiguous.  The paper should say upfront that only a specific kind of "local memory-less"  algorithms is considered: a process sends its current position to all neighbors and updates its position based on (no meta-information such as past states can be exchanged). Some detailed comments - Abstract: Say "necessary and sufficient condition" on what (the  communication graphs?) Btw, "tight necessary and sufficient"  - tight looks redundant - "f-total" models are usually known as "f-resilient" models in the  literature - Consensus is usually defined as a one-shot problems in terms of inputs and irrevocable outputs. Here it  is rather posed as a self-stabilization problem. - The convergence condition may be interpreted as "there is a round at which the processes are within an epsilon-ball, while (I guess) you want to say that there is a round r such that at every round r'>=r,   the processes are within an epsilon-ball.     - The generalized fault model defined in the paper corresponds    to the "superset-closed" adversaries, as defined in [11]. A generic adversary allows for modeling *exact* sets of processes that are allowed to fail. - Section 5 and 6 - I would propose to merge them and call it  something like "Sufficient condition" ----------------------- REVIEW 2 --------------------- PAPER: 82 TITLE: Iterative Approximate Byzantine Consensus under a Generalized Fault Model AUTHORS: Lewis Tseng and Nitin Vaidya Summary of the paper (in a few lines) The paper introduces a necessary and sufficient condition for solving iterative approximate Byzantine consensus in a synchronous system with an arbitrary communication network. It uses a generalized Byzantine fault model allowing a fine-grained modeling of various fault sets as a fault domain as well as also capturing the usual standard fault models. The stated condition itself depends solely on the structure of the communication network and the specified fault domain. The method used is a state-space description using matrices, restricted to correct processes (the effect of Byzantine processes is "distributed" over the information disseminated by correct ones). The proof of necessity is given directly while the proof of sufficiency is given by an algorithm using only the stated condition to work and proofing it correct. Reasons to Accept - interesting problem - very nice condition for solvability generalizing the standard ones - reasonably well written Reasons to Reject - none, except that some related work should be added Other Comments Overall the paper is very interesting and the condition on the communication graph is a very elegant approach. As it is very central and would not consume too much space, I would propose to add a intuitive description of Theorem 1. Something like "It is not possible to choose the fault set $F$ and the fault sets $F_x(i)$ in a way that non-faulty nodes are prevented to make progress towards convergence." More interesting and also more space consuming (but an idea for a extended version, e.g., for a journal) is the question how standard necessary conditions for Byzantine consensus like n>=3f+1 and 2f+1 connectivity is reflected in your more general setting. Related work: You should really relate your work to the very related earlier attempts to model failures via communication matrices: Starting from Santoro&Widmayer ("Time is not a healer"), there is the perception-based approach by Schmid (e.g. Schmid et al: Impossibility Results and Lower Bounds for Consensus under Link Failures, Widder&Schmid: Booting Clock Synchronization in Partially Synchronous Systems with Hybrid Process and Link Failures) and the Heard-Of-Model by Charron-Bost (e.g. Biely et al: Tolerating corrupted communication) that are even capable of modeling dynamic communication failures (i.e., ones that change from round to round). Related work is also conducted in the control theory and signal processing community (under the term "consensus"), which heavily use approaches based on linear algebra and stochastic processes, see e.g. Sluciak, Hilaire and Rupp: A general formalism for the analysis of distributed algorithms, Int. Conf. Acoustics, Speech and Signal Pr ocessing 2010. Presentation: The way how things are emphasized in definitions and theorems is not consistent. While it seems that in Definition 1, 2, and 4 own definitions are underlined the accentuation of "source component" in Definition 3, Theorem 1, and Section 6 is different. Also I can not explain the reason for the different typesetting of "non-negative" and "*row* stochastic" in Definition 5. Minors: Def.2, second item: "... either ... j does not have a directed path to i in H, OR BOTH". Sec.6.4: Why don't you use the standard term adjacency matrix instead of connectivity matrix? Lemma 6: What is \tau here? Also, in eq.(11), what is k? ----------------------- REVIEW 3 --------------------- PAPER: 82 TITLE: Iterative Approximate Byzantine Consensus under a Generalized Fault Model AUTHORS: Lewis Tseng and Nitin Vaidya Summary of the paper (in a few lines) This paper presents an algorithm to solve approximate agreement in a non fully connected synchronous environment under a generalized fault model.  This fault model is nearly identical to the adversarial structure given by Hirt and Maurer in Complete characterization of adversaries tolerable in secure multi-party computation. (This paper is referenced by one of the references referenced.) They first explicitly state what type of model the algorithm runs in and what the fault model is.  Then they give a specific explanation of what the problem that is to be solved is.  They present an algorithm to solve this problem and then prove its correctness. Reasons to Accept This paper gives a way to do approximate agreement in not fully connected communication graph.  They use a method of proving the algorithms correctness not previously used for byzantine agreement. Reasons to Reject The way the correctness is proved appears to be unnecessarily complex.  The description of the necessary condition appears to also be complex. If I interpret it correctly, it boils down to there is at most one strongly connected component that has no incoming edges.  Also, no mention of computational complexity is given and the construction leads me to believe the computational complexity is exponential. Other Comments In the step two of algorithm 1 on page 7, it says that if no message is received then substitute a default value.  What happens when the default value is outside the convex hull of the values from non-faulty processes?  Will the update step take care of this case? I suspect only if a receipt of no value can come from a faulty process.  I.e., I think receiving no message must mean that process is faulty or the update step can't guarantee that the range it considers is within the convex hull of non-faulty process values.  For the synchronous model considered, receipt of no message does imply the process is faulty, but earlier it is stated that this can be extended to the asynchronous case. In step three of algorithm 1 on page 7, the calculation of $f_1$ and $f_2$ must look through the set $\{ F \cap N_i^- : F \in \mathscr{F}\},$ i.e., the set of all feasible sets intersected with the input set.  Which is potentially exponential is size. No mention of the computational complexity of this algorithm is given.  I would assume that the computation complexity is exponential because the fault domain is potentially exponential in size. For example, the case where any $n/3$ process could be faulty, the faulty domain is exponential. The authors may wish to give a sentence or two somewhere explaining the advantage of this model and algorithm. In the first paragraph of the introduction, the start of the third sentence, should  read "In the presence of..." rather than "In presence of...". Throughout the paper all quotation marks appear to be closing quotes. On page 11, the upper case phi symbol is used for empty set. The symbol usually used is a zero with a diagonal slash through it. (In latex this symbol can be obtained in math mode with \emptyset.) Note that the fault domain may be exponential in size. On page five in definition 2, the two bullet points are part of the definition of being strongly connected components.  This is a bit repetitive.