Error in the UNITY substitution rule for subscripted operators

UNITY, introduced by Chandy and Misra [ChM88], is a programming logic intended to reason about temporal properties of distributed programs. Despite the fact that UNITY does not have the full power of, for example, linear temporal logic, it enjoys popularity due to its simplicity.There was however a serious problem with the Substitution Rule. The logic is incomplete without the rule, and with the rule it is inconsistent.     

Processor membership in asynchronous distributed systems

Presents protocols for determining processor membership in asynchronous distributed systems that are subject to processor and communication faults. These protocols depend on the placement of a total order on broadcast messages. The types of systems for which each of these protocols is applicable are characterized by the properties of the communication mechanisms and by the availability of stable storage. In the absence of stable storage or of a mechanism for distinguishing promptly delivered messages, the authors show that no membership protocol can exist. They also discuss their experience in implementing these membership protocols     

Unstructured tree search on SIMD parallel computers

We present new methods for load balancing of unstructured tree computations on large-scale SIMD machines, and analyze the scalability of these and other existing schemes. An efficient formulation of tree search on an SIMD machine consists of two major components: a triggering mechanism, which determines when the search space redistribution must occur to balance the search space over processors, and a scheme to redistribute the search space. We have devised a new redistribution mechanism and a new triggering mechanism. Either of these can be used in conjunction with triggering and redistribution mechanisms developed by other researchers. We analyze the scalability of these mechanisms and verify the results experimentally. The analysis and experiments show that our new load-balancing methods are highly scalable on SIMD architectures. Their scalability is shown to he no worse than that of the best load-balancing schemes on MIMD architectures. We verify our theoretical results by implementing the 15-puzzle problem on a CM-2 SIMD parallel computer     

Quantization effects in digitally behaving circuit implementationsof Kohonen networks

Implementing a neural network on a digital or mixed analog and digital chip yields the quantization of the synaptic weights dynamics. This paper addresses this topic in the case of Kohonen's self-organizing maps. We first study qualitatively how the quantization affects the convergence and the properties, and deduce from this analysis the way to choose the parameters of the network (adaptation gain and neighborhood). We show that a spatially decreasing neighborhood function is far more preferable than the usually rectangular neighborhood function, because of the weight quantization. Based on these results, an analog nonlinear network, integrated in a standard CMOS technology, and implementing this spatially decreasing neighborhood function is then presented. It can be used in a mixed analog and digital circuit implementation.     

Bounded disorder file organization

The bounded disorder file organization proposed by W. Litwin and D.B. Lomet (1987) uses a combination of hashing and tree indexing. Lomet provided an approximate analysis with the mention of the difficulty involved in exact modeling of data nodes, which motivated this work. In an earlier paper (M.V. Ramakrishna and P. Mukhopadhyay, 1988) we provided an exact model and analysis of the data nodes, which is based on the solution of a classical sequential occupancy problem. After summarizing the analysis of data nodes, an alternate file growth method based on repeated trials using universal hashing is proposed and analyzed. We conclude that the alternate file growth method provides simplicity and significant improvement in storage utilization     

Machine independent AND and OR parallel execution of logicprograms. I. The binding environment

We describe a binding environment for the AND and OR parallel execution of logic programs that is suitable for both shared and nonshared memory multiprocessors. The binding environment was designed with a view of rendering a compiler using this binding environment machine independent. The binding environment is similar to closed environments proposed by J. Conery. However, unlike Conery's scheme, it supports OR and independent AND parallelism on both types of machines. The term representation, the algorithms for unification and the join algorithms for parallel AND branches are presented in this paper. We also detail the differences between our scheme and Conery's scheme. A compiler based on this binding environment has been implemented on a platform for machine independent parallel programming called the Chare Kernel     

Genetic evolution of the topology and weight distribution of neuralnetworks

This paper proposes a system based on a parallel genetic algorithm with enhanced encoding and operational abilities. The system, used to evolve feedforward artificial neural networks, has been applied to two widely different problem areas: Boolean function learning and robot control. It is shown that the good results obtained in both cases are due to two factors: first, the enhanced exploration abilities provided by the search-space reducing evolution of both coding granularity and network topology, and, second, the enhanced exploitational abilities due to a recently proposed cooperative local optimizing genetic operator.     

Connectivity and performance tradeoffs in the cascade correlationlearning architecture

The cascade correlation is a very flexible, efficient and fast algorithm for supervised learning. It incrementally builds the network by adding hidden units one at a time, until the desired input/output mapping is achieved. It connects all the previously installed units to the new unit being added. Consequently, each new unit in effect adds a new layer and the fan-in of the hidden and output units keeps on increasing as more units get added. The resulting structure could be hard to implement in VLSI, because the connections are irregular and the fan-in is unbounded. Moreover, the depth or the propagation delay through the resulting network is directly proportional to the number of units and can be excessive. We have modified the algorithm to generate networks with restricted fan-in and small depth (propagation delay) by controlling the connectivity. Our results reveal that there is a tradeoff between connectivity and other performance attributes like depth, total number of independent parameters, and learning time.     

MEETING THE IT CHALLENGES OF BUSINESS The Changing Mandate for MBAs

What is the implication for business when information technology (IT) changes in the workplace without a commensurate change in the composition of business programs educating tomorrow's employees? A survey of MBA graduates forms the basis of this article on the IT skills needed in the marketplace.