2025-11-16T15:01:13.538180

Age of Job Completion Minimization with Stable Queues

Mitrolaris, Banerjee, Ulukus

We consider a time-slotted job-assignment system with a central server, N users and a machine which changes its state according to a Markov chain (hence called a Markov machine). The users submit their jobs to the central server according to a stochastic job arrival process. For each user, the server has a dedicated job queue. Upon receiving a job from a user, the server stores that job in the corresponding queue. When the machine is not working on a job assigned by the server, the machine can be either in internally busy or in free state, and the dynamics of these states follow a binary symmetric Markov chain. Upon sampling the state information of the machine, if the server identifies that the machine is in the free state, it schedules a user and submits a job to the machine from the job queue of the scheduled user. To maximize the number of jobs completed per unit time, we introduce a new metric, referred to as the age of job completion. To minimize the age of job completion and the sampling cost, we propose two policies and numerically evaluate their performance. For both of these policies, we find sufficient conditions under which the job queues will remain stable.

academic

안정적 큐를 갖춘 작업 완료 나이 최소화

기본 정보

논문 ID: 2511.04630
제목: Age of Job Completion Minimization with Stable Queues
저자: Stavros Mitrolaris, Subhankar Banerjee, Sennur Ulukus (메릴랜드 대학교 칼리지 파크)
분류: cs.IT, cs.NI, cs.SY, eess.SP, eess.SY, math.IT, math.PR
발표 시간: 2025년 11월 6일 (arXiv 사전 인쇄본)
논문 링크: https://arxiv.org/abs/2511.04630

초록

본 논문은 중앙 서버, N명의 사용자, 마르코프 체인으로 상태가 변하는 기계(마르코프 기계)로 구성된 시간 슬롯 기반 작업 할당 시스템을 연구한다. 사용자는 확률적 작업 도착 프로세스에 따라 중앙 서버에 작업을 제출하며, 서버는 각 사용자를 위해 전용 작업 큐를 유지한다. 기계가 서버에서 할당한 작업을 처리하지 않을 때, 내부 바쁜 상태 또는 유휴 상태에 있을 수 있으며, 이러한 상태의 동역학은 이진 대칭 마르코프 체인을 따른다. 서버는 기계 상태 정보를 샘플링하여 기계가 유휴 상태임을 인식할 때 사용자를 스케줄링하고 작업을 제출한다. 단위 시간당 완료된 작업 수를 최대화하기 위해, 저자들은 "작업 완료 나이(Age of Job Completion)"라는 새로운 메트릭을 도입한다. 작업 완료 나이와 샘플링 비용을 최소화하기 위해 두 가지 전략을 제안하고 그 성능을 수치적으로 평가하며, 두 전략 모두에 대해 작업 큐 안정성을 보장하는 충분 조건을 도출한다.

연구 배경 및 동기

1. 해결해야 할 문제

본 논문은 엣지 컴퓨팅 시나리오에서의 작업 오프로딩 문제를 연구하며, 여러 사용자가 공유 엣지 컴퓨팅 장치(마르코프 기계)를 놓고 경쟁한다. 핵심 과제는 다음을 포함한다:

기계 상태의 불확실성(유휴/내부 바쁜 상태)
상태 샘플링의 비용
다중 사용자 경쟁 하에서의 작업 스케줄링
큐 안정성 보장

2. 문제의 중요성

지능형 감시 등 중요 작업 제어 애플리케이션에서 엣지 장치는 일반적으로 여러 사용자 또는 서버에 의해 공유되며, 각각 독립적으로 계산 작업을 생성한다. 다음과 같은 이유로:

작업 오프로딩 프로세스의 확률성
엣지 장치 가용성의 높은 불확실성
장치 운영 상태 추적의 필요성
시스템 성능 보장을 위한 적시 작업 오프로딩의 필요성

3. 기존 방법의 한계

기존 문헌에는 다음과 같은 부족함이 있다:

5의 AoII 메트릭: 완료된 작업 수 최대화를 직접 목표로 하지 않음
6의 이진 신선도(BF), 거짓 거부율(FRR), 거짓 수용율(FAR): 마찬가지로 완료된 작업 수 최대화 목표를 직접 포착하지 못함
7,8,10의 방법: 무한 큐를 고려하지 않으며, 큐 안정성 분석 부재
대부분의 연구: 작업 큐가 없거나 큐 용량이 제한되어 실제 장기 운영 시나리오에 부적합

4. 연구 동기

작업 완료 효율을 더 직접적으로 반영하는 메트릭 도입
무한 큐 용량의 실제 시나리오 고려
큐 안정성의 이론적 보장 제공
작업 완료 효율과 샘플링 비용 간의 균형

핵심 기여

새로운 메트릭 "작업 완료 나이(Age of Job Completion)" 제안: 단위 시간당 완료된 작업 수를 직접 반영하며, 기존 AoII, BF 등의 메트릭보다 작업 오프로딩 시스템에 더 적합
두 가지 전략 설계:
- 적응형 무작위 전략(Adaptive Randomized Policy, ϕ₁)
- 최대 나이 스케줄링 전략과 적응형 무작위 샘플링(Max-Age Policy with Adaptive Randomized Sampling, ϕ̄₁)
이론적 안정성 분석: 두 전략에 대해 큐 안정성의 충분 조건을 도출(명제 1과 2)하며, 이는 마르코프 기계 작업 오프로딩 연구에서 처음 제공되는 안정성 결과
폐쇄형 표현식: 고정 부분 시스템이 영구적 적체 조건 하에서, 평균 작업 완료 나이와 샘플링 비용의 폐쇄형 표현식 제공(정리 1-4)
수치 평가: 수치 실험을 통해 전략 성능을 검증하며, 높은 도착률에서 최대 나이 전략이 적응형 무작위 전략을 현저히 능가함을 발견

방법론 상세 설명

작업 정의

시스템 모델:

입력: N명의 사용자, 각 사용자가 시간 슬롯 말에 확률 pᵢ로 작업 제출(i.i.d. 베르누이 프로세스)
상태 공간: 기계 상태 x(t) ∈ {-1, 0, 1, ..., N, fr}
- -1: 내부 바쁜 상태
- 0: 작업 완료 후 상태 미확인
- i ∈ {1,...,N}: 사용자 i의 작업 처리 중
- fr: 유휴 상태
마르코프 동역학: 유휴↔내부 바쁜 상태의 전이 확률은 q(이진 대칭)
서비스 시간: 사용자 i의 작업은 매개변수 qᵢ의 기하 분포를 따름
작업 완료 후: 확률 s로 내부 바쁜 상태로, 확률 (1-s)로 유휴 상태로 전이

결정 변수:

샘플링 결정 μ(t) ∈ {0,1}: 시간 슬롯 t에서 기계 상태를 샘플링할지 여부(비용 L)
스케줄링 결정 π(t) = (π₁(t),...,πₙ(t)): 어느 사용자의 작업을 선택할지

최적화 목표: 총 평균 비용 최소화: $\Delta^{\phi} + S^{\phi} = \frac{1}{N}\sum_{i=1}^{N}\Delta_i^{\phi} + S^{\phi}$

여기서:

$\Delta_i^{\phi}$ : 사용자 i의 평균 작업 완료 나이
$S^{\phi}$ : 평균 샘플링 비용

제약: 큐 안정성(정상 복귀 마르코프 체인)

모델 아키텍처

1. 적응형 무작위 전략 (ϕ₁)

정의 (정의 1): 전략은 집합 Π = {(μ(S), π(S)) : S ⊆ N, S ≠ ∅}로 특징지어지며, 여기서:

μ(S) ∈ (0,1]: 비어있지 않은 큐 집합이 S일 때의 샘플링 확률
π(S) = (π₁(S),...,πₙ(S)): 스케줄링 확률 분포
- πᵢ(S) > 0 당且仅当 i ∈ S
- ∑ᵢ∈S πᵢ(S) = 1

구성 방법:

각 비어있지 않은 부분집합 S ⊆ N에 대해 영구적 적체 시나리오 고려
정리 1과 2를 사용하여 총 비용 상한의 폐쇄형 표현식 도출
최적화 문제(12) 해결: $\min_{\phi} \sum_{k\in S}\Delta_k^{\phi}(S) + S_{ub}^{\phi}(S)$ 제약: μ ∈ (0,1), πₖ ∈ (0,1), ∑ₖ∈S πₖ = 1
국소 최적해(μ*(S), π*(S)) 도출
모든 부분집합의 해를 통합하여 전략 집합 Πc 구성

핵심 공식 (정리 1): 사용자 k의 평균 나이: $\Delta_k^{\phi}(S) = \frac{1}{\left(\frac{s}{q}+2\left(\frac{1}{\mu}-1\right)+\bar{\eta}\right)\left(\frac{\psi_k^2}{\pi_k}+\left(\frac{1}{q_k}+\frac{1-s}{q}-2\right)\psi_k+\ldots\right)} + 1$

여기서 $\bar{\eta} = \sum_{i\in S}\frac{\pi_i}{q_i}$ , $\psi_k = \eta_k + \pi_k + 2(\frac{1}{\mu}-1) + \frac{s}{q}$

샘플링 비용 상한 (정리 2): $S_{ub}^{\phi}(S) = \frac{(L+1)\mu}{p^*}\left(\frac{1}{\frac{1}{\mu}p^* + \bar{\eta}}\right)$

여기서 $p^* = \frac{q}{1-(1-2q)(1-\mu)}$

2. 최대 나이 전략과 적응형 무작위 샘플링 (ϕ̄₁)

스케줄링 전략: πᴹᴬ(S)는 각 시간 슬롯에서 집합 S의 작업 완료 나이가 최대인 사용자 선택(라운드 로빈 전략과 동등)

샘플링 전략: 적응형 무작위 샘플링, 집합 Π̄c = ∪_{S⊆N,S≠∅}{μ̄*(S)}로 특징지어짐

핵심 공식 (정리 3): 사용자 k의 평균 나이: $\Delta_k^{\bar{\phi}}(S) = \frac{N(\beta_2 - \beta_1^2) + \sum_{i\in S}\frac{1-q_i}{q_i^2}}{2\left(N\beta_1 + \sum_{i\in S}\frac{1-q_i}{q_i}\right)} + \frac{1}{2}\left(N\beta_1 + \sum_{i\in S}\frac{1-q_i}{q_i} + 1\right)$

여기서:

$\beta_1 = \frac{1}{\bar{\mu}}\left((1-\bar{\mu}) + \frac{s}{\bar{\mu}q} + 1\right)$
$\beta_2 = 2\frac{1-\bar{\mu}}{\bar{\mu}}\left(\frac{s}{1-\bar{\mu}}\alpha^2 + \alpha - s - \bar{\mu}(1-s) + 3\right) + \beta_1$
$\alpha = 1-\bar{\mu}+\frac{\bar{\mu}}{q}$

샘플링 비용 (정리 4): $S^{\bar{\phi}}(S) = \frac{\bar{\mu}NL}{N\left((1-\bar{\mu}) + \frac{s\bar{\mu}}{q} + 1\right) + \bar{\mu}\sum_{i\in S}\frac{1-q_i}{q_i}}\cdot\frac{1}{\left(p_1^* + \frac{(1-p_1^*)(1+p^*)}{p^*}\right)}$

여기서 $p_1^* = s(1-\bar{\mu})p^* + (1-s)(1-(1-\bar{\mu})p^*)$

기술적 혁신점

작업 완료 나이 메트릭의 도입:
- 정의: vᵢ(t) = t - sup{t' : t' < t, bᵢ(t') = 1}(마지막 작업 완료 이후의 시간)
- 장점: 작업 완료 빈도를 직접 반영하며, 단위 시간당 완료된 작업 수 최대화와 동등
- AoII와의 차이: AoII는 정보 정확성에 관심, 작업 완료 나이는 처리량에 관심
적응형 무작위 전략 설계:
- 전통적 고정 확률 무작위 전략과 구별
- 비어있지 않은 큐 집합에 따라 동적으로 샘플링 및 스케줄링 확률 조정
- 시스템 리소스의 효율적 활용(빈 큐 사용자 스케줄링 안 함)
- 수학적으로 처리 가능(각 부분집합은 고정 무작위 전략에 대응)
영구적 적체 분석 방법:
- 부분집합 S의 큐가 영구적으로 비어있지 않다고 가정
- 폐쇄형 비용 표현식 도출
- 최적화를 통해 해당 부분집합의 최적 전략 매개변수 도출
- 모든 부분집합의 해를 통합하여 완전한 적응형 전략 구성
큐 안정성 충분 조건:
- 명제 1: 적응형 무작위 전략의 지수 수준 조건
- 따름정리 1: 단일하지만 더 보수적인 충분 조건
- 명제 2: 최대 나이 전략의 충분 조건
- χ(q,s) 함수 도입으로 기계 유휴 확률 하한 특징화

실험 설정

수치 실험 매개변수

시스템 구성:

사용자 수: N = 4
기계 매개변수:
- 상태 전이 확률: q ∈ 0.1, 0.9
- 완료 후 내부 바쁜 확률: s = 0.5(일부 실험) 또는 s = 0.3
샘플링 비용: L = 5
서비스율 벡터: q̄ = [0.1, 0.4, 0.6, 0.9](일부 실험) 또는 기타 구성

도착률 구성:

낮은 도착률: p = 0.01, 0.02, 0.05, 0.06
높은 도착률: p̃ = 0.05, 0.2, 0.5, 0.6
안정성 테스트: 다양한 구성

평가 지표

총 평균 비용: Δ^φ + S^φ
- 평균 작업 완료 나이와 평균 샘플링 비용 포함
- 주요 성능 지표
큐 안정성:
- 수치 시뮬레이션을 통한 큐 길이 프로세스 관찰
- 이론적 안정성 조건 검증

비교 방법

ϕ₁: 적응형 무작위 전략
ϕ̄₁: 최대 나이 스케줄링 + 적응형 무작위 샘플링

구현 세부사항

최적화 문제(12)와(16)은 수치 방법으로 국소 최적 해결
모든 2^N - 1개의 비어있지 않은 부분집합에 대해 최적화 수행
마르코프 체인 시뮬레이션을 사용하여 전략 성능 평가
정상 상태 동작 획득을 위한 장시간 시뮬레이션

실험 결과

주요 결과

그림 4: q에 따른 총 비용 변화

N=4, s=0.5, L=5, q̄=0.1, 0.4, 0.6, 0.9 구성 하에서:

낮은 도착률 p = 0.01, 0.02, 0.05, 0.06:
- 두 전략의 성능이 유사
- 총 비용은 q 증가에 따라 감소
- 이유: 낮은 도착률에서 두 가지 작업 보존 전략 모두 작업을 효과적으로 처리
높은 도착률 p̃ = 0.05, 0.2, 0.5, 0.6:
- ϕ̄₁(최대 나이 전략)이 ϕ₁(적응형 무작위 전략)을 현저히 능가
- 성능 차이 명확(약 10-20 단위)
- 두 전략의 비용 모두 q 증가에 따라 감소
- 이유: 높은 부하에서 결정적 라운드 로빈이 무작위 스케줄링보다 효율적
추세 분석:
- q가 클수록(상태 전이가 빠를수록) 시스템 성능이 우수
- 높은 도착률에서 전략 선택이 더 중요

큐 안정성 실험

사례 1: 불안정

매개변수: N=4, q=0.35, s=0.3, L=5
서비스율: q̄ = 0.55, 0.73, 0.84, 0.91
도착률: p = 0.09, 0.09, 0.12, 0.14
결과: 명제 1과 2의 조건이 만족되지 않으며, 수치 검증에서 큐 불안정
설명: 도착률이 서비스율에 비해 상대적으로 높음

사례 2: 안정이지만 조건 불만족

매개변수: N=4, q=0.5, s=0.5, L=5
서비스율: q̄ = 0.4, 0.6, 0.8, 0.94
도착률: p = 0.04, 0.05, 0.06, 0.06
결과: 충분 조건이 만족되지 않으나, 수치에서 두 전략 모두 큐 안정
설명: 제시된 충분 조건이 보수적(충분하지만 필요하지 않음)

실험 발견

전략 성능:
- 최대 나이 전략이 높은 부하에서 명확한 우위
- 낮은 부하에서 전략 차이 미미
- 두 전략 모두 작업 보존
안정성 조건:
- 사용자 도착률이 서비스율보다 훨씬 낮을 때만 큐 안정
- 이론적 충분 조건이 보수적
- 조건 불만족이지만 실제 안정인 경우 존재
시스템 매개변수 영향:
- 상태 전이 확률 q가 성능에 현저한 영향
- 도착률 구성이 전략 선택의 중요성 결정

결론 및 논의

주요 결론

메트릭 혁신: 작업 완료 나이가 작업 오프로딩 시스템의 처리량 목표를 효과적으로 포착
전략 설계:
- 적응형 무작위 전략은 부분 시스템 최적화를 통해 구성
- 최대 나이 전략이 높은 부하에서 성능 우수
- 두 전략 모두 큐 안정성 보장 가능
안정성 이론:
- 충분 조건 제공(명제 1-2)
- 조건은 도착률, 서비스율, 기계 매개변수의 관계 포함
- 충분하지만 필요하지 않음(보수성 존재)
성능 통찰:
- 낮은 부하에서 전략 차이 작음
- 높은 부하에서 결정적 스케줄링이 무작위보다 우수
- 기계 상태 전이 속도가 성능에 현저한 영향

한계

대칭성 가정:
- 현재 이진 대칭 마르코프 체인만 고려(전이 확률 동일)
- 실제 시스템은 비대칭일 수 있음
안정성 조건 보수성:
- 충분 조건이 엄격
- 지수 수준(2^N - 1) 조건 검증 필요
- 단일 조건(따름정리 1)이 더 보수적
국소 최적:
- 최적화 문제(12)와(16)은 국소 최적만 해결
- 더 우수한 해 존재 가능
필요 조건 분석 부재:
- 큐 안정성의 필요 조건 미제시
- 충분과 필요 조건 간 차이 미정량화
증명 생략:
- 모든 증명이 지면 제약으로 인해 저널 버전에서 제공 예정
- 결과의 검증 가능성 영향

향후 방향

비대칭 마르코프 체인: 일반 상태 전이 확률로 확장
필요 조건: 큐 안정성의 필요 조건 도출, 충분 필요 조건 간 차이 축소
전역 최적: 최적화 문제의 전역 최적해 또는 근사 알고리즘 연구
이질적 사용자: 사용자 우선순위, 다양한 QoS 요구사항 고려
다중 기계 시나리오: 기계 네트워크로 확장
실제 시스템 검증: 실제 엣지 컴퓨팅 플랫폼에서 테스트

심층 평가

장점

이론적 기여 현저:
- 마르코프 기계 작업 오프로딩에 대한 큐 안정성 이론 최초 제공
- 폐쇄형 성능 표현식(정리 1-4)의 이론적 가치
- 수학적 유도 엄밀(증명 미포함에도 불구하고)
메트릭 설계 합리적:
- 작업 완료 나이가 직관적이고 효과적
- 처리량 최대화 목표와 직접 대응
- 기존 AoII, BF 등 메트릭보다 작업 오프로딩에 적합
전략 설계 혁신적:
- 적응형 무작위 전략이 유연성과 분석 가능성 균형
- 최대 나이 전략이 단순하고 효율적
- 두 전략이 무작위와 결정적 방법 포괄
문제 모델링 실제적:
- 샘플링 비용 고려
- 무한 큐가 장기 운영 시스템에 더 부합
- 마르코프 기계 모델이 엣지 컴퓨팅에 적합
실험 설계 합리적:
- 다양한 부하 시나리오 비교
- 안정성 이론 검증
- 충분 조건의 보수성 발견

부족함

증명 부재:
- 모든 정리와 명제의 증명 미제공
- 결과 검증 가능성과 신뢰도에 심각한 영향
- 독자가 유도 과정 이해 불가
실험 불충분:
- 소규모 시스템(N=4 사용자)만 고려
- 대규모 시스템의 확장성 분석 부재
- 기타 문헌 방법과의 정량적 비교 없음
- 통계적 유의성 검증 부재
최적화 방법 불명확:
- 문제(12)와(16)의 수치 해결 방법 미설명
- 국소 최적이 전략 성능에 미치는 영향
- 계산 복잡도 논의 부재
안정성 분석 불완전:
- 충분 조건만 제공, 필요 조건 없음
- 조건의 타이트함 미분석
- 충분 필요 조건 간 차이 미정량화
가정의 제한:
- 대칭 마르코프 체인 가정이 강함
- 기하 서비스 시간 분포가 실제와 맞지 않을 수 있음
- 통신 지연, 전송 오류 등 실제 요소 미고려
작성 문제:
- 일부 기호 정의가 불명확(예: xa(t) 사용 적음)
- 그림 2와 3의 설명이 더 상세할 수 있음
- 알고리즘 의사 코드 부재

영향력

이론적 영향:
- 마르코프 기계 작업 오프로딩의 안정성 이론 프레임워크 수립
- 작업 완료 나이 메트릭이 후속 연구에 채택될 가능성
- 적응형 무작위 전략 설계 사고가 영감 제공
실용적 가치:
- 엣지 컴퓨팅 작업 오프로딩 시나리오에 적용 가능
- 전략 설계가 실제 시스템 지도 가능
- 안정성 조건이 설계 기준 제공
한계:
- 완전한 증명 필요로 충분한 평가 불가
- 소규모 실험이 설득력 제한
- 실제 배포에는 더 많은 공학 문제 해결 필요

적용 시나리오

엣지 컴퓨팅:
- 다중 사용자가 공유 엣지 서버 사용
- 상태 샘플링이 필요한 시나리오
- 작업이 큐에 대기 가능
클라우드 컴퓨팅 리소스 스케줄링:
- 가상 머신 상태 불확실
- 다중 테넌트 리소스 경쟁
IoT 작업 오프로딩:
- 장치 상태 무작위 변화
- 샘플링 비용 0이 아님
부적용 시나리오:
- 실시간 요구사항이 극도로 높음(큐 대기 불가)
- 상태 완전 관찰 가능(샘플링 비용 없음)
- 작업이 큐에 대기 불가(즉시 처리 또는 폐기)

참고문헌

본 논문은 주로 다음의 핵심 문헌을 참고한다:

5 Banerjee & Ulukus (2025): 마르코프 기계 추적 및 작업 할당, AoII 메트릭 도입
6 Liyanaarachchi & Ulukus (2025): 다중 마르코프 기계의 최적 모니터링 및 작업 할당
10 Chamoun et al. (2025): MAPPO를 사용한 엣지 서버 모니터링, MDP 방법
11 Kadota et al. (2018): 방송 무선 네트워크에서 정보 나이 최소화 스케줄링 전략
12 Tassiulas & Ephremides (1990): 제약 큐 시스템의 안정성 성질
13 Neely (2010): 확률적 네트워크 최적화, 강 안정성 정의

종합 평가: 본 논문은 마르코프 기계 작업 오프로딩 분야에서 중요한 이론적 기여를 하였으며, 특히 큐 안정성 분석을 최초로 제공한다. 작업 완료 나이 메트릭의 도입이 혁신적이며, 두 가지 전략 설계가 합리적이다. 그러나 증명의 부재, 실험 규모의 제한, 안정성 조건의 보수성은 명백한 부족함이다. 저자들이 상세한 증명, 대규모 실험, 필요 조건 분석을 포함한 완전한 저널 버전을 조속히 제공할 것을 권장하여 이 연구의 가치를 충분히 드러내기를 바란다.