Search
Join ACM

Software Engineering and Programming Languages

Advertisement

Research and Advances

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

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

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

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

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

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

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

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

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

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
Research and Advances

Some practical experience with a software quality assurance program

Within a production programming environment, a software quality assurance program (QAP) was instituted to produce standards, conventions, and methodologies for all phases of the software development process. Software language standards and several support processors, in turn, developed. The authors offer a plan which may help others avoid some of the pitfalls they experienced while attempting to construct a meaningful software QAP.
and
Research and Advances

Control flow and data structure documentation: two experiments

Two experiments were carried out to assess the utility of external documentation aids such as macro flowcharts, pseudocode, data structure diagrams, and data structure descriptions. A 223 line Pascal program which manipulates four arrays was used. The program interactively handles commands that allow the user to manage five lists of items. A comprehension test was given to participants along with varying kinds of external documentation. The results indicate that for this program the data structure information was more helpful than the control flow information, independently of whether textual or graphic formats were used.

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