/[cvs]/bcast-kanada/reviewer-comments-tcs
ViewVC logotype

Contents of /bcast-kanada/reviewer-comments-tcs

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph


Revision 1.5 - (show annotations)
Wed Aug 8 16:20:04 2007 UTC (11 years, 4 months ago) by riso
Branch: MAIN
CVS Tags: HEAD
Changes since 1.4: +12 -6 lines
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 first
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 first, 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