The list of QMIPS Papers

This document lists the contents of all documents delivered during the QMIPS project: deliverables, workshop proceedings and other documents.

It has been established on 25 October 1995.

Deliverables
Workshops
Other Documents

Deliverables

Deliverable D1

Title: State-of-the-art on model classification (proceedings of the workshop on ``Formalisms'')
Workpackage/Task: WP1 T0
Participants: All partners involved
Responsible: UER

: Proposal of INR for the Classification of Performance Evaluation Models of Parallel and Distributed Systems, F. Baccelli, A. Jean-Marie and Z. Liu
: 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 and G. Chiola
: Stochastic Well Formed Model of the UTO3 Example, M. Ribaudo
: Multiprocessor and Distributed System Design: The Integration of Functional Specification and Performance Analysis Using Stochastic Process Algebras, N. Gotz, U. Herzog and M. Rettelbach
: Process Algebra for Discrete Event Simulation, P.G. Harrison and B. Strulo
: Temporal Logic in a Stochastic Environment, B. Strulo, P.G. Harrison and D. Gabbay,
: A Survey on Solution Methods for Task Graph Models, F. Baccelli, A. Jean-Marie and 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
: Using Stochastic Recursive Equations as a Tool for Modeling and Performance Evaluation of Parallel Processing Systems, F. Baccelli, A. Jean-Marie and Z. Liu
: Application and Evaluation of the Spectral Expansion Solution Method, I. Mitrani and R. Chakka
: Optimization of Static Traffic Allocation Policies, M.B. Combe and O.J. Boxma
: Load Balancing Pragmatics, E. Gelenbe and F. Pekergin

Deliverable D2a

Title: Interleaving semantics for timed process algebras: motivation and semantics models
Workpackage/Task: WP1 T1
Participants: IMP, IER
Responsible: UER

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

Deliverable D2b

Title: Integral specification of functional properties and performace evaluation by timed process algebra
Workpackage/Task: WP1 T1
Participants: IMP, UER
Responsible: UER

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
D2b-2: ``A Stochastic Process Algebra Based Modelling Tool'', H. Hermanns and V. Mertsiotakis
D2b-3: ``Exploiting Quasi-reversible Structures in Markovian Process Algebra Models'', P. Harrison and J. Hillston
D2b-4: `` Formal Characterisation of Immediate Actions in SPA with Nondeterministic Branching'', H. Hermanns, M. Rettelbach and T. Weiß
D2b-5: `` Probabilistic Branching in Markovian Process Algebras'', M. Rettelbach

Deliverable D3

Title: Timed and stochastic temporal logic models
Workpackage/Task: WP1 T1
Participants: IMP, UER
Responsible: IMP

D3-1: ``Temporal Logic in a Stochastic Environment'' B. Strulo, D. Gabbay and P.G. Harrison
D3-2: ``Performance Prediction of Behavioural Descriptions with Temporal Logics'' Holger Hermanns

Deliverable D4

Title: Characteristic equations for the different modelling techniques
Workpackage/Task: WP1 T2
Participants: INR, UER, UTO+Z
Responsible: UTO+Z

: Immediate Transitions in Parametric Stochastic Petri Nets, G. Chiola, S. Donatelli and G. Franceschinnis
: Structural, Temporal and Stochastic Properties of Unbounded Free-Choice Petri Nets, F. Baccelli, S. Foss and B. Gaujal
: Characteristic Equations for Markovian TIPP, H. Herrmanns and M. Rettelbach
: Understanding Stochastic Process Algebras via their Stochastic Petri Nets Semantics, M. Ribaudo

Deliverable D5

Analysis of 2-dimensional Markov chains and random walks WP2 T1 CWI, UNE CWI

D5-1: On a Class of Two-Dimensional Nearest Neighbouring Random Walks, J.W. Cohen
D5-2: The Compensation Approach Applied to a 2 x 2 Switch, O.J. Boxma and G.J. van Houtum
D5-3: Heterogeneous Multiprocessor Systems with Breakdowns: Performance and Optimal Repair Strategies, Ram Chakka and Isi Mitrani
D5-4: Spectral Expansion Solution for a Class of Markov Models: Application and Comparison with the Matrix-Geometric Method, Isi Mitrani and Ram Chakka
D5-5: Routing in the Presence of Breakdowns, Isi Mitrani and Paul E. Wright

Deliverable D6

Title: State-of-the-art in the theory and applications of queueing networks with negative and positive customers
Workpackage/Task: WP2 T1
Participants: EHE, IMP
Responsible: EHE

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
D6-3: The M/G/1 Queue with Negative Customers, P. G. Harrison and E. Pitel

Deliverable D7

Title: A solver of queueing networks with negative and positive customers
Workpackage/Task: WP2 T1
Participants: EHE
Responsible: EHE

D7-1: ``A solver tool for G-networks'' Chabridon, Labed, Hernández and Gelenbe

Deliverable D8

Title: Parallel evaluation of large-scale models
Workpackage/Task: WP2 T1
Participants: INR, UNE, UTO+Z
Responsible: UNE

D8-1: ``Parallel and Distributed Simulation of Free Choice Petri Nets'', by François Baccelli, Nathalie Furmento and Bruno Gaujal.
D8-2: ``An asymptotic analysis of closed queueing networks with branching populations'', N. Bayer, E.G. Coffman, Jr. and Y. Kogan,

Deliverable D9

Title: Approximation techniques based on fixed-point approximations
Workpackage/Task: WP2 T1
Participants: EHE, IMP, UNE
Responsible: UNE

D9-1: Modelling and Evaluation of Cache Coherence Protocols in Multiprocessor Systems, E. Ametistova and I. Mitrani
D9-2: A Uniform-Memory Access Model of a Distributed Coherent Cache System, A.J. Field, P.G. Harrison and N. Lehovetsky

Deliverable D10

Title: Performance of interconnection networks for parallel systems
Workpackage/Task: WP2 T1
Participants: IMP
Responsible: IMP

D10-1: An approximate analysis of asynchronous, packet-switched, buffered Banyan networks with blocking, P.G. Harrison, A. de C. Pinto, IMP
D10-2: Response time distributions in packet-switched banyan networks, P.G. Harrison and A. de C. Pinto, IMP
D10-3: A Uniform-memory Access Model of a Distributed Coherent Cache System, A.J. Field, P.G. Harrison and N. Lehovetski, IMP
D10-4: Transmission times in buffered full crossbar communication networks with cyclic arbitration, A.J. Field and P.G. Harrison, IMP
D10-5: On the determination of the stationary distribution of a symmetric clocked buffered switch, J.W. Cohen, CWI

Deliverable D11

Title: Distribution of transmission times in queueing networks
Workpackage/Task: WP2 T1
Participants: CWI, IMP
Responsible: IMP

D11-01: Tandem queues with deterministic service times, O.J. Boxma and J.A.C. Resing, CWI
D11-02: On the analysis of the symmetrical shortest queue, J.W. Cohen, CWI
D11-03: Waiting time distribution in a class of wireless multi-channel local area networks, S. Coury and P.G. Harrison IMP
D11-04: Transmission times in buffered full crossbar communication networks with cyclic arbitration, A.J. Field and P.G. Harrison IMP
D11-05: Response time distributions in packet-switched banyan networks, P.G. Harrison and A. de C. Pinto, IMP
D11-06: On the power series algorithm, G.M. Koole, CWI
D11-07: Sojourn times in single-server queues with negative customers, P.G. Harrison and E. Pitel, IMP
D11-08: Response time distributions in tandem G-networks, P.G. Harrison and E. Pitel, IMP
D11-09: Response times in two-headed queues, P.G. Harrison and A.J. Field, IMP
D11-10: Response times in two random queues, P.G. Harrison and A.J. Field, IMP
D11-11: Queueing-theoretic solution methods for models of parallel and distributed systems, O.J. Boxma, G.M. Koole and Z. Liu, CWI+INR
D11-12: Response time distributions in queueing network models, P.G. Harrison. IMP

Deliverable D12

Title: Bounds for networks
Workpackage/Task: WP2 T1-T2
Participants: INR, UTO+Z
Responsible: INR

D12-1

Structural Techniques and Performance Bounds for Stochastic Petri Net Models, J. Campos and M. Silva, ZAR

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

D12-3

Computing bounds for the performance indices of quasi-lumpable Stochastic Well-Formed Nets, G. Franceschinis and R. R. Muntz

D12-4

Analytical Computation of Lyapunov Exponents in Stochastic Event Graphs, Alain Jean-Marie

D12-5

On the Saturation Rule for the Stability of Queues/ On the Stability of Jackson Queueing Networks, F. Baccelli and S. Foss

Deliverable D13

Title: Markovian analysis of symmetric CGSPNs
Workpackage/Task: WP2 T2
Participants: UTO+Z
Responsible: UTO+Z

: Markovian analysis of symmetric CGSPNs: Symmetry Exploitation in Stochastic Well-Formed Colored Nets, G. Chiola, G. Franceschinis, R. Gaeta and M. Ribaudo

Deliverable D14

Title: Approximation techniques in stochastic Petri nets
Workpackage/Task: WP2 T2
Participants: INR, UTO+Z
Responsible: INR

D14-1: Approximation Techniques for Stochastic Macroplace/Macrotransition Nets, H. Jungnitz, A. Desrochers and M. Silva
D14-2: A Survey on Solution Methods for Task Graph Models, F. Baccelli, A. Jean-Marie and Z. Liu
D14-3: Approximate Throughput Computation of Stochastic Marked Graphs, J. Campos, J.M. Colom, H. Jungnitz, and M. Silva
D14-4: Approximate Performance Analysis on Petri Net Based Models of Manufacturing Systems, M. Tilgner and M. Silva

Deliverable D16a

Title: Distributed and parallel simulation of networks
Workpackage/Task: WP2 T3
Participants: INR, UNE, UTO+Z
Responsible: INR

D16a-1

Distributed Simulation of Timed Petri Nets, G. Chiola and A. Ferscha

Parallel simulation of Stochastic Petri Nets Using Recursive Equations, F. Baccelli and M. Canales

D16a-2

Marking Optimization and Parallelism of Marked Graphs, Miguel Canales and Bruno Gaujal

Deliverable D16b

Title: Distributed and parallel simulation of networks
Workpackage/Task: WP2 T3
Participants: INR, UNE, UTO+Z
Responsible: INR

D16b-1: ``Parallel and Distributed Simulation of Free Choice Petri Nets'', by François Baccelli, Nathalie Furmento and Bruno Gaujal.
D16b-2: ``Some Algebraic Considerations for Efficient Computations in Timed Petri Nets'', by Bruno Gaujal.
D16b-3: ``Minimal Representation of Uniform Recurrence Equations'', by Bruno Gaujal, Alain Jean-Marie and Jean Mairesse.

Deliverable D17

Title: Task graph parametrisation
Workpackage/Task: WP3 T1
Participants: EHE, IMP
Responsible: EHE

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, EHE

Deliverable D18

Title: State-of-the-art and advances in load balancing
Workpackage/Task: WP3 T2
Participants: CWI, EHE, INR
Responsible: CWI

D18-1: ``Routing among different nodes where servers break down without losing jobs'' N. Thomas and I. Mitrani
D18-2: ``Optimization of Static Traffic Allocation Policies'' M.B. Combe and O.J. Boxma
D18-3: ``Static optimization of queueing systems'', O.J. Boxma
D18-4: ``Failure detection algorithms for a reliable execution of parallel programs'', S. Chabridon and E. Gelenbe,
D18-5: ``Approximate Solution Methods for Open Queueing Networks with Breakdowns and Repairs'', R. Chakka and I. Mitrani

Deliverable D19

Title: Communication in parallel and distributed systems
Workpackage/Task: WP3 T2-T3
Participants: CWI, INR
Responsible: INR

D19-1: ``Communications in Multiprocessor Machines: A Survey'', Alain Jean-Marie, Philippe Mussi and Michel Syska
D19-2: ``Polling systems'', O.J. Boxma
D19-3: ``Polling models with threshold switching'', O.J. Boxma, G.M. Koole, I. Mitrani
D19-4: ``A polling model with threshold switching'', D.G. Down, O.J. Boxma
D19-5: ``Polling models with and without switchover times'', S.C. Borst and O. Boxma
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

Deliverable D20

Title: Scheduling issues
Workpackage/Task: WP3 T2
Participants: All Partners
Responsible: IMP

: Scheduling of Parallel Programs in Single-Bus Multiprocessor Systems, L. Finta and Z. Liu
: Regular Sequences and Applications in Cyclic Scheduling, B. Gaujal
: Assigning a Single Server to Inhomogeneous Queues with Switching Costs, G. Koole
: Optimal Probabilistic Allocation of Customer Types to Servers, S.C. Borst
: A Simulator for Task Assignment and Load Balancing in Presence of Failures, M. Hernández and J. Aguilar
: Strategies for Load Balancing in the Distributed Computation of Associative Operations, B. Gaujal, A. Jean-Marie and S. Mazeau
: Dependable Distributed Computing, S. Chabridon and E. Gelenbe
: Incremental Dynamic Load Balancing in Distributed Systems, E. Gelenbe and R. Kushwaha
: Routing Among Different Nodes Where Servers Break Down Without Losing Jobs, N. Thomas and I. Mitrani
: Cache Coherency in an SCI Ring, A.J. Field, P.G. Harrison and N. Lehovetski
: The M/G/1 Queue with Negative Customers, P.G. Harrison and E. Pitel

Deliverable D22

Title: Performance engineering for parallel computation
Workpackage/Task: WP3 T4
Participants: All Partners
Responsible: UTO

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

Deliverable D23

Title: The Extra Deliverable
Workpackage/Task: WP2 T1-2-3
Participants: CWI, EHE, UER, UNE, ZAR
Responsible: All Partners

D5-6: ``On the role of Rouché's theorem in queueing analysis'', J.W. Cohen and D.G. Down
D5-7: ``On the symmetrical shortest queue and the compensation approach'', J.W. Cohen
D5-8: ``Two-dimensional nearest-neighbour queueing models, a review and an example'', J.W. Cohen
D6-4: ``G-Networks with Multiple Classes of Positive Customers, Negative Customers and Triggers'', Erol Gelenbe and Ali Labed
D6-5: ``On the identification of Wiener-Hopf factors'', N. Bayer
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
D6-7: ``The workload in the M/G/1 queue with work removal'', R.J. Boucherie and O.J. Boxma
D6-8: ``G-networks: A Survey of Results, Applications and Solutions'', S. Chabridon, E. Gelenbe, M. Hernández and A. Labed.
D14-5: ``Response Time Approximation for Decision-Free TIPP Specifications'', V. Mertsiotakis and M. Silva

Workshops

Proceedings of the Sophia-Antipolis Workshop

Location: Sophia-Antipolis
Date: 11-13 November 1992
Topic: State-of-the-Art on Stochastic Petri Nets
Organizer: INRIA
Availability: INRIA publication, Centre de documentation, INRIA, BP 93, 2004 Route des Lucioles, F-06902 Sophia-Antipolis.

Chapter 1: Program of the Workshop

Chapter 2: Formalisms

Petri Nets and Queueing Networks. Similarities and Differences, by G. Chiola.
Recursive Equations for Stochastic Event Graphs, by F. Baccelli.
Timed Petri Nets, by M. Ajmone Marsan, G.Balbo A. Bobbio, G. Chiola, G. Conte, and A. Cumani.

Chapter 3: Computational Aspects

Structural Techniques and Performance Bounds for Stochastic Petri Nets Models, J. Campos, M. Silva.
Approximation Techniques for Stochastic Macroplace/Macrotransition Nets, Hauke Jungnitz, Alan Desrochers and Manuel Silva.
Comparison Properties of Stochastic Decision Free Petri Nets, by F. Baccelli and Z. Liu.
Superposed Stochastic Automata: a Class of Stochastic Petri Nets with Parallel Solution and Distributed State Space, by S. Donatelli.
On Efficient Markov Modelling by M. Siegle.

Chapter 4: Software Tools

Distributed Simulation of Timed Petri Nets, by G. Chiola and A. Ferscha.
Parallel Simulation of Stochastic Petri Nets Using Recursive Equations, by F. Baccelli and M. Canales.

Proceedings of the Erlangen Workshop

Location: Erlangen/Pommersfelden
Date: 17-19 March 1993
Topic: Formalisms: Principles and State-of-the-Art
Organizer: University of Erlangen
Availability: Arbeitsberichte des Instituts für Mathematische Maschinen und Datenferarbeitung (IMMD), Friedrich Alexander Universität Erlangen-Nürnberg. N. Götz, U. Herzog and M. Rettelbach (eds.). Band 26, Nummer 14, September 1994.

Preamble

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

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

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

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

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

Application and Evaluation of the Spectral Expansion Solution Method (I. Mitrani, R. Chakka)

Chapter 6: Workload and Architecture

Optimization of Static Traffic Allocation Policies (M.B. Combe, O.J. Boxma)
Load Balancing Pragmatics (E. Gelenbe, F. Pekergin)

Proceedings of the Torino Workshop

Location: Torino
Date: 25-26 September 1993
Topic: Solution Methods
Organizer: University of Torino and CWI
Availability: ``Performance Evaluation of Parallel and Distributed Systems: Solution Methods'', parts 1 and 2. CWI Tracts #105 and #106, O.J. Boxma and G.M. Koole (eds.), 1994.

Survey papers

Queueing-theoretic solution methods for models of parallel and distributed systems, O.J. Boxma, G.M. Koole & Z. Liu
Annotated bibliography on stochastic Petri nets, F. Baccelli, G. Balbo, R.J. Boucherie, J. Campos & G. Chiola

Queueing models

Applying spectral expansions in evaluating the performance of multiprocessor systems, M. Ettl & I. Mitrani
The compensation approach applied to a 2x2 switch, O.J. Boxma & G.J. van Houtum
Routing with breakdowns, I. Mitrani & P.E. Wright
G-networks with multiple class negative and positive customers, J.-M. Fourneau, E. Gelenbe & R. Suros
Response time distributions in tandem G-networks, P.G. Harrison & E. Pitel
On the power series algorithm, G.M. Koole

Petri net models

A structural characterisation of product form stochastic Petri nets, R.J. Boucherie & M. Sereno
Computational Algorithms for Product Form Solution Stochastic Petri Nets, M. Sereno & G. Balbo
Operational analysis of timed Petri nets and application to the computation of performance bounds, G. Chiola, C. Anglano, J. Campos, J.M. Colom & M. Silva
Computing bounds for the performance indices of quasi-lumpable stochastic well-formed nets, G. Franceschinis & R.R. Muntz
Functional and performance analysis of cooperating sequential processes, J. Campos, J.M. Colom, M. Silva & E. Teruel
Stationary regime and stability of free-choice Petri nets, F. Baccelli & B. Gaujal
A general iterative technique for approximate throughput computation of stochastic marked graphs, J. Campos, J.M. Colom, H. Jungnitz & M. Silva
Marking optimization and parallelism of marked graphs, M. Canales & B. Gaujal

The (Max,+) algebra

Analytical computation of Lyapunov exponents in stochastic event graphs, A. Jean-Marie
A graphical representation for matrices in the (Max,+) algebra, J. Mairesse

Proceedings of the London Workshop

Location: Imperial College, London
Date: 14-15 Avril 1994
Topic: Performance of Parallel Computer Systems
Organizer: Department of Computing, Imperial College
Availability: ``Proceedings of the 4th QMIPS Workshop on the Performance of Parallel Computer Systems'', P.G. Harrison and A.C. de Pinto (eds.), Research Report DoC 94/18, Department of Computing, Imperial College, October 1994.

Chapter 1: Optimization and Scheduling

Scheduling of Parallel Programs in Single-Bus Multiprocessor Systems, L. Finta and Z. Liu.
Regular Sequences and Applications in Cyclic Scheduling, B. Gaujal.
Assigning a Single Server to Inhomogeneous Queues with Switching Costs, G. Koole.
Optimal Probabilistic Allocation of Customer Types to Servers, S.C. Borst.

Chapter 2: Load Balancing

A Simulator for Task Assignment and Load Balancing in Presence of Failures, M. Hernández and J. Aguilar.
Strategies for Load Balancing in the Distributed Computation of Associative Operations, B. Gaujal, A. Jean-Marie and S. Mazeau.
Dependable Distributed Computing, S. Chabridon and E. Gelenbe.
Incremental Dynamic Load Balancing in Distributed Systems, E. Gelenbe and R. Kushwaha.

Chapter 3: Work in Progress

Routing Among Different Nodes Where Servers Break Down Without Losing Jobs, N. Thomas and I. Mitrani.
Cache Coherency in an SCI Ring, A.J. Field, P.G. Harrison and N. Lehovetski.
The M/G/1 Queue with Negative Customers, P.G. Harrison and E. Pitel.