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 |
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 |
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 |
|
|