Numerical study on the deadline-concerning priority queuing model

Hang-Hyun Jo [email protected] Department of Physics, The Catholic University of Korea, Bucheon 14662, Republic of Korea

Abstract

The Barabási’s priority queuing model [A.-L. Barabási, Nature 435, 207 (2005)] and its variants have been extensively studied to understand heavy-tailed distributions of the inter-event times and the response times observed in various empirical analyses of human dynamics. In this paper, we focus on the effects of deadlines assigned to the tasks in a queue of fixed size on the response-time distributions. Here, the response time is defined as the time interval between the arrival and the execution of the task. We propose a deadline-concerning priority queuing model, in which as the deadline approaches, the priority is adjusted using the inverse of the remaining time to the deadline. By performing the numerical simulations, we find that the power-law exponent characterizing the response-time distributions is less than $1$ under the deterministic selection protocol while it has the value of $1$ under the nondeterministic selection protocol.

I Introduction

Recently, a huge amount of digital data on human activities and social interaction has enabled us to explore human behavior in an unprecedented way [1]. Among many other topics, non-Poissonian or heterogeneous temporal patterns of human individuals have been extensively studied for last few decades in terms of bursty human dynamics [2]. The bursty temporal patterns have been characterized by using heavy-tailed distributions of inter-event times and response times. Here, the inter-event time denotes the time interval between two consecutive events in the event sequence while the response time denotes the time interval between arrival and execution of, e.g., a task in the queue. Barabási reported in his seminal paper [3] that both the inter-event times and the response times for an individual email user follow a heavy-tailed distribution such as $P(\tau)\sim\tau^{-\alpha}$ with $\alpha\approx 1$ , where $\tau$ denotes either the inter-event time or the response time. Since then, a wide range of values of $\alpha$ have been reported based on analyses of a number of empirical datasets for human social phenomena; for example, the value of $\alpha$ ranges from $0.7$ [4, 5] up to $3$ [6] for mobile phone communications. For a summary of such empirical results, one can refer to Tables in Chapter 3 of Ref. [2] and references therein.

To understand the origin of heavy tails in the distributions of the inter-event times and the response times observed in the email communication dataset, Barabási proposed a priority queuing model with a queue of fixed size [3]: An individual is assumed to have a list of $L$ tasks, each of which is assigned a priority that is randomly drawn from a certain priority distribution. At each time step, with a probability $p$ , the task with the highest priority is selected; otherwise, with a probability $1-p$ , one of $L$ tasks is uniformly and randomly selected. The selected task is executed and removed from the list, and a new task with a random priority arrives at the list. The time interval between the arrival and the execution of the task defines the response time. Due to the task selection protocol based on the priority assigned to the tasks, some tasks with low priority have to wait longer for execution than those with high priority, leading to a power-law distribution of response times with the power-law exponent $\alpha=1$ . Note that $\alpha=1$ is obtained only when $p\to 1$ . Later, this model was exactly solved for the case with $L=2$ [7, 8], as well as for the general $L$ case [9].

A number of variants of the Barabási’s priority queuing model have also been studied to understand the diverse scaling behaviors observed in various empirical analyses [10, 11, 12, 13, 14, 15, 16, 17, 2, 18, 19]. For example, a time-varying priority of the task was considered to understand the editorial review processes of papers published in Physical Review journals [20]. The priority of the task can vary depending on the context or situation. One common situation in real life is the deadline assigned to the task. The effects of a deadline for the conference on the registration behavior have been empirically studied [21, 22, 23] while how such deadlines affect the response-time distribution for the tasks has not yet been fully explored, to our knowledge. In this paper, to understand the effects of deadlines assigned to the tasks in a queue of fixed size on the response-time distribution, we introduce a deadline-concerning priority queuing model and numerically study the model to find the scaling behavior of the response-time distributions.

II Model

Refer to caption — Figure 1: Definition of the terms for task $i$ used in the model: Task $i$ with a random priority $x_{i}$ and a random relative deadline $d_{i}$ arrives in time $t_{i}$ and is executed in time $t^{\prime}_{i}$ . Note that the absolute deadline is given as $a_{i}=t_{i}+d_{i}$ and that the response time is defined as $\tau_{i}=t^{\prime}_{i}-t_{i}$ .

We study the effects of the deadlines assigned to the tasks on their response times. We consider a model for a queue with a fixed size $L$ . Each task $i$ ( $i=1,\ldots,L$ ) in the queue arrives in discrete time $t_{i}$ with a random priority $x_{i}$ and a random relative deadline $d_{i}$ , leading to the absolute deadline being given as $a_{i}=t_{i}+d_{i}$ (see Fig. 1). Note that $d_{i}$ is a positive integer and that $t_{i}=0$ for tasks that are initially given. The priority and the relative deadline are randomly drawn from the priority distribution $P(x)$ and the relative deadline distribution $P(d)$ , respectively. In the beginning of each time step $t$ , all tasks that meet the absolute deadlines, i.e., $\{i|a_{i}=t\}$ , are removed from the queue without execution; then, they are replaced by the same number of newly arrived tasks with random priorities and random relative deadlines. The priority of each task $i$ is adjusted using the information on how much time is left until the absolute deadline for $t_{i}\leq t<a_{i}$ :

\displaystyle\hat{x}_{i}(t)\equiv\frac{x_{i}}{a_{i}-t}.

(1)

The inverse proportion of the remaining time to the absolute deadline in Eq. (1) implies that as the absolute deadline approaches, the effective priority of the task increases. Then, with probability $p$ , the task with the highest adjusted priority is selected among $L$ tasks; otherwise, one of $L$ tasks is uniformly and randomly selected with probability $1-p$ . The selected task is executed at the end of the time step $t$ , and a new task arrives in the beginning of the time step $t+1$ with a random priority and a random relative deadline. For the executed task $i$ , the response time is calculated as $\tau_{i}=t-t_{i}$ . This procedure is repeated until the time step reaches $T$ .

The case with $p=1$ implies a deterministic selection of the task for execution while $p=0$ means a fully random selection of the task. In our work, we will call the case with $0<p<1$ the nondeterministic selection protocol. We remark that the inverse proportion of the remaining time to the absolute deadline in Eq. (1) has been introduced to explain the temporal behavior of conference registrations and fee payments [21, 22, 23]. We also note that some tasks can be executed as soon as they arrive, implying $\tau_{i}=0$ . Finally, for the executed task $i$ , $\tau_{i}<d_{i}$ by definition.

In our work, we focus on the case with uniform distributions for both $x_{i}$ and $d_{i}$ as follows:

	$\displaystyle P(x)=1\quad\textrm{for}\ x\in[0,1],$		(2)
	$\displaystyle P(d)=\frac{1}{D}\quad\textrm{for}\ d=1,\ldots,D.$		(3)

Therefore, the maximum response time is set to $D-1$ .

III Numerical results

III.1 Deterministic case with $p=1$

We first study the case with $p=1$ , i.e., the deterministic case in which the task with the highest adjusted priority is always selected for execution at each time step. We numerically simulate the model up to time $T=10^{9}$ for various combinations of $L$ and $D$ to obtain the response-time distribution $P_{p=1}(\tau)$ , and the result is shown in Fig. 2. We find that $\tau=0$ is dominant in all combinations of $L$ and $D$ . For each $L$ , the fraction of $\tau=0$ , i.e., $P_{p=1}(0)$ , increases with the increasing $D$ , which can be approximated as

\displaystyle P_{p=1}(0)\approx 1-\frac{c_{L}}{D}

(4)

with an $L$ -dependent coefficient $c_{L}$ , as shown in Fig. 2(a). Precisely, we get $c_{L}\propto L^{1.22(8)}$ . For a fixed $L$ , in the limit of $D\to\infty$ , one obtains $P_{p=1}(0)\to 1$ . The distributions for the range $\tau>0$ can be characterized in the following scaling form with a normalization constant $C$ :

\displaystyle P_{p=1}(\tau)=C\tau^{-\alpha}f\left(\frac{\tau}{D}\right).

(5)

Here, $f$ denotes a cutoff function, which can be approximated as $f(u)=\theta(1-u)$ with $\theta$ denoting a Heaviside step function. Naturally, the cutoff is found to be linear in $D$ because by the definition of the model $\tau$ is limited only by $D$ . The power-law exponent $\alpha$ characterizing the scaling behavior of the response-time distributions for $D=10^{4}$ is estimated as $\approx 0.72(1)$ for $L=2$ , $\approx 0.64(1)$ for $L=5$ , and $\approx 0.60(1)$ for $L=10$ , see Fig. 2(b–d). In all cases, we find $\alpha$ to be less than one, which has been rarely reported in the literature [2]: $\alpha\approx 0.7$ was observed for the inter-event time distributions in mobile phone-call communications [4, 5]. In addition, $\alpha<1$ for the response-time distributions was suggested in a model study considering the cost and the benefit of communication [24].

The normalization condition of $P_{p=1}(\tau)$ reads

\displaystyle\sum_{\tau=0}^{D-1}P_{p=1}(\tau)=1.

(6)

Plugging Eqs. (4) and (5) into Eq. (6), one gets for $D\gg 1$

\displaystyle C\approx c_{L}(1-\alpha)D^{\alpha-2},

(7)

leading to

\displaystyle P_{p=1}(\tau)\propto D^{-2}\left(\frac{\tau}{D}\right)^{-\alpha}f\left(\frac{\tau}{D}\right)

(8)

for $\tau\geq 1$ . Therefore, the distributions for different values of $D$ are expected to collapse onto a single curve when $P_{p=1}(\tau)D^{2}$ is plotted against $\tau/D$ , which turns out to be the case, as shown in Fig. 2(b–d).

For understanding the results, we obtain the statistics for the executed tasks. We expect a task with longer relative deadline and smaller priority to wait longer for execution, implying a larger response time. In Fig. 3(a), we find a positive (or roughly linear) correlation between $d/x$ and $\tau$ , as expected. We also measure the distributions of $x$ and $d$ for executed tasks (Fig. 3(b, c)) and find that $P_{\rm ex}(x)\sim x^{-\beta_{x}}$ with $\beta_{x}\approx 1.27(4)$ and that $P_{\rm ex}(d)\sim d^{\beta_{d}}$ with $\beta_{d}\approx 1.05(2)$ . As the relative deadline $d$ affects the response time $\tau$ linearly, we focus on the effect of the priority $x$ on $\tau$ . Using the identity relation $P(\tau)d\tau=P_{\rm ex}(x)dx$ together with $P_{\rm ex}(x)\sim x^{-\beta_{x}}$ and $\tau\propto 1/x$ , one gets

\displaystyle P(\tau)\sim\tau^{-(2-\beta_{x})},

(9)

implying that

\displaystyle\alpha=2-\beta_{x}.

(10)

This relation is confirmed by the estimated values of $\alpha$ and $\beta_{x}$ from the numerical simulations for the various values of $L$ when $D=10^{4}$ is used, as shown in Fig. 3(d).

III.2 Nondeterministic case with $0<p<1$

Next, we study the effect of stochastic selection of the task for the case with $p<1$ . We numerically obtain the response-time distributions for various values of $p$ close to $1$ for the case with $L=2$ and $D=10^{4}$ , and we show the result in Fig. 4. In contrast to the deterministic case, a cutoff appears in the distribution due to the finite value of $p$ as long as the order of $(1-p)^{-1}$ is smaller than that of $D$ . As shown in Fig. 4(a), the response-time distributions for various values of $p\leq 0.9995$ can be characterized in the following form:

\displaystyle P_{p<1}(\tau)\propto(1-p)^{2}[\tau(1-p)]^{-\alpha}g[\tau(1-p)],

(11)

where $g$ denotes an exponential cutoff function. Here, the power-law exponent $\alpha$ is found to have a value of $\approx 0.99(1)$ . On the other hand, in Fig. 4(b), we observe that the distribution for $p\geq 0.9999$ develops a hump in the range of $10^{2}<\tau<10^{3}$ , leading to a heavier tail characterized by a smaller value of $\alpha$ . The distribution for the range of $\tau$ for the hump is found to overlap with that for the case with $p=1$ . Therefore, we conclude that the nature of exponential cutoff in the distribution is associated with a different scaling behavior: $\alpha\approx 1$ when the cutoff is determined by $(1-p)^{-1}$ , while $\alpha<1$ when the cutoff is determined by $D$ . Similar behavior is found for other values of $L$ (not shown). Finally, we remark that in the Barabási’s priority queuing model, the power-law tail of the response-time distribution appears only for the range of $p<1$ [3, 7], whereas in our model, the scaling behavior is found even at $p=1$ .

IV Conclusion

In this paper, we have studied the effects of the deadlines assigned to tasks on the response times by focusing on the scaling behavior of the response-time distributions. We numerically find a power-law exponent less than $1$ under the deterministic selection protocol ( $p=1$ ). Such a scaling behavior can be, to some extent, understood by means of the power-law distribution of the priorities of executed tasks with response times larger than $0$ . When the nondeterministic selection protocol is applied ( $0<p<1$ ), an exponential cutoff in the distributions develops as it is stronger than the cutoff due to the maximum relative deadline. The power-law exponent characterizing the scaling behavior of the response-time distribution is found to be around $1$ . Hence, we conclude that the value of power-law exponent is associated with the nature of a cutoff. The analytical approach to understanding these numerical results is left for a future work.

Acknowledgements.

H.-H.J. was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2018R1D1A1A09081919).

References

Lazer et al. [2009] D. Lazer, A. Pentland, L. Adamic, S. Aral, A.-L. Barabasi, D. Brewer, N. Christakis, N. Contractor, J. Fowler, M. Gutmann, T. Jebara, G. King, M. Macy, D. Roy, and M. Van Alstyne, Computational social science, Science 323, 721 (2009).
Karsai et al. [2018] M. Karsai, H.-H. Jo, and K. Kaski, Bursty Human Dynamics (Springer International Publishing, Cham, 2018).
Barabási [2005] A.-L. Barabási, The origin of bursts and heavy tails in human dynamics, Nature 435, 207 (2005).
Karsai et al. [2011] M. Karsai, M. Kivelä, R. K. Pan, K. Kaski, J. Kertész, A.-L. Barabási, and J. Saramäki, Small but slow world: How network topology and burstiness slow down spreading, Physical Review E 83, 025102(R) (2011).
Karsai et al. [2012] M. Karsai, K. Kaski, and J. Kertész, Correlated Dynamics in Egocentric Communication Networks, PLoS ONE 7, e40612 (2012).
Jiang et al. [2013] Z.-Q. Jiang, W.-J. Xie, M.-X. Li, B. Podobnik, W.-X. Zhou, and H. E. Stanley, Calling patterns in human communication dynamics, Proceedings of the National Academy of Sciences 110, 1600 (2013).
Vázquez [2005] A. Vázquez, Exact Results for the Barabási Model of Human Dynamics, Physical Review Letters 95, 248701 (2005).
Gabrielli and Caldarelli [2007] A. Gabrielli and G. Caldarelli, Invasion Percolation and Critical Transient in the Barabási Model of Human Dynamics, Physical Review Letters 98, 208701 (2007).
Anteneodo [2009] C. Anteneodo, Exact results for the Barabási queuing model, Physical Review E 80, 041131 (2009).
Vázquez et al. [2006] A. Vázquez, J. G. Oliveira, Z. Dezsö, K.-I. Goh, I. Kondor, and A.-L. Barabási, Modeling bursts and heavy tails in human dynamics, Physical Review E 73, 036127 (2006).
Cajueiro and Maldonado [2008] D. O. Cajueiro and W. L. Maldonado, Role of optimization in the human dynamics of task execution, Physical Review E 77, 035101 (2008).
Masuda et al. [2009] N. Masuda, J. S. Kim, and B. Kahng, Priority queues with bursty arrivals of incoming tasks, Physical Review E 79, 036106 (2009).
Min et al. [2009] B. Min, K. I. Goh, and I. M. Kim, Waiting time dynamics of priority-queue networks, Physical Review E 79, 056110 (2009).
Oliveira and Vazquez [2009] J. Oliveira and A. Vazquez, Impact of interactions on human dynamics, Physica A: Statistical Mechanics and its Applications 388, 187 (2009).
Jo et al. [2011] H.-H. Jo, R. K. Pan, and K. Kaski, Emergence of Bursts and Communities in Evolving Weighted Networks, PLoS ONE 6, e22687 (2011).
Mryglod et al. [2012] O. Mryglod, Y. Holovatch, and I. Mryglod, Editorial process in scientific journals: Analysis and modeling, Scientometrics 91, 101 (2012).
Zhou et al. [2017] B. Zhou, J.-R. Xie, X.-Y. Yan, N. Wang, and B.-H. Wang, A model of task-deletion mechanism based on the priority queueing system of Barabási, Physica A: Statistical Mechanics and its Applications 466, 415 (2017).
Mukherjee and Whalen [2018] S. Mukherjee and R. Whalen, Priority Queuing on the Docket: Universality of Judicial Dispute Resolution Timing, Frontiers in Physics 6, 1 (2018).
Lee and Lee [2021] T. H. Lee and J. W. Lee, Self-organized human behavioral patterns in book loans from a library, Physica A: Statistical Mechanics and its Applications 563, 125473 (2021).
Jo et al. [2012a] H.-H. Jo, R. K. Pan, and K. Kaski, Time-varying priority queuing models for human dynamics, Physical Review E 85, 066101 (2012a).
Alfi et al. [2007] V. Alfi, G. Parisi, and L. Pietronero, Conference registration: How people react to a deadline, Nature Physics 3, 746 (2007).
Alfi et al. [2009] V. Alfi, A. Gabrielli, and L. Pietronero, How people react to a deadline: Time distribution of conference registrations and fee payments, Central European Journal of Physics 7, 483 (2009).
Flandrin [2010] P. Flandrin, An empirical model for electronic submissions to conferences, Advances in Complex Systems 13, 439 (2010).
Jo et al. [2012b] H.-H. Jo, E. Moon, and K. Kaski, Optimized reduction of uncertainty in bursty human dynamics, Physical Review E 85, 016102 (2012b).