Parent Directory | Revision Log | Revision Graph

Revision **1.2** -
(**show annotations**)

*Wed Mar 29 09:18:27 2006 UTC*
(12 years, 6 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 | 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 | ========================================================================= |

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