+612 9045 4394
On a Method of Multiprogramming : Monographs in Computer Science - W.H.J. Feijen

On a Method of Multiprogramming

Monographs in Computer Science

Hardcover Published: 11th June 1999
ISBN: 9780387988702
Number Of Pages: 370

Share This Book:


RRP $571.99
or 4 easy payments of $99.06 with Learn more
Ships in 7 to 10 business days

Other Available Editions (Hide)

  • Paperback View Product Published: 1st December 2010

Among all the interests in parallelism, there is an essential and fundamental one that has remained largely unexplored, namely the question of how to design parallel programs from their specification. And that is what this book is about. It proposes a method for the formal development of parallel programs - multiprograms as we have preferred to call them -, and it does so with a minimum of formal gear, viz. with the predicate calculus and with the meanwhile well-established theory of Owicki and Gries. The fact that one can get away with just this theory will probably not convey anything to the uninitiated, but it may all the more come as a surprise to those who were exposed earlier to correctness of multiprograms. Contrary to common belief, the Owicki/Gries theory can indeed be effectively put to work for the formal development of multiprograms, regardless of whether these algorithms are distributed or not. That is what we intend to exemplify with this book.

Forewordp. vii
Prefacep. xi
On Our Computational Modelp. 1
Our Program Notation and Its Semanticsp. 7
The notationp. 7
Hoare-triples and the wlpp. 9
Properties of Hoare-triples and the wlpp. 10
Definition of the wlp'sp. 11
The skip, the assignment, and the compositionp. 12
The alternative constructp. 14
The repetitive constructp. 18
On our choice of formalismp. 19
The Core of the Owicki/Gries Theoryp. 23
Annotating a multiprogramp. 24
Two examplesp. 28
Postconditionsp. 32
Two Disturbing Divergencesp. 35
Bridling the Complexityp. 41
Private variables and orthogonalityp. 42
System Invariantsp. 45
Mutual Exclusionp. 50
Co-assertions and Strengthening the Annotationp. 55
Three Theorems and Two Examplesp. 61
Synchronization and Total Deadlockp. 75
Guarded Statementsp. 76
Progress issuesp. 77
Some examplesp. 80
Total Deadlockp. 82
More examplesp. 83
Individual Progress and the Multiboundp. 89
Concurrent Vector Writingp. 97
More Theorems and More Examplesp. 111
The Yellow Pagesp. 123
A Summaryp. 124
Predicate Calculusp. 124
Our computational modelp. 125
Annotationp. 125
The Core of the Owicki/Gries theoryp. 126
Variablesp. 127
Atomicityp. 127
Progressp. 128
Rules and Lemmatap. 129
Exercisesp. 130
The Safe Sluicep. 153
Peterson's Two-Component Mutual Exclusion Algorithmp. 163
Re-inventing a Great Ideap. 171
On Handshake Protocolsp. 177
Phase Synchronization for Two Machinesp. 187
The Parallel Linear Searchp. 201
The Initialization Protocolp. 207
Co-componentsp. 219
The Initialization Protocol Revisitedp. 229
The Non-Blocking Write Protocolp. 237
Mutual Inclusion and Synchronous Communicationp. 243
A Simple Election Algorithmp. 257
Peterson's General Mutual Exclusion Algorithmp. 265
Monitored Phase Synchronizationp. 281
Distributed Liberal Phase Synchronizationp. 287
Distributed Computation of a Spanning Treep. 299
Shmuel Safra's Termination Detection Algorithmp. 313
The Alternating Bit Protocolp. 333
Peterson's Mutual Exclusion Algorithm Revisitedp. 347
Epiloguep. 357
Referencesp. 361
Indexp. 367
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780387988702
ISBN-10: 038798870X
Series: Monographs in Computer Science
Audience: Professional
Format: Hardcover
Language: English
Number Of Pages: 370
Published: 11th June 1999
Publisher: Springer-Verlag New York Inc.
Country of Publication: US
Dimensions (cm): 24.77 x 16.51  x 2.54
Weight (kg): 0.68