Leslie Lamport, Robert E. Shostak, Marshall C. Pease
SRI International Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army ...
of Optimized Code The long-standing conflict between code optimization and symbolic debugging is examined. The effects oflocal and global optimizations on the variables ofa program are categorized,and models for representing the effect of ...
Susan S. Owicki, Leslie Lamport
A liveness property asserts that program execution eventually reaches ome desirable state. While termination has been studied extensively, many other liveness properties are important for concurrent programs. A formal proof method, based on temporal ...
Finite differencing is a program optimization method that generalizes strength reduction, and provides an efficient implementation for a host of program transformations including "iterator inversion." Finite differencing is formally ...
The basic idea of the Schorr-Waite graph-marking algorithm can be precisely formulated, explained, and verified in a completely applicative (functional) programming style. Graphs are specified algebraically as objects of an abstract data type. When ...
Statistical measurements of the behavior of LISP programs have shown a marked asymmetry in the distribution of their data structures (binary trees). On the basis of a statistical model for such a distribution, we evaluate the expected storage cost of ...