SRC Research Report 28

A Theorem on Atomicity in Distributed Algorithms.

Leslie Lamport

Reasoning about a distributed algorithm is simplified if we can ignore the time needed to send and deliver messages and can instead pretend that a process sends a collection of messages as a single atomic action, with the messages delivered instantaneously as part of the action. A theorem is derived that proves the validity of such reasoning for a large class of algorithms. It generalizes and corrects a well known folk theorem about when an operation in a multiprocess program can be considered atomic.

Back to the SRC Research Reports main page.

• PostScript compressed with UNIX compress -- 90 Kbytes
  
• PostScript compressed with GNU compress (gzip) -- 72 Kbytes
  
• PostScript compressed with ZIP -- 72 Kbytes
  
• PostScript -- 240 Kbytes
  
• Portable Document Format (PDF) -- 264 Kbytes