In this chapter we consider some problems that are non-approximable by NC algorithms unless P=NC. The basic technique used to prove non-approximability is the design of a reduction that generates instances in such a way that a gap in the value of the objective function is created.

First we concentrate on the Induced Subgraph of High Weight type problems studied in Chapter 3. Anderson and Mayr [AM86] studied this problem when the weight considered is the minimum degree of the graph. They provide a reduction from the Circuit Value problem to the High Degree Subgraph problem that creates a 1/2 gap in the weight of the so obtained instance. Kirousis, Serna and Spirakis studied this problem for two new weight functions, namely, vertex connectivity and edge connectivity, (see [SS89], [Ser90], [KSS93]). Kirousis and Thilikos analyzed the graph linkage [KT96] whose approximability presents the same kind of threshold behavior. All non-approximability results follow the same technique, that is, they create a graph, translating each circuit component or connection into a particular subgraph, in order to generate a graph that satisfies the required gap properties.

Our second result corresponds to problems that are non-approximable in NC, which means that for any e we are able to generate an instance in which an e-gap appears. Serna [Ser91] showed that the linear programming problem cannot be approximated in NC for any ratio, other non-approximable problems can be found in [SS89], [KS88], [Ser90].

To complement the non-approximability view we want to consider also the possible paralellization of heuristics used to deal with NP-hard problems.

In this chapter we provide an intuitive introduction to the topic of approximability and parallel computation. The method of approximation is one of the well established ways of coping with computationally hard optimization problems. Many important problems are known to be NP-hard, therefore assuming the plausible hypothesis that P≠NP, it would be impossible to obtain polynomial time algorithms to solve these problems.

In Chapter 2, we will give a formal definition of optimization problem, and a formal introduction to the topics of PRAM computation and approximability. For the purpose of this chapter, in an optimization problem the goal is to find a solution that maximizes or minimizes an objective function subjected to some constrains. Let us recall that in general to study the NPcompleteness of an optimization problem, we consider its decision version. The decision version of many optimization problems is NP-complete, while the optimization version is NP-hard (see for example the book by Garey and Johnson [GJ79]). To refresh the above concepts, let us consider the Maximum Cut problem (MAXCUT).

Given a graph G with a set V of n vertices and a set E of edges, the MAXCUT problem asks for a partition of V into two disjoint sets V1 and V2 that maximizes the number of edges crossing between V1 and V2. From now on through all the manuscript, all graphs have a finite number of vertices n. The foregoing statement of the MAXCUT problem is the optimization version and it is known to be NP-hard [GJ79].

In Chapter 2, we presented several complexity classes based on the approximability degree of the problems they contain: APX, PTAS, FPTAS and their parallel counterparts NCX, NCAS, FNCAS. These classes, defined in terms of degree of approximability, are known as the “computationally defined” approximation classes. We have seen that in order to show that a problem belongs to one of these classes, one can present an approximation algorithm or a reduction to a problem with known approximability properties. In this chapter we show that in some cases the approximation properties of a problem can be obtained directly from its syntactical definition. These results are based on Fagin's characterization of the class NP in terms of existential second-order logic [Fag75], which constitutes one of the most interesting connections between logic and complexity. Papadimitriou and Yannakakis discovered that Fagin's characterization can be adapted to deal with optimization problems. They defined classes of approximation problems according to their syntactical characterization [PY91]. The importance of this approach comes from the fact that approximation properties of the optimization problems can be derived from their characterization in terms of logical quantifiers. Papadimitriou and Yannakakis defined the complexity classes MaxSNP and MaxNP which contain optimization versions of many important NP problems. They showed that many MaxSNP problems are in fact complete for the class. The paradigmatic MaxSNP-complete problem is Maximum 3SAT. Recall that the Maximum 3SAT problem consists in, given a boolean formula F written in conjunctive normal form with three literals in each clause, finding a truth assignment that satisfies the maximum number of clauses.

In the previous chapter, we gave a brief introduction to the topic of parallel approximability. We keep the discussion at an intuitive level, trying to give the feeling of the main ideas behind parallel approximability. In this chapter, we are going to review in a more formal setting the basic definitions about PRAM computations and approximation that we shall use through the text. We will also introduce the tools and notation needed. In any case, this chapter will not be a deep study of these topics. There exists a large body of literature for the reader who wishes to go further in the theory of PRAM computation, among others the books by Akl [Akl89], Gibbons and Rytter [GR88], Reif [Rei93] and JáJá [JaJ92]. There are also excellent short surveys on this topic, we just mention the one by Karp and Ramachandran [KR90] and the collection of surveys from the ALCOM school in Warwick [GS93]. In a similar way, many survey papers and lecture notes have been written on the topic of approximability, among others the Doctoral Dissertation of V. Kann [Kan92] with a recent update on the appendix of problems [CK95], the lecture notes of R. Motwani [Mot92], the survey by Ausiello et al. [ACP96] which includes a survey of non-approximability methods, the recent book edited by Hochbaum [Hoc96] and a forthcoming book by Ausiello et al. [ACG+96]

The PRAM Model of Computation

We begin this section by giving a formal introduction to our basic model of computation, the Parallel Random Access Machine. A PRAM consists of a number of sequential processors, each with its own memory, working synchronously and communicating between themselves through a common shared memory.

Introduction

In this chapter the main results of the thesis are summarised. The extent to which these address the problems facing performance analysis, identified in Section 2.4, is assessed. In Section 9.4, the direction for further work and future development of PEPA, as it appeared at the end of the thesis, are discussed. The chapter concludes with a review of work which has been developed since the thesis was completed, particularly examining the extent to which the areas outlined in Section 9.4 have been addressed.

Summary

A compositional approach to performance modelling has been presented. This novel model construction technique, based on the stochastic process algebra PEPA, has been shown to be suitable for specifying a Markov process. This underlying process can subsequently be solved using any appropriate numerical technique. The ease with which models can be constructed and modified using PEPA was demonstrated in the case studies presented in Chapter 4. For example, when the effect of a faulty component was to be investigated, only the relevant component within the model had to be modified.

As outlined in Section 3.6, one of the major advantages of PEPA over the standard paradigms for specifying stochastic performance models is the inherent apparatus for reasoning about the structure and behaviour of models. In the later chapters of the thesis this apparatus has been exploited to define four equivalence relations over PEPA components. Each of these notions of equivalence has intrinsic interest from a process algebra perspective.

Introduction

In this chapter we develop a strong bisimulation, based on the labelled multi-transition system for PEPA developed in Chapter 3, and examine some of its properties. The strong bisimulation relation aims to capture the idea that strongly bisimilar components are able to perform the same activities, resulting in derivatives that are themselves strongly bisimilar. In Section 7.2 we show how this property may be expressed in the definition of a strong bisimulation relation. Strong bisimilarity is then defined as the largest relation satisfying the conditions of a strong bisimulation relation.

The rest of the chapter is concerned with the properties exhibited by the strong bisimilarity relation, ∼. In Section 7.3 the relation is investigated from a process algebra perspective. In particular it is shown that strong bisimilarity is a congruence relation for PEPA. The implications of strong bisimilarity for the system components being modelled are discussed in Section 7.4. The relationship between strong bisimilarity and the underlying Markov process is examined in Section 7.5, as we investigate whether the partition induced by the relation forms a suitable basis for exact aggregation. This is found not to be the case.

Finally in Section 7.6 we suggest how strong bisimilarity may be used as a model simplification technique. The relation is used to find components which exhibit the same activities. These may then be subjected to a simple further test to ensure that the behaviours of the components are indeed the same.

Commit protocols are used for concurrency control in distributed data bases. Thus they belong to the application layer. For an introduction to this area we recommend the book by Bernstein et al. [BHG87, Chapter 7].

If a data base is distributed over several sites, it is very possible that a data base operation which is logically a single action in fact involves more than one site of the data base. For example, consider the transfer of a sum of money sm from one bank account to another. The balance of the first bank account has to be decreased by sm, while the balance of the second has to be increased by sm. These two subactions might have to take place at different sites. It is imperative that both subactions are executed, and not one. If it is not possible to execute one of them, e.g. because its site is temporarily down, they should both be not executed.

In data base management such a logically single action is called a transaction, and it should behave as if it is an atomic action. At some point in the execution of the transaction it has to be decided whether the transaction is (going to be) executed as a whole and will never be revoked (commit), or that the transaction cannot be completed, and parts already done will be undone (abort). In general, an algorithm to ensure that the transaction can be viewed as an atomic action is called an atomic commitment protocol. Thus all processes participating in an atomic commitment protocol have to reach agreement upon whether to commit or to abort the transaction under consideration.

A basic problem that must be addressed in any design of a distributed network is the routing of messages. That is, if a node in the network wants to send a message to some other node in the network or receives a message destined for some other node, a method is needed to enable the node to decide over which outgoing link it has to send this message. Algorithms for this problem are called routing algorithms. In the sequel we will only consider distributed routing algorithms which are determined by the cooperative behavior of the local routing protocols of the nodes in order to guarantee effective message handling and delivery.

Desirable properties of routing algorithms are for example correctness, optimality, and robustness. Correctness seems easy to achieve in a static network, but the problem is far less trivial in case links and nodes are allowed to go down and come up as they can do in practice. Optimality is concerned with finding the “quickest” routes. Ideally, a route should be chosen for a message on which it will encounter the least delay but, as this depends on the amount of traffic on the way, such routes are hard to predict and hence the goal is actually difficult to achieve. A frequent compromise is to minimize the number of hops, i.e., the number of links over which the message travels from origin to destination. We will restrict ourselves to minimum-hop routing. Robustness is concerned with the ease with which the routing scheme is adapted in case of topological changes.

Introduction

This chapter presents the background material for the thesis. The field of performance modelling is introduced and the standard paradigms for specifying stochastic performance models, queueing networks and stochastic Petri nets, are reviewed. In Section 2.3 process algebras are introduced, and some of the extensions into timed and probabilistic processes are considered in the following subsections. In particular we describe the Calculus of Communicating Systems (CCS), and various extended calculi based upon it.

We present the motivation for applying process algebras to performance modelling in Section 2.4. This outlines the objectives of the work presented in the remainder of the thesis. Finally, in Section 2.5, some related work, involving process algebras and performance evaluation, is discussed.

Performance Modelling

Performance evaluation is concerned with the description, analysis and optimisation of the dynamic behaviour of computer and communication systems. This involves the investigation of the flow of data, and control information, within and between components of a system. The aim is to understand the behaviour of the system and identify the aspects of the system which are sensitive from a performance point of view.

In performance modelling an abstract representation, or model, of the system is used to capture the essential characteristics of the system so that its performance can be reproduced. A performance study will address some objective, usually investigating several alternatives— these are represented by values given to the parameters of the model.

Originally, the research reported in this book was motivated by the way the material used for an introductory course on Distributed Computing (taught in the spring of 1985) was presented in the literature. The teacher of the course, Jan van Leeuwen, and I felt that many results were presented in a way that needed clarifying, and that correctness proofs, if existent, were often far from convincing, if correct at all. Thus we started to develop correctness proofs for some distributed protocols. Gradually a methodology emerged for such proofs, based on the idea of “protocol skeletons” and “system-wide invariants”. Similar ideas were developed by others in the context of formal proof systems for parallel and distributed programs.

I thank the ESPRIT Basic Research Action No. 7141 (project ALCOM II: Algorithms and Complexity), the Netherlands Organization for Scienctific Research (NWO) under contract NF 62-376 (NFI project ALADDIN: Algorithmic Aspects of Parallel and Distributed Systems), and the Department of Computer Science at Utrecht University for giving me the opportunity to do research on this topic, and for providing such a stimulating environment. I thank my coauthors Jan van Leeuwen, Hans Bodlaender, and Gerard Tel, and also Petra van Haaften, Hans Zantema, and Netty van Gasteren for all the discussions we had.

Later the idea came up to write a thesis about this subject, and I especially thank my thesis advisor Jan van Leeuwen for his stimulating support. The first four chapters of the thesis served as preliminary versions for the first four chapters of this book, while chapter 5 on commit protocols was added later.

Performance modelling is concerned with the capture and analysis of the dynamic behaviour of computer and communication systems. The size and complexity of many modern systems result in large, complex models. A compositional approach decomposes the system into subsystems that are smaller and more easily modelled. In this thesis a novel compositional approach to performance modelling is presented. This chapter presents an overview of the thesis. The major results are identified.

A significant contribution is the approach itself. It is based on a suitably enhanced process algebra, PEPA (Performance Evaluation Process Algebra). As this represents a new departure for performance modelling, some background material and definitions are provided in Chapter 2 before PEPA is presented. The chapter includes the motivations for applying process algebras to performance modelling, based on three perceived problems of performance evaluation. The recent developments of timed and probabilistic process algebras are unsuitable for performance modelling. PEPA, and related work on TIPP [1], represent a new area of work, stochastic process algebras [2]. The extent to which work on PEPA attempts to address the identified problems of performance evaluation is explained. The chapter concludes with a brief review of TIPP and other related work.

Chapter 3 presents PEPA in detail. The modifications which have been made to the language to make it suitable for performance modelling are explained. An operational semantics for PEPA is given and its use to generate a continuous time Markov process for any PEPA model is explained.

Introduction

In this chapter we develop a framework to analyse notions of equivalence between models. Within this framework we present several equivalences which have been applied to process algebra models and performance models. By notions of equivalence we mean criteria which may be applied to determine whether two entities can be considered to be, in some sense, the same. For example, a common concern for most modelling methodologies is model verification—the problem of ascertaining whether a model is the same as the system under study, in the sense of providing an adequate representation to meet the objectives of the study. For a performance model “adequate representation” is usually interpreted as the calculation of certain quantitative performance characteristics within acceptable error bounds. For a process algebra model it is interpreted as a condition on the observable behaviour of the model, as represented by its actions, compared with the observable or intended behaviour of the system.

The framework we consider identifies three different classes of entity-to-entity equivalence which may arise during a modelling study: system-to-model equivalence, model-to-model equivalence and state-to-state equivalence. We will see that for process algebra models these equivalences are all addressed by a single notion of equivalence, the bisimulation. Two agents are considered to be equivalent in this way when their externally observed behaviour appears to be the same. This is a formally defined notion of equivalence, based on the labelled transition system underlying the process algebra.