We extend Nisan's breakthrough derandomization result that BPHL sube SC2(1992) to bounded error probabilistic complexity classes based on auxiliary pushdown automata. In particular, we show that any logarithmic space, polynomial time two-sided bounded-error probabilistic auxiliary pushdown automaton (the corresponding complexity class is denoted by BPHLOGCFL) can be simulated by an SC2machine. This derandomization result improves a classical result by Cook (1979) that LOGDCFL sube SC2since LOGDCFL is contained in BPHLOGCFL. We also present a simple circuit-based proof that BPHLOGCFL is in NC2

We consider the problem of disseminating an update known to a set of servers to other servers in the system via a gossip protocol. Some of the servers can exhibit malicious behavior. We require that only the updates introduced by authorized clients are accepted by non-malicious servers. Spurious updates, in particular those generated by compromised nodes, are not accepted by non-malicious servers. We take the approach of collective endorsement where each server endorses an accepted update by computing a list of message authentication codes with symmetric keys allocated to it. We use a novel key allocation scheme that allocates a set of symmetric keys to each participating server to minimize the total number of keys. Our protocol is designed to minimize update diffusion time. In the absence of faulty nodes, its diffusion time is O(log n), which is the best possible time achieved when nodes only suffer from benign faults. If the actual number of Byzantine faults experienced during an update's dissemination is f, diffusion time increases to O(log n) + f. This is better than the latency of previously known protocols that take O(log n) +b time, where b is the assumed threshold that defines the maximum number of malicious servers that can be tolerated rather than f, the actual number of failures. The buffer requirements and message sizes are higher in our protocol than other known protocols, thus it trades off memory and bandwidth resources to improve latency.

We present the design of a distributed store that offers various levels of security guarantees while tolerating a limited number of nodes that are compromised by an adversary. The store uses secret sharing schemes to offer security guarantees namely availability, confidentiality and integrity. However, a pure secret sharing scheme could suffer from performance problems and high access costs. We integrate secret sharing with replication for better performance and to keep access costs low. The tradeoffs involved between availability and access cost on one hand and confidentiality and integrity on the other are analyzed. Our system differs from traditional approaches such as state machine or quorum based replication that have been developed to tolerate Byzantine failures. Unlike such systems, we augment replication with secret sharing and demonstrate that such a hybrid scheme offers additional flexibility that is not possible with replication alone.

We present the design of a distributed store that offers various levels of security guarantees while tolerating a limited number of nodes that are compromised by an adversary. The store uses secret sharing schemes to offer security guarantees, namely, availability, confidentiality, and integrity. However, a pure secret sharing scheme could suffer from performance problems and high access costs. We integrate secret sharing with replication for better performance and to keep access costs low. The trade offs involved between availability and access cost on one hand and confidentiality and integrity on the other are analyzed. Our system differs from traditional approaches such as state machine or quorum-based replication that have been developed to tolerate Byzantine failures. Unlike such systems, we augment replication with secret sharing and offer weaker consistency guarantees. We demonstrate that such a hybrid scheme offers additional flexibility that is not possible with replication alone.

As computers become pervasive in environments like the home and community, data repositories that can maintain the long term state of applications will become increasingly important. Because of the greater reliance of people on such applications and the potentially sensitive nature of the data manipulated by them, the repository must be highly available and it should provide secure access to data. Furthermore, many different types of data, ranging from private data belonging to a single user to data shared across different users may be stored in the repository. We present the design of a distributed data repository, called a secure store, which can meet the data access needs of diverse applications. We develop protocols that replicate data at multiple servers to enhance availability, and work even when a limited number of compromised servers exhibit arbitrary failure behavior. We also discuss how the nature of the data that is stored in the secure store impacts the availability and costs associated with data access.

Evaluating and analyzing the performance of a parallel application on an architecture to explain the disparity between projected and delivered performance is an important aspect of parallel systems research. However, conducting such a study is hard due to the vast design space of these systems. We study two important aspects related to the performance of parallel applications on shared memory parallel architectures. First, we quantify overheads observed during the execution of these applications on three different simulated architectures. We next use these results to synthesize the bandwidth requirements for the applications with respect to different network topologies. This study is performed using an execution-driven simulation tool called SPASM, which provides a way of isolating and quantifying the different parallel system overheads in a nonintrusive manner. The first exercise shows that in shared memory machines with private caches, as long as the applications are well-structured to exploit locality, the key determinant that impacts performance is network connection. The second exercise quantifies the network bandwidth needed to minimize the effect of network connection. Specifically, it is shown that for the applications considered, as long as the problem sizes are increased commensurate with the system size, current network technologies supporting 200-300 MBytes/sec link bandwidth are sufficient to keep the network overheads (such as latency and contention) within acceptable bounds.

Abstracting features of parallel systems is a technique that has been traditionally used in theoretical and analytical models for program development and performance evaluation. We explore the use of abstractions in execution-driven simulators in order to speed up simulation. In particular, we evaluate abstractions for the interconnection network and locality, properties of parallel systems in the context of simulating cache-coherent shared memory (CC-NUMA) multiprocessors. We use the recently proposed LogP model to abstract the network. We abstract locality by modeling a cache at each processing node in the system which is maintained coherent, without modeling the overheads associated with coherence maintenance. Such an abstraction tries to capture the true communication characteristics of the application without modeling any hardware induced artifacts. Using a suite of applications and three network topologies simulated on a novel simulation platform, we show that the latency overhead modeled by LogP is fairly accurate. On the other hand, the contention overhead can become pessimistic when the applications display sufficient communication locality. Our abstraction for data locality closely models the behavior of the target system over the chosen range of applications. The simulation model which incorporated these abstractions was around 250-300% faster than the simulation of the target machine.>

Synthesizing architectural requirements from an application viewpoint can help in making important architectural design decisions towards building large scale parallel machines. In this paper, we quantify the link bandwidth requirement on a binary hypercube topology for a set of five parallel applications. We use an execution-driven simulator called SPASM to collect data points for system sizes that are feasible to be simulated. These data points are then used in a regression analysis for projecting the link bandwidth requirements for larger systems. The requirements are projected as a function of the following system parameters: number of processors, CPU clock speed, and problem size. These results are also used to project the link bandwidths for other network topologies. Our study quantifies the link bandwidth that has to be made available to limit the network overhead in an application to a specified tolerance level. The results show that typical link bandwidths (200-300 MBytes/sec) found in current commercial parallel architectures (such as Intel Paragon and Cray T3D) would have fairly low network overhead for the applications considered in this study. For two of the applications, this overhead is negligible. For the other applications, this overhead can be limited to about 30% of the execution time provided the problem sizes are increased commensurate with the processor clock speed. The technique presented can be useful to a system architect to synthesize the bandwidth requirements for realizing well-balanced parallel architectures.

The overheads in a parallel system that limit its scalability need to be identified and separated in order to enable parallel algorithm design and the development of parallel machines. Such overheads may be broadly classified into two components. The first one is intrinsic to the algorithm and arises due to factors such as the work-imbalance and the serial fraction. The second one is due to the interaction between the algorithm and the architecture and arises due to latency and contention in the network. A top-down approach to scalability study of shared memory parallel systems is proposed in this research. We define the notion of overhead functions associated with the different algorithmic and architectural characteristics to quantify the scalability of parallel systems; we isolate the algorithmic overhead and the overheads due to network latency and contention from the overall execution time of an application; we design and implement an execution-driven simulation platform that incorporates these methods for quantifying the overhead functions; and we use this simulator to study the scalability characteristics of five applications on shared memory platforms with different communication topologies.

This paper considers restrictions on Boolean circuits and uses them to obtain new uniform circuit characterizations of nondeterministic space and time classes. It also obtains characterizations of counting classes based on nondeterministic time bounded computations on the arithmetic circuit model. It is shown how the notion of semi-unboundedness unifies the definitions of many natural complexity classes.

A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined by Dymond and Tompa [J. Comput. System Sci., 30 (1985), pp. 149–161] and is used to characterize two natural parallel complexity classes, namely LOGCFL and ${\text{AC}}^1 $. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well-known results of complexity theory.

Two properties, called semi-unboundedness, and polynomial proof-size, are identified as key properties shared by the definitions of LOGCFL on several models of computations. The semi-unboundedness property leads to the definition of new models of computation based on unbounded fan-in circuits. These are circuits obtained from unbounded fan-in circuits by restricting the fan-in of gates of one type. A new characterization of LOGCFL is obtained on such a model in which the fan-in of the AND gates are bounded by a constant. This property also suggests new characterizations of LOGCFL on the following models: alternating Turing machines [CKS81], nondeterministic auxiliary pushdown automata [Co71], and bounded fan-in Boolean circuits [Co85].

A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined in [DT85] and is used to characterize two natural parallel complexity classes, namely LOGCFL and AG1. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well known results of complexity theory.

Abstract An interactive assembly level debugging system has been developed to facilitate program development on an INTEL 8080A/8085 based microcomputer. It has features such as decoding machine level instructions into the assembly language, relocating programs in memory, changing instructions interactively at assembly level etc. This paper deals with the design of the assembly level debugging system and the various facilities and features it provides. The debugging system requires only 4.5K bytes of RAM besides the memory requirements of the application program that has to be debugged.

Abstract An assembler which provides facilities for programming in assembly language for the Intel 8080A micro‐computer is described. This assembler is a single pass self‐assembler and it requires a storage of 2K bytes. The assembler has been designed to be operated from a keyboard to develop programs in assembly language. It allows subroutine calls and nesting of subroutines to any depth. It flashes syntax errors, if any, while an instruction is being keyed in. The most important feature of the assembler is that it does not require costly peripherals such as floppy discs, cassette tapes, etc. It operates through a keyboard with letters (A‐Z), Arabic numerals (0–9) and some special characters to accommodate mnemonics used in label, opcode and operand fields of programs in the assembly language. A display facility will be greatly helpful. In this paper, design and implementation details of assembler are presented. The authors have the view that assemblers for other micro‐computers can be designed and implemented on similar lines. Though implementation may slightly differ from one micro‐computer to another, the design details will mostly remain the same.

A data-structure suitable for multivariable polynomial processing is introduced. Using this data-structure, arithmetic algorithms are described for addition, subtraction and multiplication of multivariable polynomials; also algorithms are described for forming the inner product and tensor product of vectors, whose components are multivariable polynomials. Application of these algorithms. for multivariable cardinal spline approximation is described in detail.