Parent Directory | Revision Log | Revision Graph

Revision **1.1** -
(**show annotations**)

*Fri Feb 27 12:42:38 2009 UTC*
(9 years, 10 months ago)
by *riso*

Branch:**MAIN**

CVS Tags:**HEAD**

File MIME type: text/plain

Branch:

CVS Tags:

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 |

5 | |

6 | |

7 | Dear Mr. Richard Kralovic, |

8 | |

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. |

15 | |

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. |

20 | |

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. |

27 | |

28 | Kind regards, |

29 | Shmuel Zaks |

30 | Managing Guest Editor |

31 | Theoretical Computer Science |

32 | |

33 | |

34 | Comments: |

35 | |

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 |

96 |

CVS Admin">CVS Admin | ViewVC Help |

Powered by ViewVC 1.1.26 |