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.