Browsing LCS Technical Memos (1974 - 2003) by Title
Now showing items 470-489 of 492
-
UDM: User Direct Messaging for General-Purpose Multiprocessing
(1996-03)User Direct Messaging (UDM) allows user-level, processor-to- processor messaging to coexist with general multiprogramming and virtual memory. Direct messaging, where processors launch and receive messages in tens of cycles ... -
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
(1986-09)A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g. the Santha and Vazirani model [26]). The sources considered output strings according to probability ... -
Understanding ALGOL: A View of a Recent Convert to Denotational Semantics
(1983-10)The advantages of denotational over copy-rule semantics are argued. A denotational semantics is indicated for an ALGOL-like language with finite-mode procedures, blocks with local storage, and sharing (aliasing). Procedure ... -
A Unified Framework for Schedule and Storage Optimization
(2000-11)We present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. Using this framework, we show how to find the best storage mapping for a ... -
Use of High Level Languages for Sytems Programming
(1970-09)(This paper is a slightly edited version of a transcript so that it still contains the colloquial flavor of the oral presentation.) I'm going to talk about languages for systems programming what they can do for us, and ... -
The Use of Queues in the Parallel Data Flow Evaluation of "If-Then-While" Programs
(1978-05)A property of a model of parallel computation is analyzed. We show that the use of queues may speed-up the execution of well formed data flow schemas by an arbitrarily large factor. A general model of data flow computation ... -
The Use of the Domain Name System for Dynamic References in an Online Library
(1994-05)Persistent, dynamic references (or links) to remove documents are an essential part of an online library. This thesis examines two distributed database systems, X.500 and the Domain Name System(DNS), upon which to build ... -
A User's Guide to the Macro Control Language
(1973-12) -
Using Non-interactive Proofs to Achieve Independence Efficiently and Securely
(1994-11)Independence or simultaneous broadcast is a fundamental tool to achieve security in fault tolerant distributed computing. It allows n players to commit to independently chosen values. In this paper we present a constant ... -
Verifiable Secret Sharing as Secure Computation
(1994-03)We present a stronger notion of verifiable secret sharing and exhibit a protocol implementing it. We show that our new notion is preferable to the old ones whenever verifiable secret sharing is used as a tool within larger ... -
Verification of the Randomized Consensus Algorithm of Aspnes and Herlihy: a Case Study*
(1997-06)The Probabilistic I/O Automaton model of [20] is used as the basis for a formal presentation and proof of the randomized consensus algorithm of Aspnes and Herlihy. The algorithm guarantees termination within expected ... -
Virtual Wires: Overcoming Pin Limitations in FPGA-based Logic Emulators
(1992-11)Existing FPGA-based logic emulators suffer from limited inter-chip communication bandwidth, resulting in low gate utilization (10 20 percent). This resource imbalance increases the number of chips needed to emulate a ... -
Wafer-scale Integration of Systolic Arrays
(1983-02)VLSI technologists are fast developing wafer-scale integration. Rather than partitioning a silicon wafer into chips as is usually done, the idea behind wafer-scale integration is to assemble an entire system (or network ... -
Weak Monadic Second Order Theory of Successor is not Element-recurive
(1973-12)Let L SIS be the set of formulas expressible in a week monadic second order logic using only the predicates [x =y+1] and [x E z]. Bucci and Elgot [3,4] have shown that the truth of sentences in L SIS (under the standard ... -
What are principal typings and what are they good for?
(1995-11)We demonstrate the pragmatic value of the principal typing property, a property more general than ML's principal type property, by studying a type system with principal typings. The type system is based on rank 2 intersection ... -
What are principal typings and what are they good for?
(1995-08)We demonstrate the pragmatic value of the principal typing property, a property more general than ML's principal type property, by studying a type system with principal typings. The type system is based on rank 2 intersection ... -
What is a Model of the Lamda Calculus? Expanded Version
(1981-07)An elementary, purely algebraic definition of model for the untypes lambda calculus is given. This definition is shown to be equivalent to the natural semantic definition based on environments. These definitions of model ... -
What Price for Eliminating Expression Side-effects?
(1985-06)Separating a programming language into side-effect-free expressions and effect-only statements should make the language more amenable to axiomatization, as well as providing benefits for style, pedagogy, and implementation ... -
Width-3 Permutation Branching Programs
(1985-12)We consider a restricted class of width-3 branching programs where each column of nodes depends on a single variable, and the 0-edges and the 1-edges out of each column form a permutation. In this model, parity and the ... -
With what Frequency are Apparently Intractable Problems Difficult?
(1979-02)An algorithm is almost polynomial-time (apt) iff there is a polynomial p such that for all n, the algorithm halts within p(n) steps on all by at most p(n) inputs of size at most n. It is nown that for NP-complete and ...
