Waiting time dynamics of priority-queue networks

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.

Figure 1

(Color online) [(a) and (b)] The waiting time distribution $P\left(\tau \right)$ of the OV model on star networks (a) for $I$ tasks and (b) for $O$ tasks, with various $N=3,4,5,20$. Both $P\left(\tau \right)$ decay with an asymptotic power law with $N$-independent exponent, (a) ${\alpha }_I\approx 1.9$ and (b) ${\alpha }_O\approx 2.8$, indicated with dotted lines. Deviations from the power law for large $\tau$ for large $N$ are due to the finite simulation time (${10}^{10}$ steps). [(c) and (d)] The (c) double logarithmic and (d) semilogarithmic plots of the number of executed $I$ tasks, $\eta \left(t\right)$, for the OV model on fully connected networks starting from random initial priority assignments versus time. Different dotted line patterns are used for different network size $N$ (see legend). (c) For small $N$, $\eta \left(t\right)$ decays algebraically with $N$-dependent exponent, (d) while it decays exponentially for large $N\gtrsim 10$. Indicated slopes of dotted line are 1.5, 2.5, and 3.5, from right to left, drawn for the eyes. Also shown is $\eta \left(t\right)$ for $N=20$ with the star graph topology (black solid) for comparison.

Figure 2

(Color online) [(a) and (b)] The waiting time distribution $P\left(\tau \right)$ of the OR model on star topology with $N=3,4,5,20$. (a) $P\left(\tau \right)$ for $I$ tasks decay as power laws asymptotically and the power-law exponent decreases as $N$ from ${\alpha }_I\approx 3$ for $N=3$ to ${\alpha }_I\approx 1.5$ for $N=20$. (b) $P\left(\tau \right)$ for $O$ tasks show distinct behaviors between the hub node (open symbols) and leaf nodes (full symbols). For the hub node, the power-law exponent varies from ${\alpha }_{O,hub}\approx 1.5$ for $N=3$ to $\alpha \approx 1$ for $N=20$. For the leaf nodes, $P\left(\tau \right)$ decays faster, with exponents ranging from ${\alpha }_{O,leaf}\approx 2$ for $N=3$ to ${\alpha }_{O,leaf}\approx 1.5$ for $N=20$. For $I$ task and leaf nodes’ $O$ task, we shifted $P\left(\tau \right)$ curve vertically to enhance visibility. [(c) and (d)] $P\left(\tau \right)$ of the OR model on fully connected topology. (c) $P\left(\tau \right)$ for $I$ tasks decay with asymptotic powers, with exponents decreasing with $N$ from ${\alpha }_I\approx 3$ for $N=3$ to ${\alpha }_I\approx 2$ for $N=20$. (d) $P\left(\tau \right)$ for $O$ tasks follow the power-law decay with $N$-insensitive exponent ${\alpha }_O\approx 1.5$. Deviations for large $\tau$ are due to finite simulation time. All quoted slopes are indicated with dotted lines drawn for the eyes.

Figure 3

(Color online) The waiting time distribution $P\left(\tau \right)$ of the OR model with parallel updates. [(a) and (b)] $P\left(\tau \right)$ of the parallel OR model on star topology for (a) the $I$ tasks and (b) the $O$ tasks. For $I$ tasks, the power-law decay of $P\left(\tau \right)$ exhibits a weak $N$ dependence as the exponent varies from ${\alpha }_I\approx 2.2$ for $N=3$ to ${\alpha }_I\approx 1.7$ for $N=20$. For $O$ tasks, hub and leaf nodes exhibit different $N$-insensitive power laws with ${\alpha }_{I,hub}\approx 1.5$ for the hub and ${\alpha }_{I,leaf}\approx 2.5$ for the leaf nodes. [(c) and (d)] $P\left(\tau \right)$ of the parallel OR model on fully connected topology. For $I$ tasks the power-law exponent is found to be insensitive to $N$ as ${\alpha }_I\approx 2$ (c). For $O$ tasks, however, the asymptotic power-law exponent increases with $N$ from ${\alpha }_O\approx 2$ for $N=3$ to ${\alpha }_O\approx 3$ for $N=20$. In (d), the $P\left(\tau \right)$ curves for different $N$ are shifted vertically to enhance comprehensibility. All quoted slopes are indicated with dotted lines drawn for the eye.