Edsger Wybe Dijkstra / His Life, Work, and Legacy / Krzysztof R. Apt, Tony Hoare.

Format:

Book

Author/Creator:

Apt, Krzysztof R, editor.

Series:

ACM books - Collection 2 ; #45.

ACM books, 2374-6777 ; #45

Language:

English

Subjects (All):

Edsger Wybe Dijkstra (Computer Science).

Genre:

Electronic books.

Physical Description:

1 online resource (xxiv, 550 pages) LuaTEX

Edition:

First Edition

Place of Publication:

[New York, NY, USA] : Association for Computing Machinery; [2022].

System Details:

Mode of access: World Wide Web

System requirements: Adobe Acrobat Reader

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

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

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

6 Dijkstra's Legacy on Program Verification

Reiner Hä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

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

8 Nondeterminism and Guarded Commands

Krzysztof R. Apt and Ernst-Rü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

9 A Personal View of Edsger W. Dijkstra and His Stance on Software Construction

Christian Lengauer

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

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

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

PART III SELECTED PAPERS

13 A Note on Two Problems in Connexion with Graphs

E. W. Dijkstra

14 Recursive Programming

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

Reference

15 Some Meditations on Advanced Programming

E. W. Dijkstra

16 Solution of a Problem in Concurrent Programming Control

17 Go To Statement Considered Harmful

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

18.A Appendix

19 Self-stabilizing Systems in Spite of Distributed Control

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

21 On the Reliability of Programs

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

23 Memories of Edsger W. Dijkstra

E. Allen Emerson

23.1 Weakest Preconditions

23.2 Fairness

23.3 Personal Reminiscences

24 Reflections on Edsger and His Influence

25 Forty Years with Edsger

Tony Hoare

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

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

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

30 The Edsger W. Dijkstra Archive

Hamilton Richards

Edsger W. Dijkstra: Biographical Information

Krzysztof R. Apt

Authors' Biographies

Index

Other Format:

Print version:

ISBN:

3544585

9781450397742

9781450397728

Access Restriction:

Restricted for use by site license.