Search
Now showing items 1-10 of 357
Planar Embedding of Planar Graphs
(1983-02)
Planar embedding with minimal area of graphs on an integer grid is an interesting problem in VLSI theory. Valiant [V] gave an algorithm to construct a planar embedding for trees in linear area; he also proved that there ...
An Approximation Algorithm for Manhattan Routing
(1983-02)
Density has long been known to be an important measure of difficulty for Manhattan routing. In this paper, we identify a second important measure of difficulty, which we call flux. We show that flux, like density, is a ...
From Denotational to Operational and Axiomatic Semantics for ALGOL-like Languages: An Overview
(1983-10)
The advantages of denotational over operational semantics are argued. A denotational semantics is provided for an ALGOL-like language with finite-model procedures, blocks with local storage, and sharing (aliasing). Procedure ...
On Concurrent Identification Protocols
(1983-12)
We consider communication networks in which it is not possible to identify the source of a message which is broadcastes through the network. A natural question is whether it is possible for two users to identify each other ...
On BPP
(1983-12)
An Application of Number Theory to the Organization of Raster Graphics Memory
(1984-04)
A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ...
Empirical Analysis of a Token Ring Network
(1984-01)
The MIT Laboratory for Computer Science 10 Megabit token ring local area network was monitored. Over a one-week period 7 million packets and 1.3 billion bytes passes by the monitor. This thesis compares the MIT ring traffic ...
Consensus in the Presence of Partial Synchrony
(1985-10)
The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper ...
PADL - A Packet Architecture Description Language: A Preliminary Reference Manual
(1983-10)
PADL is a hardware description language for specifying the behavior and structure of packet communication systems. In such systems, hardware units called modules communicate by sending and receiving packets. The behavior ...
Reliable Object Storage to Support Atomic Actions
(1983-05)
To preserve the consistency of on-line, long-lived, distributed data in the presence of concurrency and in the event of hardware failures, it is necessary to ensure atomicity and data resiliency in applications. The ...