/[cvs]/bcast-fraction-threshold/response_to_referee_2.tex
ViewVC logotype

Diff of /bcast-fraction-threshold/response_to_referee_2.tex

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

revision 1.1 by kralovic, Thu Jul 31 22:01:52 2008 UTC revision 1.2 by riso, Mon Aug 4 17:43:43 2008 UTC
# Line 29  Line 29 
29  \vskip 1cm  \vskip 1cm
30    
31  \begin{enumerate}  \begin{enumerate}
32  \item {\bf fractional vs. fractional with threshold models}  \item {\bf ``Fractional'' vs. ``Fractional with threshold'' models}
33    
34  \noindent  \noindent
35  There are two points to be stressed here: first, there are no acknowledgements (i.e. the sender does not know which message was delivered), and  There are two points to be stressed here: first, there are no acknowledgements (i.e. the sender does not know which message was delivered), and
36  second, we are dealing with a distributed scenario. This is a different setting from the one from paper [22] in references where the messages were  second, we are dealing with a distributed scenario. This is a different setting from the one from paper [22] in references where the messages were
37  a-priori sent only to uninformed vertices (which corresponds to either a centralized scenario, or some  a-priori sent only to uninformed vertices (which corresponds to either a centralized scenario, or some
38  system of acknowledgemets).  system of acknowledgements).
39    
40  In particular, it is not true that if $\lfloor\alpha m\rfloor\le c(G)-1$ where $m$ is the number of messages  In particular, it is not true that if $\lfloor\alpha m\rfloor\le c(G)-1$ where $m$ is the number of messages
41  sent in this particular step, then at least one {\em new vertex} is reached (as stated in the review  sent in this particular step, then at least one {\em new vertex} is reached (as stated in the review
# Line 44  Line 44 
44    
45  As for the comparison of the fractional, and fractional with threshold models, there are no known results. On one hand, if the topology is known to the vertices,  As for the comparison of the fractional, and fractional with threshold models, there are no known results. On one hand, if the topology is known to the vertices,
46  one can easily  one can easily
47  construct an example of a graph (e.g. a caterpilar) where optimal broadcast in the fractional model would send a single message in every of the  construct an example of a graph (e.g. a caterpillar) where optimal broadcast in the fractional model would send a single message in every of the
48  first few steps in order to inform a ''cirtical path'' (recall that one message is guaranteed to be delivered); this is not possible in  first few steps in order to inform a ''critical path'' (recall that one message is guaranteed to be delivered); this is not possible in
49  the fractional model with threshold which leads to a slower broadcast. On the other hand, one might possibly argue that  the fractional model with threshold which leads to a slower broadcast. On the other hand, one might possibly argue that
50  if the topology is not known to the vertices, no such strategy is possible, and the best strategy in the fractional model  if the topology is not known to the vertices, no such strategy is possible, and the best strategy in the fractional model
51  requires sending many messages; the models would be more-or-less the same then.  requires sending many messages; the models would be more-or-less the same then.
52    
53  Even if the latter  Even if the latter
54  was true, there are no results concerning broadcasting in fractional model in the distributed setting without acknowledgemets.  was true, there are no results concerning broadcasting in fractional model in the distributed setting without acknowledgements.
55    
56  To help readers to settle this issue, we stressed more the difference in settings between paper [22] and this, and the lack of acknowledgements.  To help readers to settle this issue, we stressed more the difference in settings between paper [22] and this, and the lack of acknowledgements.
57    
58    
59  \item {\bf lack of motivation}  \item {\bf Lack of motivation}
60    
61  \noindent  \noindent
62  We included a more detailed discussion about the motivation.  We included a more detailed discussion about the motivation.
63    
64  \item {\bf use of $T$ in the definition of the model}  \item {\bf Use of $T$ in the definition of the model}
65    
66  \noindent  \noindent
67  We changed the wording of abstract. In the definition it is explicitly stated that $T$ is always assumed to be $c(G)-1$.  We changed the wording of abstract. In the definition it is explicitly stated that $T$ is always assumed to be $c(G)-1$.
68    
69  \item {\bf statement of Lemma 1}  \item {\bf Statement of Lemma 1}
70    
71  \noindent  \noindent
72  The statement of Lemma 1 holds for any (integer) $n>0$. This has been added to the  The statement of Lemma 1 holds for any (integer) $n>0$. This has been added to the
73  claim of the Lemma.  claim of the Lemma.
74    
75  \item {\bf p.7, l-7: derivation of the limit}  \item {\bf P.7, l-7: derivation of the limit}
76    
77  \noindent  \noindent
78  The derivation of the limit is straightforward, using well-known standard  The derivation of the limit is straightforward, using well-known standard
# Line 84  Line 84 
84  $$ \lim_{n\to\infty}1/2\frac{4X(1-2/n)}{1+\sqrt{1-4X(1/n-2/n^2)}} = X$$  $$ \lim_{n\to\infty}1/2\frac{4X(1-2/n)}{1+\sqrt{1-4X(1/n-2/n^2)}} = X$$
85  We opted not to include these standard steps in the paper.  We opted not to include these standard steps in the paper.
86    
87  \item {\bf numbers $\ell$ and $r$ in Lemmata 1 and 2, respectively}  \item {\bf Numbers $\ell$ and $r$ in Lemmata 1 and 2, respectively}
88    
89  \noindent  \noindent
90  Formally speaking, $r$ in Lemma 2 denotes the number of delivered messages, whereas $\ell$ in Lemma 1 denotes the number  Formally speaking, $r$ in Lemma 2 denotes the number of delivered messages, whereas $\ell$ in Lemma 1 denotes the number
91  of informed vertices. However, given the context of their usage, the quantities are almost identical, so we changed $\ell$ to $r$  of informed vertices. However, given the context of their usage, the quantities are almost identical, so we changed $\ell$ to $r$
92  in Lemma 1  in Lemma 1.
93    
94  \item {\bf Lemma 4 is trivial}  \item {\bf Lemma 4 is trivial}
95    
Legend:
Removed from v.1.1  
changed lines
  Added in v.1.2
CVS Admin">CVS Admin
 ViewVC Help
Powered by ViewVC 1.1.26