[Tccc] Jackson Network and Queueing Theory

Prof. Victor Li vli
Tue Nov 15 09:12:51 EST 2011


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: Flaminio Borgonovo 
Sent: Tuesday, November 15, 2011 2:01 AM
To: Prof. Victor Li ; Flaminio Borgonovo ; lachlan.andrew at gmail.com 
Cc: tccc at lists.cs.columbia.edu ; 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] 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. http://home.dei.polimi.it/borgonov/index.html
    2. http://www.eee.hku.hk/research/doc/tr/TR2011003_Queueing_Theory_Revisited.pdf 
    3. 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
  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 http://home.dei.polimi.it/borgonov/index.html

visit  http://www.como.polimi.it/Patria/




More information about the TCCC mailing list