Parent Directory | Revision Log | Revision Graph

Revision **1.5** -
(**hide annotations**)

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

Branch:**MAIN**

CVS Tags:**HEAD**

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

Branch:

CVS Tags:

Changes since

Small fixes

1 | riso | 1.2 | Todo: |

2 | |||

3 | riso | 1.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 | riso | 1.5 | |

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

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

15 | |||

16 | riso | 1.5 | - ok |

17 | |||

18 | riso | 1.3 | 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 | riso | 1.2 | |

26 | riso | 1.1 | --- 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 | riso | 1.2 | R: Should be better now. |

37 | riso | 1.1 | |

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 | riso | 1.2 | R: Should be better now. |

48 | riso | 1.1 | |

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 | riso | 1.2 | R: Should be better now. |

57 | riso | 1.1 | |

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 | riso | 1.3 | ok |

66 | riso | 1.1 | |

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 | riso | 1.3 | Hyperkocky obnasaju optimalizaciu, nechal by som to tam. |

72 | riso | 1.1 | |

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 | riso | 1.3 | Je to premenna, je inicializovana tam, kde ma byt. Ignore. |

79 | riso | 1.1 | |

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 | riso | 1.3 | 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 | riso | 1.5 | |

94 | - added subsubsections, should be ok. | ||

95 | |||

96 | riso | 1.3 | 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 | riso | 1.5 | - improved formulation, should be ok. |

101 | |||

102 | |||

103 | riso | 1.3 | - 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 | riso | 1.5 | ok |

165 | riso | 1.3 | |

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 | riso | 1.4 | snad ok |

176 | |||

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

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

179 | |||

180 | riso | 1.5 | ok |

181 | |||

182 | riso | 1.3 | 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 | riso | 1.4 | |

193 | ok |

CVS Admin">CVS Admin | ViewVC Help |

Powered by ViewVC 1.1.26 |