ViewVC logotype

Contents of /bcast-fraction-threshold/referee-3.txt

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph

Revision 1.1 - (show annotations)
Fri Feb 27 12:42:38 2009 UTC (10 years ago) by riso
Branch: MAIN
File MIME type: text/plain
3rd referee report added

1 Manuscript Number: TCS-D-07-00352R2
2 Manuscript Title: Rapid Almost-Complete Broadcasting in Faulty Networks
3 Author(s): Rastislav Kralovic; Richard Kralovic
4 Submitted to: Theoretical Computer Science
7 Dear Mr. Richard Kralovic,
9 Referees have evaluated your paper mentioned above. Comments are
10 below. On the basis of these comments, the member of the Editorial
11 Board handling your paper has decided that a moderate revision is
12 needed before your paper can be considered for publication. I would
13 appreciate it if you could revise your paper within two months of this
14 email.
16 I look forward to receiving the revised version of your paper. You
17 should explain how and where the reviewers' comments have been
18 addressed by your changes to the text (overview of changes). Should
19 you disagree with some of these comments, please explain why.
21 To upload the source file (LaTeX, or Word) of the revised paper and
22 the overview of changes, please log-in to the system at
23 http://ees.elsevier.com/tcs/ with
24 username: Your username is: richard.kralovic
25 password: Your password is: kralovic365568
26 selecting the 'Author' button.
28 Kind regards,
29 Shmuel Zaks
30 Managing Guest Editor
31 Theoretical Computer Science
36 By reading the author answer and the revised version of the paper, my
37 main question
38 For the problem of broadcasting in Complete Graphs and Hypercubes, is
39 the asymp-
40 totic time complexity under the fractional with threshold (equal to
41 degree -1) model
42 indeed different from that of the same problem under the fractional
43 model?
44 does not get any definite answer, as also stated by the authors:
45 "we admit that we can not prove that the model with threshold is
46 actually "harder",
47 i.e. that there is an example of a problem whose time complexity in
48 the thresholded
49 model is higher that in the fractional (taking into account all
50 messages as opposed to
51 the model of [22]). It might be that using more advanced
52 techniques one can prove
53 that the threshold indeed does not influence the computation too
54 much."
55 The points toward studying such a problem in the fractional with
56 threshold model raised by the
57 authors are
58 * That the only previous paper on the fractional model
59 [22] R. Kralovic, R. Kralovic, and P. Ruzicka. Broadcasting with many
60 faulty links. In J.
61 F. Sibeyn, editor, SIROCCO, volume 17 of Proceedings in Informatics,
62 2003.
63 imposes a further restriction on the fractional model: It applies the
64 possibility of having a
65 fraction of lost messages only to those messages sent to "uninformed"
66 nodes instead than to
67 all the sent messages (which I find a questionable assumption, but
68 outside this discussion).
69 * Some proof gets more complicate introducing the threshold, e.g., as
70 * the authors say
71 "the existence of threshold adds the difficulty of making sure that
72 there are
73 enough messages in every step. Since there is no a-priori notification
74 mechanism,
75 the number of sent messages must be controlled more carefully."
76 In this scenario, I am still dubious on the use of this model to study
77 the uncomplete broad-
78 casting problem .
79 While the paper contains some ideas and new results that are
80 interesting, I do not agree on a
81 paper where the first question of the reader "is the model really new
82 for the studied problem?"
83 has no answer.
84 In my opinion it would have been much more interesting to apply the
85 ideas of the paper to study
86 the broadcasting problem (what can be done and what cannot be done) in
87 the threshold model
88 with the threshold applied to ALL sent messages.
89 Should the paper be accepted, it has at least to state clearly an OPEN
90 PROBLEM saying that
91 the asymptotic time complexity under the fractional with threshold
92 (equal to degree -1) model IS
93 NOT KNOWN to be different from that of the same problem under the
94 fractional model.
95 1

CVS Admin">CVS Admin
ViewVC Help
Powered by ViewVC 1.1.26