Summary of QMIPS deliverables

• by pattern search
• by going directly to the deliverable: D1 D2a D2b D3 D4 D5 D6 D8 D9 D10 D11 D12 D13 D14 D16a D16b D17 D18 D19 D22 D23

Deliverable 1

State-of-the-art on model classification

• Chapter 1: Stochastic Petri Nets
• Chapter 2: Stochastic Process Algebras and Logic
• Chapter 3: Stochastic Graph Models
• Chapter 4: Recurrence Equations
• Chapter 5: Evaluation Techniques
• Chapter 6: Workload and Architecture

• Preamble
  • Outer titlepage
  • Inner titlepage
  • Table of Contents
  • Brief Introduction and List of Participants
  • Initial Call for Contributions (Guidelines)
  • Proposal of INR for the Classification of Performance Evaluation Models of Parallel and Distributed Systems
  • Workshop Program

  ---

• Chapter 1: Stochastic Petri Nets
  • Titlepage
  • The Timed (Coloured) Petri-Net Formalism: position paper (QMIPS groups in UTO+ZAR)
  • (Coloured) GSPN Models of the UTO1 Example (R. Gaeta)
  • SWN Models of the UTO2 Example (C. Anglano, G. Chiola)
  • Stochastic Well Formed Model of the UTO3 Example (M. Ribaudo)

  ---

• Chapter 2: Stochastic Process Algebras and Logic
  • Titlepage
  • Multiprocessor and Distributed System Design: The Integration of Functional Specification and Performance Analysis Using Stochastic Process Algebras (N. Gotz, U. Herzog, M. Rettelbach)
  • Process Algebra for Discrete Event Simulation (P.G. Harrison, B. Strulo)
  • Temporal Logic in a Stochastic Environment (B. Strulo, P.G. Harrison, D. Gabbay)

  ---

• Chapter 3: Stochastic Graph Models
  • Titlepage
  • A Survey on Solution Methods for Task Graph Models (F. Baccelli, A. Jean-Marie, Z. Liu)
  • A QMIPS Significant Example: Multiprocessor Performance with Task Graph Models (E. Gelenbe)
  • Stochastic Graph Models for Performance Evaluation of Parallel Programs and the Evaluation Tool PEPP (F. Hartleb)

  ---

• Chapter 4: Recurrence Equations
  • Titlepage
  • Using Stochastic Recursive Equations as a Tool for Modeling and Performance Evaluation of Parallel Processing Systems (F. Baccelli, A. Jean-Marie, Z. Liu)

  ---

• Chapter 5: Evaluation Techniques
  • Titlepage
  • Application and Evaluation of the Spectral Expansion Solution Method (I. Mitrani, R. Chakka)

  ---

• Chapter 6: Workload and Architecture
  • Titlepage
  • Optimization of Static Traffic Allocation Policies (M.B. Combe, O.J. Boxma)
  • Load Balancing Pragmatics (E. Gelenbe, F. Pekergin)

Deliverable D2a

Interleaving semantics for timed process algebras: motivation and semantics models

Deliverable D2b

Integral Specification of Functional Properties and Performance Evaluation by Stochastic Process Algebra

Contents of the Deliverable

D2b-1

Stochastic Process Algebras - Constructive Specification Techniques Integrating Functional, Performance and Dependability Aspects, N. Götz, H. Hermanns, U. Herzog, V. Mertsiotakis and M. Rettelbach (included in the QMIPS book).

D2b-2

A Stochastic Process Algebra Based Modelling Tool, H. Hermanns and V. Mertsiotakis (presented at the UK Performance Engeneering Workshop 1995 and enclosed).

D2b-3

Exploiting Quasi-Reversible Structures to Find Product Form Solutions in Markovian Process Algebra Models, P. Harrison and J. Hillston (presented at the Workshop on Process Algebras and Performance Modelling 1995 PAPM'95 and enclosed). (Front page)

D2b-4

Formal Characterisation of Immediate Actions in SPA with Nondeterministic Branching, H. Hermanns, M. Rettelbach and T. Weiß(presented at PAPM'95 and enclosed).

D2b-5

Probabilistic Branching in Markovian Process Algebras, M. Rettelbach (presented at PAPM'95 and enclosed).

Deliverable D3

Timed and Stochastic Temporal Logic Models

Contents of the Deliverable

D3-1

Temporal Logic in a Stochastic Environment, by B. Strulo, D.M. Gabbay and P.G. Harrison, (Front page).

D3-2

Performance Prediction of Behavioural Descriptions with Temporal Logics, by Holger Hermanns.

Deliverable D4

Characteristic Equations for the Different Modeling Techniques

Front Page

Model Properties and Simplifications (p. 1)

Introduction and Summary (p. 2)

Table of Contents (p. 4)

Part 1

Immediate Transitions in Parametric Stochastic Petri Nets (p. 5)

Part 2

Structural, Temporal and Stochastic Properties of Unbounded Free-Choice Petri Nets (p. 33 and following)

Part 3

Characteristic Equations for Markovian TIPP (p. 72)

Part 4

Understanding Stochastic Process Algebra via their Stochastic Petri Nets Semantics (p. 86)

Deliverable D5

Analysis of 2-dimensional Markov Chains and Random Walks

D5-1

On a Class of Two-Dimensional Nearest Neighbouring Random Walks, J.W. Cohen. (front page).

D5-2

The Compensation Approach Applied to a 2x2 Switch, O.J. Boxma and G.J. van Houtum. (front page).

D5-3

Heterogeneous Multiprocessor Systems with Breakdowns: Performance and Optimal Repair Strategies, Ram Chakka and Isi Mitrani. (front page).

D5-4

Spectral Expansion Solution for a Class of Markov Models: Application and Comparison with the Matrix-Geometric Method, Isi Mitrani and Ram Chakka. (front page).

D5-5

Routing in the Presence of Breakdowns, Isi Mitrani and Paul E. Wright. (front page).

Deliverable D6

State of the Art in the Theory and Applications of Queueing Networks with Negative and Positive Customers

D6-1

``G-Networks with multiple class of negative and positive customers'', J.M. Fourneau, E. Gelenbe and R. Suros.

D6-2

``Response Time Distributions in Tandem G-Networks'', P.G. Harrison and E. Pitel. (front page)

D6-3

``The M/G/1 Queue with Negative Customers'', P. G. Harrison and E. Pitel. (front page)

Deliverable D8

Parallel Evaluation of Large Scale Models

Contents of the Deliverable

D8-1

Parallel and Distributed Simulation of Free Choice Petri Nets, by François Baccelli, Nathalie Furmento and Bruno Gaujal (also: deliverable D16b-2).

D8-2

``An asymptotic analysis of closed queueing networks with branching populations'', by N. Bayer, E.G. Coffman, Jr. and Y. Kogan. CWI report #BS-R952x, September 1995, Amsterdam (front page).

Deliverable D9

Fixed-Point Methods

Contents of the Deliverable

D9-1

Modelling and Evaluation of Cache Coherence Protocols in Multiprocessor Systems, by E. Ametistova and I. Mitrani (front page).

D9-2

A Uniform-Memory Access Model of a Distributed Coherent Cache System, by A.J. Field, P.G. Harrison and N. Lehovetsky (front page).

Deliverable D10

Interconnection Networks

Contents of the Deliverable

D10-1

An approximate analysis of asynchronous, packet-switched, buffered Banyan networks with blocking, P.G. Harrison, A. de C. Pinto. Performance Evaluation Journal, 1994 (front page).

D10-2

Response time distributions in packet-switched banyan networks, P.G. Harrison, A. de C. Pinto. In Proc. 2nd Workshop on Performance Modelling and Evaluation of ATM Networks, Bradford, July 1994 (front page). Report included with deliverable D11.

D10-3

A Uniform-memory Access Model of a Distributed Coherent Cache System, A.J. Field, P.G. Harrison, N. Lehovetski. In Proc. 10th UK Performance Engineering Workshop, Edinburgh, September 1994 (front page). . Report in proceedings of the QMIPS London Workshop, deliverable D20. Also in deliverable D9.

D10-4

Transmission times in buffered full crossbar communication networks with cyclic arbitration, A.J. Field, P.G. Harrison. In Proc Int. Conf. on Parallel Processing, St. Charles, Illinois, USA, 1993 (front page). Report included with deliverable D11.

D10-5

On the determination of the stationary distribution of a symmetric clocked buffered switch, J.W. Cohen. CWI Research Report BS-R9427, July 1994 (front page).

Deliverable D11

Distribution of Transmission Times in Queueing Networks

Contents of the Deliverable

• Switches and networks
• Negative customers
• Special queues
• Surveys

Switches and networks

D11-01

Tandem queues with deterministic service times, O.J. Boxma, J.A.C. Resing. Annals of Operations Research 49 (1994), 221-239 (front page).

D11-02

On the analysis of the symmetrical shortest queue, J.W. Cohen. CWI Report BS-R9420, May 1994 (front page).

D11-03

Waiting time distribution in a class of wireless multi-channel local area networks, S. Coury, P.G. Harrison. In Proc. International Conference on Local and Metropolitan Communication Systems, Kyoto, Japan, December 1994 (front page).

D11-04

Transmission times in buffered full crossbar communication networks with cyclic arbitration, A.J. Field, P.G. Harrison. In Proc. Int. Conf. on Parallel Processing, St. Charles, Illinois, USA, 1993 (front page).

D11-05

Response time distributions in packet-switched banyan networks, P.G. Harrison, A. de C. Pinto. In Proc. 2nd Int. Workshop on Performance Modelling and Evaluation of ATM Networks, Bradford, July 1994 (front page).

D11-06

On the power series algorithm, G.M. Koole. In Proc. 3rd QMIPS workshop: Performance Evaluation of Parallel and Distributed Systems, eds. O.J. Boxma and G.M. Koole, CWI Tract 105, 1994, pp. 139-155 (front page).

Negative customers

D11-07

Sojourn times in single-server queues with negative customers, P.G. Harrison, E. Pitel. Journal of Applied Probability 30 (1993), 943-963 (front page).

D11-08

Response time distributions in tandem G-networks, P.G. Harrison, E. Pitel. Journal of Applied Probability 32 (1995), to appear (front page).

Special queues

D11-09

Response times in two-headed queues, P.G. Harrison, A.J. Field. Draft report (front page).

D11-10

Response times in two random queues, A.J. Field, P.G. Harrison. Very drafty report (front page).

Surveys

D11-11

Queueing-theoretic solution methods for models of parallel and distributed systems, O.J. Boxma, G.M. Koole, Z. Liu. In Proc. 3rd QMIPS workshop: Performance Evaluation of Parallel and Distributed Systems, eds. O.J. Boxma and G.M. Koole, CWI Tract 105, 1994, pp. 1-24 (front page).

D11-12

Response time distributions in queueing network models , P.G. Harrison. In Performance Analysis of Computer and Communication Systems, eds. L. Donatielli and R.D. Nelson, Springer, New York, 1993, pp. 147-164.

Deliverable D12

Bounds for Networks

Contents of the Deliverable

D12-1

Chapter 3 of the Proceedings of the INRIA-Sophia Antipolis Qmips Workshop on Stochastic Petri Nets, INRIA Internal Publication, November 1992.

• Structural Techniques and Performance Bounds for Stochastic Petri Net Models, J. Campos and M. Silva.
• Approximation Techniques for Stochastic Macroplace/Macrotransition Nets, H. Jungnitz, A. Desrochers and M. Silva.
• Comparison Properties of Stochastic Decision Free Petri Nets, F. Baccelli and Z. Liu.

D12-2

Operational Analysis of Timed Petri Nets and Application to the Computation of Performance Bounds, G. Chiola, C. Anglano, J. Campos, J.M. Colom and M. Silva (front page). To appear in the Proceedings of the Torino Qmips Workshop on Solution Methods, CWI Internal Publication, 1993.

D12-3

Computing bounds for the performance indices of quasi-lumpable Stochastic Well-Formed Nets, G. Franceschinis and R. R. Muntz (front page). To appear in the Proceedings of the Torino Qmips Workshop on Solution Methods, CWI Internal Publication, 1993.

D12-4

Analytical Computation of Lyapunov Exponents in Stochastic Event Graphs, Alain Jean-Marie. To appear in the Proceedings of the Torino Qmips Workshop on Solution Methods, CWI Internal Publication, 1993.

D12-5

On the Saturation Rule for the Stability of Queues/ On the Stability of Jackson Queueing Networks, F. Baccelli and S. Foss, INRIA Reports No. 1945 and 2015 (front page). To appear in the Proceedings of the Torino Qmips Workshop on Solution Methods, CWI Internal Publication, 1993.

Deliverable D13

Markovian analysis of symmetric CGSPNs

Contents of the Deliverable

Chapter 1

(p. 1) SWN Definition

Chapter 2

(p. 27) Symmetries and Markovian Analysis

Chapter 3

(p. 32) Bounds for Quasi-Lumpable Nets

Chapter 4

(p. 55) Structural Decolorization

Chapter 5

(p. 72) Tool Support

Chapter 6

(p. 85) Applications to Parallel Computer Architectures

Deliverable D14

Approximation Techniques in Stochastic Petri Nets

Contents of the Deliverable

D14-1

Approximation Techniques for Stochastic Macroplace/Macrotransition Nets, by H. Jungnitz, A. Desrochers and M. Silva.

In chapter 3 of the Proceedings of the Sophia-Antipolis Workshop on Stochastic Petri Nets.

D14-2

A Survey on Solution Methods for Task Graph Models, by F. Baccelli, A. Jean-Marie and Z. Liu.

In chapter 3 of the Proceedings of the Erlangen Workshop on Formalisms (D 1).

D14-3

Approximate Throughput Computation of Stochastic Marked Graphs, by J. Campos, J.M. Colom, H. Jungnitz, and M. Silva (front page).

In the Proceedings of the Torino Workshop on Solution Methods. This paper appears in the IEEE Transactions on Software Engineering,vol. 20, no. 7, pp. 526-535, July 1994.

D14-4

Approximate Performance Analysis on Petri Net Based Models of Manufacturing Systems, by M. Tilgner and M. Silva (front page).

This paper appears in Proceedings of the 1994 IEEE International Conference on Robotics and Automation, San Diego, California, May 1994.

Deliverable D16a

Distributed and Parallel Simulation of Networks

Contents of the Deliverable

D16a-1

Chapter 4 of the Proceedings of the Sophia-Antipolis Workshop on Stochastic Petri Nets.

D16a-2

Marking Optimization and Parallelism of Marked Graphs, Miguel Canales and Bruno Gaujal, INRIA Report RR 2049, presented at the Torino Qmips Workshop on Solution Methods, 1993.

Deliverable D16b

Distributed and Parallel Simulation of Networks

Contents of the Deliverable

D16b-1

Parallel and Distributed Simulation of Free Choice Petri Nets, by François Baccelli, Nathalie Furmento and Bruno Gaujal. This paper appears in the proceedings of PADS'95, Lake Placid, June 1995

D16b-2

Some Algebraic Considerations for Efficient Computations in Timed Petri Nets, by Bruno Gaujal. This paper will appear in the proceedings of HICSS-29, Hawaii, Jan 96.

D16b-3

Minimal Representation of Uniform Recurrence Equations, by Bruno Gaujal, Alain Jean-Marie and Jean Mairesse. This paper appears as INRIA Research Report #2568, June 1995.

Deliverable D17

Task Graph Parametrisation

Contents of the Deliverable

D17-1

Characterization, Approximate Analysis and Simulation of Task Graph Models Representing the Dependable Execution of Parallel and Distributed Programs, Erol Gelenbe and Sophie Chabridon.

Deliverable D18

State of the Art and Advances in Load Balancing

Contents of the Deliverable

D18-1

Routing Among Different Nodes Where Servers Break Down Without Losing Jobs, by Nigel Thomas and Isi Mitrani. Procs., IPDS'95, Erlangen, 1995 (front page). Also in Quantitative Methods in Parallel Systems, eds. F. Baccelli, A. Jean-Marie and I. Mitrani, Springer, Berlin, 1995. Report included.

D18-2

Optimization of static traffic allocation policies, M.B. Combe and O.J. Boxma. This paper appears in Chapter 6 of the proceedings of the Erlangen Workshop (Deliverable D1).

D18-3

Static Optimization of Queueing Systems, by O.J. Boxma. CWI Report BS-R9506, February 1995, Amsterdam; to appear in R.P. Agarwal (ed.), Recent Trends in Optimization Theory and Applications. Report included (front page).

D18-4

Failure detection algorithms for a reliable execution of parallel programs, by S. Chabridon and E. Gelenbe. 14th Symposium on Reliable Distributed Systems (SRDS-14), Bad Neuenahr, September 13-15, 1995, pp.229-238. Report included.

D18-5

Approximate Solution Methods for Open Queueing Networks with Breakdowns and Repairs, by R. Chakka and I. Mitrani. Stochastic Networks Workshop, Edinburgh, 1995; to appear in the book edited by S. Zachary and F. Kelly. Report included (front page).

Deliverable D19

Communications in Parallel and Distributed Systems

Contents of the Deliverable

D19-1

Communications in parallel and distributed systems: a survey, A. Jean-Marie, P. Mussi and M. Syska.

D19-2

Polling systems, O.J. Boxma. In: From Universal Morphisms to Megabytes: a Baayen Space Odyssey, eds. K.R. Apt, A. Schrijver and N.M. Temme (CWI, Amsterdam, december 1994), pp. 215-230. (front page).

D19-3

Polling models with threshold switching, O.J. Boxma, G.M. Koole, I. Mitrani. In part II of Quantitative Models in Parallel Systems. In Quantitative Methods in Parallel Systems, eds. F. Baccelli and I. Mitrani, Springer, Berlin, 1995. Part of this work appears in Proc. MASCOTS '95, eds. P. Dowd and E. Gelenbe, IEEE Computer Society Press, Los Alamitos (CA), 1995, pp. 84-89.

D19-4

A polling model with threshold switching, D.G. Down, O.J. Boxma. In Proceedings NTS-12 Conference, Otaniemi, Espoo, Finland, August 22-24, 1995. (front page).

D19-5

Polling models with and without switchover times, S.C. Borst and O. Boxma. CWI Report BS-R9421, to appear in Oper. Res.. (front page).

D19-6

The use of service limits for efficient operation of multi-station single-medium communication systems, S.C. Borst, O. Boxma and H. Levy. To appear in IEEE Trans. Networking, October 1995. (front page).

Deliverable D22

Performance engineering for parallel computation

Contents of the Deliverable

D22-1

``Requirements for a Modeling and Performance Evaluation Software Environment'', G. Balbo, G. Chiola and A. Jean-Marie.

Deliverable D23

The Extra Deliverable

Contents of the Deliverable

Complements to D5: Analysis of 2-dimensional Markov Chains and Random Walks

D5-6

``On the role of Rouché's theorem in queueing analysis'', J.W. Cohen and D.G. Down. (Front page). CWI Report BS-R9523, August 1995, Amsterdam. Report included.

D5-7

``On the symmetrical shortest queue and the compensation approach'', J.W. Cohen. (Front page). CWI Report BS-R9519, July 1995, Amsterdam. Report included.

D5-8

``Two-dimensional nearest-neighbour queueing models, a review and an example'', J.W. Cohen. CWI Report BS-R9519, July 1995, Amsterdam. In Quantitative Methods in Parallel Systems, eds. F. Baccelli, A. Jean-Marie and I. Mitrani, Springer, Berlin, 1995.

Complements to D6: State-of-the-Art in the Theory and Application of Queueing Networks with Negative and Positive Customers

D6-4

``G-Networks with Multiple Classes of Positive Customers, Negative Customers and Triggers'', Erol Gelenbe and Ali Labed. Technical Report EHE, October 1995. Report included.

D6-5

``On the identification of Wiener-Hopf factors'', N. Bayer. (Front page). CWI Note BS-N950x, September 1995. Report included.

D6-6

``Wiener-Hopf analysis of an M/G/1 queue with negative customers and of a related class of random walks'', N. Bayer and O.J. Boxma. (Front page). CWI Report BS-R952y, September 1995, Amsterdam. Report included.

D6-7

``The workload in the M/G/1 queue with work removal'', R.J. Boucherie and O.J. Boxma. (Front page). CWI Report BS-R9505, February 1995, Amsterdam; accepted for publication in Probability in the Engineering and Informational Sciences. Report included.

D6-8

``G-networks: A Survey of Results, Applications and Solutions'', S. Chabridon, E. Gelenbe, M. Hernández and A. Labed. In Quantitative Methods in Parallel Systems, eds. F. Baccelli, A. Jean-Marie and I. Mitrani, Springer, Berlin, 1995.

Complements to D14: Approximation Techniques in Stochastic Petri Nets

D14-5

``Response Time Approximation for Decision-Free TIPP Specifications'', V. Mertsiotakis and M. Silva. (Front page). Report included.