# Is This Scheduling Problem NP-Hard?

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?

• Some clarifications: it is not clear if the read operations of the schedule must occur exactly after a write on the same variable. In your example is Wx1(p0),Wx1(p1),Wx2(p1),Rx1,... a valid scheduling? Furthermore the trace itself seems to induce a valid scheduling (scan right-to-left, when you find a read operation put the corresponding write operation just before it if it exists, otherwise reject). Sep 27 '13 at 7:12
• $Wx1(p_0),Wx1(p_1),Wx2(p_1),Rx1, \ldots$ is not valid, because $x$ has been updated to 2 by $p_1$ and $Rx1$ is not possible to return the stale value 1. However, it does not mean that the read operations of the schedule must occur exactly after a write on the same variable. A write on a different variable may be between them. In addition, there may be many "writes" updating the same variable to the same value, so your "scan" algorithm encounters non-determinism. Actually, I think the non-determinism may be the hardness of the scheduling problem. Thanks. Sep 27 '13 at 7:39

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).

• Thanks a lot. I need time to understand it before accepting it. Also, I need more comments from peer reviewers. Sep 28 '13 at 2:10
• @hengxin: ok! I'll check it again later, too (to be honest I didn't think about it, too much :-) Sep 28 '13 at 8:10
• I got the basic idea of your smart reduction. I tend to believe that it is right. Three questions here: (1) What does the last $Rx1$ do in the read sequence pattern $Rx1, Rx2, Rx1$ (also in open sequence and close sequence)? I think $Rx1, Rx2$ is enough to force to use another $Wx2$ to satisfy the $Rx2$. (2) Does your reduction imply that the scheduling problem is NP-hard even when only three variables are used and $P_0$ is read-only? (3) You said that $P_{c2}$ is made with $3m$ write operations $Wy1$''. Is it $B \cdot m = \sum A_i$ instead of $3m$ (slip of the pen)? Thanks. Oct 2 '13 at 7:25
• @hengxin: (1) yes it is unuseful: but I realized it after drawing the figure so I leaved it :) (2) yes (it is also in NP so it is NP-complete) (3) yes it is $B \cdot m = \sum_{i=1}^{3m} a_i$ Oct 2 '13 at 8:42
• @hengxin: perhaps you can replace Wy1,Wy2,Ry1,Ry2 and Wz1,Wz2,Rz1,Rz2 with Wx3,Wx4,Rx3,Rx4 and Wx5,Wx6,Rx5,Rx6 ... so a single variable is enough ... I'll think about it. Oct 2 '13 at 10:55