Parent Directory | Revision Log | Revision Graph

Revision **1.2** -
(**hide annotations**)

*Wed Mar 29 09:18:27 2006 UTC*
(12 years, 11 months ago)
by *riso*

Branch:**MAIN**

CVS Tags:**sirocco06-cameraready, HEAD**

Changes since**1.1: +17 -8 lines**

Branch:

CVS Tags:

Changes since

Corrected typos reported by the 3rd reviewer (Richard)

1 | riso | 1.1 | 1: |

2 | |||

3 | The authors introduce a new model for dynamic link failures in the | ||

4 | synchronous setting. It encompasses two previously studied deterministic | ||

5 | models that the authors argue are problematic for opposing reasons. | ||

6 | The first model limits the number of messages lost to an absolute bound | ||

7 | per time step. This encourages sending a large number of messages. The | ||

8 | second model allows a fraction of the messages per step to be lost. In | ||

9 | some situations this encourages sending a small number of messages (since | ||

10 | one is guaranteed to be delivered). Their model combines the two by | ||

11 | using two parameters, one a threshold the second a fraction, where the | ||

12 | number lost is max of threshold and fraction of message sent. This has | ||

13 | the potential of avoiding the two extremes above and of concentrating on | ||

14 | algorithms in between. | ||

15 | |||

16 | Having defined the model, the authors give a large number of results | ||

17 | concerning broadcasting in this model on particular networks as well | ||

18 | as more general results. Some of these results may involve arguments | ||

19 | familiar | ||

20 | from the previous settings but some appear to use new techniques. In | ||

21 | either case, the arguments are non-trivial. | ||

22 | |||

23 | The organization and writing are fairly clear. The new model is likely | ||

24 | to generate a lot of further work as the authors leave plenty of | ||

25 | interesting | ||

26 | open problems. | ||

27 | |||

28 | |||

29 | =========================================================================== | ||

30 | |||

31 | 2: | ||

32 | |||

33 | - The paper only considers the special case that alpha = 1 - epsillon and | ||

34 | T=c(G). The extensive discussion of the more general case (any T) in the | ||

35 | abstract, and the more general model (any T, any alpha) in the introduction | ||

36 | and model is only misleading and confusing. I was confused by this, | ||

37 | believing that you would use the same T to compare different topologies, | ||

38 | and hence couldn't understand why the ring algorithm cannot be used in a | ||

39 | complete graph by sending only on the links of an embedded ring. | ||

40 | |||

41 | The paper would be much better off focusing a priori on the single model | ||

42 | considered therein without the lengthy (misleading and confusing) | ||

43 | discussion of the more general models. The paper is already dense as is, | ||

44 | and hence some effort should be dedicated to helping the reader follow it. | ||

45 | |||

46 | If you want to define the more general model as a direction for future | ||

47 | work, I suggest that you do so at the end of the paper in a | ||

48 | "discussion/future directions" section. | ||

49 | |||

50 | - Since your draconic model does not remedy any of the problems of previous | ||

51 | models so extensively elaborated in the introduction, this whole | ||

52 | discussion should be removed. | ||

53 | |||

54 | Instead, focus the introduction on the model you do study, the challenges | ||

55 | in this model, and the key ideas of the results. | ||

56 | |||

57 | - In the abstract, and in the model paragraph, you say that more than T | ||

58 | must be sent in order to ensure that one is received. Later it turns out | ||

59 | that if you send T this ensures that one is received. | ||

60 | |||

61 | - It is important to explain how the considered simple threshold model | ||

62 | differs from the previously defined cumulative threshold model. | ||

63 | |||

64 | - The introduction makes some claims about consensus, which are of no | ||

65 | relevance to the current paper (dealing with broadcast). The focus on | ||

66 | synchronous models is motivated by the inability to solve consensus in | ||

67 | asynchronous ones. However, reliable broadcast *is* solvable in | ||

68 | asynchronous systems. The introduction further claims that broadcast has | ||

69 | "immediate consequences for ... k-agreement.. ". | ||

70 | What immediate consequences? AFAIK, k-agreement is unsolvable in some | ||

71 | systems where reliable (albeit not atomic) broadcast is solvable. | ||

72 | |||

73 | Again, the paper would greatly benefit from focusing the introduction on | ||

74 | the context of the current paper without making confusing (and imprecise) | ||

75 | statements about other models and problems. | ||

76 | |||

77 | |||

78 | =============================================================================== | ||

79 | |||

80 | 3: | ||

81 | |||

82 | Add the word "fault-tolerant" or something similar in the related theorems. | ||

83 | |||

84 | page 2 lines 3 and 4 the word "drawback" has been repeated twice | ||

85 | line -6 better explain why exactly n-1 | ||

86 | page 6 it is not clear why Algorithm 1 should be working. Please explain it | ||

87 | in better details. | ||

88 | line 5 "send": who sends these messages? | ||

89 | line 12 assume n=5, cycle of line 2 goes from 1 to 2. | ||

90 | consider k=2, thus d=2 | ||

91 | we are then in the else condition and | ||

92 | x=4-4=0, y=2-0=2 | ||

93 | at line 12 you send messages to vertices n-x=5-0=5 | ||

94 | but this vertex does not exist. Please fix | ||

95 | I looked at the proof in the appendix and there you assume | ||

96 | that x>=1 (page IV line -3) which here does not hold | ||

97 | unless I made a mistake. | ||

98 | |||

99 | page 7 better explain the meaning of the different invariants. | ||

100 | E.g., why I1 implies that the last delivered token is green? | ||

101 | Do you mean sent on {a,b}. Could it not be red? A reader should be | ||

102 | convinced of its truth without reading the appendix. | ||

103 | |||

104 | Explain more the general idea of algorithm 2. | ||

105 | line 6 is B=empty at the very beginning? | ||

106 | |||

107 | line -5 how do you select P? | ||

108 | page 10 what is Pz? Where does z appear? | ||

109 | Again better explain algorithm 3. | ||

110 | |||

111 | riso | 1.2 | ========================================================================= |

112 | |||

113 | Done: | ||

114 | |||

115 | 1: | ||

116 | |||

117 | 2: | ||

118 | |||

119 | 3: | ||

120 | |||

121 | line 19 proposed -> propose | ||

122 | line -6 is a -> in a | ||

123 | page 4 line -13 in the -> at the | ||

124 | page 8 algorithm 2 line 3 has -> have | ||

125 | page 9 section 4 line 1 we assume -> we consider k-connected graphs | ||

126 | and we assume | ||

127 | line 7 a dot is missing | ||

128 | riso | 1.1 | page 12 please extend the name of the journals in [6], [11] |

129 | [13] complexity -> Complexity |

CVS Admin">CVS Admin | ViewVC Help |

Powered by ViewVC 1.1.26 |