\section{Introduction}

We consider fixed-priority uniprocessor real-time task scheduling with constrained deadlines and arbitrary release jitter in the \emph{sporadic task model} \cite{DBLP:phd/ndltd/Mok83} which is a common model to analyze real-time task systems.

\subparagraph*{Model}

A sporadic task system $\mathscr{T}=\set{\tau_1,\dots,\tau_n}$ is a set of sporadic tasks $
\tau_i$ which are given as a quadruple of non-negative integers $\tau_i = (c_i,d_i,p_i,\jitter_i)$ where $c_i$ represents the task's worst-case execution time, $d_i$ its relative deadline, $p_i$ its period, and $\jitter_i$ its release jitter. The task $\tau_i$ generates an infinite sequence of jobs. Each job has an execution time of at most $c_i \geq 1$ time units and a deadline exactly $d_i$ time units after its arrival time, where $c_i \leq d_i \leq p_i$. The jobs of the task are considered to arrive separated in time by at least $p_i\geq 1$ time units. However, a job is not ready for execution until it is \emph{released}. The time difference between the arrival time and the release time is called \emph{release jitter}. Hence,
in jitter-free systems the jobs are released in the moment they arrive, i.e.
arrival time equals release time.
The release jitter $\jitter_i$ of the task is the maximum time difference between the arrival times and the release times over all jobs of $\tau_i$.

The task system $\mathscr{T}$ has \emph{harmonic periods} iff $p_i \geq p_j$ implies that $p_i/p_j\in\Z$ for all tasks $\tau_i,\tau_j$.
The \emph{utilization} of a task $\tau_i$ is the quantity $c_i/p_i$ and the utilization of the task set $\mathscr{T}$ is $\sum_{i\leq n}c_i/p_i$. The common assumption is that $\sum_{i\leq n}c_i/p_i \leq 1$ as otherwise there are job sequences of $\mathscr{T}$ which can not be scheduled by any algorithm. We refer to this utilization bound as the \emph{schedulability utilization bound}. However, a necessary utilization bound is $\sum_{i<n}c_i/p_i < 1$ as otherwise there is no solution for worst-case response times at all. We refer to this bound as the \emph{general utilization bound}.

\begin{figure}[h]
    \centering
    \tikz[xscale=0.19,yscale=0.6]{
        \def.15{.15}
        \def.2{.2}
        \foreach [count=\i] \c/\p/\jit/\periods/\ops in {
            15/65/8/1/[fill=white!50!blue],
            7/30/5/2/[fill=orange],
            13/50/25/1/[fill=white]
        } {

            \draw [gray] (0,-\i) node [left=5,black] {$\tau_{\i}$} -- (65,-\i);
            \foreach \j in {1,...,\periods} {
                \def\ifnum\j>1{\j}\else{}\fi{\ifnum\j>1{\j}\else{}\fi}
                \draw (\j*\p,-\i+.2) -- (\j*\p,-\i-.2) node [below] {$\ifnum\j>1{\j}\else{}\fi p_{\i}$};
                \draw [-stealth] (\j*\p-\p+\jit,-\i-4*.15) -- (\j*\p-\p+\jit,-\i-.15);
                \draw \ops (\j*\p-\p+\jit,-\i-.15) rectangle (\j*\p-\p+\jit+\c,-\i+.15);
            }
        }
        \draw (0,-1+.2) -- (0,-4-.2) node [below] {$0$};
        \draw [gray] (0,-4) node [left=5,black] {\textsc{fp}} -- (65,-4);
        \draw [fill=orange] (5,-4-.15) rectangle (8,-4+.15);
        \draw [fill=white!50!blue] (8,-4-.15) rectangle (23,-4+.15);
        \draw [fill=orange] (23,-4-.15) rectangle (27,-4+.15);
        \draw [fill=white] (27,-4-.15) rectangle (35,-4+.15);
        \draw [fill=orange] (35,-4-.15) rectangle (42,-4+.15);
        \draw [fill=white] (42,-4-.15) rectangle (47,-4+.15);
    }
    \caption{An example instance $\mathscr{T} = \set{\tau_1,\tau_2,\tau_3}$ with $\tau_1 = (15,d_1,65,8)$, $\tau_2 = (7,d_2,30,5)$, $\tau_3 = (13,d_3,50,25)$ and the resulting \acs{FP} schedule. The arrows indicate the release times of the jobs.}
    \label{fig:example}
\end{figure}

\subparagraph*{Fixed-priority scheduling}

In \ac{FP} scheduling (or static-priority scheduling) the tasks are considered to have a predefined order of priorization. A task $\tau_i$ has a larger priority than a task $\tau_j$ if and only if $i<j$. An \ac{FP} schedule preempts jobs according to these priorities; in more detail, a running job is preempted on the release of a job of task of a higher priority to schedule the new job instead (see \cref{fig:example} for an example).

Two important special cases of \ac{FP} scheduling are \ac{DM} scheduling \cite{DBLP:journals/rts/Baruah11,AUDSLEY1991127} and \ac{RM} scheduling \cite{DBLP:conf/rtss/Ekberg20,DBLP:journals/jacm/LiuL73,DBLP:conf/afips/Serlin72}.
In \ac{DM} scheduling earlier deadlines imply larger priorities while in \ac{RM} scheduling smaller periods imply larger priorities. Both are equal if the deadline of each task is equal to its period.

\subparagraph*{Response time analysis and schedulability testing}

The \emph{response time} of a task is the maximum time difference between the arrival of a job and its completion. In a worst-case scenario we refer to them as \emph{worst-case response times} and these may be used to decide the schedulability of a system. Since task release jitters intensify the complexity of worst-case response times and schedulability testing as well as other types of analysis, they are often assumed to be zero, i.e. $\jitter_i=0$ for all $i\leq n$.
As pointed out by Liu and Layland \cite{DBLP:journals/jacm/LiuL73}, in such \emph{jitter-free} systems the \emph{critical instant} occurs when the jobs of all tasks $\tau_i$ are released simultaneously.
Therefore, without release jitters the worst-case response time of task $\tau_j$ is the earliest point in time $r_j$ where
\[
    \textstyle
    r_j \geq c_j + \sum_{i=1}^{j-1}c_i\ceil{r_j/p_i}.
\]
This inequality models the situation that all jobs are released at time $0$.
If $r_j \leq d_j$, then task $t_j$ completes its job on time which means that task $\tau_j$ is schedulable. If $r_j \leq d_j$ for all tasks $t_j$, then the task system $\mathscr{T}$ is schedulable using the given priorities.

In this paper we consider systems with release jitters. Audsley et al. \cite{DBLP:journals/iee/AudsleyBRTW93} and Tindell et al. \cite{DBLP:journals/rts/TindellBW94} have discussed the release jitter problem in detail. Their work leads to the following understanding of worst-case response times in systems with task release jitters.
The worst-case response time of task $\tau_j$ is the earliest point in time $r_j$ where
\[
    \textstyle
    r_j \geq c_j + \sum_{i=1}^{j-1}c_i\ceil{(r_j+\jitter_i)/p_i}.
\]
The task is schedulable if $r_j \leq d_j-\jitter_j$ and the task set $\mathscr{T}$ is schedulable if $r_j \leq d_j-\jitter_j$ for all tasks $\tau_j$.
Without loss of generality we can assume that the execution requirement of each job of a task $\tau_i$ always equals the task's worst-case execution time $c_i$. Also we can assume that the $i$-th job of a task $\tau_j$ is released at time $(i-1)p_j+\jitter_j$ and its due time is $(i-1)p_j+d_j$. See also \ac{SAS} \cite{DBLP:reference/crc/BaruahG04,DBLP:journals/cj/JosephP86,DBLP:journals/rts/TindellBW94}.
Furthermore, we may restrict our interest to the response time $r_n$ of the last task $\tau_n$:
\[\addtocounter{equation}{1}\tag{\theequation}\label{wcrt-with-jitters-original}
    r_n = \min\set{t|t \geq c_n + \sum_{i<n} c_i\ceil[\Big]{\frac{t+\jitter_i}{p_i}}, t \in \Z_{\geq 0}}.
\]
We refer to the problem to compute $r_n$ as \emph{response time computation} (RTC).

For \ac{FP} scheduling, RTC is NP-hard in general due to Eisenbrand and Rothvoß \cite{DBLP:conf/rtss/EisenbrandR08} even for $\jitter=0$ and it is even hard to approximate within a constant factor. However, for harmonic periods it is polynomial which is a great result by Bonifaci~et~al.~\cite{DBLP:conf/rtss/BonifaciMMW13} and it may even be computed in near-linear time, cf. Nguyen~et~al.~\cite{DBLP:conf/iwoca/NguyenGJ22}.

The computation of response times in real-time systems is often treated as a fixed point problem, where one aims for the smallest fixed point $t$ to the fixed point equation
\(\Phi(t) = t\)
where $\Phi(t) = c_n+\sum_{i<n}c_i\ceil{(t+\jitter_i)/p_i}$. Especially, this allows to argue about intersections of $\Phi$ with the identity function. However, in this paper we present a whole new approach.

\subparagraph*{Mixing Set}

In the \textsc{Mixing Set} problem one is given capacities $a\in\Q^n$ and a right-hand side $b\in\Q^n$ and the goal is to find a solution $(s,x)\in\R_{\geq 0}\times\Z^n$ which optimizes a linear objective function while satisfying the following system of inequalities:
\begin{align*}
    s+a_ix_i & \geq b_i \quad \forall i\in\set{1,\dots,n}
\end{align*}
The problem is \NP-hard due to Eisenbrand and Rothvoß \cite{DBLP:conf/approx/EisenbrandR09}. However, it can be solved in polynomial time in the case of unit capacities \cite{DBLP:journals/mp/GunlukP01,DBLP:journals/mp/MillerW03} or harmonic capacities \cite{DBLP:journals/mp/ZhaoF08} (see also \cite{DBLP:conf/ipco/ConfortiSW08,DBLP:journals/orl/ConfortiZ09} for simpler approaches). The \textsc{Mixing Set} problem plays an important role in production planning (in particular lot-sizing \cite{Pochet:2006:PPM:1202598}).

\subparagraph*{Related work}

In the early '70s it was independently shown by Liu and Layland \cite{DBLP:journals/jacm/LiuL73} and Serlin \cite{DBLP:conf/afips/Serlin72}, that a set of $n$ implicit-deadline synchronous periodic tasks is always schedulable in \ac{RM} scheduling if the task's total utilization is bounded by $n(2^{1/n}-1)$ which is $\ln(2)\approx 0.69$ for $n\rightarrow\infty$. Recently, this seminal result was complemented by Ekberg \cite{DBLP:conf/rtss/Ekberg20} who proved that $\ln(2)$ is in fact the boundary between polynomial and NP-hard schedulability testing; the \ac{FP} schedulability problem is NP-hard even if it is restricted to task sets with \ac{RM} priorities and utilization-bounded from above by any constant truly larger than $\ln(2)$.

Baruah \cite{DBLP:conf/rtss/Baruah20} introduced the idea of ILP-tractability of schedulability analysis problems and in fact, our results prove tractability in his sense.
As mentioned earlier, Eisenbrand and Rothvoß proved hardness results for both RTC \cite{DBLP:conf/rtss/EisenbrandR08} and the \textsc{Mixing Set} problem \cite{DBLP:conf/approx/EisenbrandR09}; in fact, they proved reductions from directed diophantine approximation \emph{to} these problems but they did not give any reductions from them or \emph{between} them, which is what we have found.

\begin{table}[H]
    \centering
    \begin{tabularx}{\textwidth}{p{3cm}|p{5.5cm}|X}
        \toprule
            \textsc{RTC} & $p_i$ harmonic & $p_i \geq 1$
        \\\hline
            $\jitter_i \leq p_i$
            &
            $\Oh(n^2(q+\log p_{\max}))$ *
            &
            $\Oh(n\lcm_{i<n}p_i)$ *\newline
            $\Oh(\max(Sn,T_{\mixing}\log p_{\max}))$ *
        \\\hline

            $\jitter_i=0$
            &
            $\Oh(n\log(n+p_{\max}))$ \cite{DBLP:conf/rtss/BonifaciMMW13}, $\Oh(n\log n)$ \cite{DBLP:conf/iwoca/NguyenGJ22}
            &
            $\Oh(T_{\mixing}\log p_{\max})$ *
        \\\midrule
            \textsc{Mixing Set} & $a_i$ harmonic & $a_i \geq 1 $
        \\\hline
            $b_i \in \Z$
            &
            $\Oh(n^2)$ \cite{DBLP:journals/orl/ConfortiZ09}
            &
            $\Oh(n\lcm_{i\leq n}a_i)$ *\newline
            $\Oh(T_{\response}\log b_{\max})$ *
        \\\hline

            $b_i = \beta \geq \lcm_{j\leq n} a_j$
            &
            $\Oh(n\log(n+\beta))$ *
            &
            $\Oh(T_{\response}\log\beta)$ *

        \\\bottomrule
    \end{tabularx}
    \medskip
    \caption{Overview of algorithmic results for RTC and \textsc{Mixing Set}. Here $S \leq (\sum_{i<n}c_i)/(1-U)$ for utilization $U=\sum_{i<n}c_i/p_i$ is an upper bound on the value of $s$ in any optimal solution to an instance of \textsc{Mixing Set}, $T_{\mixing}$ and $T_{\response}$ are upper bounds on the time required to solve an instance of \textsc{Mixing Set} or RTC, respectively, and $q \leq \abs{\set{p_i-\jitter_i|i\leq n}} \leq n$.\hfill * Result is in this paper}
    \label{tab:results-overview}
\end{table}

\subparagraph*{Our contribution}
Here we give a short summary about all of our results.
\begin{enumerate}[(a)]
    \item\label{dualision-teaser}

    We present a simple dualization technique which allows to solve inequality-constrained optimization problems in a binary search by consecutively solving a dual formulation of the associated decision problem (see \cref{dualision}).
    \item \para{Response Times}
    \begin{enumerate}[1.]
        \item We establish new bounds for worst-case response times in \ac{FP} real-time task systems with period-constrained task release jitter (see \cref{sec:response-time-bounds}).
        \item We present a conditional Karp reduction from RTC to the \textsc{Mixing Set} problem (see \cref{conditional-karp-reduction}). We show how it can be used to derive a bunch of algorithmic results for both problems (see \cref{tab:results-overview} for an overview).
        \item For the most important case of harmonic periods we prove a Cook reduction from RTC to \textsc{Mixing Set} (see \cref{wcrt-harmonic-periods}).
        \item Usually, algorithmic results for worst-case response times are achieved for special cases like equal or harmonic periods only; in fact, we can cope even with the general case of \emph{arbitrary} periods. Especially, we give a Turing reduction from RTC to \textsc{Mixing Set} and we study the dependence of the running times on the utilization (see \cref{wcrt-arbitrary-periods}).
    \end{enumerate}
    \item \para{Mixing Set} We can reverse our methodology to solve the \textsc{Mixing Set} problem by computing worst-case response times for associated real-time task systems (see \cref{sec:mixing-set}).
    \item \para{4-block Programs} Finally, we show how the dualization technique can by applied to solve specific 4-block integer programs (see \cref{application-to-4-block}). Furthermore, we show that they are NP-hard to approximate to any constant factor (see \cref{4-block-hardness}).
\end{enumerate}

\subparagraph*{RTC with Harmonic Periods}

We consider the decision problem $r_n \leq_? k$ for which we present a Karp reduction to the \textsc{Mixing Set} problem in constant time. However, this reduction works for large values of $k$ only, i.e. $k \geq S$ for some value $S$.
In the case of harmonic periods we managed to develop an algorithm which discovers variable values which allow to reduce $S$ such that smaller values for $k$ can be decided. To this end we prove a structural property, which, given only a rough knowledge about $r_n$, reveals the exact variable values of the variables for the tasks of largest period. The algorithm then works in two steps. First, we do a walk over the differences $p_i-\jitter_i$ in non-decreasing order to identify two consecutive differences $k_i = p_i-\jitter_i$ and $k_{i+1} = p_i-\jitter_i$ such that $r_n\in[k_i,k_{i+1}]$. Here, the order is of utmost importance, as we rely on the information of the previous decisions. In the second step we utilize a binary search to compute $r_n$. Together, this yields a Cook reduction to \textsc{Mixing Set}. We highlight this result, as it gives an efficient algorithm to the most important case of a long-standing problem (e.g.
\cite{

    DBLP:journals/iee/AudsleyBRTW93,%
    DBLP:journals/rts/TindellBW94,%
    DBLP:conf/rtss/DavisB08,%

    DBLP:conf/rtss/BonifaciMMW13,%

    DBLP:conf/iwoca/NguyenGJ22%
}) \todo{cite more}.
Remark that \ac{FP} scheduling superceeds the generality of \ac{DM} and \ac{RM} scheduling and in fact, we never rely on their properties.

\subparagraph*{Notation}

We define $[n]=\set{z\in\Z|1\leq z \leq n}$ to denote the set of the first $n$ natural numbers. Given a vector $v=(v_1,\dots,v_n)\in\R^n$ we denote the largest or smallest entry in $v$ by $v_{\max} = \max_{i\leq n}v_i$ or $v_{\min} = \min_{i\leq n}v_i$, respectively. For sizes $a,b$ we write $a \leq_? b$ to denote the decision problem to decide whether $a \leq b$ is true or not, i.e. the correct answer to $a \leq_? b$ is \textsc{yes} if $a \leq b$ and \textsc{no} otherwise. In the same manner we define $a \geq_? b$. For any positive integers $z_i \in \Z_{\geq 1}$ and an index set $I$ let $\lcm_{i\in I} z_i$ denote the least common multiple of all numbers in $\set{z_i|i\in I}$.

Whenever we specify the computation time of an algorithm in $\Oh$-notation, we quantify its total number of arithmetic operations on numbers from the input. With $\log=\log_2$ we always refer to the \emph{binary} logarithm.

\section{Preliminaries}

Here we introduce a dualization technique for optimization problems. Also we show first insights about the \textsc{Mixing Set} problem and present some new bounds for response times in real-time systems.

\subsection{A Dualization Technique}\label{dualision}

We present a simple optimization technique by studying a dual formulation of the associated decision problem. Consider a general optimization problem as follows.
Let $X$ be a set and let $f:X\rightarrow\Z$ and $g:X\rightarrow\R$ be two computable functions and we seek to minimize $f(x)$ over all $x\in X$ while $g(x) \geq b$ for some right-hand side $b\in\R$ and other constraints $G(x)$ have to be satisfied, i.e. we aim to compute
\[
    \sigma = \min\set{f(x)|g(x)\geq b,\;G(x),\;x \in X}.
\]
For an integer $k$ it holds that $\sigma \leq k$ if and only if
\[\addtocounter{equation}{1}\tag{\theequation}\label{dual-program-technique-dual-decision}
    \max\set{g(x)|f(x)\leq k,\;G(x),\;x\in X} \geq b.
\]
Hence, if we can bound $\sigma$ to an interval $[\ell,u]$ and have an algorithm to decide \eqref{dual-program-technique-dual-decision} in at most time $T$ for each $k\in[\ell,u]$, then we can compute $\sigma$ in time $\Oh(T\log(u-\ell))$ by using a binary search for the smallest feasible $k$ in $[\ell,u]$.
At first glance this does not help a lot, as we have replaced one optimization problem by another. However, if $f$ is a function of low complexity, then in order to decide \eqref{dual-program-technique-dual-decision} we can try to utilize an algorithm for \(\max\set{g(x)|G(x),x\in X}\) with respect to the simple additional constraint \(f(x)\leq\kappa\) (which is of low complexity). Remark that the approach may be adapted to approximate $\sigma$ for a function $f:X\rightarrow\R$ as well. However, in this paper we only care about integer-valued objectives. The technique is applied in \cref{response-time-computation,application-to-4-block}.

\subsection{Mixing Set}

Although \textsc{Mixing Set} can be solved in more general settings, for the scope of this paper we will always assume that $a\in\Z_{\geq 1}^n$ and $b\in\Z^n$. In more detail, given capacities $a\in\Z_{\geq 1}^n$, a right-hand side $b\in\Z^n$, and weights $w\in\Z_{\geq 0}^n$ (and $w_0\in\Z_{\geq 0}$) we consider the following minimization problem:
\[\label{mixing-set}
    \min\set{w_0s+\textstyle\sum_{i\leq n} w_ix_i | s+a_ix_i \geq b_i\;\forall i \in [n],\quad  s\in\Z_{\geq 0},\quad x\in\Z^n}
    \tag{\textsc{Mix}}
\]
Formally, this is not a \textsc{Mixing Set} problem, since $s\in\Z_{\geq 0}$ is required to be an integer instead of a real number. However, due to the integrality of all other numbers the relaxation to $s\in\R_{\geq 0}$ admits just the same set of \emph{optimal} solutions. From \cite{DBLP:journals/mp/ZhaoF08,DBLP:conf/ipco/ConfortiSW08,DBLP:journals/orl/ConfortiZ09} we can derive the following theorem:
\begin{theorem}[\cite{DBLP:journals/mp/ZhaoF08,DBLP:conf/ipco/ConfortiSW08,DBLP:journals/orl/ConfortiZ09}]\label{harmonic-mixing-set}
    For harmonic capacities, \eqref{mixing-set} can be computed in time $\Oh(n^2)$.
\end{theorem}
Given a value for $s$ it is obvious that $x_i = \ceil{(b_i-s)/a_i}$ for all $i\leq n$ leads to an optimal completion of $s$ to a solution $(s,x)$ to \eqref{mixing-set}. The solution $(s,x)$ might not be optimal overall but the choice of $x$ is optimal with respect to $s$. Therefore, given a solution $(s,x)$ we will assume that $x_i = \ceil{(b_i-s)/a_i}$. Furthermore, we we will write $x_i(s) = \ceil{(b_i-s)/a_i}$ (and $x(s) = (x_1(s),\dots,x_n(s))$) to denote the dependency of variable $x_i$ on $s$. Remark that by adding/subtracting the least common multiple $m = \lcm_{j\leq n} a_j$ to/from $s$ the value $x_i(s)$ is shifted by $m/a_i$ in the sense that
\[
    x_i(s\pm m)
    = \ceil[\Big]{\frac{b_i-s\mp m}{a_i}}
    = \ceil[\Big]{\frac{b_i-s}{a_i}} \mp \frac{m}{a_i}
    = x_i(s) \mp \frac{m}{a_i} \qquad \text{for all $i\leq n$.}
\]

We will depend on an upper bound on the value of $s$ in optimal solutions to \eqref{mixing-set}. Therefore, the following observations will be important.
\begin{observation}\label{mixing-set-unbounded}
    If $\sum_{i\leq n} \frac{w_i}{a_i} > w_0$, then \eqref{mixing-set} is unbounded.
    \qed
\end{observation}
\begin{proof}
    Let $m=\lcm_{i\leq n} a_i$. For any feasible solution $(s,x)$ we get another feasible solution by adding a multiple of $m$ to $s$. In particular it holds that
    \begin{align*}
        w_0(s+m) + \sum_{i\leq n} w_ix_i(s+m)
        &\;=\; w_0(s+m) + \sum_{i\leq n} w_ix_i(s) - \sum_{i\leq n} w_i\frac{m}{a_i}\\
        &\;=\; w_0 s + \sum_{i\leq n}w_ix_i(s) + m\Big(w_0 - \sum_{i\leq n} \frac{w_i}{a_i}\Big)
    \end{align*}
    and that means that solution $(s',x(s'))$ with $s' = s+m > s$ will be a truly better solution than $(s,x)$ if $\sum_{i\leq n} \frac{w_i}{a_i} > w_0$.
\end{proof}
Hence, we assume that $\sum_{i\leq n}\frac{w_i}{a_i} \leq w_0$ in general.
\begin{observation}\label{mixing-set-small-solution}
    There is an optimal solution to \eqref{mixing-set} with $s < \lcm_{i\leq n} a_i$.
\end{observation}
\begin{proof}
    Let $m=\lcm_{i\leq n} a_i$ and let $(s,x)$ be an optimal solution with $s\geq m$. We find
    \[w_0(s-m) + \sum_{i\leq n}w_ix_i(s-m) = w_0 s + \sum_{i\leq n}w_ix_i(s)-m\Big(\!\underbrace{w_0-\sum_{i\leq n}\frac{w_i}{a_i}}_{\geq\,0}\!\Big) \leq w_0 s + \sum_{i\leq n}w_ix_i(s).\]
    Hence, $(s' = s -m,x'=x(s'))$ is an optimal solution too. Iterate this argument to find an optimal solution with $s$ smaller than $m$.
\end{proof}
By using an analog contradiction proof it is easy to see that \emph{any} optimal solution will hold $s<\lcm_{i\leq n} a_i$ if $\sum_{i\leq n}\frac{w_i}{a_i}$ is truly smaller than $w_0$. We will use this strengthening:
\begin{observation}\label{mixing-set-small-utilization}
    If $\sum_{i\leq n}\frac{w_i}{a_i} < w_0$, then any optimal solution to \eqref{mixing-set} holds $s < \lcm_{i\leq n} a_i$.
\end{observation}
In \cref{lcm-bound-for-S-is-tight} we show that this bound on $s$ is tight in general.

\subsection{Response time bounds}
\label{sec:response-time-bounds}

First of all, we refine the utilization bound $\sum_{i<n}c_i/p_i < 1$. In general it holds that
\[\addtocounter{equation}{1}\tag{\theequation}\label{general-utilization-bound}
    \sum_{i<n}\frac{c_i}{p_i} \leq 1-\frac{1}{\lcm_{i<n}p_j}.
\]
To see this, let $m = \lcm_{j<n}p_j$. From $\sum_{i<n}c_i/p_i < 1$ it follows that $m\cdot\sum_{i<n}c_i/p_i < m$ and both sides of this inequality are integers which implies that $m\cdot\sum_{i<n}c_i/p_i \leq m-1$ and division by $m$ yields the claim.

In the following we give bounds to worst-case response times for both the presence and absence of task release jitters. We start with the former case.

\begin{lemma}\label{wcrt-bounds}
    It holds that $\ell \leq r_n \leq u = \min\set{u_1,u_2}$ where
    \[
        \ell = \frac{c_n+\sum_{i<n}\frac{\jitter_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}},

        \;
        u_1=\ell + \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}},

        \;
        u_2 = \ceil*{\frac{\sum_{i\leq n}c_i}{(1-\sum_{i<n}\frac{c_i}{p_i})\lcm_{i<n}p_i}}\lcm_{i<n}p_i.
    \]
\end{lemma}
\begin{proof}
    By dropping the roundings it is easy to see that
    \[
        r_n
        \;=\; c_n + \sum_{i<n} c_i\ceil*{\frac{r_n+\jitter_i}{p_i}}
        \;\geq\; c_n + r_n\sum_{i<n} \frac{c_i}{p_i} + \sum_{i<n} \frac{\jitter_i}{p_i}c_i
    \]
    which directly implies the lower bound $\ell$.
    To prove the former upper bound $u_1$ we see that
    \[
        r_n
        \;=\; c_n + \sum_{i<n}\ceil[\Big]{\frac{r_n+\jitter_i}{p_i}}c_i
        \;\leq\; c_n + \sum_{i<n}\Big(\frac{r_n+\jitter_i}{p_i}+1\Big)c_i
    \]
    and rearrangement yields
    \[
        r_n
        \;\leq\; \ell + \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        \;=\; u_1.
    \]
    To confirm the latter upper bound $u_2$ we can argue that
    $u_2 \geq (\sum_{i\leq n}c_i)/(1-\sum_{i<n}c_i/p_i)$ which implies $\sum_{i\leq n}c_i \leq u_2(1-\sum_{i<n}c_i/p_i)$ and we observe
    \begin{align*}
        c_n+\sum_{i<n}\ceil[\Big]{\frac{u_2+\jitter_i}{p_i}}c_i\;
        &=\; c_n+\sum_{i<n}\Big(\frac{u_2}{p_i}+\ceil[\Big]{\frac{\jitter_i}{p_i}}\Big)c_i\reason{$\lcm$ property}\\
        &\leq\; c_n+\sum_{i<n}\Big(\frac{u_2}{p_i}+1\Big)c_i \;=\; u_2\sum_{i<n}\frac{c_i}{p_i}+\sum_{i\leq n} c_i\reason{$0 \leq \jitter_i \leq p_i$}\\

        &\leq\; u_2\sum_{i<n}\frac{c_i}{p_i}+u_2\Big(1-\sum_{i<n}\frac{c_i}{p_i}\Big)
        \;=\; u_2
    \end{align*}
    which proves the claim.
\end{proof}

We will use the bound $u_1$ to show that the length of the interval $[\ell,u]$ is pseudo-polynomial and bound $u_2$ to prove that $u$ is tight. We start with the former goal.

\begin{lemma}\label{pseudo-polynomial-interval-length}
    By using only the general utilization bound it follows that $u-\ell \leq p_{\max}^n$.
    With the schedulability utilization bound it follows that $u-\ell \leq p_{\max}^2$ and even $u \leq 2p_{\max}^2$.
\end{lemma}
\begin{proof}
    Using the general utilization bound \eqref{general-utilization-bound}, i.e. $\sum_{i<n}c_i/p_i \leq 1-1/\lcm_{i<n}p_i$, it follows that $\sum_{i<n}c_i \leq p_{\max}\sum_{i<n}c_i/p_i < p_{\max}$ and
    \[
        u_1 - \ell
        = \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        \leq (\lcm_{i<n}p_i)\sum_{i<n}c_i
        \leq (\lcm_{i<n}p_i)p_{\max}
        \leq p_{\max}^n.
    \]
    Assume that $\sum_{i\leq n}c_i/p_i \leq 1$ which implies that $1/(1-\sum_{i<n}c_i/p_i) \leq p_n/c_n$. It holds that $\sum_{i\leq n}c_i \leq p_{\max}\sum_{i\leq n}c_i/p_i \leq p_{\max}$ which implies that
    \[
        u_1 - \ell
        = \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = \frac{p_n}{c_n}\sum_{i<n}c_i
        \leq \frac{p_n}{c_n}p_{\max}
        \leq p_{\max}^2
    \]
    and by also using the definition of $\ell$ it follows that
    \[
        u_1
        = \frac{\sum_{i\leq n}c_i+\sum_{i<n}\frac{\jitter_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        \leq \frac{p_n}{c_n}\Big(p_{\max}+\sum_{i<n}c_i\Big)
        \leq \frac{p_n}{c_n}\cdot 2p_{\max}
        \leq 2p_{\max}^2
    \]
    and that proves the claim.
\end{proof}

\begin{lemma}\label{wcrt-upper-bound-is-tight}
    The upper bound of \cref{wcrt-bounds} is tight, even for harmonic periods.
\end{lemma}
\begin{proof}
    We set $\jitter_i=p_i$ for all $i\leq n$. According to \cref{construct-extreme-instances} we can always construct an instance with these release jitters, harmonic periods, and full utilization, i.e. $\sum_{i\leq n} \frac{c_i}{p_i} = 1$, as well as $c_n=1$ and $p_{n-1} = p_n$. Turning to \cref{wcrt-bounds} we see that such an instance holds
    \[
        \ell
        = \frac{c_n+\sum_{i<n}\frac{\jitter_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = \frac{c_n+\sum_{i<n}\frac{p_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = \frac{\sum_{i\leq n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = u_2
    \]
    where the last equality follows as $\ell$ is an integer multiple of $\lcm_{i<n}p_i$ since
    \[
        \frac1{1-\sum_{i<n}\frac{c_i}{p_i}} = \frac1{\frac{c_n}{p_n}} = \frac{p_n}{c_n} = p_n = p_{n-1} = {\textstyle\max_{i<n}p_i} = \lcm_{i<n}p_i
    \]
    and that completes the proof.
\end{proof}

We want to highlight that the instances of \cref{wcrt-upper-bound-is-tight} (or \cref{construct-extreme-instances} respectively) are also extreme for the case without release jitters, i.e. $\jitter=0$. Then the tight upper bound is $P=\lcm_{i\leq n}p_i$; in fact, the upper bound of $c_n \cdot P$, which was given by Bonifaci et al. \cite[Lemma 1]{DBLP:conf/rtss/BonifaciMMW13}, can be improved to $P$. The proof is short:

\begin{lemma}\label{wcrt-bounds-without-jitters}
    If $\jitter=0$, then $c_n/(1-\sum_{i<n}\frac{c_i}{p_i}) \leq r_n \leq P$.
\end{lemma}
\begin{proof}
    The lower bound is implied by \cref{wcrt-bounds}. For the upper bound see that
    \[
        c_n+\sum_{i<n}\ceil*{\frac{P}{p_i}}c_i
        \;=\; c_n + P\cdot\sum_{i<n}\frac{c_i}{p_i}
        \;=\; p_n\cdot\frac{c_n}{p_n}+P\cdot\sum_{i<n}\frac{c_i}{p_i}
        \;\leq\; P\cdot\sum_{i=1}^{n}\frac{c_i}{p_i}
        \;\leq\; P.\qedhere
    \]
\end{proof}

\section{Response time computation}\label{response-time-computation}

We introduce a generalized problem formulation as follows. For a selection of tasks $I \subseteq [n-1]$ and an integer $\gamma\geq 1$ we aim to compute
\[\addtocounter{equation}{1}\tag{\theequation}\label{wcrt-with-jitters}
    \response(I,\gamma) = \min\set{t|t \geq \gamma + \textstyle\sum_{i\in I}\displaystyle c_i\ceil[\Big]{\frac{t+\jitter_i}{p_i}},\quad t \in \Z_{\geq 0}}.
\]
Obviously, $r_n = \response([n-1],c_n)$ is the worst-case response time of task $\tau_n$.

\subsection{Conditional Karp reduction}
\label{conditional-karp-reduction}

In the following we apply the dualization technique of \cref{dualision} to RTC. We write $x \in \Z^{I}$ to introduce a variable $x_i \in \Z$ for each $i\in I$.
Apparently, \eqref{wcrt-with-jitters} may also be stated using the following formulation as an integer linear program:
\[\label{wcrt-decision}
    \response(I,\gamma) = \min\set{t|t \geq \gamma + \textstyle\sum_{i\in I} c_ix_i,\quad p_ix_i \geq t+\jitter_i \;\forall i\in I,\quad t \in \Z_{\geq 0},\quad x \in \Z^I}
    \tag{$\response$}
\]
Let $u$ be the upper bound of \cref{wcrt-bounds} and let $k \in [u]$. One can readily verify that the associated decision problem $\response(I,\gamma) \leq_? k$ may be decided by answering $\responsedual(I,k) \geq_? \gamma$ where
\[\label{wcrt-dual}
    \responsedual(I,k) = \max\set{t-\textstyle\sum_{i\in I}c_ix_i|t \leq k,\quad p_ix_i \geq t+\jitter_i\;\forall i\in I,\quad t\in\Z_{\geq 0},\quad x\in\Z^I}.
    \tag{$\responsedual$}
\]
Let $S$ be the smallest upper bound on the value of $s$ in any optimal solution to the following instance of \textsc{Mixing Set}:
\[\label{wcrt-mixing-set}
    \mixing(I,k) = \min\set{s+\textstyle\sum_{i\in I}c_ix_i | s+p_ix_i \geq k+\jitter_i\;\forall i \in I,\quad  s\in\Z_{\geq 0},\quad x\in\Z^I}
    \tag{$\mixing$}
\]
We will prove that, if $k \geq S$ holds true, then $    \responsedual(I,k) = k-\mixing(I,k)$.
Hence, if $k$ is large enough, i.e. $k\geq S$, we can decide $\response(I,\gamma) \leq_? k$ by using the following equivalence:
\[\addtocounter{equation}{1}\tag{\theequation}\label{response-mixing-equivalence}
    \response(I,\gamma) \leq k
    \quad\Leftrightarrow\quad \responsedual(I,k) \geq \gamma
    \quad\Leftrightarrow\quad k-\mixing(I,k) \geq \gamma
    \quad\Leftrightarrow\quad \mixing(I,k) \leq k-\gamma
\]
Thus, we get the following theorem.
\begin{theorem}
    Let $I \subseteq [n-1]$ and $\gamma\in\Z_{\geq 1}$. If $k \geq S$, then there is a reduction from $\response(I,\gamma) \leq_? k$ to $\mixing(I,k) \leq_? k-\gamma$ in constant time
\end{theorem}
In the case of harmonic periods we get harmonic capacities in the instance of \textsc{Mixing Set} which implies an efficient decision algorithm. However, without further insights we can decide $\response(I,\gamma) \leq_? k$ only for large values of $k$. In \cref{wcrt-harmonic-periods} we describe how to overcome this issue in the case of harmonic periods.

If $k \geq S$ holds, remark that optimal solutions to \eqref{wcrt-mixing-set} also do hold $x \in \Z_{\geq 0}^I$, since $s \leq S \leq k$ which implies $x_i = \ceil{(k-s+\jitter_i)/p_i} \geq \ceil{\jitter_i/p_i} \geq 0$ for all $i\in I$. By using \cref{mixing-set-small-utilization} it holds that $S \leq \lcm_{i\in I}p_i$, since $\sum_{i\in I} \frac{c_i}{p_i} \leq \sum_{i<n} \frac{c_i}{p_i} < 1$.

\begin{lemma}\label{reduction-to-mixing-set}
    If $k \geq S$, then $\responsedual(I,k) = k-\mixing(I,k)$.
\end{lemma}
\begin{proof}
    Let $(t,x)$ be an optimal solution to \eqref{wcrt-dual}
    with objective value $k-\sigma$ for some value $\sigma$. We know that $0 \leq t \leq k$. Then by setting $s = k-t \geq 0$ we see that $(s,x)$ is a solution to \eqref{wcrt-mixing-set} since $s+p_ix_i = k-t+p_ix_i \geq k-t+t+\jitter_i = k+\jitter_i$. Its objective value is
    \[
        s+\sum_{i\in I} c_ix_i
        = k - t + \sum_{i\in I} c_ix_i
        = k-\Big(t-\sum_{i\in I} c_ix_i\Big)
        = k-(k-\sigma)
        = \sigma.
    \]
    Vice-versa let $(s,x)$ be an optimal solution to \eqref{wcrt-mixing-set} with objective value $\sigma$. We know that $0 \leq s \leq S \leq k$. Hence, by setting $t = k-s \geq 0$ we see that $(t,x)$ is a solution to \eqref{wcrt-dual} since $t+\jitter_i = k-s+\jitter_i = k+\jitter_i-s \leq s+p_ix_i -s = p_ix_i$
    and $t = k-s \leq k$. Its objective value is
    \[
        t-\sum_{i\in I} c_ix_i
        = k-s - \sum_{i\in I} c_ix_i
        = k-\Big(s+\sum_{i\in I} c_ix_i\Big)
        = k - \sigma
    \]
    and that proves the claim.
\end{proof}

\subsection{Harmonic Periods}\label{wcrt-harmonic-periods}

Here we assume harmonic periods, i.e. $p_i\geq p_j$ implies $p_i/p_j \in \Z$ for all $i,j \in I$. A direct consequence is that $\lcm_{i \in I}p_i = \max_{i\in I} p_i$. Also it holds that $u \leq u_2 \leq p_{\max}\sum_{i\leq n} c_i \leq 2p_{\max}^2$.
By using the described reduction to the \textsc{Mixing Set} instance \eqref{wcrt-mixing-set} and solving it in time $\Oh(n^2)$ using \cref{harmonic-mixing-set} we get the following result.
\begin{theorem}\label{large-k-is-okay}
    Let $I \subseteq [n-1]$ and $\gamma\in\Z_{\geq 1}$. If $k \geq \max_{i\in I}p_i$, then $\response(I,\gamma) \leq_? k$ can be decided in time $\Oh(n^2)$
\end{theorem}
Obviously, by itself \cref{large-k-is-okay} does not allow to binary search for the optimal solution in general, since we do not know how to find it if it is smaller than $\max_{i\in I}p_i$. For now, we only see that we can utilize a binary search to get the following corollary.

\begin{corollary}
    Let $t^*$ be the optimum value to \eqref{wcrt-decision}. If $t^* \geq \max_{i\in I}p_i$, then $t^*$ can be computed in time $\Oh(n^2\log p_{\max})$
\end{corollary}

However, if the values for the variables of the tasks with the largest periods are known \emph{a priori}, then the largest period of the residual instance will be smaller than before and we can decide even lower values of $k$. In fact, for tasks $\tau_i$ with large periods a rough knowledge about the optimum value suffices to find the exact value of the variables $x_i$. The following lemma will be crucial to exploit this idea (see also \cref{fig:two-possible-situations}).

\begin{lemma}\label{two-values}
    Let $(t,x)$ be an optimal solution to \eqref{wcrt-decision}. If $0 < t \leq p_i$ for some $i\in I$, then
    \[x_i = \begin{cases}1 &: t \leq p_i-\jitter_i\\2 &: t > p_i-\jitter_i\end{cases}.\]
\end{lemma}
\begin{proof}
    Since $(t,x)$ is an optimal solution, we know that $x_i = \ceil{(t+\jitter_i)/p_i}$.
    Now, if we are in the case that $t \leq p_i-\jitter_i$, then
    $0 < (t+\jitter_i)/p_i \leq (p_i-\jitter_i+\jitter_i)/p_i = 1$
    and if $p_i-\jitter_i < t$, then
    $1 = (p_i-\jitter_i+\jitter_i)/p_i < (t+\jitter_i)/p_i \leq (p_i+p_i)/p_i = 2$
    which proves the claim.
\end{proof}

\begin{figure}
    \centering
    \tikz[xscale=0.7,yscale=0.15]{
        \draw (0,1) -- (0,-1) node [below] {$0$};
        \draw (0,0) -- (18,0);
        \draw (10,1) -- (10,-1) node [below] {$p_j-\jitter_j$};
        \draw (6,1) -- (6,-1) node [below] {$k_i$};
        \draw (18,1) -- (18,-1) node [below] {$p_j$};
        \draw [|-|,draw=gray] (0,3) -- node [above] {$x_j = 1$} (10,3);
        \draw [|-|,draw=gray] (10,3) -- node [above] {$x_j = 2$} (18,3);
        \begin{scope}[shift={(0,-11)}]
            \draw (0,1) -- (0,-1) node [below] {$0$};
            \draw (0,0) -- (18,0);
            \draw (3,1) -- (3,-1) node [below] {$p_j-\jitter_j$};
            \draw (6,1) -- (6,-1) node [below] {$k_i$};
            \draw (18,1) -- (18,-1) node [below] {$p_j$};
            \draw [|-|,draw=gray] (0,3) -- node [above] {$x_j = 1$} (3,3);
            \draw [|-|,draw=gray] (3,3) -- node [above] {$x_j = 2$} (18,3);
        \end{scope}
    }
    \caption{Two possible situations; the former is simple while the latter is complicated}
    \label{fig:two-possible-situations}
\end{figure}

To describe our algorithm in detail, we consider integers $k_0 = 0$, $k_{q+1}=u$, as well as $0< k_1 < \dots < k_q$ with $\set{k_1,\dots,k_q}=\set{p_j-\jitter_j|j\in I}\setminus\set{0}$ where $q \leq \abs{I}$. Our algorithm walks over these differences \enquote{from left to right}, starting with the smallest difference $p_j-\jitter_j$. Powered by the invariants \cref{first-invariant,catch-search}, it discovers variable values; in fact, the tasks whose variables are identified to have value $1$ are stored in the set $I_1$ while those which are known to have value $2$ are stored in set $I_2$.

\noindent\begin{minipage}[t]{0.52\textwidth}
\begin{myalgorithm}{\textsc{Narrow}}
\setstretch{1.5}
\begin{algorithmic}[1]
    \For{$i=1,\dots,q$}
        \State $I_1 \gets \set{j\in I|k_i \leq p_j-\jitter_j}$
        \State $I_2 \gets \set{j\in I|p_j-\jitter_j < k_i \leq p_j}$
        \State $\gamma_i \gets \gamma + \sum_{v\in\{1,2\}}\sum_{j\in I_v}vc_j$

        \If{$\mixing(I\setminus(I_1\cup I_2),k_i) \leq k_i-\gamma_i$}
            \State \Return $\ref{alg:catch}(k_{i-1}+1,k_i)$
        \EndIf
    \EndFor
    \State \Return $\ref{alg:catch}(k_q+1,u)$
\end{algorithmic}
\caption{\!\!\(\)}
\label{alg:narrow}
\end{myalgorithm}
\end{minipage}
\hfill
\begin{minipage}[t]{0.46\textwidth}
\begin{myalgorithm}{\textsc{Catch}}
\setstretch{1.035}
\begin{algorithmic}[1]
    \State $I_1 \gets \set{j\in I|R\leq p_j-\jitter_j}$

    \While{$L \neq R$}
        \State $\kappa \gets \floor{(L+R)/2}$

        \State $I_2 \gets \set{j\in I|\kappa \leq p_j < L+\jitter_j}$

        \State $\gamma'_{\kappa} \gets \gamma + \sum_{v\in\{1,2\}}\sum_{j\in I_v}vc_j$

        \If{$\mixing(I\setminus(I_1\cup I_2),\kappa) \leq \kappa - \gamma'_{\kappa}$}
            \State $R \gets \kappa$
        \Else
            \State $L \gets \kappa+1$
        \EndIf
    \EndWhile
    \State \Return $R$
\end{algorithmic}
\caption{\!\!\((L,R)\)}
\label{alg:catch}
\end{myalgorithm}
\medskip
\end{minipage}
\begin{figure}
    \centering
    \tikz[xscale=0.35,yscale=0.18]{
        \draw [black!30!red] (9,0) -- (18,0);
        \draw [black!50!green] (26,0) -- (42,0);
        \draw (20,1) -- (20,-1) node [below] {$p_a$};
        \draw (23,1) -- (23,-1) node [below] {$p_b$};
        \draw [fill=blue!50!white] (18,-.3) rectangle (26,.3);
        \draw (18,1) -- (18,-1) node [below,black!30!red] {$k_{i-1}$};
        \draw (31,1) -- (31,-1) node [below] {$p_c$};
        \draw (33,1) -- (33,-1) node [below] {$p_d$};
        \draw (37,1) -- (37,-1) node [below] {$p_e$};
        \draw (40,1) -- (40,-1) node [below=-0.3] {$p_f$};
        \draw (26,1) -- (26,-1) node [below,black!50!green] {$k_i$};

        \draw [|-|,draw=gray] (12,6) -- node [above] {$x_a = 2$} (20,6);
        \draw [|-|,draw=gray] (18,3) -- node [above] {$x_b = 2$} (23,3);
        \draw [|-|,draw=gray] (27,6) -- node [above] {$x_c = 2$} (31,6);
        \draw [|-|,draw=gray] (26,3) -- node [above] {$x_d = 2$} (33,3);
        \draw [|-|,draw=gray] (18,-4) -- node [below] {$x_e = 2$} (37,-4);
        \draw [|-|,draw=gray] (14,-7) -- node [below] {$x_f = 2$} (40,-7);
    }
    \caption{A ($\log$-scaled) example where $k_i$ is feasible while $k_{i-1}$ is not, i.e. $k_{i-1} < \response(I,\gamma) \leq k_i$}
    \label{fig:second-search}
\end{figure}
So, the algorithm works in two steps. The first one is to identify the interval $(k_{i-1},k_i]$ which contains the desired response time (\cref{alg:narrow}). The second step is to use a binary search inside this interval to find the exact response time (\cref{alg:catch}). We heavily use the fact, that \emph{any} solution which gives a \textsc{yes} answer to the decision problem $\response(I,\gamma) \leq_? k$ is smaller than $k$. The correctness of the algorithm crucially depends on the following two invariants.

\begin{lemma}[Invariant]\label{first-invariant}
    For each iteration $i\in[q]$ of \cref{alg:narrow} and each $j\in I$ with $k_i \leq p_j$ the value for variable $x_j$ is known a priori.
\end{lemma}
\begin{proof}
    We do a case distinction as follows. If $k_i \leq p_j-\jitter_j$, then by \cref{two-values} we know that $x_j=1$. If otherwise $k_i > p_j-\jitter_j$, then by the order of the algorithm we know that there is an index $i' < i$ such that we already have checked $k_{i'} = p_j-\jitter_j < k_i$ and $k_{i'}$ was not feasible. Hence, any feasible solution $t$ has to be truly greater than $k_{i'} = p_j-\jitter_j$ and by \cref{two-values} we know that $x_j = 2$.
\end{proof}

\begin{lemma}[Invariant]\label{catch-search}
    For each iteration $\kappa \in [L,R]$ of \cref{alg:catch} and each $j \in I$ with $\kappa \leq p_j$ the value for variable $x_j$ is known a priori.
\end{lemma}
\begin{proof}
    Remark that $k_i \notin [L,R)$ for each $i\in I$. We do a case distinction as follows. If $R \leq p_j$, then $x_j = 1$ if $R \leq p_j-\jitter_j$ and $x_j = 2$ otherwise (if $p_j-\jitter_j < R$ which implies $p_j-\jitter_j \leq L)$. If $\kappa \leq p_j < R$, then $p_j-\jitter_j < L$ which implies $x_j=2$.
\end{proof}

\Cref{fig:second-search} gives an example to see that in the second step all variable values for tasks with periods above $\kappa$ are known a priori. The key property is, that by the definition of $k_1,\dots,k_q$ there is no difference $p_j-\jitter_j$ inside of the interval $(k_{i-1},k_i)$ for any task $\tau_j$.

\begin{lemma}\label{narrowing-correctness}
    Let $i \in [q]$. If $\response(I,\gamma) > k_j$ for any $j<i$, then $\response(I,\gamma) \leq_? k_i$ can be decided in time $\Oh(n^2)$.
\end{lemma}
\begin{proof}
    Consider the task sets $I_1 = \set{j\in I|k_i \leq p_j-\jitter_j}$, $I_2 = \set{j\in I|p_j-\jitter_j < k_i \leq p_j}$, and $I_* = \set{j\in I|p_j<k_i}$ such that $I_* = I \setminus (I_1 \cupdot I_2)$. Then by using \cref{first-invariant} and setting $\gamma' = \gamma + \sum_{v\in\{1,2\},j\in I_v}vc_j$ the decision problem $\response(I,\gamma) \leq_? k_i$ simplifies to $\response(I_*,\gamma') \leq_? k_i$ as all variables for the tasks in $I_1$ have value $1$ and the variables for the tasks in $I_2$ have value $2$. By definition, all periods of the remaining tasks $I_*$ are smaller than $k_i$, i.e. $k_i \geq \max_{j\in I_*}p_j$. Therefore, by using \eqref{response-mixing-equivalence} again we can solve the \textsc{Mixing Set} problem $\mixing(I_*,k_i)$ to find the correct decision for $\response(I,\gamma) \leq_? k_i$ in time $\Oh(n^2)$.
\end{proof}

By \cref{narrowing-correctness} we see that \cref{alg:narrow} correctly narrows the response time candidate interval $(0,u]$ down to some interval $[L,R]$ such that $L = k_{i-1}+1$ and $R=k_i$ for some $i\in[q+1]$. The correctness of the subsequent binary search in \cref{alg:catch} is then implied by \cref{catch-search}. Together we get the following result.

\begin{theorem}\label{harmonic-result}
    Let $I \subseteq [n-1]$ and $\gamma\in\Z_{\geq 1}$. In the case of harmonic periods $\response(I,\gamma)$ can be computed in time $\Oh(q\cdot \abs{I}^2+\abs{I}^2\log p_{\max})$ where $q=\abs{\set{p_i-\jitter_i|i\in I}}$.
\end{theorem}

Note that the running time improves to strongly polynomial time $\Oh(q\abs{I}^2)$ if $\log(p_{\max}) \leq \Oh(q)$ and to $\Oh(\abs{I}^2\log p_{\max})$ otherwise.

\subsection{Arbitrary Periods}
\label{wcrt-arbitrary-periods}

For the ease of notation and w.l.o.g. we consider $I=[n-1]$ and $\gamma = c_n$ here.
The following theorem reveals a first simple algorithm to compute worst-case response times for general periods in pseudo-polynomial time.

\begin{theorem}
    The worst-case response time $r_n$ can be computed in time $\Oh(n\cdot\lcm_{i<n}p_i)$.
\end{theorem}
\begin{proof}
    Let $m=\lcm_{i<n}p_i$ and define $w(t) = c_n+\sum_{i<n}c_i\ceil{\frac{t+\jitter_i}{p_i}}$. Then there is a remainder $\rho \in \set{0,\dots,m-1}$ and some $\lambda \in \Z_{\geq 0}$ such that $r_n = \rho+\lambda m$. We find that
    \[
        \rho+\lambda m
        \;=\; r_n
        \;=\; w(r_n)
        \;=\; w(\rho+\lambda m)
        \;=\; w(\rho)+\lambda m\cdot\sum_{i<n}\frac{c_i}{p_i}
    \]
    and thus, $\lambda = (w(\rho)-\rho)/((1-\sum_{i<n}\frac{c_i}{p_i})\cdot m)$ can be computed in time $\Oh(n)$ for a given $\rho$. Hence, we can compute $r_n$ by simply trying each $\rho$ in $\set{0,\dots,m-1}$ and compute $\lambda$ for this choice to find the smallest sum $\rho+\lambda m$ for which the computed $\lambda$ is a non-negative integer. This yields a total running time of $\Oh(n\cdot m)$.
\end{proof}

However, by using our reduction we can prove a Turing reduction as follows.

\begin{theorem}
    The response time $r_n$ can be computed in time $\Oh(\max(Sn,T_{\mixing}\log p_{\max})) \leq \Oh(Sn\log p_{\max})$ where $S$ is a global upper bound on variable $s$ in any optimal solution to \eqref{wcrt-mixing-set} and $T_{\mixing}$ is a global upper bound on the running time required to compute \eqref{wcrt-mixing-set}.
\end{theorem}
\begin{proof}
    We may run an algorithm as follows. First decide $\response(I,\gamma) \leq_? S$. If the answer is \textsc{yes}, then try out all candidates $t\in[S-1]$ in time $\Oh(Sn)$, i.e. we check whether $t$ is a solution to \eqref{wcrt-with-jitters-original}.
    If this reveals a feasible solution, return the smallest. Otherwise $r_n = S$. If the answer is \textsc{no}, then it holds that $r_n > S$.
    From \cref{pseudo-polynomial-interval-length} we know that $u - \ell \leq p_{\max}^2$ and thus, a subsequent binary search in $[\ell,u]$ leads to a total running time of $\Oh(\max(Sn,T_{\mixing}\log(u-\ell))) \leq \Oh(\max(Sn,T_{\mixing}\log p_{\max}))$. For example we can bound $T_{\mixing}$ as follows.
    We can compute $\mixing([n-1],k)$ in time $\Oh(Sn)$ by simply trying solution $(s,x(s))$ for each $s\in [0,S)$. Hence, $T_{\mixing} \leq \Oh(Sn)$ and this gives a total running time of $\Oh(Sn\log p_{\max})$.
\end{proof}

In the case without task release jitter, i.e. $\jitter_i = 0$ for all $i\in I$, we can even prove an \emph{unconditional} Karp reduction as follows. For $\jitter = 0$ we get the following form of \eqref{wcrt-mixing-set}:
\[\label{wcrt-mixing-set-without-jitter}
    \mixing_{\jitter=0}(I,k) = \min\set{s+\textstyle\sum_{i\in I}c_ix_i | s+p_ix_i \geq k\;\forall i \in I,\quad  s\in\Z_{\geq 0},\quad x\in\Z^I}
    \tag{$\mixing_{\jitter=0}$}
\]
In this case we can show that $S \leq k$. Apparently, $(s=k,x=0)$ is always a solution to \eqref{wcrt-mixing-set-without-jitter} since $s+p_ix_i = k$. It has the objective value $s+\sum_{i\in I}c_ix_i = k$. Any solution $(s,x)$ to \eqref{wcrt-mixing-set-without-jitter} with $s>k$ has an objective value truly larger than $k$, since
\[
    s+\sum_{i\in I}c_ix_i(s)
    \;=\; s+\sum_{i\in I}c_i\ceil*{\frac{k-s}{p_i}}
    \;\geq\; s+\underbrace{(k-s)}_{<\,0}\cdot\underbrace{\sum_{i\in I}\frac{c_i}{p_i}}_{<\,1}
    \;>\; s+(k-s)\cdot 1
    \;=\; k.
\]
Hence, any optimal solution $(s,x)$ to \eqref{wcrt-mixing-set-without-jitter} holds $s \leq k$ which implies that $S \leq k$.

Therefore, $\responsedual(I,k) = k-\mixing(I,k)$ is directly implied. Thus, we can use a binary search to compute $r_n$ in time $\Oh(T_{\mixing}\log p_{\max})$ where $T_{\mixing}$ is a global upper bound on the time required to compute $\mixing(I,k)$. This yields the following result.

\begin{theorem}
    If $\jitter=0$, then $r_n$ can be computed in time $\Oh(T_{\mixing}\log p_{\max})$ where $T_{\mixing}$ is a global upper bound on the time required to compute \eqref{wcrt-mixing-set}.
\end{theorem}

\subparagraph*{Small Utilization}
As for \ac{RM} scheduling (cf. \cite{DBLP:journals/jacm/LiuL73,DBLP:conf/afips/Serlin72}) the complexity of RTC decreases with a smaller utilization  also for \ac{FP} scheduling. Let $U = \sum_{i<n}c_i/p_i$ denote the utilization.

\begin{lemma}\label{bound-S-with-utilization}
    In general it holds that $S \leq (\sum_{i<n}c_i)/(1-U)$.
    \qed
\end{lemma}
\begin{proof}
    Let $S' = (\sum_{i< n}c_i)/(1-U)$, set $f(s) = s+\sum_{i<n}c_ix_i(s)$ as the objective function of $\mixing(I,k)$, and assume that $s \geq S'$ is a solution to $\mixing(I,k)$. Then
    \begin{align*}
        f(s-S')
        &= s-S' + \sum_{i<n}c_i\ceil[\Big]{\frac{k+\jitter_i-s+S'}{p_i}}\\
        &\leq s - S' + \sum_{i<n}c_i\Big(\ceil[\Big]{\frac{k+\jitter_i-s}{p_i}}+\ceil[\Big]{\frac{S'}{p_i}}\Big)\\
        &= f(s) - S' + \sum_{i<n}c_i\ceil[\Big]{\frac{S'}{p_i}}
        < f(s) - S' + \sum_{i<n}c_i\Big(\frac{S'}{p_i}+1\Big)
        = f(s)
    \end{align*}
    which implies that $s' = s-S'$ is a truly better solution to $\mixing(I,k)$.
\end{proof}
Using the schedulability utilization bound this immediately assures that $S$ is pseudo-polynomial using only the general utilization bound it suffices for example that $U \leq 1-p_{\max}^{-\Oh(1)}$. Since $u_1-\ell = (\sum_{i<n}c_i)/(1-U)$ this also implies a pseudo-polynomial algorithm by simply guessing the right value in in the interval $[\ell,u]$. However, especially if $r_n > S$ our algorithm may be faster.

\section{Mixing Set}
\label{sec:mixing-set}

Our technique may be reversed to solve the \textsc{Mixing Set} problem by computing worst-case response times. This allows us to make efficient approaches to RTC applicable to solve \textsc{Mixing Set}. We simply do a substitution in \eqref{response-mixing-equivalence} (substitute $k \mapsto k'+\gamma$, $\gamma \mapsto \beta - k'$, $k' \mapsto k$ in this order) to achieve the following corollary.

\begin{corollary}\label{reverse-reduction}
    Let $\beta \geq S$. Then $\mixing(I,\beta) \leq k$ if and only if $\response(I,\beta-k) \leq \beta$.
\end{corollary}

With the reverse reduction we can improve the running time for general capacities, if the entries of the right-hand side $b$ are large and close to $b_{\min}$:

\begin{lemma}\label{mixing-set-with-large-crowded-right-hand-side}
    Given capacities $a\in\Z_{\geq 1}^n$, a right-hand side $b\in\Z^n$ which holds that $\lcm_{j\leq n} a_j \leq b_i \leq b_{\min}+a_i$ for all $i\leq n$, and weights $w \in \Z_{\geq 0}^n$, one can compute
    \[\label{mixing-with-crowded-right-hand-side}
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq b_i\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_b$}
    \]
    in time $\Oh(T_{\response}\log b_{\max})$ where $T_{\response}$ is a global upper bound on the time required to compute \eqref{wcrt-decision}.
\end{lemma}
\begin{proof}
    Choose $\beta = b_{\min}$ and $\jitter_i = b_i - b_{\min}$ for all $i \in [n]$. We get $\beta \geq \lcm_{i\leq n} a_i \geq S$ and $0 \leq \jitter_i \leq a_i$ for all $i\leq n$. This implies $b_i = \beta + \jitter_i$ and thus, we can write \eqref{mixing-with-crowded-right-hand-side} as
    \[
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq \beta+\jitter_i\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}.
    \]
    Now, we use \cref{reverse-reduction} to start a binary search for the optimal $k$. We know that $\response([n],\beta-k)$ can be computed in time $T_{\response}$ and the objective value of our \textsc{Mixing Set} instance is upper bounded by $b_{\max}$ (since $(s=b_{\max},x=0)$ is always a solution with objective value $b_{\max}$) which implies a total running time of $\Oh(T_{\response}\log b_{\max})$.
\end{proof}
In fact, \cref{mixing-set-with-large-crowded-right-hand-side} implicitly solves the general case. We use it to prove the following.
\begin{theorem}
    Given capacities $a\in\Z_{\geq 1}^n$, a right-hand side $b\in\Z^n$, and weights $w \in \Z_{\geq 0}^n$, one can compute
    \[
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq b_i\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_b$}
    \]
    in time $\Oh(n+T_{\response}\log b_{\max})$ where $T_{\response}$ is a global upper bound on the time required to compute \eqref{wcrt-decision}.
\end{theorem}
\begin{proof}
    Let $m = \lcm_{j\leq n}a_j$. We define a new right-hand side $b' \in \Z^n$ by
    \[
        b_i' = b_i + \ceil*{\frac{m - b_i}{a_i}}a_i
    \]
    for each $i\leq n$. It is easy to see that $m \leq b_i' \leq m+a_i \leq b'_{\min}+a_i$ for all $i\leq n$. Also, we have
    \begin{align*}
        &\min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i \geq b'_i\forall i\leq n, s\in\Z_{\geq 0},x\in\Z^n}\\
        &= \min\set{s+\sum_{i\leq n}w_i\ceil*{\frac{b'_i-s}{a_i}}| s\in\Z_{\geq 0}}\\
        &= \min\set{s+\sum_{i\leq n}w_i\ceil*{\frac{b_i + \ceil*{\frac{m - b_i}{a_i}}a_i-s}{a_i}}| s\in\Z_{\geq 0}}\\
        &= \sum_{i\leq n}w_i\ceil*{\frac{m - b_i}{a_i}} + \min\set{s+\sum_{i\leq n}w_i\ceil*{\frac{b_i-s}{a_i}}| s\in\Z_{\geq 0}}\\
        &= \sum_{i\leq n}w_i\ceil*{\frac{m - b_i}{a_i}} + \min\set{s+\sum_{i\leq n}w_ix_i| s+a_ix_i \geq b_i\forall i\leq n, s\in\Z_{\geq 0},x\in\Z^n}
    \end{align*}
    Hence, we can solve the system for $b'$ with \cref{mixing-set-with-large-crowded-right-hand-side} and subtract $\sum_{i\leq n}w_i\ceil{(m - b_i)/a_i}$ to obtain the optimal value. This gives the desired running time.
\end{proof}

Now, we aim to identify the instances of \textsc{Mixing Set} which may be solved by using our reversed reduction in combination with efficient algorithms for the computation of worst-case response times. By turning to harmonic periods $p_i$ and using \cref{reverse-reduction} again, we can apply Nguyen et al. \cite{DBLP:conf/iwoca/NguyenGJ22} to compute
\[
    \min\set{s+\sum_{i\in I}c_ix_i|s+p_ix_i\geq \beta\;\forall i\in I,\quad s\in\Z_{\geq 0},\quad x\in\Z^I}
\]
in time $\Oh(n\log n+n\log\beta)$ for any $\beta \geq \max_{i \in I} p_i$ by computing the response times
\[
    \min\set{t|t \geq \beta - k + \textstyle\sum_{i\in I} \ceil[\big]{\frac{t}{p_i}}c_i,\quad t \in \Z_{\geq 0}}
\]
in a binary search for the smallest feasible $k$. It suffices to search in the interval $[0,\beta]$ since $(s=\beta,x=0)$ is always a solution with value $\beta$. Remark that the usual running time to solve instances of \textsc{Mixing Set} with harmonic capacities is $\Oh(n^2)$. In a more classical formulation this yields the following theorem.

\begin{theorem}
    Given harmonic capacities $a\in\Z_{\geq 1}^n$, a right-hand side value $\beta\geq a_{\max}$, and weights $w \in \Z_{\geq 0}$, one can compute
    \[\label{mixing-beta}
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq \beta\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_{\beta}$}
    \]
    in time $\Oh(n\log n+n\log\beta) \leq \Oh(n\log(n+\beta))$.
\end{theorem}

The algorithm of Nguyen et al. runs in linear time $\Oh(n)$ after an initial sorting step in time $\Oh(n\log n)$ to sort the tasks by their periods. As we seek to apply the algorithm multiple times, we can save the time to sort by only doing it once.

However, for arbitrary capacities and the special case $b_i=\beta$ for all $i\leq n$ and $\beta \geq \lcm_{j\leq n}a_j$ we can also derive the following corollary from \cref{mixing-set-with-large-crowded-right-hand-side}.
\begin{corollary}
    Given capacities $a\in\Z_{\geq 1}^n$, a right-hand side value $\beta\geq\lcm_{i\leq n}a_i$, and weights $w \in \Z_{\geq 0}^n$, one can compute
    \[
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq \beta\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_b$}
    \]
    in time $\Oh(T_{\response}\log\beta)$ where $T_{\response}$ is a global upper bound on the time required to compute \eqref{wcrt-decision}.
\end{corollary}

\section{4-block Integer Programming}
\label{application-to-4-block}

Block-structured integer programming has received major interest in the recent past. Namely, the three most important lines of research are $n$-fold integer programming, $2$-stage stochastic integer programming, and $4$-block integer programming \cite{DBLP:conf/icalp/EisenbrandHK18,DBLP:conf/esa/0009K0S20,arxiv/2201.05874,DBLP:conf/ipco/HemmeckeKW10}. The latter is the most general but also the least understood flavor of block-structured integer programs. In this section we will consider 4-block integer programs with only one coupling constraint inequality. Furthermore, we consider a simpler objective function which addresses at most two \emph{bricks}. From \cref{4-block-hardness} it follows that this problem is still hard to approximate to any constant factor.
In fact, the literature on $4$-block integer programs is not unified in its formal presentation. Here we consider $4$-block integer programs as follows.

Consider matrices $A_1,\dots,A_n$, $B_1,\dots,B_n$, $C_1,\dots C_n$, and $D$ such that $A_i \in \Z^{r\times t}$, $B_i \in \Z^{r\times s}$, and $C_i\in\Z^{q\times t}$ for all $i\in[n]$ and $D\in\Z^{q\times s}$. We aim to compute
\[\addtocounter{equation}{1}\tag{\theequation}\label{4-block}
    \min\set{w^\intercal x|\mathcal{B}x = b, \quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}}
\]
where
\[
    \mathcal{B}=\begin{pmatrix}
        D&C_1&\cdots&C_n\\
        B_1&A_1\\
        \vdots&&\ddots\\
        B_n&&&A_n
    \end{pmatrix}.
\]

We use the notion of \emph{bricks} $w^{(0)},w^{(1)},\dots,w^{(n)}$ and $x^{(0)},x^{(1)},\dots,x^{(n)}$ to refer to different areas of $w$ and $x$. For each $i\in\set{1,\dots,n}$ let $w^{(i)} = (w_{(i-1)t+1},\dots,w_{it})$ and $x^{(i)} = (x_{(i-1)t+1},\dots,x_{it})$ denote the $i$-th bricks of $w$ and $x$. Furthermore, let $w^{(0)} = (w_1,\dots,w_s)$ and $x^{(0)} = (x_1,\dots,x_s)$ denote the $0$-th bricks of $w$ and $x$.

In the following we assume that there is exactly one coupling constraint \emph{inequality} and that there is a $j \in [n]$ such that $w^{(i)}=0$ for all $i\in[n]\setminus\set{j}$. In other words, the objective function addresses exactly two bricks of the solution and at least one of them is the first brick.
Let $a \in \Z^{s+nt}$ denote the first row of $\mathcal{B}$. We aim to compute
\[\addtocounter{equation}{1}\tag{\theequation}\label{simple-4-block}
    \tau=\min\set{w^\intercal x|a^\intercal x \geq b_0,\quad\mathcal{B}'x = b, \quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}}
\]
where
\[
    \mathcal{B}'=\begin{pmatrix}C_1&B_1\\\vdots&&\ddots\\C_n&&&B_n\end{pmatrix}.
\]
For the decision problem $\tau \leq_? k$ we get the following dual formulation:
\[
    \max\set{a^\intercal x|w^\intercal x\leq k,\quad\mathcal{B}'x = b,\quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}} \geq_? b_0
\]
Introduce a slack variable $y\geq 0$ to replace the inequality \enquote{$w^\intercal x\leq k$} with the equation \enquote{$w^\intercal x+y = k$}:
\[
    \max\set{a^\intercal x|w^\intercal x+y= k,\quad\mathcal{B}'x = b,\quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}, \quad y \in \Z_{\geq 0}}
\]
By placing the additional constraint \enquote{$w^\intercal x+y=k$} on top of the $j$-th block matrices we get a new matrix
\[
    \mathcal{B}''=\begin{pmatrix}
         \tikz[scale=0.8]{
            \draw (0,4) rectangle node {$C_1$} (1,5);
            \draw (1,4) rectangle node {$B_1$} (2,5);
            \draw (0,3) rectangle node {$\overbar{w}^{(0)}$} (1,3.4);
            \draw (4,3) rectangle node {$1$} (4.4,3.4);
            \draw (3,3) rectangle node {$\overbar{w}^{(j)}$} (4,3.4);
            \draw (0,2) rectangle node {$C_j$} (1,3);
            \draw [dashed] (4,2) -- (4.4,2) -- (4.4,3);
            \draw (3,2) rectangle node {$B_j$} (4,3);
            \draw (0,0) rectangle node {$C_n$} (1,1);
            \draw (5,0) rectangle node {$B_n$} (6,1);
         }
    \end{pmatrix}
\]
where $\overbar{w}^{(0)}=(w^{(0)})^\intercal$ and $\overbar{w}^{(j)}=(w^{(j)})^\intercal$. Finally, we arrive at the $2$-stage stochastic integer program
\[\addtocounter{equation}{1}\tag{\theequation}\label{2-stage}
    \max\set{a^\intercal x|\mathcal{B}''x = b',\quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}, \quad y \in \Z_{\geq 0}}
\]
where $b'$ is the modified right-hand side with value $k$.
Use, for example, \cite{DBLP:conf/esa/CslovjecsekEPVW21} to solve it.

\begin{theorem}
    Program \eqref{simple-4-block} can be solved in time $\Oh(T_{\eqref{2-stage}}\cdot\log(2H))$ where $T_{\eqref{2-stage}}$ is a global upper bound on the time to solve \eqref{2-stage} and $H$ is an upper bound on the absolute objective value of an optimal solution to \eqref{simple-4-block}.
\end{theorem}

Using the state-of-the-art algorithm for 2-stage stochastic integer programming by Cslovjecsek et al. \cite{DBLP:conf/esa/CslovjecsekEPVW21} we can bound $T_2 \leq 2^{(2\Delta)^{\Oh(s(s+t))}}\cdot\log^{\Oh(st)}n$ by using parallel computation where $\Delta = \max\set{\norm{\mathcal{B}}_{\infty},\norm{w}_{\infty}}$ is the largest absolute value of the entries in $\mathcal{B}$ and $w$.
To give a simple bound on $H$ one can use standard arguments (e.g. \cite[Theorem 13.5]{DBLP:books/ph/PapadimitriouS82}) to show that $\log(2H) \leq \Oh(\log(st\norm{w}_1\norm{b}_{\infty})+(nr+q)\log((nr+q)\norm{A}_{\infty}))$.


\section{Introduction}
From the fifth-generation (5G) wireless communication to the forthcoming 6G wireless communication, we are moving towards the Internet of everything (IoE) era. This disruptive achievement is credited to massive multiple-input multiple-output (MIMO), millimeter wave (mmWave) communication, integrated space-to-ground communication, and so on. However, due to the broadcast nature of wireless networks, malicious users can easily launch a series of attacks through the physical layer, such as eavesdropping, media access control (MAC) layer spoofing, etc \cite{7539590}. As more and more ubiquitous wireless networks put into use, the investigation of defense strategy of physical layer security (PLS) becomes more important. Thus, integrating security at physical layer is indispensable for the evolution of wireless communication. Traditionally, symmetric encryption schemes play an important role in information security, such as providing information confidentiality, information integrity and authentication. Whereas, the secret key managements of massive wireless devices, such as the key generation, update, and storage, are constantly facing substantial pressure.

Physical layer key generation (PLKG) is a promising technology to extract symmetric keys from wireless
channel fading in a plug-and-play manner \cite{8883129}. Specifically, the PLKG is based on short-term channel reciprocity, spatial channel uniqueness and  intrinsic channel randomness, which require no public key infrastructure (PKI). From the perspective of information-theoretical security, PLKG is the most promising scheme to achieve Shannon's perfect encryption. The standard process of PLKG includes channel probing, quantization, information reconciliation and privacy amplification, which can be described as follows;
\begin{itemize}
  \item \textit{Channel probing}: Based on the short-term channel reciprocity in time division duplex (TDD) systems, the legitimate users transmit the pilot sequences accordingly to estimate the channel and collect the channel probing characteristics, such as the received signal strength (RSS) and channel state information (CSI).
  \item \textit{Quantization}: The legitimate users independently quantify the channel characteristics into binary bit sequences, which are used as raw key sequences. Due to the quantization accuracy and channel intrinsic randomness, there are some mismatched bits in the raw key.
  \item \textit{Information reconciliation}: The legitimate users negotiate the possible bit disagreements between each other by using an error correcting code, i.e., low density parity check (LDPC) code or principle component analysis, etc.
  \item \textit{Privacy amplification}: To remove the possible information leakage in public negotiation, the final symmetric key is distilled from the discussed raw key sequences via the hash function, which completes the PLKG process.
\end{itemize}

However, the performance of the PLKG is strongly depended on the intrinsic channel randomness. The key generation rate cannot be guaranteed in some static fading environments but the data transmission is on the order of Gbit/s, which limits the large-scale penetration and deployment in practice. For example, in static indoor environments, negotiating a sufficiently random raw key is a laborious and time-consuming task due to the fact that the channel based attenuations are almost predictable. This situation is predominant in some scenarios, such as an empty room or a corridor at night. Previous works have focused on PLKG in static wireless environments \cite{6311224,9000831,1528749}. The widely studied approach is to increase the randomness of the wireless channel by employing a single relay and/or cooperative relays \cite{6311224}. The participation of untrusted relays can cause the information leakage for the secret key, and the deployment of additional trusted relays can increase the cost of PLKG. Artificial random source assistance is another method to improve the key generation rate \cite{9000831}. Although this method utilizes not only the channel intrinsic randomness but also the signal randomness, it needs to modify the frame structure of the pilot signal, which limits its application on existing commercial devices, i.e., Wi-Fi. What is more, intelligent antennas have been studied to provide a high fluctuation of the channel characteristics, thereby extracting the high-entropy secret key \cite{1528749}. Nevertheless, the scalability and compatibility of off-the-shelf devices is a hindrance to the development of this approach.

Reconfigurable intelligent surfaces (RISs) with their excellent ability on electromagnetic wave control, can customize the wireless channel with moderate hardware cost and low energy consumption, and for these reasons are becoming a potential innovative technology for 6G \cite{8746155}. At present, RISs are gradually coming at the research forefront for assisting PLKG and enhancing PLS. As an early attempt, a programmable metasurface, namely HyperSurface, has been developed to show groundbreaking performance and security potential in indoor wireless communication \cite{LIASKOS20191}. Moreover, the RIS units optimization and the prototype system measurement of RIS-aided PLKG have been respectively studied in recent works \cite{9298937,9569556,9771319}. On the other hand, from the attack perspective, RIS based attacks for PLKG have been investigated, such as environment reconstruction attack and RIS manipulating attack, which make the defense strategy of PLKG even more challenging \cite{8957701,1683399}.

The combination of PLKG with RISs entails new challenges and opportunities. For instance, in RIS assisted wireless communication, the participants can realize dual-functional integration via RIS that is improving PLKG while communicating. This gives rise to the interesting concept of 6G intrinsic security that we refer to as integrating communications and security (ICAS). In the past five years, although several works have been reported on RIS-aided wireless communication with extremely diversified application scenarios, research on RIS-aided PLKG is still relatively scarce \cite{9326394}. In this context, we illustrate several potential application scenarios of RIS-aided PLKG in Fig. \ref{Fig:RIS_deployment}. The first scenario is the basic indoor RIS-aided PLKG, where Eve attempts to eavesdrop the channel information and recover the raw key. The second scenario considers a multi-RIS cooperation that is used to further increase the bit generation rate and reduce the information leakage on Eve via the cooperative RIS control strategy. In the third scenario, the direct link between Alice and Bob is blocked, and a RIS can be deployed at the obstacle edge to boost the PLKG. The optimization deployment of RIS is critical for facilitating key generation and preventing information leakage. The fourth application scenario shows that given the wireless coverage enhancement assisted by the RIS, Eve can hide in the corner of the obstacle to eavesdrop the key information, which increases the covertness of Eve. The fifth scenario is from the active attack perspective: it illustrates that the RIS can be utilized by a malicious user to launch denial of service (DoS) attacks to further prevent key generation and communication. The last one is an attack-defense scenario where both the legitimate users and malicious user are equipped with RIS. In this scenario, the control strategy of the RIS between the honker and hacker is a promising research field. The deployment of mobile RIS for PLKG, aerial RIS-aided PLKG as well as RIS-aided PLKG among multi-user and/or multi-antenna are also potential application scenarios. In addition, we highlight that only few works have measured the actual performance of the RIS-aided PLKG, whilst many PLKG challenges for RIS-aided channel are still unknown. Therefore, the real-world performance and design challenges of RIS-aided PLKG in static indoor environments should be further studied. This discussion is the motivating factor of this article in the space of RIS-aided PLKG. We start our analysis with the RIS-aided channel model and hardware architecture; then, we present proof-of-concept experiments using a RIS-aided PLKG prototype
system and discuss the design challenges, which includes channel reciprocity, RIS switch speed and RIS deployment. Moreover, we design a RIS flip attack via prototype experiments and discuss its attack-defense countermeasures. Some insightful conclusions and future research pathways are identified.

\begin{figure*}[!ht]
 \centering
  \includegraphics[width=18cm]{./figures/RIS_PKG1}
  \caption{The potential application scenarios for RIS-aided PLKG.}
  \label{Fig:RIS_deployment}
\end{figure*}

\section{System Model}
In this section, we first provide the RIS-aided channel model, and then give the hardware architecture of RIS.
\subsection{Channel Model}
We consider a Alice-Bob-Eve network in a static indoor environment, where transmitter Alice and Bob are legitimate users and Eve is a malicious user. All participants are equipped with a single antenna and work in the TDD mode. Alice and Bob plan to generate a common secret key from wireless fading channel, whilst Eve plans to hear the PLKG information over the wireless fading channel. When the RIS is added to the Alice-Bob-Eve network, the RIS-aided channel can be roughly written as the sum of the multiplicative channel and the direct link channel. Thus, the RIS-aided channel from Alice to Bob can be denoted as
\begin{equation}
\label{A2B}
\widetilde{h}_{AB}=\underbrace{\mathbf{h}^T_{RB}\mathbf{\Phi}\mathbf{h}_{AR}}_{\text{Multiplicative
channel}}+\underbrace{h_{AB}}_{\text{Direct link channel}},
\end{equation}
and the RIS-aided channel from Bob to Alice is given by
\begin{equation}
\label{A2B}
\widetilde{h}_{BA}=\mathbf{h}^T_{RA}\mathbf{\Phi}\mathbf{h}_{BR}
+h_{BA},
\end{equation}
where $\mathbf{h}_{AR}$ and $\mathbf{h}_{BR}$ represent the channel from Alice to RIS and from Bob to RIS, $\mathbf{h}_{RA}$ and $\mathbf{h}_{RB}$ represent the channel from RIS to Alice and from RIS to Bob, $(\cdot)^T$ is the transpose operation, and $\mathbf{\Phi}$ denotes the reflection matrix of the RIS in bidirectional channel probing, respectively. Similarly, the channel from Alice to Eve or from Bob to Eve can be written-out in the same manner by substituting $\mathbf{h}^T_{RE}\mathbf{\Phi}\mathbf{h}_{AR}$ or $\mathbf{h}^T_{RE}\mathbf{\Phi}\mathbf{h}_{BR}$ to the multiplicative channel and substituting $h_{AE}$ or $h_{BE}$ to the direct link channel.
\subsection{Hardware Architecture}
A RIS is made of a planar digitally programmable metasurfaces \cite{CuiTieJunRIS}. Specifically, a RIS is typically composed of three layers and a smart controller. The outer layer contains a large number of periodically repeated metasurface units, which can act directly on the incident electromagnetic signals. The subwavelength metamaterial units are composed of individual units equivalent to ``molecules/atoms" of natural materials. The middle layer is a metal isolation plate, which is used to avoid electromagnetic leakage. The inner layer is the control circuit, which is used to adjust the reflection amplitude and/or phase shift of each metasurface unit. The smart controller of RIS is usually a programmable field-programmable gate array (FPGA), which can send coding sequence to RIS and connect wirelessly to communication components, i.e., access points and terminals. In this case, by using FPGA as a smart controller, the RIS can realize different wireless propagation functions.

Theoretically, the reflection amplitude and/or phase can be continuously adjusted, where the reflection amplitude can be effectively customized within $[0,1]$ by changing the resistor load, while the reflection phase can be shifted within $[0,\pi]$ by designing binary coding sequences. However, due to the hardware cost and implementation complexity, the existing works often consider the discrete control with finite amplitude and/or phase values. Take $1$-bit phase shift control as an example: each metasurface unit can independently realize 0 and $\pi$ phase shifts by switching the PIN diode between ``OFF" and ``ON" states, respectively.

\section{Challenges in Design}
\begin{figure*}[!ht]
 \centering
  \includegraphics[width=18cm]{./figures/RIS_deployment}
  \caption{The experiment representation for RIS-aided PLKG. Figure 2(a) is for the experiment of channel
reciprocity and RIS switch speed, where Alice, Bob and RIS are at fixed positions. Figure 2(b) is for the experiment of RIS deployment, where Alice and RIS static, while Bob can move along the horizontal direction.}
  \label{Fig:RIS_deployment}
\end{figure*}
In this section, we analyze the main challenges in designing RIS-aided PLKG from proof-of-concept experiments, which are shown in Fig. \ref{Fig:RIS_deployment}, including channel reciprocity, RIS switch speed and RIS deployment. Specifically, the experiment scenario of channel reciprocity and RIS switch speed is shown in Fig. \ref{Fig:RIS_deployment}(a), and the experiment of RIS deployment is based on the scenario in Fig. \ref{Fig:RIS_deployment}(b).

Regarding the experiment architecture, the experiment requires the usage of the high-performance notebook HOST PC, the software radio platform USRP-RIO, the synchronous clock node WR LEN, the clock distributor WR switch, and the RIS. The RIS operates at $4.25$ GHz, and has $8$ rows $\times$ $32$ columns RIS units, where each RIS unit is a square with size $0.012$ m and every two rows of RIS units are a group. The RIS is controlled by four voltage signals V1, V2, V3, V4, where each voltage signal can randomly generate one of 16 equal interval voltages within $[0,21]$ to control four groups of RIS units. Alice and Bob are configured with a single antenna and connected to the PC terminal via an optical fiber. For signal design, each wireless frame is $10$ ms and $2$ OFDM symbols with $1200$ sub-carriers for each symbol are inserted to each frame. The first OFDM symbol is inserted with a pilot at every $6$ sub-carriers, and a total of $200$ pilots are inserted for the acquisition of CSI. The second OFDM symbol includes $1200$ bit of data for the calculation of RSS. The least squares (LS) channel estimation is used to obtain the CSI, and the double threshold quantization method and single bit cumulative distribution function (CDF) quantization method are adopted to obtain the raw key sequences \cite{CDFquantization}. All the raw key sequences are carried on randomness tests based on the statistical test suite for random number generators (NIST).

\subsection{Channel Reciprocity}
In the experiment of channel reciprocity, we discuss that whether the introduction of RIS can preserve the channel reciprocity or not.
\subsubsection{Setup}
For this experiment setup, the Alice-Bob transmitter pair is placed in a static indoor environment, where channel fading is varying slowly and there are few scatterers. Alice and Bob are at fixed locations and the distance between Alice and Bob is about $1.5$ m. In order to compare it to the case without RIS, we first collect $20000$ frames in the Alice-Bob pair and refer to as DATA 1. Next, by setting the RIS switch speed to be $100$ ms/time, we extract one frame every ten frames and record it in the PC terminal. Then, we take $20000$ frames in $2000$ seconds and represent it as DATA 2.
\subsubsection{Results} With CSI estimation, RSS calculation and bit quantization for DATA 1 and DATA 2, respectively, we can obtain the raw key sequences before information reconciliation and privacy amplification. From the results in Fig. \ref{Fig:PGR11}(a), we find that the bit inconsistency rate using CSI is significantly lower than the bit inconsistency rate using RSS, both in double threshold quantization and single bit CDF quantization. The reason is that RSS represents the average signal energy over a period of time and is a coarse-grained measure of channel information. On the contrary, CSI is a kind of fine-grained channel information measurement, which can better reflect the characteristics of the channel. Most obviously, from the results of DATA 1 and DATA 2 in Fig. \ref{Fig:PGR11}(a), we see that the bit inconsistency rate of DATA 1 is significantly higher than that of
DATA 2, which indicates that the received signal energy can be enhanced with the assistance of the RIS in the reflected path. In other words, the addition of RIS in Alice-Bob transmitter pair can improve the channel reciprocity by increasing the signal to noise ratio (SNR), and then reduce the inconsistency rate of bit, which facilitates the raw key generation. The CDF of RSS for DATA 1 and DATA 2 can be found in Fig. \ref{Fig:PGR11}(b); the CDF of DATA 1 changes rapidly with RSS, whereas this change is slower in DATA 2. This observation showcases that with the addition of RIS, the RSS values have a wider fluctuation range, which increases the randomness of the channel. Notably, from Fig. \ref{Fig:PGR11}(d), we observe that the key generation rate has 15-fold improvement.
\subsection{RIS Switch Speed}
In this experiment, by analyzing the different RIS switch frequencies, we reveal the influence of RIS control on PLKG.
\subsubsection{Setup} In this experimental design, Alice and Bob are also placed in a static indoor environment with fixed locations. Apart from changing the RIS switch speed with $100$ ms/time just like in the channel reciprocity experiment, we also adjust the RIS switch speed with $1000$ ms/time and collect one wireless frame in every $100$ frames. After recording $20000$ frames on the PC terminal, we denote this data set as DATA 3.
\subsubsection{Results} DATA 3 is also transformed into raw key bits via CSI estimation, RSS calculation and bit quantization. In Fig. \ref{Fig:PGR11}(a), compared with DATA 1 and DATA 2, the bit inconsistency rate of DATA 3 is the smallest. This observation showcases that the RIS switch speed can affect the reciprocity of the channel and change the inconsistency rate of raw key. This implies that a high RIS switch speed may increase the bit mismatch rate due to the increase of channel randomness. This experiment also fully proves the importance of optimization on RIS switch speed to attain a tradeoff between bit mismatch rate and channel randomness in RIS-aided PLKG design. From the results of DATA 2 and DATA 3 in Fig. \ref{Fig:PGR11}(b), we can further conclude that the RIS plays a constructive role in PLKG. In addition, based on Fig. \ref{Fig:PGR11}(d), we find that the key generation rate of DATA 3 is slightly lower than that of DATA 2. The reason is that the reduction of RIS switch speed leads to the decrease of channel fluctuation frequency, which reduces the successful probability of quantization.
\subsection{RIS Deployment}
The deployment of RIS gives a new degree of freedom for PLKG, which creates new challenges and opportunities. Here, we reveal the impact of RIS deployment on PLKG.
\begin{figure*}[!ht]
 \centering
  \includegraphics[width=18cm]{./figures/PGR11.eps}
  \caption{The experiment results of RIS-aided PLKG design.}
  \label{Fig:PGR11}
\end{figure*}
\subsubsection{Setup}
In a static indoor scenario, Alice's location is fixed and $0.5$ m away from the RIS, while Bob can move horizontally to different locations, thereby representing different RIS deployments. Specifically, the RIS switch speed is $100$ ms/time, thus one frame is extracted and stored from every ten frames. We collect three data sets, DATA 4, DATA 5, and DATA 6 with respect to the distance between RIS and Bob at $0.5$ m, $1$ m and $1.5$ m, respectively.
\subsubsection{Results} In the same way, LS channel estimation is used to obtain the CSI, and then the double threshold quantization  and single bit CDF quantization are utilized to produce the raw key. Based on Fig. \ref{Fig:PGR11}(a), the results show that with the distance between Bob and RIS growing, the bit inconsistency rate gets higher, which indicates the following two things. On one hand, the longer the distance between two communication participants, the greater the path loss will be. Thus, low SNR results in poor channel quality, which leads to a higher bit inconsistency rate. On the other hand, the longer the distance between Bob and RIS is, the proportion of the energy of RIS reflected path in the energy of all scattered paths will decrease, and then the RIS will no longer play a major role in the wireless environment. As a result, with the channel reciprocity decreasing, the bit inconsistency rate increases. This phenomenon can also be seen from Fig. \ref{Fig:PGR11}(d), which shows that it is better to deploy the RIS near the transmitter sides to reach a high key generation rate. Furthermore, this experiment also reflects that CSI has a better performance than that of RSS for PLKG with different RIS deployments. Moreover, from Fig. \ref{Fig:PGR11}(c), we can prove that the closer RIS is to the transmitter, the larger the channel fluctuation becomes.
\section{RIS for Attack}
In this section, we study the case that the RIS is controlled by Eve and give some insightful results from real-world experiments. Then, we discuss potential countermeasures.
\subsection{Challenges \& Experiments}
When malicious Eve has control over a RIS, it can rapidly flip its RIS to change the wireless environment, which can affect the PLKG between Alice and Bob. Here, this attack is referred to as RIS flip attack. Next, we show the influence of such an attack by analyzing the RIS switch speed during PLKG.
\subsubsection{Setup}
In this considered scenario, the location of Alice is fixed and the distances between Bob and RIS are $0.5$ m, $1$ m and $1.5$ m, respectively. Particularly, the RIS is assumed to be controlled by Eve and the RIS switch speed is set to be $1$ ms/time. According to the different distances between Bob and RIS, we collect three data sets, namely, DATA 7, DATA 8 and DATA 9, respectively.
\begin{figure}[!ht]
 \centering
  \includegraphics[width=8.8cm]{./figures/risATTACK.eps}
  \caption{The key generation rate: Legitimate RIS vs. RIS flip attack.}
  \label{Fig:RISat}
\end{figure}
\subsubsection{Results}
Based on the raw key sequences generated from DATA 7, DATA 8 and DATA 9, we observe that when the RIS switch speed is changed to $1$ ms/time, the Alice-Bob communication pair cannot complete an effective channel probing within a coherence time. In this case, the channel reciprocity between Alice and Bob is seriously compromised. Therefore, at the same distance between Bob and RIS, the bit inconsistency rate with RIS switch speed $1$ ms/time is much higher than that of $100$ ms/time. This produces a great pressure on information reconciliation for PLKG, which indicates more negotiation overhead. Figure \ref{Fig:RISat} shows that when the RIS is switched at $1$ ms/time by Eve, the key generation rate in different distances is only $0$-$1$ bit/frame, which seriously hinders the PLKG process of legitimate users.
\subsection{Discussions}
The RIS flip attack is an active attack which can change the RIS switch speed in a very short time, i.e., in the order of $\mu s$, which can be regarded as if the channel coherence time being compressed to some extend. In this case, Alice and Bob cannot complete bidirectional probing for at least one frame. Thus, the RIS attack is a DoS attack, which restrains the process of PLKG. Unfortunately, different from traditional active attack countermeasures, which can trace such attack based on wireless radio frequency (RF) fingerprints, RIS flip attack is inherently undetectable due to the passive nature of RIS which has no RF chain. Therefore, some new ideas are necessary to defend against such detrimental attack.
\begin{itemize}
  \item \textbf{Countermeasure 1}: Since the flip attack may achieve its malicious objective by changing the wireless channel environment using a RIS, similarly, legitimate users can deploy RIS to counteract the changes of radio electromagnetic wave, thus extending the coherence time of the channel. Specifically, Alice and Bob can superimpose a multiplicative channel, i.e., $\mathbf{h}^T_{RB}\mathbf{\Phi}\mathbf{h}_{AR}$, to counteract the influence of the illegal multiplicative channel, i.e., $\mathbf{h}^T_{EB}\mathbf{\Phi}_E\mathbf{h}_{AE}$, on the wireless signal. The challenge of this defense strategy is that the legitimate users need to know the RIS switch speed model of attack. Deep learning and reinforcement learning are powerful tools to learn the control strategy of RIS in a model-free approach, thereby confronting the attack strategy. Furthermore, multi-RIS can be used by legitimate users to simultaneously resist this attack and improve the PLKG rate in a static indoor environments.
  \item \textbf{Countermeasure 2}: The RIS flip attack causes a rapid variation of the wireless signal's amplitude and phase, which makes bidirectional channel probing fail. In this case, we can choose more robust features of the wireless channel to generate the raw key. Specifically, although the bidirectional channel probing for RSS or CSI is different in the presence of RIS flip attack, the legitimate users share the physical space and the scatterers. In this case, we can deploy multiple antennas on the legitimate users and extract the spatial reciprocity features to generate the raw key. For example, the delay and angle of each path are bidirectional reciprocal and can be captured based on Newton orthogonal matching pursuit (NOMP) algorithm. Then, we can robustly generate a key without considering the damage caused by the RIS flip attack. Since the spatial reciprocity features are often slow-varying, we have to deploy RISs for legitimate users to artificially create time-varying scatter environment or design high resolution quantization approaches to increase the key generation rate.
  \item \textbf{Countermeasure 3}: From the experiment of channel reciprocity, we saw that the addition of RIS improves the SNR of PLKG. Inspired by this, we can detect the RIS attack by monitoring the variation of RSS. Specifically, we have to obtain the statistical property of RSS in both secure and attack states. Then, a binary hypothesis test can be used to decide whether there is a RIS flip attack in the current wireless environment. When the attack occurs, the Alice-Bob pair stops the PLKG process to reduce the unnecessary resource consumption. However, this countermeasure is a passive defense strategy which can detect the existence of RIS flip attack but cannot eliminate such attack to achieve the fundamental PLKG purposes. Therefore, to transform passive defense strategy to active defense strategy, we can use a fine-grained wireless link signature to trace back the physical location of the attack and then mitigate it.
\end{itemize}

\section{Conclusions and Future Directions}
In this article, we have provided an overview of the promising RIS-aided PLKG technology for achieving a high key generation rate in a static indoor environment. Notably, a RIS can increase the SNR, thereby improving the channel reciprocity. Moreover, the RIS switch speed affects the bit mismatch rate, but the overall key generation rate is 15-fold higher than that without RIS. Next, to achieve a high bit generation rate, we find that it is better to deploy RIS near the transceiver side. Furthermore, the investigation of RIS attack-defense for RIS-aided PLKG is important. Based on our review, we identify several open challenges for RIS-aided PLKG in the following.
\begin{itemize}
  \item \textbf{RIS and/or multi-RIS optimization and configuration in RIS-aided PLKG}: Although the RIS-aided PLKG can increase the channel fluctuation and improve key generation rate, the condition of the wiretap channel is also changed. When the multipath scattering and interference are not rich enough, i.e., in an empty room, there is a strong correlation between the legitimate channel and wiretap channel even their protected zone is more than half a wavelength away. One possible direction of investigation is to optimize the RIS and/or multi-RIS to reconstruct the channel environment, thereby obtaining the achievable key secrecy rate.
  \item \textbf{RIS-aided PLKG in frequency division duplex (FDD) system}: Different from TDD communication system, FDD communication system lacks reciprocity on the frequency related channel parameters between uplink and downlink. One possible solution is to control RIS and/or multi-RIS to artificially create a large number of frequency independent reciprocal channel parameters to generate the secret key, i.e., multipath delay, angle of arrival and/or departure, etc. In addition, for massive MIMO FDD communication systems, the RIS-aided PLKG can be integrated with CSI feedback, which is a promising topic for ICAS.
  \item \textbf{Defense strategy of PLKG for RIS active attacks}: RIS active attacks can realize a reconfigurable smart and programmable jamming and eavesdropping channel. Then, by injecting the malicious signal to manipulate the channel probing, the information of the secret key can be partially or completely leaked. Particularly, given the passive components of RIS, these attacks are often highly covert. On these lines, the countermeasures for RIS active attacks in PLKG are still largely open.
  \item \textbf{RIS-aided PLKG in ubiquitous 6G wireless networks}:
      Except for the static indoor scenario, RIS-aided PLKG can be combined with ubiquitous wireless networks, i.e., airborne, autonomous vehicle networks, and so on. This provides new degrees of freedom to further jointly optimize the RIS and network mobility, thereby improving the performance of key generation rate and data transmission rate, simultaneously.
\end{itemize}

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{IEEEtran