4
$\begingroup$

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:

"simple trace" 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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Marzio De Biasi Sep 27 '13 at 7:12
  • $\begingroup$ $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. $\endgroup$ – hengxin Sep 27 '13 at 7:39
3
$\begingroup$

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)

enter image description here

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

$\endgroup$
  • $\begingroup$ Thanks a lot. I need time to understand it before accepting it. Also, I need more comments from peer reviewers. $\endgroup$ – hengxin Sep 28 '13 at 2:10
  • $\begingroup$ @hengxin: ok! I'll check it again later, too (to be honest I didn't think about it, too much :-) $\endgroup$ – Marzio De Biasi Sep 28 '13 at 8:10
  • $\begingroup$ 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. $\endgroup$ – hengxin Oct 2 '13 at 7:25
  • $\begingroup$ @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$ $\endgroup$ – Marzio De Biasi Oct 2 '13 at 8:42
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Oct 2 '13 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.