The reports available electronically in this directory (/pub/DEC/SRC/research-reports/..) are flagged below by the words AVAILABLE ELECTRONICALLY next to the associated report number. For hardcopy orders of other SRC research reports, please send electronic mail to one of the addresses below and include your full postal address and the number of the report you wish to receive. src-report@src.dec.com decsrc::src-report SRC RESEARCH REPORTS -------------------- ************** SRC Research Report #1 Date: September 1, 1984 "A Kernel Language for Modules and Abstract Data Types." R. Burstall and B. Lampson. 51 pages. ************** SRC Research Report #2 Date: October 25, 1984 "Optimal Point Location in a Monotone Subdivision." Herbert Edelsbrunner, Leo J. Guibas, and Jorge Stolfi. 33 pages. *************** SRC Research Report #3 Date: January 11, 1985 "On Extending Modula-2 for Building Large, Integrated Systems." Paul Rovner, Roy Levin, John Wick. 45 pages. *************** SRC Research Report #4 Date: July 15, 1985 "Eliminating go to's while Preserving Program Structure." Lyle Ramshaw. 26 pages. *************** SRC Research Report #5 (OUT OF PRINT) Date: July 24, 1985 SUPERSEDED BY REPORTS 58, 60, 72, 74, 82 "Larch in Five Easy Pieces." J. V. Guttag, J. J. Horning, and J. M. Wing. 119 pages. *************** SRC Research Report #6 Date: October 19, 1985 AVAILABLE ELECTRONICALLY "A Caching File System for A Programmer's Workstation." Michael D. Schroeder, David K. Gifford, and Roger M. Needham. 23 pages. *************** SRC Research Report #7 Date: November 30, 1985 AVAILABLE ELECTRONICALLY "A Fast Mutual Exclusion Algorithm." Leslie Lamport. 15 pages. *************** SRC Research Report #8 Date: December 25, 1985 AVAILABLE ELECTRONICALLY "On Interprocess Communication." Leslie Lamport. 50 pages. *************** SRC Research Report #9 Date: April 1, 1986 "Topologically Sweeping an Arrangement." Herbert Edelsbrunner and Leonidas J. Guibas. 31 pages. *************** SRC Research Report #10 Date: May 1, 1986 AVAILABLE ELECTRONICALLY "A Polymorphic lambda-calculus with Type:Type." Luca Cardelli. 27 pages. *************** SRC Research Report #11 Date: May 5, 1986 AVAILABLE ELECTRONICALLY "Control Predicates Are Better Than Dummy Variables For Reasoning About Program Control." Leslie Lamport. 19 pages. *************** SRC Research Report #12 Date: June 23, 1986 "Fractional Cascading." Bernard Chazelle and Leonidas J. Guibas. 58 pages. *************** SRC Research Report #13 Date: August 20, 1986 "Retiming Synchronous Circuitry." Charles E. Leiserson and James B. Saxe. 42 pages. *************** SRC Research Report #14 Date: November 27, 1986 "An O(n^2) Shortest Path Algorithm for a Non-Rotating Convex Body." John Hershberger and Leonidas J. Guibas. 33 pages. *************** SRC Research Report #15 Date: December 25, 1986 AVAILABLE ELECTRONICALLY "A Simple Approach to Specifying Concurrent Systems." Leslie Lamport. 38 pages. *************** SRC Research Report #16 Date: April 2, 1987 "A Generalization of Dijkstra's Calculus." Greg Nelson. 56 pages. *************** SRC Research Report #17 Date: May 1, 1987 AVAILABLE ELECTRONICALLY "win and sin: Predicate Transformers for Concurrency." Leslie Lamport. 30 pages. *************** SRC Research Report #18 (WITHDRAWN) Date: June 1, 1987 "Synchronizing Time Servers." Leslie Lamport. 34 pages. *************** SRC Research Report #19 Date: June 21, 1987 "Blossoming: A Connect-the-Dots Approach to Splines." Lyle Ramshaw. 172 pages. *************** SRC Research Report #20 Date: August 20, 1987 AVAILABLE ELECTRONICALLY "Synchronization Primitives for a Multiprocessor: A Formal Specification." A. D. Birrell, J. V. Guttag, J. J. Horning, R. Levin. 21 pages. *************** SRC Research Report #21 Date: September 28, 1987 "Evolving the UNIX System Interface to Support Multithreaded Programs." Paul R. McJones and Garret F. Swart. 100 pages. *************** SRC Research Report #22 Date: October 2, 1987 AVAILABLE ELECTRONICALLY "Building User Interfaces by Direct Manipulation." Luca Cardelli. 45 pages. *************** SRC Research Report #23--OUT OF PRINT Date: December 30, 1987 "Firefly: A Multiprocessor Workstation." C. P. Thacker, L. C. Stewart, and E. H. Satterthwaite, Jr. 17 pages. *************** SRC Research Report #24 Date: January 30, 1988 AVAILABLE ELECTRONICALLY "A Simple and Efficient Implementation for Small Databases." Andrew D. Birrell, Michael B. Jones, and Edward P. Wobber. 13 pages. *************** SRC Research Report #25 Date: February 14, 1988 "Real-time Concurrent Collection on Stock Multiprocessors." John R. Ellis, Kai Li, and Andrew W. Appel 24 pages. *************** SRC Research Report #26 Date: March 1, 1988 "Parallel Compilation on a Tightly Coupled Multiprocessor." Mark Thierry Vandevoorde 87 pages. *************** SRC Research Report #27 Date: April 1st, 1988 AVAILABLE ELECTRONICALLY "Concurrent Reading and Writing of Clocks." Leslie Lamport 7 pages. *************** SRC Research Report #28 Date: May 1, 1988 AVAILABLE ELECTRONICALLY "A Theorem on Atomicity in Distributed Algorithms." Leslie Lamport 21 pages. *************** SRC Research Report #29 Date: August 14, 1988 AVAILABLE ELECTRONICALLY "The Existence of Refinement Mappings." Martin Abadi and Leslie Lamport. 42 pages. *************** SRC Research Report #30 Date: August 15, 1988 "The Power of Temporal Proofs." Martin Abadi. 57 pages. *************** SRC Research Report #31 OUT OF PRINT Date: August 25, 1988 SUPERSEDED BY REPORT #52 "Modula-3 Report." Luca Cardelli, James Donahue, Lucille Glassman, Mick Jordan, Bill Kalsow, Greg Nelson 55 pages. *************** SRC Research Report #32 Date: October 15, 1988 AVAILABLE ELECTRONICALLY "Bounds on the Cover Time." Andrei Broder and Anna Karlin. 22 pages. SRC Research Report #33 Date: November 1, 1988 "A Two-view Document Editor with User-definable Document Structure." Kenneth P. Brooks. 192 pages. *************** SRC Research Report #34 Date: January 2, 1989 "Blossoms Are Polar Forms." Lyle Ramshaw. 46 pages. ************** SRC Research Report #35 Date: January 6, 1989 AVAILABLE ELECTRONICALLY "An Introduction to Programming with Threads." Andrew D. Birrell. 35 pages. *************** SRC Research Report #36 Date: January 27, 1989 "Primitives for Computational Geometry." Jorge Stolfi. 228 pages. *************** SRC Research Report #37 Date: February 14, 1989 "Ruler, Compass, and Computer The Design and Analysis of Geometric Algorithms." Leonidas J. Guibas and Jorge Stolfi. 55 pages. *************** SRC Research Report #38 Date: February 16, 1989 "Can fair choice be added to Dijkstra's calculus?." Manfred Broy and Greg Nelson. 17 pages. *************** SRC Research Report #39 Date: February 28, 1989 "A Logic of Authentication." Michael Burrows, Martin Abadi, and Roger Needham. 48 pages. *************** SRC Research Report #40 Date: March 21, 1989 "Implementing Exceptions in C." Eric S. Roberts. 13 pages. *************** SRC Research Report #41 Date: March 31, 1989 "Evaluating the Performance of Software Cache Coherence." Susan Owicki and Anant Agarwal. 29 pages. *************** SRC Research Report #42---OUT OF PRINT Date: April 2, 1989 "WorkCrews: An Abstraction for Controlling Parallelism." Eric S. Roberts and Mark T. Vandevoorde. 17 pages. *************** SRC Research Report #43 Date: April 15, 1989 AVAILABLE ELECTRONICALLY "Performance of Firefly RPC." Michael D. Schroeder and Michael Burrows. 17 pages. *************** SRC Research Report #44 Date: May 1, 1989 AVAILABLE ELECTRONICALLY "Pretending Atomicity." Leslie Lamport and Fred B.~Schneider. 29 pages. *************** SRC Research Report #45 Date: May 24, 1989 AVAILABLE ELECTRONICALLY "Typeful Programming." Luca Cardelli. 63 pages. *************** SRC Research Report #46 Date: June 1, 1989 AVAILABLE ELECTRONICALLY "An Algorithm for Data Replication." Timothy Mann, Andy Hisgen, and Garret Swart. 55 pages. *************** SRC Research Report #47 Date: June 10, 1989 AVAILABLE ELECTRONICALLY "Dynamic Typing in a Statically Typed Language." Martin Abadi, Luca Cardelli, Benjamin C. Pierce, and Gordon D. Plotkin. 35 pages. *************** SRC Research Report #48 ---HARDCOPY OUT OF PRINT Date: August 25, 1989 AVAILABLE ELECTRONICALLY "Operations on Records." Luca Cardelli and John C. Mitchell. 60 pages. *************** SRC Research Report #49 Date: September 1, 1989 AVAILABLE ELECTRONICALLY "The Part-Time Parliament." Leslie Lamport. 43 pages. *************** SRC Research Report #50 Date: September 10, 1989 AVAILABLE ELECTRONICALLY SRC 50a "An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon." David Dobkin, Leonidas Guibas, John Hershberger, and Jack Snoeyink. 22 pages. A Videotape (50b) accompanies report 50a. "Boolean Formulae for Simple Polygons." John Hershberger and Marc H. Brown. Time 6:15 *************** SRC Research Report #51 Date: September 15, 1989 "Experience with the Firefly Multiprocessor Workstation." Susan Owicki. *************** SRC Research Report #52 Date: November 1, 1989 "Modula-3 Report (revised)." Luca Cardelli, James Donahue, Lucille Glassman, Mick Jordan, Bill Kalsow, Greg Nelson. 71 pages. *************** SRC Research Report #53 Date: November 15, 1989 "IO Streams: Abstract Types, Real Programs." Mark R. Brown and Greg Nelson. 46 pages. ****************SRC Research Report 54 Date: February 6th, 1990 Explicit Substitutions Martin Abadi, Luca Cardelli, Pierre-Louis Curien, Jean-Jacques Levy 56 pages ****************SRC Research Report 55 Date: February 14, 1990 AVAILABLE ELECTRONICALLY A Semantic Basis for Quest Luca Cardelli and Giuseppe Longo 51 pages ****************SRC Research Report 56 Date: March 10, 1990 Abstract Types and the Dot Notation Luca Cardelli and Xavier Leroy 32 pages ****************SRC Research Report 57 --SUPERSEDED BY REPORT #79 Date: April 1, 1990 A Temporal Logic of Actions Leslie Lamport 36 pages ***********************SRC Research Report 58 April 14, 1990 AVAILABLE ELECTRONICALLY Report on the Larch Shared Language: Version 2.3 John V. Guttag, James J. Horning, Andres Modet 43 pages (This report supersedes Pieces II and III of "Larch in Five Easy Pieces," SRC Report 5, by J. Guttag, J. Horning, and J. Wing.) **********************SRC Research Report 59 April 30, 1990 AVAILABLE ELECTRONICALLY Autonet: a High-speed, Self-configuring Local Area Network with Point-to-point Links Michael D. Schroeder, Andrew D. Birrell, Michael Burrows, Hal Murray, Roger M. Needham, Thomas L. Rodeheffer, Edwin H. Satterthwaite, Charles P. Thacker 42 pages ***********************SRC Research Report 60 July 4, 1990 AVAILABLE ELECTRONICALLY Debugging Larch Shared Language Specifications Stephen J. Garland, John V. Guttag, James J. Horning 34 pages ***********************SRC Research Report 61 August 7, 1990 In Memoriam: J.C.R. Licklider 1915-1990 ***********************SRC Research Report 62 August 14, 1990 AVAILABLE ELECTRONICALLY Subtyping Recursive Types Roberto M. Amadio and Luca Cardelli 60 pages ***********************SRC Research Report 63 August 20, 1990 AVAILABLE ELECTRONICALLY Heap Usage in the Topaz Environment John D. DeTreville 42 pages ***********************SRC Research Report 64 November 22, 1990 Experience with Concurrent Garbage Collectors for Modula-2+ John DeTreville 54 pages ***********************SRC Research Report 65 October 12, 1990 AVAILABLE ELECTRONICALLY An Axiomatization of Lamport's Temporal Logic of Actions Martin Abadi 18 pages ***********************SRC Research Report 66 October 10, 1990 AVAILABLE ELECTRONICALLY Composing Specifications Martin Abadi and Leslie Lamport 90 pages ***********************SRC Research Report 67 October 22, 1990 AVAILABLE ELECTRONICALLY Authentication and Delegation with Smart-cards M. Abadi, M. Burrows, C. Kaufman, B. Lampson 24 pages ***********************SRC Research Report 68 December, 1991 Trestle Reference Manual Mark S. Manasse and Greg Nelson 154 pages ***********************SRC Research Report 69 May 1, 1992 Trestle Tutorial Mark S. Manasse and Greg Nelson 70 pages ***********************SRC Research Report 70 March 4, 1991 AVAILABLE ELECTRONICALLY A Calculus for Access Control in Distributed Systems M. Abadi, M. Burrows, B. Lampson, G. Plotkin 41 pages **********************SRC Research Report 71 May 7, 1991 AVAILABLE ELECTRONICALLY Trading Space for Time in Undirected s-t Connectivity Andrei Z. Bruder, Anna R. Karlin, Prabhakar Raghavan, Eli Upfal 28 pages ***********************SRC Research Report 72 June 13, 1991 AVAILABLE ELECTRONICALLY LM3: A Larch Interface Language for Modula-3 A Definition and Introduction, Version 1.0 Kevin D. Jones 82 pages ************************SRC Research Report 73 June 18, 1991 AVAILABLE ELECTRONICALLY Decidability and Expressiveness for First-Order Logics of Probability Martin Abadi and Joseph Y. Halpern 46 pages ************************SRC Research Report 74 July 24, 1991 AVAILABLE ELECTRONICALLY Introduction to LCL, A Larch/C Interface Language J. V. Guttag and J. J. Horning 90 pages ************************SRC Research Report 75 February 28, 1992 AVAILABLE ELECTRONICALLY Zeus: A System for Algorithm Animation and Multi-View Editing Marc H. Brown 34 pages ************************SRC Research Reports 76a & b August 30, 1991 AVAILABLE ELECTRONICALLY SRC 76a Color and Sound in Algorithm Animation Marc H. Brown and John Hershberger 44 pages A videotape (76b) accompanies report 76a: An Anthology of Algorithm Animations using Zeus Edited by Marc H. Brown Time: 59:00 ************************SRC Research Report 77 September 18, 1991 AVAILABLE ELECTRONICALLY Automatic Reconfiguration in Autonet Thomas L. Rodeheffer and Michael D. Schroeder 56 pages ************************SRC Research Report 78 September 25, 1991 Using Transformations and Verification in Circuit Design James B. Saxe, Stephen J. Garland, John V. Guttag, James J. Horning 36 pages ************************SRC Research Report 79 December 25, 1991 AVAILABLE ELECTRONICALLY The Temporal Logic of Actions Leslie Lamport 86 pages ************************SRC Research Report 80 December 30, 1991 AVAILABLE ELECTRONICALLY An Extension of System F with Subtyping Luca Cardelli, Simone Martini, John JC. Mitchell, Andre Scedrov 56 pages ************************SRC Research Report 81 January 3, 1992 AVAILABLE ELECTRONICALLY Extensible Records in a Pure Calculus of Subtyping Luca Cardelli 56 pages ************************SRC Research Report 82 December 31, 1991 AVAILABLE ELECTRONICALLY A Guide to LP, the Larch Prover Stephen J. Garland and John V. Guttag 112 pages *************************SRC Research Report 83 February 4, 1992 Authentication in Distributed Systems: Theory and Practice Butler Lampson, Martin Abadi, Michael Burrows, Edward Wobber 45 pages **************************SRC Research Report 84 and 84b March 17, 1992 AVAILABLE ELECTRONICALLY Graphical Fisheye Views of Graphs Manojit Sarkar and Marc H. Brown 24 pages Graphical Fisheye Views of Graphs Marc H. Brown, James R. Meehan, Manojit Sarkar Video #84b, July 1, 1992 Time: 3:51 minutes ***************************SRC Research Report 85 April 15, 1992 AVAILABLE ELECTRONICALLY On-line Data Compression in a Log-structured File System Michael Burrows, Charles Jerian, Butler Lampson, Timothy Mann 19 pages *************************SRC Research Report 86 May 1, 1992 AVAILABLE ELECTRONICALLY A Logical View of Composition Martin Abadi and Gordon D. Plotkin 35 pages *************************SRC Research Reports 87a & b June 6, 1992 AVAILABLE ELECTRONICALLY SRC 87a Animation of Geometric Algorithms: A Video Review Edited by Marc H. Brown and John Hershberger 23 pages A videotape (87b) accompanies the above report: Animation of Geometric Algorithms: A Video Review Edited by Marc H. Brown and John Hershberger Time: 74:00 *************************SRC Research Report 88 June 15, 1992 AVAILABLE ELECTRONICALLY Factors in the Performance of the AN1 Computer Network Susan S. Owicki and Anna R. Karlin 25 pages ************************SRC Research Report 89 July 15, 1992 AVAILABLE ELECTRONICALLY Compositional Refinement of Interactive Systems Manfred Broy 48 pages ***********************SRC Research Report 90 September 23, 1992 AVAILABLE ELECTRONICALLY A High-speed DES Implementation for Network Applications Hans Eberle 24 pages **********************SRC Research Report 91 October 12, 1992 AVAILABLE ELECTRONICALLY An Old-Fashioned Recipe for Real Time Martin Abadi and Leslie Lamport 67 pages **********************SRC Research Report 92 (a) and (b) REPORT 92a: AVAILABLE ELECTRONICALLY October 20, 1992 Hector: Connecting Words with Definitions Lucille Glassman, Dennis Grinberg, Cynthia Hibbard James Meehan, Loretta Guarino Reid, Mary-Claire van Leunen 46 pages VIDEOTAPE 92b accompanies the above report: Time: 14:34 ****************************SRC Research Report 93 November 12, 1992 AVAILABLE ELECTRONICALLY "Experiences with Software Specification and Verification Using LP, the Larch Proof Assistant" Manfred Broy 69 pages *****************************SRC Research Report 94 February 14, 1993 AVAILABLE ELECTRONICALLY "How to Write a Proof" Leslie Lamport 12 pages *****************************SRC Research Report 95 February 2, 1993 AVAILABLE ELECTRONICALLY "Baby Modula-3 and a Theory of Objects" Martin Abadi 43 pages *****************************SRC Research Report 96 February 14, 1993 AVAILABLE ELECTRONICALLY How to Make a Correct Multiprocess Program Execute Correctly on a Multiprocessor Leslie Lamport *****************************SRC Research Report 97 February 23, 1993 AVAILABLE ELECTRONICALLY "An Implementation of F<:" Luca Cardelli 52 pages ***************************SRC Research Report 98 March 27, 1993 AVAILABLE ELECTRONICALLY "The 1992 SRC Algorithm Animation Festival" Marc H. Brown 12 pages ***************************SRC Research Report 99 April 26, 1993 AVAILABLE ELECTRONICALLY "High Speed Switch Scheduling for Local Area Networks" Thomas E. Anderson, Susan S. Owicki, James B. Saxe, Charles P. Thacker 37 pages *****************************SRC Research Report 100 June 5, 1993 "The First 99 Reports" Compiled by James Mason 122 pages *****************************SRC Research Report 101a & b May 4, 1993 AVAILABLE ELECTRONICALLY SRC 101a "The Second Annual Video Review of Computational Geometry" Edited by Marc H. Brown and John Hershberger Report 101a, May 4, 1993 34 pages. A videotape (101b) accompanies report 101a: "The Second Annual Video Review of Computational Geometry" Edited by Marc H. Brown and John Hershberger Time: 57:53 ****************************SRC Research Report 102 June 10, 1993 AVAILABLE ELECTRONICALLY "Safe, Efficient Garbage Collection for C++" John R. Ellis and David L. Detlefs 76 pages ****************************SRC Research Report 103 June 10, 1993 AVAILABLE ELECTRONICALLY "A Coherent Distributed File Cache With Directory Write-behind" Timothy Mann, Andrew Birrell, Andy Hisgen, Charles Jerian, Garret Swart 45 pages ****************************SRC Research Report 104 June 23, 1993 AVAILABLE ELECTRONICALLY "New-Value Logging in the Echo Replicated File System" Andy Hisgen, Andrew Birrell, Charles Jerian, Timothy Mann, Garret Swart 39 pages ****************************SRC Research Report 105 June 14, 1993 AVAILABLE ELECTRONICALLY "The Vesta Approach to Precise Configuration of Large Software Systems" Roy Levin, Paul R. McJones 38 pages ****************************SRC Research Report 106 June 14, 1993 AVAILABLE ELECTRONICALLY "The Vesta Repository: A File System Extension for Software Development" Sheng-Yang Chiu, Roy Levin 34 pages ****************************SRC Research Report 107 June 14, 1993 AVAILABLE ELECTRONICALLY "The Vesta Language for Configuration Management" Christine B. Hanna, Roy Levin 60 pages ****************************SRC Research Report 108 June 14, 1993 AVAILABLE ELECTRONICALLY "Bridges: Tools to Extend the Vesta Configuration Management System" Mark R. Brown, John R. Ellis 42 pages ****************************SRC Research Report 109 July 15, 1993 AVAILABLE ELECTRONICALLY "Formal Parametric Polymorphism" Martin Abadi, Luca Cardelli, Pierre-Louis Curien 43 pages ****************************SRC Research Report 110a and b September 15, 1993 "Algorithm Animation Using 3D Interactive Graphics" Marc H. Brown and Marc A. Najork Report 19 pages. Video Time: 10:00 ****************************SRC Research Report 111 September 10, 1993 AVAILABLE ELECTRONICALLY "The Echo Distributed File System" Andrew D. Birrell, Andy Hisgen, Chuck Jerian, Timothy Mann, and Garret Swart 22 pages ****************************SRC Research Report 112 September 10, 1993 AVAILABLE ELECTRONICALLY "Availability in the Echo File System" Garret Swart, Andrew Birrell, Andy Hisgen, and Timothy Mann 43 pages ***************************SRC Research Report 113 In preparation ****************************SRC Research Report 114 October 5, 1993 AVAILABLE ELECTRONICALLY "Automated Proofs of Object Code for a Widely Used Microprocessor" Yuan Yu 122 pages.