[Tccc] Jackson Network and Queueing Theory
Flaminio Borgonovo
borgonov
Wed Nov 16 09:11:43 EST 2011
Dear Victor and Guang-Lian,
after refreshing some logical definitions,
the issue has become, to me, simpler than I thought:
in your notation the first statement of the theorem writes
1. V(X,Y)=FALSE
This does not mean a logical implication. To demonstrate
a logical implication you should also demonstrate the entire table of
thruth:
2 V(X,Y')=TRUE
3 V(X',Y')=TRUE
4 V(X',Y)=TRUE
Although I'm convinced that 2 holds , 2 is not automatically implied
by 1.
On the contrary 3 is not likely to hold.
Furthermore, 4 is the very statement you want to prove.
Then, you can not assume logical implication. By assuming it,
you assume what you want to prove.
This, I think, is what Lachlan implied in his first messages.
Similarly,
6. V(Y',X')=FALSE
does not mean
7 V(Y',X)=TRUE
regards,
Flaminio
At 15.12 15/11/2011, Prof. Victor Li wrote:
Dear Flaminio,
An implication is equivalent to its contrapositive.
If two implications are not equivalent, then their
contrapositives are not necessarily equivalent.
Please allow us to continue using our
notations in the following clarification.
We use X and Y to represent P(B) = 1 and
P(S) = 0, respectively. From V(T, F) = F
we have V'(T, F) = F where V' is the
contrapositive of V, and V'(T, F) = F
means "the value of V'(X' Y') is F when
(X', Y') = (T, F) with X' and Y' representing
P(S) = 1 and P(B) = 0, respectively.
Your argument concerns the contrapositive of
V(X, X'). Since V(X, X') and V(X, Y) are
not equivalent, the contrapositive of V(X, Y)
and the contrapositive of V'(X, X') are not
equivalent.
You also said that you agreed with Lachlan that V(X,Y) = F is
not applicable to all queues in the set \cal G.
This is incorrect. Please see the reply to Lachlan in the previous
email.
Best regards,
Guang-Liang and Victor
From: [1]Flaminio Borgonovo
Sent: Tuesday, November 15, 2011 2:01 AM
To: [2]Prof. Victor Li ; [3]Flaminio Borgonovo ;
[4]lachlan.andrew at gmail.com
Cc: [5]tccc at lists.cs.columbia.edu ; [6]glli at eee.hku.hk
Subject: Re: [Tccc] Jackson Network and Queueing Theory
Dear Victor,
I'm afraid your argument below does not catch my point. Below You
list
what is known as "Table of implications" and conclude that
<< If one lets the value of "P(B) = 1" be "true", then one must
let the value of "P(S) = 0" >>
I never constested the above statement (although I agree with
Lachlan that it is not applicable to all queues in the set \cal G)
I only contested the use of the contrapositive argument that has
led you to affirm, in theorem 1, that the following statrement is
also true
<< P(S)=1 implies P(B)=1>>. I think you cannot logically derive
this last statement from the former.
I restate below my argument, expliciting the attribute TRUE where
I have assumed it by default
Assume:
<<P(B)=1 implies P(S)=0>> is false.
Therefore we must derive:
P(B)=1 implies P(S)=1 is TRUE
Its contrapositive statement, should be
P(S)=0 implies P(B)=0, TRUE
and not, as sustained in the paper,
P(S)=1 implies P(B)=0, FALSE , or P(S)=1 implies P(B)=1 TRUE.
best regards
Flaminio
At 05.51 14/11/2011, Prof. Victor Li wrote:
Dear Lachlan and Flaminio,
Thanks for your comments. Let V(X, Y) stand for
"X implies Y", a logical implication statement in general.
Write (X, Y) = (T, F) to mean "the value of X is T (true) and
the value of Y is F (false)". Let V(T, F) = F represent
"the value of V(X, Y) is F when (X, Y) = (T, F)".
Smilarly, V(F, F) = V(F, T) = V(T, T) = T.
In fact, V(T, F) = F and V(F, F) = V(F, T) = V(T, T) = T
correspond to the truth table values of the implication, and
V(T, F) = F is completely determined by (X, Y) = (T, F)
regardless of what X or Y means. Any other assumption
is unnecessary for V(T, F) = F.
Unless one is reasoning with a different logic,
V(T, F) = F is just fine both in general and in particular
when X and Y represent P(B) = 1 and P(S) = 0, respectively.
If one lets the value of "P(B) = 1" be "true", then one must
let the value of "P(S) = 0" be "false" because a queue with a.s.
bounded waiting time is not unstable.
Best regards,
Guang-Liang and Victor
-----Original Message----- From: Flaminio Borgonovo
Sent: Saturday, November 12, 2011 7:41 AM
To: Prof. Victor Li
Cc: tccc at lists.cs.columbia.edu ; glli at eee.hku.hk
Subject: Re: [Tccc] Jackson Network and Queueing Theory
Hi Victor and Guang-Liang,
I think the contrapositive argument in Theorem 1 of your
paper is
misused, as Lachlan suspects.
The proof of Theorem 1 shows that statement <<P(B)=1 implies
P(S)=0>>
is false. Therefore we must assume:
P(B)=1 implies P(S)=1 (bounded waiting times ----> stable
queue).
Its contrapositive statement, still true, should be
P(S)=0 implies P(B)=0, (unstable queue ----> unbounded waiting
times)
and not, as sustained in the paper,
P(S)=1 implies P(B)=1, (stable queue ----> bounded waiting
times).
Therefore P(B)=1 for stable queues is not proved. And classic
theory,
where it can be also P(S=1) and P(B)=0 (stable queue and
unbounded
waiting times), is not invalidated.
This seems to invalidate Theorem 1 and the whole paper.
Regards,
Flaminio
Prof. Flaminio Borgonovo
Dip. di Elettronica e Informazione
Politecnico di Milano
P.zza L. Da Vinci 32
20133 Milano, Italy
tel. 39-02-2399-3637
fax. 39-02-2399-3413
e-mail: borgonov at elet.polimi.it
URL [1] [7]http://home.dei.polimi.it/borgonov/index.html
On 10 November 2011 18:18, Prof. Victor Li <vli at eee.hku.hk>
wrote:
> Dear colleagues,
>
> Nearly a decade ago we initiated a discussion about Jackson
networks
of queues
> on this mailing list. Since then some colleagues have enquired
about
our follow-up
> research regarding this issue. A recent paper by us is now
available
> as a technical report at the website below:
>
>
[2]http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_
Rev
isited.pdf
>
> In this paper we consider the stability of queues. We find that
> the condition given in the literature, i.e., the traffic
intensity
is less
> than 1, is only necessary but not sufficient for a general
single-server queue to be
> stable. This shows again that product-form solutions of Jackson
networks
> are incorrect for such networks are actually unstable.
> In the paper we also give necessary and sufficient conditions
for a
G/G/1 queue to
> be stable, and discuss the implications of our results.
>
> Queueing theory has been widely used in performance analysis of
computer and
> communication systems. Colleagues who are teaching courses on
performance
> analysis or doing research in this area, and students who are
learning how to apply
> queueing theory to performance analysis, might be interested in
our
results.
> Comments on our paper are very much appreciated and can be sent
to
us by
> e-mail. Thank you very much for your attention.
>
> Best regards,
>
> Guang-Liang Li and Victor O.K. Li
> _______________________________________________
> IEEE Communications Society Tech. Committee on Computer
Communications
> (TCCC) - for discussions on computer networking and
communication.
> Tccc at lists.cs.columbia.edu
> [3]https://lists.cs.columbia.edu/cucslists/listinfo/tccc
>
References
1. [8]http://home.dei.polimi.it/borgonov/index.html
2.
[9]http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_
Revisited.pdf
3. [10]https://lists.cs.columbia.edu/cucslists/listinfo/tccc
_______________________________________________
IEEE Communications Society Tech. Committee on Computer
Communications
(TCCC) - for discussions on computer networking and communication.
Tccc at lists.cs.columbia.edu
[11]https://lists.cs.columbia.edu/cucslists/listinfo/tccc
Prof. Flaminio Borgonovo
Dip. di Elettronica e Informazione
Politecnico di Milano
P.zza L. Da Vinci 32
20133 Milano, Italy
tel. 39-02-2399-3637
fax. 39-02-2399-3413
e-mail: borgonov at elet.polimi.it
URL [12]http://home.dei.polimi.it/borgonov/index.html
visit [13]http://www.como.polimi.it/Patria/
Prof. Flaminio Borgonovo
Dip. di Elettronica e Informazione
Politecnico di Milano
P.zza L. Da Vinci 32
20133 Milano, Italy
tel. 39-02-2399-3637
fax. 39-02-2399-3413
e-mail: borgonov at elet.polimi.it
URL [14]http://home.dei.polimi.it/borgonov/index.html
visit [15]http://www.como.polimi.it/Patria/
References
1. mailto:borgonov at elet.polimi.it
2. mailto:vli at eee.hku.hk
3. mailto:borgonov at elet.polimi.it
4. mailto:lachlan.andrew at gmail.com
5. mailto:tccc at lists.cs.columbia.edu
6. mailto:glli at eee.hku.hk
7. http://home.dei.polimi.it/borgonov/index.html
8. http://home.dei.polimi.it/borgonov/index.html
9. http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_Revisited.pdf
10. https://lists.cs.columbia.edu/cucslists/listinfo/tccc
11. https://lists.cs.columbia.edu/cucslists/listinfo/tccc
12. http://home.dei.polimi.it/borgonov/index.html
13. http://www.como.polimi.it/Patria/
14. http://home.dei.polimi.it/borgonov/index.html
15. http://www.como.polimi.it/Patria/
More information about the TCCC
mailing list