\subsection{Parallel Task Scheduling} When elements of a poset are tasks that need to be done and the partial order is precedence constraints, topological sorting provides us with a legal way to execute tasks sequentially, i.e., without violating any precedence constraints. \\ But what if we have the ability to execute more than one task at the same time? \\ For example, say tasks are programs, partial order indicates data dependence, and we have a parallel machine with lots of processors instead of a sequential machine with only one. \\ How should we schedule the tasks? \\ Our goal should be to minimize the total {\em time\/} to complete all the tasks. \\ (For simplicity, say all the tasks take the same amount of time and all the processors are identical.) \\ So: \\ Given a finite poset of tasks, how long does it take to do them all, in an optimal parallel schedule? \\ Assume that all tasks take 1 unit of time and we have an unlimited number of processors. \\ \\ Use partial order concepts to analyze this problem. \\ \\ On clothes example, we could do all the minimal elements first (Lsock, Rsock, underwear, shirt), remove them and repeat. \\ Need lots of hands, or maybe dressing servants. \\ (So do pants and sweater next, and then Lshoe, Rshoe, and belt, and finally jacket.) \\ \\ Can't do any better, because the sequence shirt, pants, belt, jacket must be done in that order. \\ A sequence like this is called a chain. \begin{defin} A {\bf chain\/} in a poset is a sequence of elements of the domain, each of which is smaller than the next in the partial order ($\preceq$ and $\neq$). \end{defin} Clearly, parallel time $\geq$ length of any chain. \\ This is true, because if we used less time, then by pigeonhole two tasks in the chain would have to be done at the same time, but by definition of chain this violates precedence constraints. \\ \\ A longest chain is also known as a {\em critical path}. \\ \\ So we need at least $t$ steps, where $t$ is the length of the longest chain. \\ Fortunately, it is always possible to use only $t$: \begin{theorem} Given any finite poset $(A, \preceq)$ for which the longest chain has length $t$, it is possible to partition $A$ into $t$ subsets, $A_1, A_2, \cdots, A_t$ such that $(\forall i \in [1,t]) (\forall a \in A_i) (\forall b \preceq a, b \neq a) [ b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} ]$. \end{theorem} That is, can divide up the tasks into $t$ ``groups'' so that for each group $i$, all tasks that have to precede tasks in $i$ are in smaller-numbered groups. \begin{corollary} For $(A, \preceq)$ and $t$ as above, it is possible to schedule all tasks in $t$ steps. \end{corollary} \begin{proof} $\forall i$, schedule all elements of $A_i$ at time $i$. \\ This satisfies the precedence requirements, because all tasks that must precede a task are scheduled at preceding times. \\ \end{proof} \begin{corollary} parallel time = length of longest chain \end{corollary} So it remains to prove the partition theorem: \begin{proof} Use the rule: \\ Put each $a$ in set $A_i$, where $i$ is the length of the longest chain ending at $a$. \\ \\ See this works: \\ It gives just $t$ sets, because the longest path is length $t$. \\ \\ Need to show $(\forall i) ( \forall a \in A_i)$ \\ $(\forall b \preceq a, b \neq q) [ b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} ]$. \\ \\ Proof by contradiction: \\ If $b \not\in A_1 \cup A_2 \cup \cdots \cup A_{i-1}$ then there is a path of length $>i-1$ ending in $b$, \\ which means there is a path of length $>i$ ending in $a$, \\ which means $a \not \in A_i$. \\ This is a contradiction. \end{proof} So with an unlimited number of processors, the time to complete all the tasks is the length of the longest chain. \\ \\ It turns out that this theorem is good for more than parallel scheduling. It is usually stated as follows. \begin{corollary} If $t$ is the length of the longest chain in a poset $(A, \preceq)$ then $A$ can be partitioned into $t$ antichains. \end{corollary} \begin{defin} An {\bf antichain\/} is a set of incomparable elements. \end{defin} This is a corollary because we showed before how to partition the tasks into sets that could be done at the same time, which means that these were incomparable. (If any two comparable then one would have to precede other and so couldn't be done at same time.) Review: \begin{itemize} \item {\bf chain\/}: all elements comparable (total order) \item {\bf antichain\/}: all elements incomparable \end{itemize} \subsection{Dilworth's Theorem} We can use this to prove a famous result about posets: \subsubsection{The Basics} \begin{theorem} (Dilworth) $\forall t$, every poset with $n$ elements must have a chain of size $ > t$ or an antichain of size $\geq \frac{n}{t}$. \end{theorem} Ex: Dressing poset. $n = 10$. Try $t = 3$. Has chain of length $4$. \\ Try $t = 4$. Has no chain of length $5$, but has antichain of size $4 \geq \frac{10}{4}$. \\ \begin{proof} Assume there is no chain of length $> t$. \\ So, longest chain has length $\leq t$. \\ Then by previous result, the $n$ elements can be partitioned into $\leq t$ antichains. \\ (Cannot assume exactly $t$, since could have some empty.) \\ So there is an antichain with $\geq \frac{n}{t}$ elements. \\ As needed. \end{proof} For instance: \begin{corollary} Every poset with $n$ elements has a chain of length $> \sqrt{n}$ or an antichain of size $\geq \sqrt{n}$. \end{corollary} Set $t= \sqrt{n}$ and this is immediate. Posets arise in all sorts of contexts, and when they do Dilworth's theorem can have interesting implications. \remove{ \subsubsection{Increasing and Decreasing Sequences} A mathematical example: \\ In any sequence of $n$ different numbers, there is either an increasing subsequence of length $> \sqrt{n}$ or a decreasing subsequence of length $\geq \sqrt{n}$. \\ \\ E.g., 6 4 7 9 1 2 5 3 8 has the decreasing sequence 6 4 1 and the increasing sequence \\ 1 2 3 8. That is, it has both. \\ \\ We can get this using Dilworth's theorem; the trick is to define the appropriate poset. \\ \\ The domain is the set of values in the sequence. \\ \\ For the ordering, define $a \preceq b$ if either $a = b$, or else ($a < b$ and $a$ comes before $b$ in the sequence). \\ \\ Check this is reflexive (stated explicitly), transitive, and antisymmetric. \\ \\ A chain corresponds to a sequence that increases in value and moves to the right, that is, an increasing sequence. \\ \\ But what does an antichain correspond to? \begin{lemma} If $a,b$ are incomparable and $a > b$ then $a$ precedes $b$ in the sequence. \end{lemma} \begin{proof} By contradiction. \\ Assume $b$ precedes $a$. \\ Then $b < a$ and $b$ precedes $a$, so $b \preceq a$ in the partial order. \\ This contradicts our assumption that $a$ and $b$ are incomparable. \end{proof} Extend this to more than 2 elements: \begin{lemma} If $a_1, a_2, \cdots , a_t$ are incomparable and $a_1 > a_2 > \cdots > a_t$ then $a_1, a_2, \cdots a_t$ form a decreasing subsequence. \end{lemma} \begin{proof} $(\forall i)$, the fact that $a_i > a_{i+1}$ implies that $a_i$ precedes $a_{i+1}$ in the sequence, by the previous lemma. \end{proof} So given an antichain, arrange the elements so that they are in decreasing order and the ``left of'' relation follows, giving a decreasing subsequence. Dilworth's theorem implies that there is either a chain of size $> \sqrt{n}$ or an antichain of size $\geq \sqrt{n}$. \\ By the analysis just above, this yields either an increasing sequence of length $> \sqrt{n}$ or a decreasing subsequence of length $\geq \sqrt{n}$. }%end remove \subsubsection{Number of Comparisons for Database Setup and Searching} Consider a ``database'' of records with (distinct) numerical keys. \\ Suppose when records are inserted, some comparisons of these keys occur, and the database maintains a record of these comparisons. \\ \\ E.g., at one extreme, database could be kept totally sorted. \\ E.g., totally unsorted. \\ \\ Each comparison costs something -- the time to perform it. \\ \\ Now suppose that after this setup, a search is to be performed on the database to determine if a record with a particular key $k$ appears anywhere in the database. \\ The search is supposed to be based on comparisons only. \\ Then the worst-case number of comparisons it takes depends on the database partial order. \\ \\ E.g., if db is totally sorted, can compare with middle elements, then middle of halves, etc. \\ Binary search. \\ Approximately log n comparisons needed. \\ \\ E.g., if db totally unsorted, then in the worst case, have to compare with every element. \\ This is because each comparison with an element in the db gives no information about whether the sought element might be any of the others in the db. \\ \\ In fact, if there is an antichain of size $k$, then in the worst case, the new key could be any of the elements of the antichain. \\ So in the worse case, have to compare with all $k$, since each one gives no information about the others. \\ \\ See what Dilworth's theorem says about the database partial order. \\ For any $t$, either have a chain of length $> t$, or an antichain of size $\geq \frac{n}{t}$. \\ Setting up a chain of length $> t$ requires at least $t$ comparisons. \\ The antichain requires at least $\frac{n}{t}$ comparisons. \\ So this says that we have to pay the cost sometime -- tradeoff -- either we do $> t$ comparisons while setting up the db, or at least $\frac{n}{t}$ in the worst case to search the db. \\ \\ More refined analysis is possible. \\ That's because reliably setting up a long chain, say length $t$, in the database actually requires {\em more} than $t$ comparisons. \\ Because in the worst case, the comparisons won't come out in the most desirable way, setting up a linear chain. \\ Ex: Compare $a$ and $b$, find out $a > b$. Then compare $b$ and $c$. Would be nice if we found out $b > c$. But we might not -- might get $c > b$. Then we don't have a chain of length $3$, but still an antichain of size $2$. To get a chain, need an additional comparison. \\ \\ Return to this in analysis of algorithms. \subsection{Logical Time in Distributed Systems} One last use of p.o. \\ No use of powerful theorems here -- just showing an important place where a p.o. is used as a mathematical model for a real computational situation. \\ \\ A distributed computation consists of a sequence of ``steps'' occurring at each of a collection of $n$ ``processes''. \\ In addition to performing local steps, the processes can send messages to each other. \\ So, have $\ms{send}$ steps and $\ms{receive}$ steps. \\ \\ The processes are mostly working independently. \\ The only interaction is by means of the messages. \\ So, the only dependence among steps (feeding data from one to another, using results to make decisions, etc.) is by: \\ \begin{enumerate} \item Successive steps of same process. \item Send vs. receive of same message. \end{enumerate} Taking reflexive transitive closure leads to partial order describing the dependence among the computation steps. \\ \\ Basic theorem: Any topological sort of this p.o. describes a possible sequence in which all the distributed steps could occur. \\ (No changes in what happens based on reordering incomparable steps.) \\ \\ Example of what one might do with this p.o.: \\ Assign ``logical time'' to every step. \\ Instead of an actual real time. \\ The time is just any assignment of real numbers to the steps that is consistent with the p.o.: when one step precedes another in the p.o., it must have a smaller logical time. \\ \\ Behaves like real time: Formally, can reorder the steps in logical time order, still consistent with the p.o.\\ Then the system is behaving as if the logical time were actually real time. \\ \\ Can be maintained by simple distributed algorithm. \\ (Piggybacks time on message, adjusts local times in response to what is heard in some messages.) \\ \\ Although logical time isn't the same as actual real time, for many purposes, it can be used as an adequate substitute. \\ Logical time can be used, e.g., to timestamp files to keep updated copies consistent.