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

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

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


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