Incentive-Vacation Queueing for Edge Crowd Computing

Edge computing aims to push services closer to endusers, greatly enhancing latency and scale. Yet, there’s untapped potential beyond the network’s last mile, on the extreme edge. Extreme edge computing (XEC) is a computing paradigm that exploits computational resources in the end-user’s immediate vicinity. Edge crowd computing (ECC) is an orchestrated sharing economy model within XEC that uses idle resources on userowned devices for service provision, compensating owners. We analyze an orchestrated ECC where devices rent resources in exchange for incentives. Our incentive-vacation queueing (IVQ) model associates performance with incentive payments using vacation queueing, considering the multitenancy of devices through a server vacation dependent on incentives received. In this article, we offer a framework for analyzing any sharing economy system that can be modeled using IVQ. We discuss the relationship between incentives and vacations on performance, namely, the incentive-vacation or IVQ function. We examine two families of IVQ functions that can be adjusted to benefit either the orchestrator or the worker and introduce a performance metric for such preference. We derive analytical expressions for system performance that consider the random nature of worker devices’ availability due to fluctuating incentives. The IVQ model explores commodifying user-owned resources in an ECC system, presenting a general approach for performance analysis in such environments.

SECTION I. Introduction

Cloud computing has emerged as a fundamental component in contemporary trade and service exchanges [1]. Its expansion is marked by three notable trends: 1) the swift progress of the Internet of Things (IoT) and explosion in number of its devices [2]; 2) the need for advanced applications, such as VR/AR; and 3) the imperative of ensuring security and privacy. This growth may soon surpass the centralized cloud and its backhaul network’s capacity [3]. To address this, Fog and Edge Computing have been introduced to decentralize and meet demand by bringing services closer to users [4]. Nonetheless, the capabilities of idle, powerful consumer devices like PCs, smart devices, wearables, vehicles, and appliances are underutilized [5], [6]. These devices have evolved from specialized hardware to versatile computing tools [3].

User devices have the potential to create an underutilized tier of edge computing, which we term extreme edge computing (XEC). This involves processing done exclusively on user devices, characterized by their proximity to end-users and modest processing power [7]. XEC harnesses collective idle computational resources across numerous devices rather than relying on singular device capabilities [8]. This has become possible due to nascent technologies, such as unikernels and microcontainers [9], [10]. While inherently decentralized, XEC can also adopt a semi-decentralized architecture. edge crowd computing (ECC) represents this semi-decentralized model, where service providers distribute their offerings through third-party devices within the user’s vicinity, paralleling the service provision models of companies like Uber or Airbnb [11].

ECCs present a notable use case in game streaming services over wireless networks. For low-capability devices like smartphones, the service provider uses edge servers for streaming sophisticated games, aiming to reduce latency and enhance the user experience. Mobility-related connectivity issues, for instance, on a train, may disrupt service access, preventing enjoyment of the game [12]. Although mobile devices can store the game, they often lack the necessary processing power and battery life to run it effectively. To counter unreliable connections, the service provider might transfer game assets directly to the user’s device, which temporarily coordinates gameplay by utilizing nearby devices, such as those of fellow passengers, by sharing the game’s workload [13]. These “worker” devices would receive compensation from the service provider. While not yet viable with current technology, this model is foreseen with the advent of 6G and D2D URLLC advancements in XEC and ECC frameworks [14], [15].

Edge Cloud Computing (ECC) is promising but comes with unique challenges. This study tackles two main concerns: 1) the need for user-owned devices to perform reliably despite being multitenant and 2) the diversity in usage, connection, and capabilities among these devices. Deploying ECC on personal devices is complex, primarily due to their and their owners’ unpredictable reliability, often linked to the owners’ behavior. Similar to mobile crowd sensing (MCS), which leverages incentives to manage participant engagement [16], we argue that such strategies can be adapted for computational tasks in ECC. However, while MCS rewards are for human input, ECC incentives compensate for any device performance dips when sharing computational tasks. Thus, incentives are crucial in ECC for converting computational resources into tradable assets [11].

Several studies have explored Edge Computing frameworks where there is an interaction between customers and service providers. Harth-Kitzerow and Garrido [17] tackled the issue of mutual self-interest—workers wanting maximum reward for least effort and customers wanting maximum service for least payment—by introducing a validation entity to ensure job execution fidelity by re-evaluating job samples. Additionally, [18] presents a macroeconomic analysis based on a double auction model, focusing on enhancing social welfare considerations that align the objectives of both service providers and customers. Similarly, [19] proposes a dynamic pricing strategy in a sharing economy context to improve social welfare. Although social welfare is an important overarching metric, it is essential to acknowledge the diverse array of more immediate system performance indicators, such as latency and throughput, especially given the variable and delay-sensitive nature of edge computing environments [20].

XEC and ECC systems are emerging technologies that have not been extensively explored in existing research. The untapped computational resources of advanced edge devices are now more accessible, thanks to advancements in virtualization, software-defined networking, and containerization [9], [12], [21], [22]. These technologies enhance network adaptability and autonomous organization, facilitating seamless computational handover from user devices to proximal devices [23]. The efficacy of new semi-decentralized XEC systems, like ECC, remains unquantified. Performance largely depends on workers’ profit motives. Deployers of ECC orchestrators can gain from understanding the correlation between incentives and performance. This insight is crucial for reducing recruitment costs and maximizing profits while delivering services on time and to customer satisfaction. Therefore, investigating the incentives-performance relationship is imperative.

This study examines ECC systems with orchestrator oversight, where incentives mitigate uncertainty. We introduce the incentive-vacation queueing (IVQ) framework, a queueing-theory method, to evaluate how incentives influence a worker’s output. IVQ focuses on multitenant worker devices adopting a vacation scheme, whereby the device attends to its owner’s requirements post ECC service. We assess our model via vacation queueing theory, specifically the M/G/1 queue with restricted pure vacations, noting that incentives, being stochastic, alter vacation lengths. This article’s contributions are as follows.

1. We propose the IVQ model with an incentive-vacation function, investigate the impact of its convexity on the system’s preference of workers and orchestrator, and the performance of workers in the system.

2. We formulate a general form of a variable preference incentive-vacation function and propose two incentive-vacation function families, the log-family and the rational-family. Furthermore, we provide a general framework for analyzing systems in which incentives can impact performance.

3. We derive closed-form expressions for performance in an ECC system as well as propose two sharing economy-based performance metrics: a) revenue per job and b) revenue per second.

4. We investigate the impact of incentives distributed by the orchestrator on the worker’s performance.

The structure of this document is as follows: Section II presents a synopsis of extreme edge systems and outlines the system architecture. Section III explores vacation queueing, its connection to incentives, and introduces the IVQ model, examining the effects of their convex relationship on the system. Section IV analyzes the decision-making process of the orchestrator concerning worker incentives within IVQ systems. Section V interprets the analytical results through a numerical illustration. Section VI discusses practical implications of implementing the IVQ model. This article concludes in Section VII with a summary and prospects for subsequent research.

SECTION II. Extreme Edge System Overview

XEC is laden with heterogeneity and uncertainty because it relies on user-owned infrastructure that suffers from numerous sources of uncertainty [24], [25]. Efficient utilization of XEC infrastructure involves taming with uncertainty and constraining it so that the system’s behavior can be predicted. However, the nature of user-owned devices is sporadic as they are used by their owners. Thus, an XEC system should seek to utilize the idle resources abundant on these user-owned devices in spite of their owner’s access to them. A service can be deployed on such devices that are present in the end-user’s immediate vicinity to ultimately provide timely service to other customers. While this is possible in theory, achieving reliable service provision is a challenge of XEC. In this section, we describe an ECC system, an instance of XEC, in which the service provider’s orchestrator recruits user-owned devices, or workers, to provide service to customers. The worker devices agree to provide their resources as infrastructure for the service provider, an ECC orchestrator, in exchange for an incentive payment. Fig. 1 illustrates an orchestrated ECC system, comprised of three main entities.

1. Customer Devices: These are the client devices that request and use the services provided by the ECC service provider.

2. Worker Devices: These are user-owned devices that rent their idle computational resources to the ECC service provider in exchange for an incentive.

3. Orchestrator: The central component of the orchestrated ECC system that coordinates the activities of the customer and worker devices, to ensure that jobs are completed efficiently. In addition, the orchestrator is also responsible for providing incentives to the worker devices. In addition to acting as a liaison between customers and workers, the orchestrator also tracks the performance of workers and their profitability to avoid unexpected worker churning.

Fig. 1.

ECC system.

Fig. 2 illustrates the operation of an orchestrated ECC system. First, the customer submits a job request to the nearest orchestrator. The orchestrator can also be a latent component that is available on the customer device itself and activated when the service provider is out of reach. The orchestrator then recruits a worker to perform this job. After receiving the job request from the orchestrator, the worker and the customer directly connect to each other so that the detailed job instructions are transmitted (or required assets). Finally, the worker services the job and returns it to the customer device which acknowledges its completion. Upon acknowledgment, the orchestrator processes the incentive payment to the worker device.

Fig. 2.

Operation of an ECC system: Customers request service from the orchestrator that would recruit workers for service provision.

This system can be viewed as a server farm [26] in which the ECC orchestrator represents a scheduler with a queue in which customers’ jobs - with attached job incentives - arrive, and are then distributed to the ECC workers as illustrated in Fig. 3.

Fig. 3.

ECC job distribution model: The orchestrator distributes jobs to multitenant workers.

Generally, customer service requests can be modeled into an orchestrator arrival rate, $\lambda _{\text {orch}}$ , which is split by the orchestrator according to some scheduling mechanism into worker arrival rates $\lambda _{\text {orch}}=\sum _{i=1}^{K} \lambda _{i}$ , assuming a total of $K$ workers. Nevertheless, these workers are not entirely dedicated to servicing the edge, since they are also user devices, making them multitenant devices that provide service for more than one entity. In this case, workers serve both the XEC system (in exchange for an incentive) in addition to their owners. As an example, the owner of a personal computer can rent its idle computational resources to the XEC orchestrator in addition to using the same device for themselves. Therefore, worker devices need to manage their resources in a manner that allows them to serve both the XEC system and its owner. Such scenario is of great importance for current and future trends of infrastructure-less sharing economy-based companies, such as Uber, Airbnb, etc. This article presents methods of modeling and improving such systems.

In this article, we investigate performance from the perspective of an individual worker. We model the service time spent on serving the owner’s jobs as a vacation whose duration is dictated by the amount of incentive the worker receives. In the following section, we will briefly overview vacation queueing prior to introducing the proposed IVQ model. Table I lists the notations used throughout this article.

TABLE I Notations and Symbols

SECTION III. Modeling of Incentive-Vacation Queueing (Worker Perspective)

In an ECC system, the availability of worker devices and their resources is heavily influenced by the users’ behavior. This spontaneity introduces a degree of uncertainty in the availability of those resources. However, the uncertainty stemming from the user’s behavior can be mitigated by the use of incentives that target the human user.

In this section, we employ vacation queueing to abstract the user behavior and the influence of stochastic incentives over it. We give an overview of vacation queueing, and introduce the IVQ model which, using vacation queueing, captures the impact of incentives in an ECC system. We provide an analysis of the system, the relationship between vacations and incentives, and the performance of an orchestrator-based ECC system.

A. Overview of Vacation Queueing

Vacation queueing is a type of queueing in which the server becomes unavailable for a period of time called a vacation. Implementing a vacation policy introduces a degree of flexibility in the modeling of real systems as vacations abstract the server’s other duties into a single random variable, $V$ , that represents the duration of a server vacation [27], [28], [29]. For example, single server vacation queueing could be classified according to the vacation policy. The vacation policy can be exhaustive or nonexhaustive, with regards to whether the server starts its vacation only after having finished the queue or not. There are different types of vacation queues as well as to whether there is a threshold (i.e., a specific number of vacations has occurred or not), whether it is preemptive or not, or whether the service is gated or not [28].

Fig. 4 depicts the general vacation server’s activity over time. If the type of vacation model allows consecutive service with no vacation in between, then the service period is the total period for which the server was busy. Similarly, if consecutive vacations have no service in between (i.e., zero-length vacation), then the vacation period is the total duration of consecutive vacations. Generally, the service cycle spans the service period and a single vacation. This is the case for general vacation models [27]. In this work, we use a certain type of vacation queueing, $P$ -limited vacation queueing (PVQ) to model ECC workers in an extreme edge scenario.

Fig. 4.

General vacation model: Service periods can be followed by vacation periods.

B. P-Limited Vacation Queueing

P-Limited, or pure limited, Vacation Queueing is a type of nonexhaustive vacation queueing in which the server takes a vacation after each departure, limiting its service period to a single job [27], [28]. If no jobs were queued for service at a vacation completion instance, the server keeps repeating its vacations until a job arrives. Fig. 5 illustrates the server’s activity over time in PVQ.

Fig. 5.

P-limited vacation model: Each service period must be followed by a vacation period.

What makes PVQ interesting is its compatibility with multitenancy as it would abstract the worker’s activities in the vacation. The modeling of the vacation as a random variable (or a function of a random variable) simplifies the complexity of the worker’s non-XEC workload into the vacation duration $V$ . In addition, PVQ’s analysis is simple as it can be regarded as a modification of the service time by introducing the length of the vacation to it. In other words, an $M/G/1$ 1 queue changes to have a modified service time, becoming an $M/\widetilde {G}/1$ queue, in which the modified service time, $\widetilde {S}$ , becomes a sum of the $M/G/1$ service time, $S$ , and the vacation time, $V$ , i.e., $\widetilde {S}=S+V$ which is possible due to the stochastic decomposition property [28]. $\widetilde {S}$ also represents the duration of the PVQ service cycle. A consequence is that the stability condition then becomes

$$\begin{equation*} \widetilde {\rho } = \rho + \lambda \mathbb {E}[V] < 1 \tag{1}\end{equation*}$$ where $\lambda$ is the arrival rate, $\rho =\lambda S$ is the $M/G/1$ server utilization, $\widetilde {\rho }$ is the PVQ server utilization, and $\mathbb E[V]$ is the average vacation duration.

C. Incentive Vacation Queueing

IVQ is a form of PVQ in which vacation duration, $V$ , is defined as a function of the total incentive, $X$ , a worker is receiving. This relationship is illustrated in Fig. 6. The incentive $X$ is a random variable making $V$ a function of a random variable. By defining $V$ as a function of $X$ , $V$ inherits the randomness of $X$ and becomes a random variable. Depending on the incentive’s origin, $X$ can be defined as the sum of incentives to each of the jobs in a worker’s queue at a time instant, thus looking at incentives coming directly from the customers, or it can be defined as a set payment value that the orchestrator chooses. In both cases, we name the IVQ incentive variable, $X$ , as the total queue incentive (TQI). The implications of both cases are covered in the following section on the performance modeling of an IVQ system.

Fig. 6.

In IVQ, the impact of incentives is represented via vacation duration.

Incentives have varying forms; however, they can be categorized into two main categories: 1) monetary and 2) nonmonetary incentives. Unlike monetary incentives in which money is used to incentivize, nonmonetary incentives include rewards, such as recognition, badges, points, or discounts. Nonmonetary incentives also extend to include forms of incentive that stem from an existing context, such as a game (e.g., in-game rewards or rank) or a community (e.g., contributions of a Google Maps guide), or the gamification of an activity (e.g., gamified focus timer) [30]. The design of incentives has various aspects according to the context, such as the setting in which the ECC system takes place, what audience comprises the worker devices and their demographics, or even if it is a closed setting [31].

In IVQ, we define $V$ as a function of the incentive $r(X)$ . The choice of $r(X)$ has to be chosen such that the system is stable and the performance is achieved. The proper selection of $r(X)$ and its properties are of great effect on the IVQ as the vacation is the abstraction of user behavior. Aspects that extend beyond just incentives can be captured by $r(X)$ . For example, $r(X)$ can be defined in terms that relate to worker’s trustworthiness, benchmark capabilities, and reliability, and thus allow the study of randomness stemming from these factors. However, in this work, we isolate our analysis to only random behavior stemming from the presence of incentives. The vacation duration is inversely proportional to the incentive, which requires $r(X)$ to be monotonically decreasing as more incentives cause shorter vacations. In IVQ, the stability condition becomes

$$\begin{equation*} \widetilde \rho = \rho + \lambda \mathbb {E}[V]= \rho + \lambda \mathbb {E}[r(X)] < 1 \tag{2}\end{equation*}$$ or equivalently, it can be rewritten as $$\begin{equation*} \mathbb {E}[r(X)] < \frac {1}{\lambda } - \frac {1}{\mu } \tag{3}\end{equation*}$$ where $\mu =1/S$ is the service rate.

Equation (3) is useful as it shows that $\sup V = 1/\lambda - 1/\mu$ , i.e., the least upper bound for the vacation is the difference between the interarrival rate and the service time. This is mainly due to the fact that under PVQ a queue is stable (i.e., not infinitely growing) if and only if the service cycle as at least long as the interarrival time. As such, the duration of the vacation, $V$ is either zero or approaches $1/\lambda - 1/\mu$ , i.e., $V \in [0,1/\lambda - 1/\mu )$ . Thus, the operation range of IVQ is dictated by either pegging $\lambda$ and $\mu$ or—as will be shown throughout this section—by the choice of boundaries $V_{\min } < V=r(X) < V_{\max }$ in the design of $r(X)$ . In this work, we opt for the latter case, i.e., choosing a convenient $V_{\min }$ and $V_{\max }$ since the arrival rate $\lambda$ is controlled by the orchestrator in an orchestrated ECC setting, given the worker’s $\mu$ , and since the choice of proper boundaries would guarantee the queue stability. Thus, the choice of $r(X)$ has to respect $r(X_{\min })=V_{\max }$ and $r(X_{\max })=V_{\min }$ , i.e., $X\in [X_{\min },X_{\max }] \mapsto V\in [V_{\min }, V_{\max }]$ , to guarantee stability.

D. Convexity of $r(X)$

The choice of $r(X)$ has significant implications on the behavior of the system. Convexity, in particular, impacts whether the system leans toward—or favors—the orchestrator or the worker. To illustrate this, we look at the incentive-vacation function, which is—as previously mentioned—monotonically decreasing. As a consequence, the second derivative, $r^{\prime \prime }(x)$ which gives us information about $r(x)$ ’s convexity $(r(x)$ is convex $r^{\prime \prime }(x)>0$ , concave $r^{\prime \prime }(x) < 0$ , or linear $r^{\prime \prime }(x)=0)$ is also giving us information about how $r(x)$ decreases. For the worker, it is favorable if this quantity decreases as it would imply that the worker is not losing much vacation (i.e., portion of the cycle that goes to servicing the worker’s owner) per unit incentive. On the other hand, it would be preferrable for the orchestrator to have this quantity increasing, as it would mean that they would be gaining more service per unit incentive. A convex function, in that regard, is orchestrator-favoring, while a concave function is worker-favoring, and in between a linear function is one that treats both fairly. Fig. 7 illustrates this preference in the incentive-vacation function.

Fig. 7.

Convexity of $r(x)$ has an impact on the marginal value of vacations and thus the choice of IVQ function can be biased to favor one party over another. The $\alpha$ is used to control the IVQ function’s preference.

As a consequence, the choice of a worker’s incentive-vacation function needs to take various factors into consideration. For example, if the worker is new to the system and not much information is available about them, both the orchestrator and the worker can agree on a convex $r(x)$ until the worker proves their worth, and then move to a different $r(x)$ that decreases the worker’s vacation per unit incentive. In the following section, we propose a general formulation of $r(x)$ as a incentive-vacation function whose convexity can be tuned by a parameter, $\alpha$ .

E. Variable Convexity Incentive-Vacation Function

The objective of this section is to model a wide class of incentive-vacation functions that exist in practice, and through a tuning parameter, $\alpha$ , we can mathematically control the convexity of the incentive-vacation function. Given a seed convex function, $r_{\text {cvx}}(x)$ that starts at the point $(X_{\min },V_{\max })$ and ends on $(X_{\max },V_{\min })$ , we obtain a concave anti-convex function, $r_{\text {ccv}}(x)$ that starts and ends on the same points, but decreases concavely over the interval $[X_{\min },X_{\max }]$ . In addition, we construct a linear function, $r_{\text {lnr}}(x)$ , between the points, and combine the three functions in a single $\alpha$ -parameterized functions that allows choice of $r_{\text {cvx}}(x)$ , $r_{\text {lnr}}(x)$ , $r_{\text {ccv}}(x)$ or a convex combination of them.

The concave anti-convex of $r_{\text {cvx}}(x)$ , $r_{\text {ccv}}(x)$ can be obtained by reversing the behavior of the slope over the interval $[X_{\min },X_{\max }]$ , i.e.,

$$\begin{equation*} r^{\prime }_{\text {cvx}}(x)=r^{\prime }_{\text {ccv}}\left ({X_{\max }+X_{\min } -x}\right ) \tag{4}\end{equation*}$$ which expresses the relation between the slope of $r_{\text {ccv}}(x)$ and $r_{\text {cvx}}(x)$ . The function $r_{\text {ccv}}(x)$ can then be obtained by integrating both sides and substituting with the inverse of the argument of $r^{\prime }_{\text {ccv}}(x)$ to get $$\begin{equation*} r_{\text {ccv}}(x)=-r_{\text {cvx}}\left ({X_{\max }+X_{\min }-x}\right )+V_{\max } +r_{\text {cvx}}\left ({X_{\max }}\right ) \tag{5}\end{equation*}$$ where $r_{\text {ccv}}(x)$ is the concave anti-convex function for any $r_{\text {cvx}}(x)$ . The linear function, $r_{\text {lnr}}(x)$ is defined as $$\begin{align*} r_{\text {lnr}}(x)=&\frac {V_{\min }-V_{\max }}{X_{\max }-X_{\min }}x \\&{}+V_{\max }\left ({ 1-\frac {X_{\min }\left ({V_{\min }-V_{\max }}\right )}{V_{\max }\left ({X_{\max }-X_{\min }}\right )} }\right ). \tag{6}\end{align*}$$ We then combine all three functions in an $\alpha$ -parametrized convex combination $$\begin{equation*} r\left ({x,\alpha }\right )=\left ({-\alpha }\right )^{+} r_{\text {cvx}}(x) + \left ({-|\alpha |}\right )^{+}r_{\text {lnr}}(x) + \left ({\alpha }\right )^{+}r_{\text {ccv}}(x) \tag{7}\end{equation*}$$ where $(\cdot )^{+} = \max (0,\cdot )$ , $\alpha \in [{-}1,1]$ , and the expression becomes $r_{\text {cvx}}(x)$ for $\alpha =-1$ , $r_{\text {lnr}}(x)$ for $\alpha =0$ , and $r_{\text {ccv}}(x)$ for $\alpha =1$ . As a consequence of this definition, $r(x,\alpha )$ is convex for $\alpha \in [{-}1,0)$ and concave for $\alpha \in (0,1]$ .

The selection of the seed $r_{\text {cvx}}(x)$ , thus, dictates the sort of vacation function family that $r(x,\alpha )$ belongs to. To illustrate, we shall derive two vacation families: 1) the log-family and 2) the rational-family, that cover the modeling of different realistic applications. For instance, Uber transportation is a high stakes as customers directly interact with workers and an unfavorable interaction would negatively impact Uber’s reputation. This is due to the fact that user’s satisfaction can easily fall if the minimum service is was poorly provided [32]. Such a service would benefit from using a log incentive-vacation function as it has a high degree of bias in preferring the orchestrator (Uber in this case) to the worker (the driver) for low $\alpha$ . This preference reverses for high $\alpha$ if the driver is a reputable and reliable driver. On the other hand, the rational function could be useful in a food delivery service, such as Uber Eats, which does not often involve a prolonged interaction with the driver, and also has a larger population of drivers to recruit than transportation. Having a rational incentive-vacation function provides a fairer relationship between vacations and incentives that does not excessively bias the system toward neither the orchestrator nor the worker.

It is important to note that both, the log and the rational families are two flexible examples that cover a wide range of functions. An orchestrator can mix-and-match different $r_{\text {cvx}}(x)$ ’s with concave functions that are not anti-convex of $r_{\text {cvx}}(x)$ . The framework provided in this work is a general framework for the analysis for any system in which an incentive-vacation function $r(x,\alpha )$ is generated from a convex seed $r_{\text {cvx}}(x)$ . The choice of such function depends on the context of the service and the goals of the orchestrator.

The log-family stems from the choice of $r^{(\log )}_{\text {cvx}}(x,\beta )=\log _{\beta }(A x + B)$ , whose parameters $A$ and $B$ can be found through the initial conditions

$$\begin{align*} -\log _{\beta }(A X_{\min } + B) = V_{\max }, \quad -\log _{\beta }(A X_{\max } + B) = V_{\min } \\{}\tag{8}\end{align*}$$ to acquire $$\begin{align*} A=-\frac {\beta ^{ V_{\max }}-\beta ^{ V_{\min }}}{X_{\min } - X_{\max }},\qquad B=\frac {\beta ^{-V_{\max }} X_{\max }-\beta ^{- V_{\min }} X_{\min }}{X_{\max }-X_{\min }} \\{}\tag{9}\end{align*}$$ that result in $$\begin{align*} r^{(\log )}_{\text {cvx}} ={}-\log _{\beta } \left ({\frac {\beta ^{-V_{\max }-V_{\min }} \left ({\beta ^{V_{\max }} (x-X_{\min })+\beta ^{V_{\min }} (X_{\max }-x)}\right )}{X_{\max }-X_{\min }}}\right ). \\{}\tag{10}\end{align*}$$ Thus, we obtain the concave anti-convex of $r_{\text {cvx}}^{(\log )}(x,\beta )$ as $$\begin{align*}&r_{\text {ccv}}^{(\log )}=V_{\max }+V_{\min } \\&\;\quad {}+\log _{\beta } \left ({\frac {\beta ^{-V_{\max }-V_{\min }} \left ({\beta ^{V_{\max }} (X_{\max }-x)+\beta ^{V_{\min }} (x-X_{\min })}\right )}{X_{\max }-X_{\min }}}\right ) \\{}\tag{11}\end{align*}$$ Then, we could combine this with $r_{\text {lnr}}(x)$ to obtain $$\begin{align*}&r_{\log }(x,\alpha ,\beta ) \\&\;=(-\alpha )^{+} r^{(\log )}_{\text {cvx}}(x,\beta )+(1-| \alpha |)^{+} r_{\text {lnr}}(x)+(\alpha )^{+} r^{(\log )}_{\text {ccv}}(x,\beta ). \\{}\tag{12}\end{align*}$$

Similarly, we can derive the rational-family of vacation functions by taking

$$\begin{align*} r^{(\text {rat})}_{\text {cvx}}(x)=&\frac {1}{C x + D} \\=&\frac {V_{\max } V_{\min } \left ({X_{\min }-X_{\max }}\right )}{(V_{\min }-V_{\max })x - X_{\max }V_{\min }+V_{\max }X_{\min }} \tag{13}\end{align*}$$ with the concave anti-convex of $r_{\text {cvx}}^{(\text {rat})}(x)$ being $$\begin{equation*} r_{\text {ccv}}^{(\text {rat})}(x)=\frac {V_{\max }^{2} \left ({x-X_{\max }}\right )+V_{\min }^{2} \left ({X_{\min }-x}\right )}{V_{\max } \left ({x-X_{\max }}\right )+V_{\min } \left ({X_{\min }-x}\right )} \tag{14}\end{equation*}$$ which gives us the rational-family $$\begin{align*}&r_{\text {rat}}(x,\alpha ) \\&\;=(-\alpha )^{+} r^{(\text {rat})}_{\text {cvx}}(x)+(1-| \alpha |)^{+} r_{\text {lnr}}(x)+(\alpha )^{+} r^{(\text {rat})}_{\text {ccv}}(x). \tag{15}\end{align*}$$ Both families have different behaviors with respect to how the marginal value of vacation (i.e., vacation variation per unit incentive) changes, and they correspond to different scenarios. Figs. 8 and 9 shows a plot of both incentive-vacation families for an arbitrary choice of $X_{\min }$ , $X_{\max }$ , $V_{\min }$ , $V_{\max }$ and variable $\alpha$ .

Fig. 8.

Log-family for variable $\alpha$ . The log-family’s preference does not rely only on $\alpha$ , but it also has an inherent bias toward one party.

Fig. 9.

Rational-family for different $\alpha$ . In comparison to Fig. 8, the rational family is less obtuse, not having an inherent preference to either the orchestrator or the worker and relying only on $\alpha$ .

F. Measuring $r(x)$ ’s Preference

The convexity of the function $r(X)$ can give an indicator to whether the incentive-vacation function prefers—or is biased—toward the orchestrator or the worker: decreasing convex implies bias toward the orchestrator while decreasing concave leans toward the worker. While the second derivative of $r(X)$ gives a good indicator, it does not provide a common ground for comparing different $r(X)$ ’s. In this section, we describe a method to estimate any $r(X)$ ’s preference in terms of two extreme $r(X)$ ’s: 1) an extreme $r_{\text {abs,cvx}}(X)$ that favors the orchestrator most and 2) an extreme $r_{\text {abs,ccv}}(X)$ that favors the worker most, and through the help of the linear $r_{\text {lnr}}(X)$ .

The second derivative, while it does not provide a solid common ground for comparing how an $r(X)$ ’s preference to another, but its sign provides a binary measure of that preference, i.e., the $r(X)$ is orchestrator-preferring if $\text {sgn}(r^{\prime \prime }(X))=-1$ and worker-preferring if $\text {sgn}(r^{\prime \prime }(X))=+1$ . Our suggested metric measures how much deviation is between $r_{\text {lnr}}(X)$ and $r(X)$ . This can be captured by means of the signed area enclosed between $r(X)$ and $r_{\text {lnr}}(X)$ , i.e.,

$$\begin{align*}&\int _{X_{\min }}^{X_{\max }} (r(x)-r_{\text {lnr}}(x)) \, dx = \int _{X_{\min }}^{X_{\max }} r(x)\,dx-\int _{X_{\min }}^{X_{\max }}r_{\text {lnr}}(x) \, dx \\&\;= R(X_{\max })-R(X_{\min }) - R_{\text {lnr}}(X_{\max })+R_{\text {lnr}}(X_{\min }) \\&\;=R(X_{\max })-R(X_{\min }) - \frac {1}{2} (V_{\max }+V_{\min })(X_{\max }-X_{\min }) \\{}\tag{16}\end{align*}$$ where $R(x)$ is the anti-derivative of $r(x)$ .

We now construct the two functions of maximal preference to each the orchestrator and the worker

$$\begin{align*} r_{\text {abs,cvx}}(x)=&\begin{cases} V_{\max }, & x=X_{\min } \\ V_{\min }, & X_{\max }\geq x>X_{\min } \\ 0, & {\mathrm {otherwise}} \end{cases} \\ r_{\text {abs,ccv}}(x)=&\begin{cases} V_{\min }, & x=X_{\max } \\ V_{\max }, & X_{\max }> x\geq X_{\min } \\ 0, & {\mathrm {otherwise}}. \end{cases} \tag{17}\end{align*}$$

Then, we measure the proportion of twice the area acquired in (16) and (17), since the area between the $r_{\text {lnr}}(x)$ and $r_{\text {cvx}}(x)$ is the same as $r_{\text {ccv}}(x)$ due to rotational symmetry. Thus, instead of taking the proportion of the area with respect to the triangle bounded by either $r_{\text {abs,cvx}}(x)$ or $r_{\text {abs,ccv}}(x)$ and $r_{\text {lnr}}(x)$ , the same proportion can be directly acquired by taking the proportion of the area bounded by $r_{\text {cvx}}(x)$ and $r_{\text {ccv}}(x)$ to the whole rectangle bounded by $r_{\text {abs,cvx}}(x)$ and $r_{\text {abs,ccv}}(x)$ . Therefore, our metric, $\gamma$ becomes

$$\begin{align*} \gamma=&2\frac {\int _{X_{\min }}^{X_{\max }} (r(x)-r_{\text {lnr}}(x)) \, dx}{\int _{X_{\min }}^{X_{\max }} (r_{\text {abs,ccv}}(x)-r_{\text {abs,cvx}}(x)) \, dx} \\=&2\frac {R(X_{\max })-R(X_{\min }) - \frac {1}{2} (V_{\max }+V_{\min })(X_{\max }-X_{\min })}{(V_{\max }-V_{\min })(X_{\max }-X_{\min })} \\{}\tag{18}\end{align*}$$ where $(V_{\max }-V_{\min })(X_{\max }-X_{\min })$ is the area of the whole rectangle whose diagonal is $r_{\text {lnr}}(x)$ . As such, we have a common ground for comparing the amount of preference a vacation function $r(x)$ . This measurement technique is illustrated in Fig. 10. For a specific incentive-vacation family, a relationship between $\gamma$ and $\alpha$ , $\gamma =f(\alpha )$ can be derived that would allow comparing different families’ preference capacity. Thus, $\gamma$ is a performance metric that can estimate the parameter $\alpha$ . This allows the performance analysis of the IVQ model to extend beyond vacation queueing models to any model involving incentives that is translatable to $M/\widetilde G/1$ model. This is possible due to the one-to-one isomorphism of the PVQ model to a modified $M/G/1$ , a $M/\widetilde G/1$ queue. Vacations, in that sense, are an abstraction of the dynamics of the model that modify the service time. This versatility allows the IVQ to be a powerful model for performance analysis in presence of incentives.

Fig. 10.

Measuring preference of an IVQ function: Performance metric, $\gamma$ , is the ratio of the area encompassed by the $r_{\text{cvx}}(x)$ and $r_{\text{ccv}}(x)$ to the enveloping square.

SECTION IV. Performance Analysis

A. IVQ Performance Metrics

For IVQ in the context of ECC and XEC, there are a few performance metrics that are of concern [28]. For this work, we focus on the metrics that are related to the worker. In general, we have six main parameters: 1) the service time (or equivalently service rate); 2) $S=1/\mu$ ; 3) the interarrival time (or equivalently the arrival rate); 4) $\tau = 1/\lambda$ ; 5) the four parameters deciding $r(x)$ , namely, the minimum and maximum incentive, $X_{\min }, X_{\max }$ ; and 6) the minimum and maximum vacation duration $V_{\min }, V_{\max }$ . Knowledge of these six parameters along the first and second moments of the vacation random variable, i.e., $\mathbb E [V] = \mathbb E [r(X)]$ and $\mathbb E[V^{2}]=E[(r(X))^{2}]$ are sufficient to characterize the performance metrics covered in this work. We proceed to define the performance metrics in both the actual vacation variable, $V$ , and the vacation as a proportion of the service cycle, $V_{\%} = V/\tau = \lambda V$ . This allows us to express the relationship between the service rate and the arrival rate as a proportional relationship with a factor $(1-V_{\%})$ , i.e.,

$$\begin{equation*} \mu = \lambda \left ({ \frac {1}{1-V_{\%}} }\right ). \end{equation*}$$

The most fundamental metric is the average queue length [27], [28] that we express as

$$\begin{align*} \mathbb {E}\left [{Q_{v}}\right ]=&\lambda ^{2}\frac {2S(S+\mathbb {E}[V])+\mathbb {E}\left [{V^{2}}\right ]}{2(1-\widetilde {\rho })}+\lambda \frac {\mathbb {E}\left [{V^{2}}\right ]}{2\mathbb {E}[V]} \\=&\frac {\lambda 2S(\lambda S +\mathbb {E}\left [{V_{\%}}\right ])+ \mathbb {E}\left [{V_{\%}^{2}}\right ]}{2(1-\widetilde \rho )}+\frac {\mathbb {E}\left [{V_{\%}^{2}}\right ]}{2 \mathbb {E}\left [{V_{\%}}\right ]} \tag{19}\end{align*}$$ where $\widetilde \rho = \lambda /\mu + \lambda \mathbb E[V] = \lambda /\mu + \mathbb E[V_{\%}]$ in (2).

The queue length can then be used to obtain the number of jobs in the system by adding the current job being processed whose service time is equivalent to PVQ server utilization $\widetilde {\rho }=(S+ \mathbb E [V])/\tau$ , thus the average number of jobs in the system becomes

$$\begin{align*} \mathbb E\left [{L_{v}}\right ]=&\lambda ^{2}\frac {2S(S+\mathbb {E}[V])+\mathbb {E}\left [{V^{2}}\right ]}{2(1-\widetilde {\rho })}+\lambda \frac {\mathbb {E}\left [{V^{2}}\right ]}{2\mathbb {E}[V]} + \widetilde {\rho } \\=&\frac {\lambda 2S(\lambda S + \mathbb {E}\left [{V_{\%}}\right ])+ \mathbb {E}\left [{V_{\%}^{2}}\right ]}{2(1-\widetilde {\rho })}+\frac {\mathbb {E}\left [{V_{\%}^{2}}\right ]}{2 \mathbb {E}\left [{V_{\%}}\right ]}+\widetilde {\rho } \\=&\mathbb E\left [{Q_{v}}\right ] + \widetilde \rho {.} \tag{20}\end{align*}$$

Consequently, the mean waiting time can also be obtained via the product of the interarrival time (which is the same as the length of the PVQ service cycle) and the queue length

$$\begin{align*} \mathbb E\left [{T_{Q_{v}}}\right ]=&\lambda \frac {2S(S+\mathbb {E}[V])+\mathbb {E}\left [{V^{2}}\right ]}{2(1-\widetilde {\rho })}+\frac {\mathbb {E}\left [{V^{2}}\right ]}{2\mathbb {E}[V]} \\ \\=&\frac { 2S(\lambda S + \mathbb {E}\left [{V_{\%}}\right ])+ \tau \mathbb {E}\left [{V_{\%}^{2}}\right ]}{2(1-\widetilde {\rho })}+\frac {\tau \mathbb {E}\left [{V_{\%}^{2}}\right ]}{2 \mathbb {E}\left [{V_{\%}}\right ]} \\=&\frac {\mathbb {E}\left [{Q_{v}}\right ]}{\lambda } = \frac {\mathbb {E}\left [{L_{v}}\right ] - \widetilde \rho }{\lambda }. \tag{21}\end{align*}$$

It is important to note that while the mean waiting time captures the job-related latency, it does not capture the customer-worker-orchestrator end-to-end latency.

The queue length can also be used to obtain the mean worker’s per-job revenue, $R$ , as

$$\begin{equation*} \mathbb E[R] = \frac {\mathbb {E}[X]}{\mathbb {E}\left [{Q_{v}}\right ]}. \tag{22}\end{equation*}$$

Per-job revenue is an important metric from the worker’s perspective as it allows the worker to assess the profitability of joining the ECC system. It is of concern for the orchestrator to ensure that workers would be available for recruitment, and thus allow the persistence of service provision.

The parameters of $r(x)$ , i.e., $[X_{\min }, X_{\max }] \mapsto [V_{\min },V_{\max }]$ allow us to identify the maximum and minimum throughput, respectively

$$\begin{align*} \lambda _{\max }=&\frac {1}{V_{\min }+S}=\frac {1}{r(X_{\max })+S} \\ \lambda _{\min }=&\frac {1}{V_{\max }+S} = \frac {1}{r(X_{\min })+S} \tag{23}\end{align*}$$ which in turn is used to formulate the maximal and minimal revenue per unit time as $$\begin{align*} R_{\max }=&\frac {2 X_{\max } \left ({\lambda _{\max } V_{\min }-S \lambda _{\max }+1}\right )}{\lambda _{\max }^{2} \left ({2 S V_{\min }+S}\right )} \\=&\frac {2 X_{\max } \left ({V_{\%,\min }-S \lambda _{\max }+1}\right )}{\lambda _{\max } \left ({2 S V_{\%,\min }+S\lambda _{\max }}\right )} \tag{24}\end{align*}$$ and $$\begin{align*} R_{\min }=&\frac {2 X_{\min } \left ({\lambda _{\min } V_{\max }-S \lambda _{\min }+1}\right )}{\lambda _{\min }^{2} \left ({2 S V_{\max }+S}\right )} \\=&\frac {2 X_{\min } \left ({V_{\%,\max }-S \lambda _{\min } +1}\right )}{\lambda _{\min } \left ({2 S V_{\%,\max }+S\lambda _{\min }}\right )}. \tag{25}\end{align*}$$

It should be clear from and 25 that the minimal and maximal revenue are directly impacted by the choice of parameters $X_{\min }$ and $V_{\max }$ . Having information about the revenue allows the worker to evaluate the benefit of remaining in the ECC or to change to another ECC. It is also of concern for the orchestrator to ensure that workers do not churn and that they would not be able to provide the service, or to prepare in advance to allocate dedicated edge and fog resources.

B. Impact of Incentive Origin in ECC

In the IVQ model, customers pay orchestrators, who then compensate workers. Workers can receive incentives through: 1) orchestrator-determined rates; 2) orchestrator-mediated matchmaking with commission; or 3) direct payment from customers in a decentralized manner (if an orchestrating entity is completely absent, this would be a decentralized XEC scenario). From the perspective of the worker, both the second and third methods are equivalent, as the TQI can be cast as $X=\sum _{i \in Q_{w}} x_{i}$ where $Q_{w}$ represents the worker’s queue, and $x_{i}$ represents the incentive attached to the $i^{\text {th}}$ job in the queue. It is evident that treating $X$ on its own, as opposed to treating it as a sum of $x_{i}$ ’s leads to different conclusions in IVQ. For readers interested in the latter case that arises in the second and third methods, we provide a brief analysis in a previous work [7].

The job incentive $x_{i}$ is attached by a customer to a job they wants and passes the request to the orchestrator in the ECC. The choice of incentive stems from the valuation of the job and its completion as well as the market price. The market price, influenced by factors like supply, demand, regulations, and mechanisms, is unpredictable. These influences can be captured using game-theoretic and stochastic models, yielding a price often represented as a random variable with a general distribution at equilibrium [33]. Yet, given any underlying process, the orchestrator treats every customer equally. This aligns with the principle of indifference [34], suggesting incentives’ distribution is uniform, i.e., $x_{i} \sim \text {Unif}(x_{\min },x_{\max })$ for all $i \in Q_{w}$ , where $x_{\min }$ and $x_{\max }$ represent the minimum and maximum incentive attached to a job and $\text {Unif}(a,b)$ represents a uniform distribution over the interval $(a,b)$ . In fact, $x_{i}$ ’s can be represented in terms of the TQI by defining $X_{\min }=|Q_{w}| x_{\min }$ and $X_{\max }=|Q_{w}|x_{\max }$ , where $|Q_{w}|$ is the number of the incentive-contributing jobs in the worker’s queue. The same argument extends to the orchestrator’s choice of incentives for the workers, and as such $X \sim \text {Unif}(X_{\min }, X_{\max })$ if we assume that the set of workers the orchestrator is overseeing have equivalent reputation, trust, and performance, i.e., the orchestrator has no reason to differentiate one worker from another. Without loss of generality, the performance analysis in this work is applicable for any worker in the ECC system, as such we proceed to analyze an orchestrator-origin (Uniform TQI), i.e., $X\sim \text {Unif}(X_{\min },X_{\max })$ .

C. Impact of Orchestrator Origin Incentives

In this section, we derive the first and second moments for the Uniform TQI case for both the log-family of functions, $r_{{\mathrm {log}}}(x,\alpha )$ , and the rational-family, $r_{\text {rat}}(x,\alpha )$ . We use the notation $\mathbb {E}_{\Pi }[\cdot ]$ to indicate expectation over the uniform distribution for $X$ , i.e., $\mathbb {E}_{\Pi }[y] = \int _{-\infty }^{\infty } y f_{X,\Pi }(x) \, dx$ where

$$\begin{align*} f_{X,\Pi }(x) = \begin{cases} \frac {1}{X_{\max }-X_{\min }}, & X_{\min } \leq x \leq X_{\max } \\ 0, & {\mathrm {otherwise}}\end{cases} \tag{26}\end{align*}$$ indicates that $X\sim f_{X,\Pi }(x)=\text {Unif}(X_{\min },X_{\max })$ .

1) Log Incentive-Vacation Family:

For the log-family, i.e., $r(x)=r_{{\mathrm {log}}}(x,\alpha )$ , we now list the mathematically obtained moments, starting with the first moment is formulated as

$$\begin{align*}&\mathbb {E}_{\Pi }\left [{V_{{\mathrm {log}}}\left ({x,\alpha }\right )}\right ] \\&\;=\left ({-\alpha }\right )^{+} \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},cvx}}(x)}\right ] +\left ({1-| \alpha | }\right )^{+} \mathbb {E}_{\Pi }\left [{r_{\text {lnr}} (x)}\right ] \\&\;\quad {}+\left ({\alpha }\right )^{+} \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},ccv}}(x)}\right ] \tag{27}\end{align*}$$ where the first moment for the convex component is $$\begin{align*} \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},cvx}}\left ({x,\beta }\right )}\right ]=&\frac {\beta ^{V_{\max }} \left ({V_{\max }-V_{\min }}\right )}{\beta ^{V_{\min }}-\beta ^{V_{\max }}}+V_{\max } \\&{}+\frac {1}{\log \left ({\beta }\right )} \tag{28}\end{align*}$$ the first moment of the linear component is $$\begin{equation*} \mathbb {E}_{\Pi }\left [{r_{\text {lnr}}(x)}\right ]= \frac {V_{\max }+V_{\min }}{2} \tag{29}\end{equation*}$$ while the first moment of the decreasing anti-convex states as $$\begin{equation*} \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},ccv}}\left ({x,\beta }\right )}\right ]=\frac {\beta ^{V_{\max }}V_{\max }-V_{\min } \beta ^{V_{\min }}}{\beta ^{V_{\max }}-\beta ^{V_{\min }}}-\frac {1}{\log \left ({\beta }\right )}. \tag{30}\end{equation*}$$

We formulate the second moment for the log-family as

$$\begin{align*}&\mathbb {E}_{\Pi }\left [{V_{{\mathrm {log}}}^{2}\left ({x,\alpha ,\beta }\right )}\right ]=\left ({(\alpha )^{+}}\right )^{2} \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},ccv}}\left ({x,\beta }\right )^{2}}\right ] \\&\;\quad {}+2 \left ({(\alpha )^{+}}\right ) \left ({(1-|\alpha |)^{+}}\right ) \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},ccv}}\left ({x,\beta }\right ) r_{\text {lnr}}(x)}\right ] \\&\;\quad {}+\left ({(-\alpha )^{+}}\right )^{2} \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},cvx}}\left ({x,\beta }\right )^{2}}\right ] \\&\;\quad {}+2 \left ({(-\alpha )^{+}}\right ) \left ({(1-|\alpha |)^{+}}\right ) \mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},cvx}}\left ({x,\beta }\right ) r_{\text {lnr}}\left ({x,\alpha }\right )}\right ] \\&\;\quad {}+\left ({(1-|\alpha |)^{+}}\right )^{2} r_{\text {lnr}}(x)^{2} \tag{31}\end{align*}$$ where the second moment for the log convex component is obtained as $$\begin{align*}&\mathbb {E}_{\Pi }\left [{r^{2}_{{\mathrm {log},cvx}}\left ({x,\beta }\right )}\right ]=\frac {1}{\log ^{2}\left ({\beta }\right ) \left ({\beta ^{V_{\max }}-\beta ^{V_{\min }}}\right )} \\&\;\bigg (\beta ^{V_{\max }} \left ({V_{\min } \log (\beta ) (V_{\min } \log (\beta )+2)+2}\right ) \\&\;\quad {}-\beta ^{V_{\min }} \left ({V_{\max } \log (\beta ) (V_{\max } \log (\beta )+2)+2}\right )\bigg ) \tag{32}\end{align*}$$ while the second moment of the linear component is $$\begin{equation*} \mathbb {E}_{\Pi }\left [{r^{2}_{\text {lnr}}(x)}\right ]= \frac {1}{3} \left ({V_{\max }^{2}+V_{\max } V_{\min }+V_{\min }^{2}}\right ) \tag{33}\end{equation*}$$ and its correspondent second moment of the decreasing log anti-convex is $$\begin{align*}&\mathbb {E}_{\Pi }\left [{r^{2}_{{\mathrm {log},cvx}}\left ({x,\beta }\right )}\right ]=\frac {1}{\log ^{2}\left ({\beta }\right ) \left ({\beta ^{V_{\max }}-\beta ^{V_{\min }}}\right )} \\&\;\bigg (\beta ^{V_{\max }} \left ({V_{\min } \log (\beta ) (V_{\min } \log (\beta )+2)+2}\right ) \\&\;\quad {}-\beta ^{V_{\min }} \left ({V_{\max } \log (\beta ) (V_{\max } \log (\beta )+2)+2}\right )\bigg ). \tag{34}\end{align*}$$ In relation to the cross terms, the log concave-linear is obtained as $$\begin{align*}&\mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},cvx}}\left ({x,\beta }\right ) r_{\text {lnr}}(x)}\right ]=\frac {1}{4 \log \left ({\beta }\right ) \left ({\beta ^{V_{\max }}-\beta ^{V_{\min }}}\right )^{2}} \\&\;\bigg (-4 \beta ^{V_{\max }+V_{\min }} \left ({\log \left ({\beta }\right ) \left ({V_{\max }^{2}+V_{\min }^{2}}\right )+V_{\max }+V_{\min }}\right ) \\&\;\quad {}+\beta ^{2 V_{\max }} \left ({2 V_{\min } \log (\beta ) (V_{\max }+V_{\min })+3 V_{\max }+V_{\min }}\right ) \\&\;\quad {}+\beta ^{2 V_{\min }} \left ({2 V_{\max } \log (\beta ) (V_{\max }+V_{\min })+V_{\max }+3 V_{\min }}\right )\bigg ) \\{}\tag{35}\end{align*}$$ and the log convex-linear cross term is $$\begin{align*}&\mathbb {E}_{\Pi }\left [{r_{{\mathrm {log},cvx}}\left ({x,\beta }\right ) r_{\text {lnr}}(x)}\right ]=\frac {1}{4 \log \left ({\beta }\right ) \left ({\beta ^{V_{\max }}-\beta ^{V_{\min }}}\right )^{2}} \\&\;\bigg (-4 \beta ^{V_{\max }+V_{\min }} \left ({\log \left ({\beta }\right ) \left ({V_{\max }^{2}+V_{\min }^{2}}\right )+V_{\max }+V_{\min }}\right ) \\&\;\quad {}+\beta ^{2 V_{\max }} \left ({2 V_{\min } \log (\beta ) (V_{\max }+V_{\min })+3 V_{\max }+V_{\min }}\right ) \\&\;\quad {}+\beta ^{2 V_{\min }} \left ({2 V_{\max } \log (\beta ) (V_{\max }+V_{\min })+V_{\max }+3 V_{\min }}\right )\bigg ). \\{}\tag{36}\end{align*}$$

Upon inspecting (28)–​(36), we find that the terms constituting $\mathbb E_{\Pi }[V_{{\mathrm {log}}}(x,\alpha )$ are in terms of $V_{\min }$ , $V_{\max }$ , and the scaling parameter $\beta$ . Thus, the combination of these parameters, especially $V_{\min }$ and $V_{\max }$ , greatly impacts the moments of the vacation duration.

2) Rational Incentive-Vacation Family:

For the rational-family, i.e., $r(x)=r_{\text {rat}}(x,\alpha )$ , the first moment is of the form

$$\begin{align*}&\mathbb {E}_{\Pi } \left [{V_{\text {rat}}\left ({x,\alpha }\right )}\right ] \\&\;=\left ({-\alpha }\right )^{+}\mathbb {E}_{\Pi }\left [{r_{\text {rat,cvx}}(x)}\right ] +\left ({1-| \alpha | }\right )^{+} \mathbb {E}_{\Pi }\left [{r_{\text {lnr}}(x)}\right ] \\&\;\quad {}+\left ({\alpha }\right )^{+} \mathbb {E}_{\Pi }\left [{r_{\text {rat,ccv}}(x)}\right ] \\{} \tag{37}\end{align*}$$ where the first moment for the rational convex component is $$\begin{equation*} \mathbb {E}_{\Pi }\left [{r_{\text {rat,cvx}}(x)}\right ]=\frac {V_{\max } V_{\min } \ln \left ({\frac {V_{\max }}{V_{\min }}}\right )}{V_{\max }-V_{\min }} \tag{38}\end{equation*}$$ and first moment of the decreasing rational anti-convex is $$\begin{equation*} \mathbb {E}_{\Pi }\left [{r_{\text {rat,ccv}}(x)}\right ]=\frac {V_{\max } V_{\min } \ln \left ({\frac {V_{\min }}{V_{\max }}}\right )}{V_{\max }-V_{\min }}+V_{\max }+V_{\min }. \tag{39}\end{equation*}$$

The second moment for the rational-family is of the form

$$\begin{align*}&\mathbb {E}_{\Pi }\left [{V_{\text {rat}}^{2}\left ({x,\alpha }\right )}\right ]=\left ({(\alpha )^{+}}\right )^{2} \mathbb {E}_{\Pi }\left [{r_{\text {rat,ccv}}(x)^{2}}\right ] \\&\;\quad {}+2 \left ({(\alpha )^{+}}\right ) \left ({(1-|\alpha |)^{+}}\right ) \mathbb {E}_{\Pi }\left [{r_{\text {rat,ccv}}(x) r_{\text {lnr}}(x)}\right ] \\&\;\quad {}+\left ({(-\alpha )^{+}}\right )^{2} \mathbb {E}_{\Pi }\left [{r_{\text {rat,cvx}}(x)^{2}}\right ] \\&\;\quad {}+2 \left ({(-\alpha )^{+}}\right ) \left ({(1-|\alpha |)^{+}}\right ) \mathbb {E}_{\Pi }\left [{r_{\text {rat,cvx}}(x) r_{\text {lnr}}(x)}\right ] \\&\;\quad {}+\left ({(1-|\alpha |)^{+}}\right )^{2} r_{\text {lnr}}(x)^{2} \tag{40}\end{align*}$$ where the second moment for the rational convex component is $$\begin{equation*} \mathbb {E}_{\Pi }\left [{r^{2}_{\text {rat,cvx}}(x)}\right ]=V_{\max } V_{\min } \tag{41}\end{equation*}$$ second moment of the decreasing rational anti-convex is $$\begin{align*}&\mathbb {E}_{\Pi }\left [{r^{2}_{\text {rat,ccv}}(x)}\right ]=V_{\max }^{2}+3 V_{\max } V_{\min } \\&\;\quad {}+\frac {2 V_{\max } V_{\min } \left ({V_{\max }+V_{\min }}\right ) \ln \left ({\frac {V_{\min }}{V_{\max }}}\right )}{V_{\max }-V_{\min }}+V_{\min }^{2} \tag{42}\end{align*}$$ for the rational concave-linear cross term is $$\begin{equation*} \mathbb {E}_{\Pi }\left [{r_{\text {rat,ccv}}(x) r_{\text {lnr}}(x)}\right ]= \frac {1}{2}\left ({V_{\max }^{2} + V_{\min }^{2}}\right ) \tag{43}\end{equation*}$$ and the rational convex-linear cross term is $$\begin{align*}&\mathbb {E}_{\Pi }\left [{r_{\text {rat,cvx}}(x)r_{\text {lnr}}(x)}\right ] \\&\;=V_{\max } V_{\min }\left ({\frac {V_{\max } + V_{\min }}{V_{\max } - V_{\min }} \ln \left ({\frac {V_{\max }}{V_{\min }}}\right )}\right ). \tag{44}\end{align*}$$

Similar to how the log-family moments are, the rational family’s moments in (37)–​(44) depend on the choice of $V_{\min }$ and $V_{\max }$ that form the bounds of the vacation duration.

With these closed-form expressions, the performance metrics in the Uniform TQI are direct substitutions of the expressions. The performance metrics, as a consequence, are directly impacted by the values of $V_{\min }$ and $V_{\max }$ agreed upon by the workers and the orchestrator, even after being filtered by $r(x,\alpha )$ . The choice of $r(x,\alpha )$ to be monotonically decreasing guarantees the existence of an inverse function $X=r^{-1}(v,\alpha )$ which allows forming a bijection between vacations and incentives. This has great impact on the tractability and convergence of both $\mathbb E[V]$ and $\mathbb E[V^{2}]$ .

SECTION V. Results and Discussion

This section provides an analysis based on the closed-form formulations obtained for an IVQ system. We look at three main performance metrics for IVQ and how they behave under the log and rational vacation families. In particular, we look at the PVQ utilization (2), the mean number of jobs in the system (20), and the mean revenue per job (22), both the log case and the rational case. We also evaluate the job satisfaction proportion with a delay threshold for a single worker. Throughout this section, we vary the minimum incentive and its corresponding maximum vacation parameter as a percentage proportion of the service cycle and regard it for different $\alpha$ . We analyze a scenario in which $\mu =50$ , $\lambda =25$ , $X_{\min }=2$ , $X_{\max }=10$ , $V_{\%,\min }=0.1$ , and $V_{\%,\max }=0.5$ .

In Fig. 11, the same PVQ utilization is plotted twice, once with different minimum incentive values on the $x$ -axis, and another for the corresponding maximum vacation, $V_{\max }=r(X_{\min })$ . We only look at $\alpha =\{-1,0,1\}$ for both families (where $\alpha = 0$ is the linear case which is the same for both families) as these values of $\alpha$ cover the preference range from orchestrator-favoring to worker-favoring. It can be seen in Fig. 11 that the PVQ utilization drops for higher incentives (and equivalently, increases for higher vacations). This drop is due to the fact that the PVQ utilization is the proportion of both service time and vacation to the interarrival time (i.e., $\widetilde \rho = (S+\mathbb E [V])/\tau )$ . Thus, for a large interarrival time $\tau$ , the PVQ utilization increases with longer vacations; otherwise, the worker would remain idle for a duration $\tau - S$ (3) written in terms of $\tau$ and $S)$ . It can also be seen that increasing $\alpha$ causes the PVQ utilization curve to bend upward. This is due to the fact that having a low-$\alpha$ penalizes vacations, thus favoring the orchestrator and reducing the average PVQ utilization. This reflects on changing the maximum vacation as well. However, from the perspective of changing the maximum vacation it can be seen that the log and the rational families behave similarly. However, this is not the case when we look at it from the perspective of changing the minimum incentive. In Fig. 11, we can observe the variation of each family by looking at the difference between $\alpha =1$ and $\alpha =-1$ curves and see that the log-family, compared to the rational-family, has a more conservative variation. In terms of incentive utilization, the log-family performs better (lower curve) than the rational-family for high $\alpha$ , and vice-versa for low $\alpha$ because of its convexity not being as symmetric as the rational function’s since it has less vacation per unit incentive for lower incentives, i.e., the marginal cost of performance is cheaper at low incentives.

Fig. 11.

Variations in PVQ utilization with incentive and vacation parameters: (a) PVQ utilization as a function of minimum incentive across different $\alpha$ values. (b) PVQ utilization as a function of the maximum incentive for different $\alpha$ values. Lowering $\alpha$ favors the orchestrator and lowers the PVQ utilization, showing how it varies with incentive and vacation parameters.

Fig. 12 shows the number of jobs the worker processed (queueing jobs and in-service). Increasing the incentives (decreasing the vacations) reduces the number of jobs in the system significantly. However, for low $\alpha$ in both vacation families, changing the incentives has a dampened impact for higher incentives but is somehow significant for lower incentives. This is because that for lower incentives a low $\alpha$ gives the orchestrators less vacation for fewer incentives. While it seems that using a lower $\alpha$ provides better performance, it is based on the assumption that the workers would accept the jobs at a low incentive. This is not always the case. From Fig. 12, it may seem that a higher $\alpha$ value causes poor performance, however for high $\alpha$ , workers would be more willing to sacrifice vacations for the sake of processing more jobs at the user’s inconvenience to get a better profit, increasing their net service.

Fig. 12.

Effect of incentives and vacations on the number of jobs in the system: (a) number of jobs processed as a function of minimum incentive across different $\alpha$ values. (b) Number of jobs processed in relation to maximum vacation across different $\alpha$ values, demonstrating how job quantity is influenced by varying incentive and vacation parameters.

In Fig. 13, we now look at the mean revenue per job. Contrary to the observations from Figs. 11 and 12 which demonstrated better performance for lower $\alpha$ , it comes at a higher average cost per job. For high-$\alpha$ vacations, they come at a lower cost to the orchestrator while giving the workers more freedom in their vacations. Looking at the behavior from the perspective of the maximum vacation, we can see that longer vacations reduce the revenue per job. The rate of reduction in revenue, however, decreases for low $\alpha$ , and increases for high $\alpha$ . Moreover, a point of intersection between different vacation families can be seen when changing the maximum vacation.

Fig. 13.

Relationship between incentives, vacations, and mean revenue per job: (a) mean revenue per job as a function of minimum incentive for various $\alpha$ values. (b) Mean revenue per job versus maximum vacation for various $\alpha$ values, showing the intersection point of vacation families and the differing rates of revenue reduction across $\alpha$ values.

To illustrate the usefulness of the metrics, we define the maximum threshold for waiting time, a deadline, of 0.8 s beyond which the job will expire and be dropped with no reward. We provide a plot of the proportion of jobs for which the delay criteria has been satisfied at different incentives and vacations in Fig. 14. It can be seen that for low incentives, there is a proportion of jobs that remain unsatisfied until a specified incentive beyond which (or equivalently, maximum vacation prior to which) all jobs are completed within their deadline. For low $\alpha$ , ensuring that all jobs are processed prior to their deadline occurs at a low incentive (at an overall higher incentive cost), while the high-$\alpha$ jobs are satisfied at a high incentive. Nevertheless, the system administrator can utilize the closed-form results obtained to identify an optimal incentive at which the target service level comprised of the different performance metrics would be satisfied for a specific $\alpha$ .

Fig. 14.

Impact of incentives and vacations on job satisfaction within delay criteria: (a) proportion of jobs meeting delay criteria versus minimum incentive for different $\alpha$ values. (b) Proportion of jobs meeting delay criteria versus maximum vacation for different $\alpha$ values. Results show the thresholds at which job satisfaction is achieved for varying incentive and vacation parameters.

SECTION VI. Practical Considerations

In practice, there are some considerations when using the IVQ model. Namely, considerations regarding the choice of vacation function and how they are priced.

A. Choice of $r(X)$ and $\alpha$

In an ECC system, the IVQ function can be thought of as a contract between the orchestrator and the workers. Both entities can negotiate both the choice of $r(X)$ and $\alpha$ . For example, an orchestrator whose service has a high cost of negative experience can decide to use the log-family, with an initial $\alpha =-1$ for any worker it recruits. As the worker grows to profit and deem the ECC system as a profitable system, and as it—from the perspective of the orchestrator—becomes more trustworthy and reliable, the value of $\alpha$ can then increase over time. The value of initial $\alpha$ in the system can also be negotiated by the worker in case it is not feasible for the worker to achieve its profitability target. As such, the orchestrator’s choice of $r(X)$ is context-based. However, the space of admissible IVQ functions can searched for an optimal $r(X)$ if the context can be properly modeled.

B. Human and Device Heterogeneity

There are a number of factors that influence the incentive-vacation $r(X)$ , and they need to be crafted in a manner that guarantees the system’s stability and performance, as mentioned earlier. In the IVQ, we have focused on the influence of incentives on the vacation as the main factor. However, we briefly point to two other factors that impact the worker’s vacation as well as overall availability. The first factor, which is the biggest source of heterogeneity, is the worker’s behavior. People differ in how, when, and what they use their devices for, which impacts how long a worker device is available for, and how much resources are available. In IVQ, this translates to how much vacation can a worker device take to address the multitenancy. The second factor is heterogeneity inherent to the devices themselves as they are of different capabilities. Both factors can influence the choice of $r(X)$ and even introduce more variables and parameters to it. However, the Internet of Behaviors (IoB) can allow proper characterization of worker capabilities through the analysis of human behavior [35]. While IoB focuses on human-centric applications, the impact of IoB can extend to XEC applications.

C. Pricing of Incentives

As previously mentioned in Section IV-B, the incentive is related to the market price for computational tasks. One way to regard an IVQ system is by looking at it as a set of contracts: a contract between the customer and the orchestrator, and a contract between the orchestrator and the worker [36]. All parties in a contract seek an agreement in spite of their different objectives. For the customer, that is the service level agreement (SLA). The SLA indirectly impacts the agreement between the orchestrator and the worker, however workers can be recruited to provide similar service to another customer. As such, the risk present at the orchestrator-worker dynamic can be transferred to the customer, ultimately influencing the price. Techniques for drafting optimal contracts to maximize the service level as well as the profit [37] are crucial for the success of XEC systems.

SECTION VII. Conclusion

The rising demand for cloud services is predicted to surpass the capacity of cloud computing. To cope with such demands, paradigms like Edge and Fog computing have physically relocated service provision closer to the customer. While this proximity achieves better latency and reduces operational costs and the burden on the backhaul network, it necessitates more complex management. XEC represents a promising frontier in which user-owned devices, rich with resources, can be exploited for service provision, albeit at the cost of dealing with the uncertainty and unreliability of these devices and their owners. In this article, we describe an orchestrator-based edge system that rents multitenant devices from users to provide an edge service, offering an incentive in return. To serve both the extreme edge and their own users, we propose the IVQ model, which utilizes the XEC worker as a server that takes a vacation to perform tasks unrelated to the extreme edge, with the effect of incentives reflected in the length of these vacations. We model the behavior of systems through our IVQ model and derive closed-form expressions that relate the performance of such a P-Limited IVQ system with uniform incentives. It has been clearly demonstrated that increasing incentives enhances performance and reduces the sojourn time for jobs in the system. The IVQ model is useful for analyzing extreme edge systems where user-owned devices have the potential to become a significant part of the infrastructure, particularly in systems with an XEC orchestrator recruiting and distributing jobs to XEC workers.

Furthermore, the principles underpinning our proposed model are not confined to vacation queueing configurations alone but are applicable to a wider array of service systems that follow similar incentive-performance interplays. This indicates that our findings have implications for a diverse set of contexts where the strategic implementation of incentives is key to optimizing operational outcomes, thereby offering a generalizable approach to understanding and enhancing system performance.