How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

1979/09/01 by Lamport · 38 citations
Computer Science · #Parallel Computing and Optimization Techniques #Logic, programming, and type systems #Embedded Systems Design Techniques

paper · doi:10.1109/tc.1979.1675439

Abstract

Many large sequential computers execute operations in a different order than is specified by the program. A correct execution is achieved if the results produced are the same as would be produced by executing the program steps in order. For a multiprocessor computer, such a correct execution by each processor does not guarantee the correct execution of the entire program. Additional conditions are given which do guarantee that a computer correctly executes multiprocess programs.

Cited by

• On Composition and Implementation of Sequential Consistency (Extended Version)
• Accelerating Language Model Workflows with Prompt Choreography
• Fork Sequential Consistency is Blocking
• Taming Weak Memory Models
• Actor Model of Computation: Scalable Robust Information Systems
• Decidability of Liveness on the TSO Memory Model
• Formal Modelling, Testing and Verification of HSA Memory Models using\n Event-B
• Thread-Modular Static Analysis for Relaxed Memory Models
• Multi-Version Coding - An Information Theoretic Perspective of Consistent Distributed Storage
• Analyzing the memory ordering models of the Apple M1
• How to make a correct multiprocess program execute correctly on a multiprocessor
• Linearizability: a correctness condition for concurrent objects
• Mastering Concurrent Computing Through Sequential Thinking: A Half-century Evolution
• Context-Bounded Model Checking for POWER
• Parallelized sequential composition, pipelines, and hardware weak memory models
• A methodology for implementing highly concurrent data objects
• A Concurrency Problem with Exponential DPLL(T) Proofs
• Creek: Low-latency, Mixed-Consistency Transactional Replication Scheme
• Wait-free synchronization
• The Impact of Memory Models on Software Reliability in Multiprocessors
• Local Linearizability
• Formalizing and Implementing Distributed Ledger Objects
• Enabling the Adoption of Processing-in-Memory: Challenges, Mechanisms,\n Future Research Directions
• A Unified Theory of Shared Memory Consistency
• AllConcur: Leaderless Concurrent Atomic Broadcast (Extended Version)
• Behavioural Theory of Reflective Algorithms II: Reflective Parallel Algorithms
• A Proof of Correctness for the Tardis Cache Coherence Protocol
• Consistency in Non-Transactional Distributed Storage Systems
• Weak Memory Model Formalisms: Introduction and Survey
• Verifying PRAM Consistency over Read/Write Traces of Data Replicas
• Simple Executions of Snapshot Implementations
• On partial order semantics for SAT/SMT-based symbolic encodings of weak\n memory concurrency
• Virtual-Link: A Scalable Multi-Producer, Multi-Consumer Message Queue Architecture for Cross-Core Communication
• Vive la Différence: Paxos vs. Viewstamped Replication vs. Zab
• Tardis 2.0: Optimized Time Traveling Coherence for Relaxed Consistency Models
• Shared memory consistency models: a tutorial
• Accelerating Federated Learning in Heterogeneous Data and Computational\n Environments
• On Grid Quorums for Erasure Coded Data. [europepmc]

Related

• How to make a correct multiprocess program execute correctly on a multiprocessor
• Advances in computer architecture
• Parallelism Via Concurrency at Multiple Levels
• Partial Orders for Efficient BMC of Concurrent Software
• Global Clock, Physical Time Order and Pending Period Analysis in Multiprocessor Systems