Parent Directory | Revision Log | Revision Graph

Revision **1.5** -
(**show annotations**)

*Wed Aug 8 16:20:04 2007 UTC*
(11 years, 2 months ago)
by *riso*

Branch:**MAIN**

CVS Tags:**HEAD**

Changes since**1.4: +12 -6 lines**

Branch:

CVS Tags:

Changes since

Small fixes

1 | Todo: |

2 | |

3 | - Section 3.1: Part 1 of the algorithm is described at the beginning of |

4 | this section, |

5 | while part 2 is described in the proof of Lemma 2. I propose to describe |

6 | the whole |

7 | algorithm at the beginning of the section. Aditionally, a bit more |

8 | explanation at the end |

9 | of the proof of Lemma 2, why all but one vertex become informed, would be |

10 | very helpful. |

11 | |

12 | |

13 | 8. Algorithm 2 assumes implicitly that vertex 0 is the source vertex, |

14 | but this does not seem to be mentioned anywhere. |

15 | |

16 | - ok |

17 | |

18 | 9. Algorithm 2. Wouldn't this algorithm work also if there where only |

19 | two steps in each round, that is, j = 1,2 ? |

20 | |

21 | 10. Corollary 1. The "complete graphs with neighboring sense of |

22 | direction" should be defined. |

23 | |

24 | |

25 | |

26 | --- Review #1 ---------------------------------------------------------------------------- |

27 | |

28 | - I found the discussion in Section 3.2 on unoriented complete graphs to |

29 | be somewhat confusing. On the bottom of page 10 you state that “Each token |

30 | carries all information about itself and its ancestors (i.e. IDs of its |

31 | ancestors, traversed vertices and traversed ports).” Is the information |

32 | about traversed vertices also encoded as their IDs? I would assume so as |

33 | there is no other way of identifying them as you only assume that vertices |

34 | have local port orientations. |

35 | |

36 | R: Should be better now. |

37 | |

38 | - On page 11, the confusion is slightly compounded by a statement like |

39 | “an oriented edge a, b .” I assume this “orientation” is with respect to a |

40 | given token at a given vertex (where the incoming port number is b and a |

41 | denotes the port number on the other end of that edge). It’s just that the |

42 | unfortunate use of the word “oriented” clashes with the supposition that |

43 | the complete graph is now unoriented. Presumably, these pairs of the form |

44 | a, b are how the information about “traversed ports” is tracked and would |

45 | therefore allow one to reconstruct a path in the graph. |

46 | |

47 | R: Should be better now. |

48 | |

49 | - In any event, I found myself wanting some sort of example here to help |

50 | me determine exactly what the authors intended in their explanations. If |

51 | the mean- ing is similar to that in the section on k-connected graphs |

52 | without topological knowledge, I would suggest that they rewrite this ﬁrst |

53 | part as I seemed to be able to more fully follow the part about k-connected |

54 | graphs. |

55 | |

56 | R: Should be better now. |

57 | |

58 | --- Review #2 ---------------------------------------------------------------------------- |

59 | |

60 | - The style and organization of the paper are good. However, the algorithms |

61 | in Sections 3.2 and 4.2 are not well described, and hard to understand. I |

62 | recommend acceptance if these two parts are rewritten, and the authors take |

63 | into consideration the specific remarks given below. |

64 | |

65 | ok |

66 | |

67 | - Abstract: The results concerning the hypercube should not be included in |

68 | the abstract. These results are directly obtained from the proofs and |

69 | results on arbitrary graphs. |

70 | |

71 | Hyperkocky obnasaju optimalizaciu, nechal by som to tam. |

72 | |

73 | - Algorithm 1: A description of dir-to-init would be helpful here. One can |

74 | guess what the |

75 | authors mean, however, the description of the algorithm is not |

76 | self-contained. |

77 | |

78 | Je to premenna, je inicializovana tam, kde ma byt. Ignore. |

79 | |

80 | - For the case when the graph G is a cycle, or ring, I think the |

81 | exposition would be slightly easier to follow if the author’s gave the |

82 | explanation that appears on page 7 ﬁrst, and then gave the algorithm on |

83 | page 6 after that, i.e., put the steps labeled 1-4 on page 7 before the |

84 | more formal description of the algorithm that’s shown on page 6. |

85 | |

86 | ok |

87 | |

88 | - Section 3.1: Part 1 of the algorithm is described at the beginning of |

89 | this section, |

90 | while part 2 is described in the proof of Lemma 2. I propose to describe |

91 | the whole |

92 | algorithm at the beginning of the section. Aditionally, a bit more |

93 | |

94 | - added subsubsections, should be ok. |

95 | |

96 | explanation at the end |

97 | of the proof of Lemma 2, why all but one vertex become informed, would be |

98 | very helpful. |

99 | |

100 | - improved formulation, should be ok. |

101 | |

102 | |

103 | - Section 3.2: I did not understand the algorithm in detail. Using the |

104 | ideas described in |

105 | this section one can develop an algorithm, but I still do not know whether |

106 | my algorithm |

107 | is the same as the algorithm of the authors. A formal description of the |

108 | whole algorithm |

109 | together with an example would be very helpful. |

110 | |

111 | Snad ok. |

112 | |

113 | - Section 4.2: I could not understand the algorithm described in this |

114 | section. First, the |

115 | authors talk about red and green edges and define K(a) as the knowledge of |

116 | node a. |

117 | However, this is not used in the description of the algorithm. |

118 | Additionally, they claim |

119 | that all edges in the chosen k-edge disjoint paths are red, excepting the |

120 | last edges, but |

121 | I do not understand, how can the initiator node only know far edges without |

122 | knowing the |

123 | local edges. For clarity, this part has to be rewritten. An example would |

124 | also be helpful. |

125 | |

126 | Snad ok. |

127 | |

128 | --- Review #3 ---------------------------------------------------------------------------- |

129 | |

130 | 1. No page numbers make it difficult to refer to particular |

131 | sentences/lines! |

132 | |

133 | ok |

134 | |

135 | 2. In 3rd paragraph above Section 1.2: it is not clear what the term |

136 | "omissions" refers to. |

137 | |

138 | ok |

139 | |

140 | 3. Sec. 1.2, in 1st paragraph, "... the algorithm has to send at least |

141 | T messages in a time step t in order to have any guarantees about the |

142 | number of faults." This wording looks somewhat ackward. Maybe "to have |

143 | any guarantee about the number of of messages delivered"? |

144 | |

145 | ok |

146 | |

147 | 4. Section 1.3. Do "Round" and "step" refer to the same basic time |

148 | unit? In other parts of the paper, for example in Sec. 3.1 and 4.2, |

149 | one round consists of a number of steps. |

150 | |

151 | ok |

152 | |

153 | 5. Section 2, 4th paragraph. A remark that the passive nodes continue |

154 | participating in sending messages might be helpful. |

155 | |

156 | ok |

157 | |

158 | 6. Section 2, 4th paragraph, Shouldn't the definition of active and |

159 | passive vertices be more precise? A vertex is active in the current |

160 | phase, if and only if it has received a message from only one of its |

161 | neighbors in _previous_ phases (according to the pseudocode Algorithm |

162 | 1, a vertex changes its state only at the end of a phase). |

163 | |

164 | ok |

165 | |

166 | 7. Sec. 2. The paragraph "If n is unknown ...". "In the second part |

167 | of the algorithm v broadcasts n ..." Can the second broadcast be |

168 | initiated by more than one vertex v? There could be two vertices v1 |

169 | and v2 which have received discover messages from both directions: v1 |

170 | and v2 are adjacent, v1 receives a discover message from its left |

171 | neighbor x =/= v2, v2 receives a discover message from its right |

172 | neighbor z, and then v1 and v2 send discover messages to each other in |

173 | the same step. |

174 | |

175 | snad ok |

176 | |

177 | 8. Algorithm 2 assumes implicitly that vertex 0 is the source vertex, |

178 | but this does not seem to be mentioned anywhere. |

179 | |

180 | ok |

181 | |

182 | 9. Algorithm 2. Wouldn't this algorithm work also if there where only |

183 | two steps in each round, that is, j = 1,2 ? |

184 | |

185 | 10. Corollary 1. The "complete graphs with neighboring sense of |

186 | direction" should be defined. |

187 | |

188 | 11. Sec. 4.2. The description of the algorithm refers to forward-active |

189 | and backwatrd-active ports, while the pseudocode "Algorithm 5" refers |

190 | to active ports. Is an active port a port which is either |

191 | forward-active and backwatrd-active? |

192 | |

193 | ok |

CVS Admin">CVS Admin | ViewVC Help |

Powered by ViewVC 1.1.26 |