A software design method for real-time systems
DARTS—a design method for real-time systems—leads to a highly structured modular system with well-defined interfaces and reduced coupling between tasks.
Computing Applications
Advertisement
Development and application of NASA’s first standard spacecraft computer
To provide the autonomy needed by low, earth-orbiting satellites, NASA's first standard on-board processor requires changing only interfacing hardware from mission to mission.
Design, development, integration: space shuttle primary flight software system
The development of Space Shuttle software posed unique requirements above and beyond raw size (30 times larger than Saturn V software), complexity, and criticality.
Hardware protection against software piracy
A system that prevents illicit duplication of proprietary software is suggested. It entails the customization of the programs for each computer by encryption. The use of a public key cryptogram for this purpose means that anyone can customize programs, but neither other programmers nor the people having complete access to the target computer can obtain copies that will run on other machines. A possible implementation of the system is considered in some detail. It is based on a hardware security unit that is attached to the computer and that decrypts and obeys some parts of the program.
Improved interpretation of UNIX-like file names embedded in data
When the data processed by a program span several files, the common practice of including file names as data in some of the files leads to difficulties in moving or sharing that data. In systems using tree structured directories, this problem can be solved by making a syntactic distinction between absolute and relative file names.
Memory occupancy patterns in garbage collection systems
Some programming languages and computer systems use dynamic memory allocation with garbage collection. It would be useful to understand how the utilization of memory depends on the stochastic parameters describing the size and life distributions of the cells. We consider a class of dynamic storage allocation systems which use a first-fit strategy to allocate cells and perform noncompacting garbage collections to recover free memory space when memory becomes fully occupied. A formula is derived for the expected number of holes (available cells) in memory immediately following a garbage collection which specializes to an analogue of Knuth's 'Fifty Percent' rule for nongarbage-collection systems. Simulations confirm the rule for exponentially distributed cell lifetimes. Other lifetime distributions are discussed. The memory-size requirements for noncompacting garbage collection are also analyzed.
The EAS-E application development system: principles and language summary
EAS-E is based on the entity-attribute-set view of system description—a useful formalism for system modeling and planning even when programming is done in languages other than EAS-E.
Determinants of program repair maintenance requirements
Considerable resources are devoted to the maintenance of programs including that required to correct errors not discovered until after the programs are delivered to the user. A number of factors are believed to affect the occurrence of these errors, e.g., the complexity of the programs, the intensity with which programs are used, and the programming style. Several hundred programs making up a manufacturing support system are analyzed to study the relationships between the number of delivered errors and measures of the programs' size and complexity (particularly as measured by software science metrics), frequency of use, and age. Not surprisingly, program size is found to be the best predictor of repair maintenance requirements. Repair maintenance is more highly correlated with the number of lines of source code in the program than it is to software science metrics, which is surprising in light of previously reported results. Actual error rate is found to be much higher than that which would be predicted from program characteristics.
Pass-algorithms: a user validation scheme based on knowledge of secret algorithms
A superset of the secondary passwords technique, pass-algorithms provide enormous flexibility and ease of implementation and represent an attractive alternative to more costly systems security features and equipment. The method validates users who demonstrate knowledge of a secret algorithm rather than a password.
The median filter is well-known [1, 2]. However, if a user wishes to predefine a set of feature types to remove or retain, the median filter does not necessarily satisfy the requirements. A more general filter, called the Weighted Median Filter, of which the median filter is a special case, is described. It enables filters to be designed with a wide variety of properties. Particular cases of filter requirements are discussed and the corresponding filters are derived. The notion of a minimal weighted median filter, of a subclass that act identically, is introduced and discussed. The question of finding the number of distinct ways a class of filters can act is considered and solved for some classes.
We are entering a new era in very high performance computing that will be dominated by parallel architectured systems. It is critical for the United States to maintain its leadership as this new era, with its broadened applications, evolves over the next decade. Toward this end the National Science Foundation sponsored a workshop in November 1983 to focus the collective strength of universities, industry, and government on projects for development of knowledge-intensive industries.
Reflections on software research
Can the circumstances that existed in Bell Labs that nurtured the UNIX project be produced again?
To what extent should one trust a statement that a program is free of Trojan horses? Perhaps it is more important to trust the people who wrote the software.
Training wheels in a user interface
New users of high-function application systems can become frustrated and confused by the errors they make in the early stages of learning. A training interface for a commercial word processor was designed to make typical and troublesome error states “unreachable,” thus eliminating the sources of some new-user learning problems. Creating a training environment from the basic function of the system itself afforded substantially faster learning coupled with better learning achievement and better performance on a comprehension post-test. A control group spent almost a quarter of their time recovering from the error states that the training interface blocked off. We speculate on how this training strategy might be refined, and more generally, on how function should be organized in a user interface.
Data that are missing, lost, or incomplete can be very significant in certain situations. Programs and languages need to be able to identify and manage such data effectively.
Visibility aspects of programmed dynamic data structures
Unlike static structures, dynamic Pascal-like data structures often suffer visibility problems due to the unrestricted use of the general pointer mechanism. By classifying these structures and identifying the different kinds of pointers, a methodology is proposed for achieving improved visibility.
A null-object detection algorithm for constructive solid geometry
Constructive solid geometry (CSG) is the primary scheme used for representing solid objects in many contemporary solid modeling systems. A CSG representation is a binary tree whose nonterminal nodes represent Boolean operations and whose terminal nodes represent primitive solids. This paper deals with algorithms that operate directly on CSG representations to solve two computationally difficult geometric problems—null-object detection (NOD) and same-object detection (SOD). The paper also shows that CSG trees representing null objects may be reduced to null trees through the use of a new concept called primitive redundancy, and that, on average, tree reduction can be done efficiently by a new technique called spatial localization. Primitive redundancy and spatial localization enable a single complex instance of NOD to be converted into a number of simpler subproblems and lead to more efficient algorithms than those previously known.
Computer graphics comes of age: an interview with Andries Van Dam
Andries van Dam describes major advances in computer graphics over the past 25 years and discusses future directions.
Audit trail compaction for database recovery
Total elapsed recovery time from disk-based database corruption can be shortened by reprocessing the audit trail off-line and thereby avoiding excessive resource utilization penalties. Using a bit map, the audit trail is compacted by eliminating irrelevant or superseded records. The compacted trail is then partitioned, and the partitions are processed in parallel.
Where can you find a solid, forthright overview of the computer systems and management behind airline reservations? NASA's space shuttle? Or any of the multitude of other large computer systems that support important projects or national activities? It's hard, sometimes impossible: partly because the people who worked on such systems often do not have the time to write about their experiences: and partly because many professional journalists who interview these people do not have the technical background to ferret out answers to the fundamental design questions addressed in these systems.
File organization: implementation of a method guaranteeing retrieval in one access
A new file organization method that guarantees retrieval of any record in one access is tested on two existing files, producing empirical results that compare favorably with theoretical predictions. The description of the method includes the algorithms used for implementing the required hashing and signature functions.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More