Waiting time dynamics of priority-queue networks

被引:27
作者
Min, Byungjoon [1 ]
Goh, K. -I. [1 ]
Kim, I. -M. [1 ]
机构
[1] Korea Univ, Dept Phys, Seoul 136713, South Korea
关键词
protocols; queueing theory; task analysis; HEAVY TAILS; IMPACT; MEMORY;
D O I
10.1103/PhysRevE.79.056110
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
We study the dynamics of priority-queue networks, generalizations of the binary interacting priority-queue model introduced by Oliveira and Vazquez [Physica A 388, 187 (2009)]. We found that the original AND-type protocol for interacting tasks is not scalable for the queue networks with loops because the dynamics becomes frozen due to the priority conflicts. We then consider a scalable interaction protocol, an OR-type one, and examine the effects of the network topology and the number of queues on the waiting time distributions of the priority-queue networks, finding that they exhibit power-law tails in all cases considered, yet with model-dependent power-law exponents. We also show that the synchronicity in task executions, giving rise to priority conflicts in the priority-queue networks, is a relevant factor in the queue dynamics that can change the power-law exponent of the waiting time distribution.
引用
收藏
页数:5
相关论文
共 26 条
[1]   Statistical mechanics of complex networks [J].
Albert, R ;
Barabási, AL .
REVIEWS OF MODERN PHYSICS, 2002, 74 (01) :47-97
[2]   PUNCTUATED EQUILIBRIUM AND CRITICALITY IN A SIMPLE-MODEL OF EVOLUTION [J].
BAK, P ;
SNEPPEN, K .
PHYSICAL REVIEW LETTERS, 1993, 71 (24) :4083-4086
[3]   The origin of bursts and heavy tails in human dynamics [J].
Barabási, AL .
NATURE, 2005, 435 (7039) :207-211
[4]   Modeling human activity in the spirit of Barabasi's queueing systems [J].
Blanchard, Ph. ;
Hongler, M. -O. .
PHYSICAL REVIEW E, 2007, 75 (02)
[5]  
Caldarelli G., 2007, SCALE FREE NETWORKS
[6]   Uncovering individual and collective human dynamics from mobile phone records [J].
Candia, Julian ;
Gonzalez, Marta C. ;
Wang, Pu ;
Schoenharl, Timothy ;
Madey, Greg ;
Barabasi, Albert-Laszlo .
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2008, 41 (22)
[7]   PRIORITY ASSIGNMENT IN WAITING LINE PROBLEMS [J].
COBHAM, A .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1954, 2 (01) :70-76
[8]   Invasion percolation and critical transient in the Barabasi model of human dynamics [J].
Gabrielli, A. ;
Caldarelli, G. .
PHYSICAL REVIEW LETTERS, 2007, 98 (20)
[9]   Burstiness and memory in complex systems [J].
Goh, K.-I. ;
Barabasi, A.-L. .
EPL, 2008, 81 (04)
[10]   Human dynamics revealed through Web analytics [J].
Goncalves, Bruno ;
Ramasco, Jose J. .
PHYSICAL REVIEW E, 2008, 78 (02)