Algorithms for Concurrent Systems


From Rachid Guerraoui and Petr Kuznetsov


EPFL Press - Collection: Computer Science - 2018-10-15

    • Paper book

      36,70 €


    The field of concurrent computing has gained in importance after major chip manufacturers switched their focus from increasing the speed of individual processors to increasing the number of processors on a chip. The computer industry has thus been calling for a software revolution: the concurrency revolution. A major challenge underlying this paradigm shift is creating a library of abstractions that developers can use for general purpose concurrent programming. We study in this book how to define and build such abstractions in a rigorous manner. We focus on those that are considered the most difficult to get right and have the highest impact on the overall performance of a program: synchronization abstractions, also called shared objects or concurrent data structures. The book is intended for software developers and students. It began as a set of lecture notes for courses given at EPFL and Télécom Paris.


    • 1. Introduction
    • I. Correctness
    • 2. Linearizability
    • 3. Progress
    • II. Read-Write objects
    • 4. Semantics of Read-Write Objects
    • 5. Basic Register Reductions
    • 6. Timestamp-Based Reductions
    • 7. Optimal Atomic Bit
    • 8. Bounded Atomic Multivalued Register Implementation
    • III. Snapshot Objects
    • 9. Collects and Snapshots
    • 10. Immediate Snapshot and Iterated Immediate Snapshot
    • IV. Consensus Objects
    • 11. Consensus and Universality
    • 12. Consensus Number and Hierarchy
    • V. Schedulers
    • 13.Resilience
    • 14. Failure Detectors
    • 15. Adversaries
    • 16. Bibliography
    • 17. Index
    • Information

    Available media

    • Paper book

      layout 160 x 240, 256 pagesIn stock

    Integrate this product on your site

    → Copy to memory :