The design of CML has been driven by practical experience. In particular, the mechanism of first-class synchronous operations is motivated by the fundamental conflict between selective communication and abstraction. This chapter explains the rationale for the design of CML, and especially for first-class synchronous operations. It is aimed at people interested in language design, and is not required to understand the remainder of the book. In this chapter, we focus on coreCML — synchronous message passing plus the event combinators — the other synchronization mechanisms found in CML, such as mailboxes, I-variables, and M-variables, can be viewed as derived forms. Some of the discussion here repeats earlier arguments, but is included for coherence.

Basic design choices

As surveyed in Chapter 2, there are many possible choices for the design of a concurrent language. CML chooses message passing over shared memory, synchronous communication over asynchronous, and simple rendezvous over extended rendezvous. This section argues in favor of these choices.

While SML is an imperative language, its design greatly encourages a mostly functional style of programming. Mutable values must be declared explicitly as such, and there is syntactic overhead on their use. For these reasons, extending SML with sharedmemory concurrency primitives is not true to the “spirit” of the language. Message passing, on the other hand, encourages a mostly functional programming style that fits well with ML. As we have seen, much of the state in typical CML programs is represented as immutable arguments to the tail-recursive functions that implement threads.

Concurrent programming is the task of writing programs consisting of multiple independent threads of control, called processes. Conceptually, we view these processes as executing in parallel, but in practice their execution may be interleaved on a single processor. For this reason, we distinguish between concurrency in a programming language, and parallelism in hardware. We say that operations in a program are concurrent if they can be executed in parallel, and we say that operations in hardware are parallel if they overlap in time.

Operating systems, where there is a need to allow useful computation to be done in parallel with relatively slow input/output (I/O) operations, provide one of the earliest examples of concurrency. For example, during its execution, a program P might write a line of text to a printer by calling the operating system. Since this operation takes a relatively long time, the operating system initiates it, suspends P, and starts running another program Q. Eventually, the output operation completes and an interrupt is received by the operating system, at which point it can resume executing P. In addition to introducing parallelism and hiding latency, as in the case of slow I/O devices, there are other important uses of concurrency in operating systems. Using interrupts from a hardware interval timer, the operating system can multiplex the processor among a collection of user programs, which is called time-sharing. Most time-sharing operating systems allow user programs to interact, which provides a form of user-level concurrency.

A principal use of concurrent programming is in the implementation of distributed systems. A distributed system consists of processes running in different address spaces on logically different processors. Because the processes are physically disjoint, there are a number of issues that arise in distributed systems that are not present in concurrent programming:

• Communication latency is significantly higher over a network than between threads running in the same address space.

• Processors and network links can go down, and come back up, during the execution of a distributed program.

• Programs running on different nodes may be compiled independently, which means that type security cannot be guaranteed statically.

For these reasons, the synchronous model used in CML does not map well to the distributed setting. A different programming model is required for dealing with remote communication.

Although concurrent programming languages, such as CML, may not directly provide a notation for distributed programming, they do have an important rôle in implementing distributed systems. A distributed system is made up of individual programs running on different machines, which must communicate with each other. Managing this communication is easier in a concurrent language. Furthermore, multiple threads of control can help hide the latency of network communication. For these reasons, most distributed programming languages and toolkits provide concurrent programming features.

This chapter explores a distributed implementation of Linda-style tuple spaces (described in Section 2.6.3).

Concurrent programming differs from sequential programming in several significant ways. Conceptually, we can view the execution of a concurrent program as an interleaving of the sequential execution of its constituent processes. Since there are many possible interleavings, the execution of a concurrent program is nondeterministic; i.e., different interleavings may produce different results. In effect, a concurrent program defines a partial order on its actions, whereas a sequential program defines a total order. This nondeterminism is both the bane and boon of concurrent programming: on the one hand, it creates additional correctness problems, while on the other hand, it provides flexibility and a more natural program structure. As argued in Chapter 1, the choice of programming notation can help the programmer control the complexity of concurrency, while reaping its benefits.

A concurrent language typically consists of a sequential core (or sub-language), extended with support for concurrency. The concurrency support can be divided into three different kinds of mechanism:

• • A mechanism for introducing independent sequential threads of control, called processes. The process creation mechanism can be either static, restricting the program to a fixed number of processes, or dynamic, allowing new processes to be created “on-the-fly.”

• • A mechanism for processes to communicate. Communication involves exchanging data, either through shared memory locations (e.g., variables) or by explicit message passing.

• • And a mechanism for processes to synchronize. Synchronization restricts the ordering of execution in otherwise independent threads, and is used to limit the program's nondeterminism where necessary.

This chapter is the first of three tutorial chapters on the basic features and programming techniques of CML. This chapter focuses on the features that make up CML's semantic core. The next chapter continues with a discussion of the two most important styles of CML programming: process networks and client-server protocols. Chapter 5 completes the tutorial with further discussion of CML's synchronization and communication mechanisms.

Sequential programming

As is the case with most concurrent languages, CML consists of a sequential core language — Standard ML — extended with concurrency primitives. The individual processes in a CML program are programmed using the features of SML. While we conceptually view CML as a programming language, it is actually implemented as a collection of modules on top of SML/NJ. The aspects of CML described in this chapter all belong to the core structure of this library, which is named CML. To reduce notational clutter, most of the examples in this chapter are assumed to be given in an environment where the CML structure has been pre-opened (i.e., all of its bindings are at top-level). The CML structure's interface is described in Appendix A, which contains an abridged version of the CML Reference Manual.

CML is a message-passing language, which means that processes are viewed as executing in independent address spaces with their only communication being via messages. But, since SML provides updatable references, this is a fiction that must be maintained by programming style and convention.

In this chapter we present some problems for which their NC approximations are obtained using other techniques like “step by step” parallelization of their sequential approximation algorithms. This statement does not implythat the PRAM implementation is trivial. In some cases, several tricks must be used to get it. A difference from previous chapters is the fact that we shall also consider “heuristic” algorithms. In the first section we present two positive parallel approximation results for the Minimum Metric Traveling Salesperson problem. We defer the non-parallel approximability results on the Minimum Metric Traveling Salesperson problem until the next chapter. The following section deals with an important problem we already mentioned at the end of Section 4.1; the Bin Packing problem. We present a parallelization to the asymptotic approximation scheme. We finish by giving a state of the art about parallel approximation algorithms for some other problems, where the techniques used do not fit into any of the previous paradigms of parallel approximation, and which present some interesting open problems.

The Minimum Metric Traveling Salesperson Problem

Let us start by considering an important problem, the Minimum Metric Traveling Salesperson problem (MTSP). It is well known the problem is in APX. There are several heuristics to do the job. The most famous of them is the constant approximation due to Christofides [Chr76]. Moreover the problem is known to be APX-complete [PY93]. Due to the importance of the problem, quite a few heuristics have been developed for the MTSP problem. For instance, the nearest neighbor heuristics, starting at a given vertex, among all the vertices not yet visited, choose as the next vertex the one that is closest to the current vertex.

The linear programming primal-dual method has been extensively used to obtain sequential exact algorithms (see for example [Chv79], [PS82]). This algorithm keeps both a primal solution and a dual solution. When the solutions together satisfy the complementary slackness conditions, then they are mutually optimal. Otherwise either the primal solution is augmented or the dual solution is improved. The primal-dual method was originally due to Dantzing, Ford and Fulkerson [DFF56]. Unless P=NP, the primaldual method cannot be used to solve exactly in polynomial time NP-hard problems.

The primal-dual framework has been particularly useful to obtain polynomial time approximation algorithms for some NP-hard combinatorial optimization problems (see for example the forthcoming survey by Goemans and Williamson [GW96]). For those problems that can be formulated as integer programming problems, the approach works with the linear programming relaxation and its dual, and seeks for an integral extension of the linear programming solution. Furthermore the use of the combinatorial structure of each problem determines how to design the improvement steps\ and how to carry on the proof of approximation guarantee. There is no general primal-dual approximate technique; however, some approaches can be seen as producing both primal and dual feasible solutions, until some conditions are met. Those last conditions insure that the values of the primal and dual solutions are within 1 + ε of each other. As the optima of the primal and dual problems are the same, the primal and dual feasible solutions produced by the algorithm have a value within 1 + ε of optimal value.

An interesting question in graph theory is to find whether a given graph contains a vertex induced subgraph satisfying a certain property. We shall consider the special case where the property depends only on the value of a certain parameter that can take (positive) integer values. Such properties are described as weighted properties. For a given graph G = (V,E), G′ ⊆ G means that G′ is a vertex induced subgraph of G. The generic Induced Subgraph of High Weight problem (ISHW) consists in, given a graph G = (V, E), a weighted property W on the set of graphs, and an integer κ, to decide if G contains a vertex induced subgraph H such that W(H) ≥ κ. A first concrete example of the Induced Subgraph of High Weight problem is the case when W is the minimum degree of a graph. This instance of the problem is known as the High Degree Subgraph problem (HDS). Historically, this is the first problem shown to be P-complete and approximated in parallel ([AM86] and [HS87]). Another instance of the Induced Subgraph of High Weight is the case when W is the vertex (or edge) connectivity of G. These problems are known as the High Vertex Connected Subgraph problem (HVCS) (respectively the High Edge Connected Subgraph problem (HECS)). As we shall show in Chapter 8, these problems are also P-complete for any κ ≥ 3.

Anderson and Mayr studied the High Degree Subgraph problem and found that the approximability of the problem exhibits a threshold type behavior. This behavior implies that below a certain value of the absolute performance ratio, it remains P-complete, even for fixed value κ.

The approximation techniques that we consider in this chapter apply to problems that can be formulated as profit/cost problems, defined as follows: given an n × n positive matrix C and two positive vectors p and b, find an n-bit vector ƒ such that its cost C . ƒ is bounded by b and its profit p . ƒ is maximized. The value of ƒ is computed incrementally. Starting from the 0 vector, the algorithm analyzes all possible extensions incrementing one bit at a time, until it covers the n bits. Notice that the new set can have twice the size of the previous one thus leading to an exponential size set in the last step. However, we can discard some of the new assignments according to some criteria to get polynomial size sets.

Consider the interval determined by the minimum current profit and the maximum one. In the interval partitioning technique this interval is divided into small subintervals. The interval partition also gives a partition of the current set of assignment. From each class the assignment that dominates all others is selected, and the remainder discarded.

In the separation technique, the criterion used to discard possible completions insures that there are no duplicated profit values, and the profits of no three partial solutions are within a factor of each other.

The rounding/scaling technique is used to deal with problems that are hard due to the presence of large weights in the problem instance. The technique modifies the problem instance in order to produce a second instance that has no large weights, and thus can be solved efficiently.

This monograph surveys the recent developments in the field of parallel approximability to combinatorial optimization problems. The book is designed not specifically as a textbook, but as a sedimentation of a great deal of research done on this specific topic. Accordingly, we do not include a collection of exercises, but throughout the text we comment about different open research problems in the field. The monograph can easily be used as a support for advanced courses in either parallel or sequential algorithms, or for a graduate course on the topic.

In Chapter 1, we motivate the topic of parallel approximability, using an example. In the same chapter we keep the reasoning at a very intuitive level, and we survey some of the techniques and concepts that will be assumed throughout the book, like randomization and derandomization. In Chapter 2 we give a formal presentation of algorithms for the Parallel Random Access Machines model. We survey some of the known results on sequential approximability, and introduce the basic definitions and classes used in the theory of Parallel Approximability. The core of the book, Chapters 3 to 7, forms a collection of paradigms to produce parallel approximations. The word “paradigm” has a different semantic from the one used by Kuhn, in the sense that we use paradigm as a particular property or technique that can be used to give approximations in parallel for a whole class of problems. Chapter 3 presents the use of extremal graph theory, to obtain approximability to some graph problems. Chapter 4 presents parallel approximability results for profit/cost problems using the rounding, interval partitioning and separation techniques.

In this appendix we give the formal definition of the problems that have been used throughout the survey.

CIRCUIT VALUE

Instance: An encoding of a boolean circuit with n gates together with an input assignment.

Solution: The value of the output gate.

LINEAR PROGRAMMING

Instance: An integer m × n matrix A, an integer m-vector b and an integer n-vector c.

Solution: A rational n-vector x such that A x ≤ b.

Measure:cTx.

HIGH DEGREE SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The minimum degree of H.

HIGH EDGE CONNECTED SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The edge connectivity of H.

HIGH LINKAGE SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The linkage of H, defined as the maximum minimum degree of any of the subgraphs.

HIGH VERTEX CONNECTED SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The connectivity of H.

LOCAL MAXIMUM CUT

Instance: A graph G = (V, E) together with a partition of V.

Solution: A partition locally optimum for non-oblivious local search.

MAXIMUM ACYCLIC SUBGRAPH

Instance: A digraph G = (V, E).

Solution: Subset E′ ⊆ E such that G′ = (V, A′) is acyclic.

Measure: |E′|.

MAXIMUM 0–1 KNAPSACK

Instance: An integer b and a finite set I = {1,…,n}, for each i ∈ I an integer size Si and an integer profit pi

Solution: Subset S ⊆ I such that ∑i∈Ssi ≤ b.

Measure: ∑spi.

For some graph problems, the fact of restricting the input to planar graphs simplifies the computational complexity of the problem. However, there are some NP-complete problems that remain NP-complete even when restricted to planar graphs, for instance the Maximum Independent Set problem (see [GJ79]). We have already mentioned in the introduction that to find a constant approximation to the problem of the Maximum Independent Set for a general graph with n vertices is as difficult as to find an approximation to the problem of finding a Maximum Clique, which means that unless P=NP, the Maximum Independent Set problem cannot be approximated within n1−ε [Has96].

Baker ([Bak83], [Bak94]) took advantage of a particular way of decomposing planar graphs to produce approximation schemes for some problems that for general graphs were difficult to approximate, among them the Maximum Independent Set problem. The idea of her method is, given a problem on a planar graph, to choose a fixed κ and decompose the graph into fcouterplanar graphs (see below for the basic definitions on planar graphs), then using dynamic programming techniques obtain the exact solution to the problem for each of the κ-outerplanar graphs. For each κ, an adequate decomposition of the graph into κ-outerplanar subgraphs gives a, κ/(κ + 1) approximation to the optimal. Moreover it could be implemented in polynomial time. Taking κ = O(c log n) where c is some constant, a Polynomial Time Approximation Scheme is obtained. Using the above technique, Baker was able to produce Polynomial Time Approximation Schemes for a set of problems on planar graphs. The most significant of them is the Maximum Independent Set problem.