Edsger Wybe Dijkstra : His Life, Work, and Legacy / Krzysztof R. Apt, Tony Hoare
- Author:
- Apt, Krzysztof R
- Published:
- [New York, NY, USA] : Association for Computing Machinery, [2022]
- Edition:
- First Edition.
- Physical Description:
- 1 PDF (xxiv, 550 pages) : LuaTEX
Access Online
- Abstract with links to full text: ezaccess.libraries.psu.edu
- Series:
- Restrictions on Access:
- Abstract freely available; full-text restricted to subscribers or individual document purchasers.
- Contents:
- Preface, Photo Credits, PART I INTRODUCTION, 1 The Humble Programmer, PART II TECHNICAL PERSPECTIVES ON DIJKSTRA'S WORK, 2 Dijkstra's Single Source Shortest Path Algorithm -- Mikkel Thorup -- 2.1 Dijkstra's Algorithm -- 2.2 Implementations -- 2.3 Dijkstra's SSSP and Beyond -- Acknowledgment -- References, 3 Programming Concurrent Systems -- Butler Lampson -- Abstract -- 3.1 Introduction -- 3.2 Concurrency -- 3.3 Why Concurrency? -- 3.4 Atomicity and Commuting -- 3.5 Taxonomy of Concurrency: Shard, Stream, or Struggle -- 3.6 Sharding -- 3.7 Streaming -- 3.8 Easy Concurrency -- 3.9 Hard Concurrency -- 3.10 Eventual Consistency -- 3.11 Nuisance Concurrency -- 3.12 Conclusion -- References, 4 Concurrent Algorithms -- Leslie Lamport -- 4.1 Introduction -- 4.2 Mutual Exclusion -- 4.3 Self-stabilization -- 4.4 On-the-fly Garbage Collection -- 4.5 Termination Detection -- 4.6 Conclusion -- References, 5 Origin of Self-Stabilization -- Ted Herman -- 5.1 Introduction -- 5.2 Privileges in a Ring -- 5.3 Privileges in an Array -- 5.4 Distance Convergence on a Circle -- 5.5 Complexity and Verification -- 5.6 Relevance -- 5.7 Adoption -- 5.8 Impact -- 5.9 Conclusions -- Acknowledgment -- References, 6 Dijkstra's Legacy on Program Verification -- Reiner Ha¿hnle -- 6.1 Dijkstra's View of Program Verification -- 6.2 The Weakest Precondition Calculus and Its Context -- 6.3 From Program Correctness to Program Certification -- 6.4 The Future of the Legacy -- Acknowledgment -- References, 7 Development of Correct Programs -- David Gries -- 7.1 Recurring Themes -- 7.2 What's a Proof? -- 7.3 Structured Programming, with Proof of Correctness the Main Concern -- 7.4 1968 NATO Conference on Software Engineering -- 7.5 1968-1969: A Period of Suffering -- 7.6 The Development of Weakest Preconditions -- 7.7 A Calculus Based on Leibniz's Substitution of Equals for Equals -- 7.8 Proofs of Concurrent Programs -- 7.9 Conclusion -- References, 8 Nondeterminism and Guarded Commands -- Krzysztof R. Apt and Ernst-Ru¿diger Olderog -- 8.1 Introduction -- 8.2 Avoiding Nondeterminism -- 8.3 Angelic Nondeterminism -- 8.4 Guarded Commands -- 8.5 Some Considerations on Guarded Commands -- 8.6 Modeling Parallel Programs -- 8.7 Communicating Sequential Processes and Their Relation to Guarded Commands -- 8.8 Fairness -- 8.9 Nondeterminism: Further Developments -- 8.10 Conclusions -- Acknowledgements -- References, 9 A Personal View of Edsger W. Dijkstra and His Stance on Software Construction -- Christian Lengauer -- References, 10 Applying Dijkstra's Vision to Numerical Software -- Robert van de Geijn and Maggie Myers -- 10.1 Introduction -- 10.2 An Example -- 10.3 Decades of Research, Development, and Impact -- 10.4 Educating the Masses -- 10.5 Conclusion -- Acknowledgments -- References, 11 Calculational Proofs -- Vladimir Lifschitz -- 11.1 A letter from Dijkstra -- 11.2 Dijkstra's Calculational Proofs are Semi-formal -- 11.3 Calculational Proofs Can Be Smooth -- 11.4 Calculational Proofs versus Natural Deduction -- 11.5 Propositional Calculations -- 11.6 Reasoning about Predicate Transformers -- 11.7 Conclusion -- Acknowledgements -- References, 12 An Homage to the Beautiful Mathematical EWDs -- Jayadev Misra -- 12.1 Kruskal's Algorithm for Minimum Spanning Tree -- 12.2 Fermat's and Wilson's Theorems -- 12.3 Arithmetic and Geometric Mean -- 12.4 Hall's Theorem on Distinct Representatives -- 12.5 Coxeter's Rabbit -- 12.6 Concluding Remarks -- Acknowledgement -- References, PART III SELECTED PAPERS, 13 A Note on Two Problems in Connexion with Graphs -- E. W. Dijkstra -- References, 14 Recursive Programming -- E. W. Dijkstra -- 14.1 The Aim -- 14.2 The Stack -- 14.3 Stacked Reservations -- 14.4 Consequences -- 14.5 The Link -- 14.6 Recursive Techniques and ALGOL 60 -- Acknowledgements -- Reference, 15 Some Meditations on Advanced Programming -- E. W. Dijkstra, 16 Solution of a Problem in Concurrent Programming Control -- E. W. Dijkstra, 17 Go To Statement Considered Harmful -- E. W. Dijkstra -- Key Words and Phrases, 18 The Structure of the "THE"-Multiprogramming System -- Edsger W. Dijkstra -- 18.1 Introduction -- 18.2 The Tool and the Goal -- 18.3 A Progress Report -- 18.4 A Survey of the System Structure -- 18.5 Design Experience -- 18.6 Conclusion -- Acknowledgements -- 18.A Appendix, 19 Self-stabilizing Systems in Spite of Distributed Control -- Edsger W. Dijkstra -- References, 20 On-the-Fly Garbage Collection: An Exercise in Cooperation -- Edsger W. Dijkstra, Leslie Lamport, A.J. Martin, C.S. Scholten, and E.F.M. Steffens -- 20.1 Introduction -- 20.2 The Grain of Action -- 20.3 Reformulation of the Problem -- 20.4 The First Coarse-Grained Solution -- 20.5 A New Coarse-Grained Solution -- 20.6 A Fine-Grained Solution -- References, 21 On the Reliability of Programs -- E. W. Dijkstra, PART IV BIOGRAPHICAL ESSAYS, 22 Edsger Dijkstra, The Man Who Carried Computer Science on His Shoulders -- Krzysztof R. Apt -- 22.1 Biography -- 22.2 EWDs -- 22.3 Early Contributions -- 22.4 Eighties -- 22.5 Nineties -- 22.6 Opinions and Attitudes -- 22.7 Character and Lifestyle -- 22.8 Legacy -- References, 23 Memories of Edsger W. Dijkstra -- E. Allen Emerson -- 23.1 Weakest Preconditions -- 23.2 Fairness -- 23.3 Personal Reminiscences -- References, 24 Reflections on Edsger and His Influence -- David Gries -- References, 25 Forty Years with Edsger -- Tony Hoare -- References, 26 Edsger Dijkstra-Some Reminiscences -- Brian Randell -- 26.1 Introduction -- 26.2 Brighton 1961 -- 26.3 Visit to the Mathematical Centre -- 26.4 Our Trip Report and Book -- 26.5 1964-IBM and Algol WG 2.1 -- 26.6 1967-SOSP -- 26.7 The THE Operating System -- 26.8 The 1968 NATO S/W Engineering Conference -- 26.9 Algol 68 -- 26.10 The 1969 NATO Conference -- 26.11 In 12 Months from June 1974 -- 26.12 Some EWD Interludes -- 26.13 The 60th Birthday Salute -- References, 27 Evoking Whitehead's Dictum -- Fred B. Schneider -- 27.1 Dijkstra's Influence: On Concurrent Programming -- 27.2 Dijkstra's Influence: On Becoming a Researcher -- Acknowledgements -- References, 28 Edsger W. Dijkstra in the Eyes of His Friends, Colleagues, and Students -- 28.1 Lex Bijlsma, Open University of the Netherlands -- 28.2 Ken Calvert, University of Kentucky, Lexington, KY -- 28.3 K. Mani Chandy, California Institute of Technology, Pasadena, CA -- 28.4 Eric C.R. Hehner, Department of Computer Science, University of Toronto -- 28.5 Wim H. Hesselink, University of Groningen -- 28.6 Rajeev Joshi, Amazon, Pasadena, CA -- 28.7 Don Knuth, Stanford Computer Science Department -- 28.8 Alain J. Martin, California Institute of Technology -- 28.9 Jayadev Misra, University of Texas at Austin, Austin, TX -- 28.10 David A. Naumann, Stevens Institute of Technology, Hoboken, NJ -- 28.11 J.R. Rao, IBM Thomas J. Watson Research Center, Yorktown Heights, NY -- 28.12 Hamilton Richards -- 28.13 Mark Scheevel, Vericast, Austin, TX -- 28.14 David Turner, University of Kent, UK, PART V VARIA, 29 Edsger W. Dijkstra as a Lecturer in Marktoberdorf -- Manfred Broy -- 29.1 The Idea Leading to the Marktoberdorf Summer School -- 29.2 "State of the Art" at the Beginning of the '70s -- 29.3 Marktoberdorf Summer Schools: The Beginnings -- 29.4 Edsger as a Director of the Marktoberdorf Summer Schools -- 29.5 The Arena of the Marktoberdorf Summer School -- 29.6 The Challenge -- 29.7 The Role of Formal Mathematics in Programming -- 29.8 Edsger's Views about the Marktoberdorf Summer School -- 29.9 A Line of Development -- 29.10 The End -- References, 30 The Edsger W. Dijkstra Archive -- Hamilton Richards, Edsger W. Dijkstra: Biographical Information -- Krzysztof R. Apt, Authors' Biographies, and Index
- Subject(s):
- Genre(s):
- ISBN:
- 9781450397742 ebook
9781450397728 epub
9781450397735 hardcover
9781450397711 paperback - Other Forms:
- Also available in print.
- Technical Details:
- Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
View MARC record | catkey: 40229638