Is This Scheduling Problem NP-Hard?

Question

The scheduling problem (arising from distributed computing) is defined as a decision problem as follows:

Instance:

A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-1}$), each of which consisting of a finite sequence of Read and Write operations on multiple shared variables in program order.

An important restriction here is that all the Read operations are on the process $p_0$.

Example:

The above figure gives a trace example. Here, $W$ is for Write operation, and $R$ is for Read operation. $Wx1$ means updating the shared variable $x$ to 1. $Ry3$ means reading the shared variable $y$ and returning 3.

Problem:

Is there some schedule (i.e., a sequence) of all the operations such that:

• the program order between operations is maintained;
• in the schedule, each Read should read the value from the latest preceding Write on the same variable.

Example (Cont.):

For example, the trace in the above figure can be scheduled as follows: $$Wx1(p_1), Wx1(p_0), Rx1, Wx2(p_1), Wy3, Ry3, Wx2(p_0), Wx1(p_3), Rx1.$$

Now, I want to study the complexity issue of this decision problem. Specifically, is this decision problem NP-hard?

Answer 1

This is a possible reduction from 3-partition which is strongly NP-complete.

Given a set $A = \{a_1,a_2,...,a_{3m}\}$ of $3m$ positibe integers, and a target sum $B$.

The basic idea is simple: if we found a read sequence like $Rx1\; Rx2\; Rx1$, even if the last write of $x$ before the sequence was a $Wx2$, the first $Rx1$ forces to "use" another $Wx2$ to satisfy the $Rx2$ in the middle.

We represent each $a_i$ with a unary chain $P_{a_i}$ made of $a_i+2$ write operations: the first operation is a $Wx2$ (green boxes in the figure), followed by $a_i$ write operations $Wy2$ (gray boxes), followed by a single $Wz2$ (blue boxes) write operation.

We add three auxiliary chains $P_{c_1}, P_{c_2}, P_{c_3}$. $P_{c_1}$ made with $4m$ write operations $Wx1$, $P_{c_2}$ made with $B \cdot m = \sum_{i=1}^{3m} a_i$ write operations $Wy1$, $P_{c_3}$ made with $4m$ write operations $Wz1$.

Now we build the chain $P_0$ made only with read operations in the following way: concatenate $m$ slot subsequences; each slot subsequence is made with:

• a leading open sequence $Rx1\; Rx2\; Rx1\; Rx2\; Rx1\; Rx2\; Rx1$, that forces to pop three operations $Wx2$ from three distinct $P_{a_i}$ and open those chains;

• followed by a sum sequence $Ry1\; Ry2$ repeated $B$ times, that forces to pop $B$ operations $Ry2$ from the chains that are currently open;

• followed by a trailing close sequence $Rz1\; Rz2\; Rz1\; Rz2\; Rz1\; Rz2\; Rz1$, that forces to pop three operations $Wz2$ from the end of the chains that are currently opened.

Note that if a chain is opened and some $Wy2$ are still there and in order to complete the current close sequence we pop them (without a corresponding $Ry2$) to reach the final $Wz2$, in one of the next slot subsequences there will be not enough $Wy2$ to reach the close sequence. And if we are in the middle of a sum sequence and we need a $Wy2$ but we've already reached the end of all the currently opened $a_i$ chains, we cannot open another chain to recover a $Wy2$ to complete the sum sequence, otherwise in one of the next slot subsequences there will be not enough $Wx2$ to complete an open sequence.

The figure represents the instance: $A = \{ 3,3,2,2,2,2 \}$, $m=2$, $B=7$ (note that every $a_i$ should be between $B/4$ and $B/2$ to force exactly three elements in each slot sequence)

NOTE: as noted in the comments, the trailing $Rx1$ (resp. $Rz1$) of the open (resp. close) sequences are unuseful and they can be removed (and $P_{c1}, P_{c3}$ shortened to $3m$ elements).