Search
Join ACM

Computing Applications

Advertisement

Research and Advances Jun 1 1982

Computer rendering of stochastic models

A recurrent problem in generating realistic pictures by computers is to represent natural irregular objects and phenomena without undue time or space overhead. We develop a new and powerful solution to this computer graphics problem by modeling objects as sample paths of stochastic processes. Of particular interest are those stochastic processes which previously have been found to be useful models of the natural phenomena to be represented. One such model applicable to the representation of terrains, known as “fractional Brownian motion,” has been developed by Mandelbrot. The value of a new approach to object modeling in computer graphics depends largely on the efficiency of the techniques used to implement the model. We introduce a new algorithm that computes a realistic, visually satisfactory approximation to fractional Brownian motion in faster time than with exact calculations. A major advantage of this technique is that it allows us to compute the surface to arbitrary levels of details without increasing the database. Thus objects with complex appearances can be displayed from a very small database. The character of the surface can be controlled by merely modifying a few parameters. A similar change allows complex motion to be created inexpensively.
, , and
Research and Advances May 1 1982

Estimating and improving the quality of information in a MIS

Most discussions of MIS's assume that the information in the records is error-free although it is recognized that errors exist. These errors occur because of delays in processing times, lengthy correction times, and, overly or insufficiently stringent data edits. In order to enable the user to implement data edits and correction procedures tailored to the degree of accuracy needed, this paper presents functional relationships between three common measures of data quality. The MIS addressed is one where records in a MIS are updated as changes occur to the record, e.g., a manpower planning MIS where the changes may relate to a serviceman's rank or skills. Since each of the updating transactions may contain an error, the transactions are subjected to various screens before the stored records are changed. Some of the transactions including some that are correct, are rejected; these are reviewed manually and corrected as necessary. In the meantime, the record is out of date and in error. Some of the transactions that were not rejected also lead to errors. The result is that at any given time the MIS record may contain errors. For each of several error control mechanisms, we show how to forecast the level of improvement in the accuracy of the MIS record if these options are implemented.
Research and Advances May 1 1982

On an improved algorithm for decentralized extrema finding in circular configurations of processors

This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2N*floor(lg N) + 3N messages in the worst case, compared to Chang and Roberts' N(N + 1)/2 and Hirschberg and Sinclair's 8N + 8*ceiling(N lg N) messages. The technique is a selective elimination of possible processes, which then merely relay future messages between the remaining contenders.
Research and Advances May 1 1982

Contemporary software development environments

There are a wide variety of software development tools and methods currently available or which could be built using current research and technology. These tools and methods can be organized into four software development environments, ranging in complexity from a simple environment containing few automated tools or expensive methods to a complete one including many automated tools and built around a software engineering database. The environments were designed by considering the life-cycle products generated during two classes of software development projects. Relative cost figures for the environments are offered and related issues, such as standardization, effectiveness, and impact, then addressed.
Research and Advances May 1 1982

Analysis of pointer “rotation”

Two high-level pointer operations, rotation and slide, reduce conceptual difficulties when writing pointer programs and increase the reliability of programs. We analyze theoretically as well as empirically why these operations are more convenient and introduce a mechanically checkable notion of the safety of rotations. Several examples show that safety is a good indication of program correctness. Examples of list marking and list copying programs demonstrate the utility of these operations.
Research and Advances Apr 1 1982

Grapevine: an exercise in distributed computing

Grapevine is a multicomputer system on the Xerox research internet. It provides facilities for the delivery of digital messages such as computer mail; for naming people, machines, and services; for authenticating people and machines; and for locating services on the internet. This paper has two goals: to describe the system itself and to serve as a case study of a real application of distributed computing. Part I describes the set of services provided by Grapevine and how its data and function are divided among computers on the internet. Part II presents in more detail selected aspects of Grapevine that illustrate novel facilities or implementation techniques, or that provide insight into the structure of a distributed system. Part III summarizes the current state of the system and the lesson learned from it so far.
, , , and
Research and Advances Apr 1 1982

Cryptographic sealing for information secrecy and authentication

A new protection mechanism is described that provides general primitives for protection and authentication. The mechanism is based on the idea of sealing an object with a key. Sealed objects are self-authenticating, and in the absence of an appropriate set of keys, only provide information about the size of their contents. New keys can be freely created at any time, and keys can also be derived from existing keys with operators that include Key-And and Key-Or. This flexibility allows the protection mechanism to implement common protection mechanisms such as capabilities, access control lists, and information flow control. The mechanism is enforced with a synthesis of conventional cryptography, public-key cryptography, and a threshold scheme.
Research and Advances Apr 1 1982

A comparison of two network-based file servers

This paper compares two working network-based file servers, the Xerox Distributed File System (XDFS) implemented at the Xerox Palo Alto Research Center, and the Cambridge File Server (CFS) implemented at the Cambridge University Computer Laboratory. Both servers support concurrent random access to files using atomic transactions, both are connected to local area networks, and both have been in service long enough to enable us to draw lessons from them for future file servers. We compare the servers in terms of design goals, implementation issues, performance, and their relative successes and failures, and discuss what we would do differently next time.
and
Research and Advances Apr 1 1982

Performing remote operations efficiently on a local computer network

A communication model is described that can serve as a basis for a highly efficient communication subsystem for local networks. The model contains a taxonomy of communication instructions that can be implemented efficiently and can be a good basis for interprocessor communication. These communication instructions, called remote references, cause an operation to be performed by a remote process and, optionally, cause a value to be returned. This paper also presents implementation considerations for a communication system based upon the model and describes an experimental communication subsystem that provides one class of remote references. These remote references take about 150 microseconds or 50 average instruction times to perform on Xerox Alto computers connected by a 2.94 megabit Ethernet.
Research and Advances Apr 1 1982

A technique for testing command and control software

A technique for testing embedded-microprocessor command and control programs is described. The continuity inherent in functions computed by programs which monitor natural phenomena is exploited by a simple difference equation-based algorithm to predict a program's next output from its preceding ones. The predicted output is compared with the actual output while indexing through the program's domain. Outputs which cannot be predicted are flagged as potential errors. Data are presented which show that this technique can be a sensitive measure of a program's correctness.
Research and Advances Mar 1 1982

The “worm” programs—early experience with a distributed computation

The “worm” programs were an experiment in the development of distributed computations: programs that span machine boundaries and also replicate themselves in idle machines. A “worm” is composed of multiple “segments,” each running on a different machine. The underlying worm maintenance mechanisms are responsible for maintaining the worm—finding free machines when needed and replicating the program for each additional segment. These techniques were successfully used to support several real applications, ranging from a simple multimachine test program to a more sophisticated real-time animation system harnessing multiple machines.
and
Research and Advances Mar 1 1982

The future of programming

The nature of programming is changing. These changes will accelerate as improved software development practices and more sophisticated development tools and environments are produced. This paper surveys the most likely changes in the programming task and in the nature of software over the short term, the medium term, and the long term. In the short term, the focus is on gains in programmer productivity through improved tools and integrated development environments. In the medium term, programmers will be able to take advantage of libraries of software components and to make use of packages that generate programs automatically for certain kinds of common systems. Over the longer term, the nature of programming will change even more significantly as programmers become able to describe desired functions in a nonprocedural way, perhaps through a set of rules or formal specification languages. As these changes occur, the job of the application programmer will become increasingly analysis-oriented and software developers will be able to attack a large number of application areas which could not previously be addressed effectively.
and

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 Involved

Communications 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