Summary This paper shows how to simplify and speed up distributed JR program start‐up. We accomplish this goal by extending JR's operation abstraction so that it includes the creation of virtual machines and remote objects, the key components in distributed JR programs. This extension is conceptually simple, fits well with the rest of the JR language, and provides additional flexibility. Extending JR's operation abstraction yields a considerably less complex solution and a simpler implementation than other approaches, which would have led to redundant or ad‐hoc language mechanisms. The extension also allows for reduced distributed JR program start‐up costs because the creation of virtual machines and remote objects can now be done in parallel. This paper also describes how we have simulated this extension and have implemented a prototype that provides this extension. These reflect closely what we would need to do to actually include the extension within the standard JR implementation. Using the simulation and prototype, we obtained performance data on a few typical distributed applications written to use the extension. The data show large reductions, ranging from about 50% to 95%, in distributed JR program start‐up times. Our experiments also explored a few strategies to further reduce start‐up times, but, among our strategies, the straightforward strategies seem the best. This paper also discusses design alternatives for creating virtual machines and remote objects. Our experience suggests that the proposed extension to JR's operation abstraction is actually worthwhile to add to the standard JR language and implementation.

Summary The JR concurrent programming language extends Java with a richer concurrency model, by adding several new types and statements. JR provides dynamic remote virtual machine creation, dynamic remote object creation, remote method invocation, dynamic process creation, rendezvous, asynchronous message passing, semaphores, concurrent invocation, and shared variables. This paper presents RJ, a package for Java that provides JR‐like features. The paper gives an overview of RJ and its key features; describes the implications of RJ's design, including how RJ provides additional, useful flexibility; discusses the implementation of RJ; and gives qualitative and quantitative evaluations of our work with respect to feasibility and usability, experimentation, migration, and performance. RJ has been successful in meeting these goals and in providing insight into the trade‐offs between using a concurrent programming language versus using the equivalent concurrent package. Our work has yielded a few surprises in dealing with some concurrent programming language features, in understanding the run‐time performances of JR versus RJ programs, and in obtaining some additional, useful flexibility for concurrent programming applications. Copyright © 2015 John Wiley & Sons, Ltd.

Summary Many message passing languages and packages include some form of synchronous invocation. In a synchronous invocation, the invoker waits for the invocation's servicer to pass back results. A synchronous invocation can be viewed as a pair of asynchronous invocations: one—initiating the computation—with parameter values from the invoker to the servicer and the other—once the requested computation has completed—with the ‘go‐ahead’ and return value from the servicer to the invoker. The target of the latter invocation is known as thereply operation, and a reference to it is known as areply capability. This paper addresses the issues of making such reply capabilities directly accessible to user code. It presents the design and prototype implementation of a new version of the JR concurrent programming language, called xJR, in which the reply capability can be explicit. This paper gives xJR examples, including realistic ones, to highlight the additional flexibility the new features offer (such as a non‐lexical reply). These additional features do not impact the run‐time performance of existing JR features and can even lead to more efficient code in some programming scenarios. Our experience with the prototype implementation indicates that an actual implementation would be fruitful and would preserve the prototype's performance advantages. Copyright © 2015 John Wiley & Sons, Ltd.

Summary Message passing notations (language, package, etc.) typically include some form of asynchronous or synchronous invocation. In a synchronous invocation, the invoker waits for the invocation's servicer to pass back results. Some message passing notations also include early reply or deferred reply (including forwarding), which alters how and when the servicer passes back its results; this additional flexibility is useful in realistic applications. It is well known how to transform a synchronous invocation into only asynchronous invocations. This paper extends such transformations to early reply and forward. This paper also describes the use of these transformations within the implementations of programming notations. Using the transformation simplifies the implementation without significantly affecting run‐time costs. Copyright © 2015 John Wiley & Sons, Ltd.

SUMMARY Over the last decade, the popularity of Python has increased considerably. Python is widely used and has been demonstrated to be effective over many problem domains including scripting, prototyping, and simulation. Python's easy to use and concise syntax is highly expressive and allows a developer to create considerably shorter and easier to understand programs than semantically equivalent programs written in languages like C, C++, or Java. An important aspect of any language's flexibility is a highly parallelizable environment that allows its users to write concurrent programs. However, Python is still lacking a high‐level, expressive concurrent and distributed programming environment. This paper presents our experience creating PySy, a Python package (on the basis of the SR and JR concurrent programming languages), which provides an easy to use and expressive concurrent environment and allows for the distributed sharing of resources. This paper discusses our design decisions, describes our implementation, and shows qualitative and quantitative analyses of well‐known concurrent programs written in PySy. Overall, PySy is reasonable to use for expressing the more common programming scenarios, while it provides acceptable performance. Copyright © 2012 John Wiley & Sons, Ltd.

SUMMARY This paper describes our work to improve the performance of distributed applications. We aim at certain application characteristics such as balancing load, allowing separately written applications to work better together, allowing a distributed application to adapt its behavior in more flexible ways, and so on. Our approach is to write application‐specific schedulers, which can access the global state of the application in making scheduling decisions. To achieve this goal, we extended our earlier work on CATAPULTS (Creating And Testing APplication‐specific User Level Thread Schedulers), a domain‐specific language for creating and testing application‐specific user‐level thread schedulers, to distributed applications by adding ‘master schedulers’ for dealing with the distributed parts of applications. This paper presents our design of, experimentation with, and implementation of distributed CATAPULTS. This paper presents several realistic examples to measure the feasibility of this approach, specifically: a website application, an embedded application, and load balancing. Each example has a scheduling goal for which we developed a customized scheduler. We measured the performance with and without the customized scheduler. The customized scheduler for each example was fairly straightforward to develop and each achieved its scheduling goal. Copyright © 2011 John Wiley & Sons, Ltd.

SUMMARY This paper describes CATAPULTS (CreatingAndTestingAPplication‐specificUserLevelThreadSchedulers), a domain‐specific language for creating and testing application‐specific user‐level thread schedulers. Using a domain‐specific language to write user‐level thread schedulers provides three advantages. First, doing so modularizes the thread scheduler, making it easy to plug in and experiment with different thread scheduling strategies. Second, using a domain‐specific language for scheduling code helps prevent several of the common programming mistakes that are easy to make when developing thread schedulers. Finally, the CATAPULTS translator has multiple backends that generate code for different languages and libraries. This makes it easy to prototype an application in a high‐level language and then later port it to a low‐level language; the CATAPULTS translator will take care of generating the appropriate code for both the prototype and the final version of the program from a single scheduler specification. This paper describes how we have used CATAPULTS to improve the performance of two important and representative Internet server applications. Copyright © 2011 John Wiley & Sons, Ltd.

Abstract The global quiescence (GQ) of a distributed computation (or distributed termination detection) is an important problem. Some concurrent programming languages and systems provide GQ detection as a built‐in feature so that programmers do not need to write special synchronization code to detect quiescence. This paper introducespartial quiescence(PQ), which generalizes quiescence detection to a specified part of a distributed computation. PQ is useful, for example, when two independent concurrent computations that both rely on GQ need to be combined into a single program. The paper describes how we have designed and implemented a PQ mechanism within an experimental version of the JR concurrent programming language, and have gained experience with several representative applications. Our early results are promising qualitatively and quantitatively. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract This paper introduces program chipping, a simple yet effective technique to isolate bugs. This technique automatically removes or chips away parts of a program so that the part that contributes to some symptomatic output becomes more apparent to the user. Program chipping is similar in spirit to traditional program slicing and debugging techniques, but chipping uses very simple techniques based on the syntactic structure of the program. We have developed a chipping tool for Java programs, called ChipperJ, and have run it on a variety of small to large programs, including a Java compiler, looking for various symptoms. The results are promising. The reduced program is generally about 20–35% of the size of the original. ChipperJ takes less than an hour on large programs to perform this reduction; even if it took overnight, that would be reasonable if it saves the developer time. Copyright © 2006 John Wiley & Sons, Ltd.

Recovering design patterns can enhance existing source code analysis tools by bringing program understanding to the design level. This paper presents a new, fully automated pattern detection approach. The new approach is based on our reclassification of the GoF patterns by their pattern intent. We argue that the GoF pattern catalog classifies design patterns in the forward-engineering sense; our reclassification is better suited for reverse engineering. Our approach uses lightweight static program analysis techniques to capture program intent. This paper also describes our tool, PINOT, that implements this new approach. PINOT detects all the GoF patterns that have concrete definitions driven by code structure or system behavior. Our tool is faster, more accurate, and targets more patterns than existing pattern detection tools. PINOT has been used successfully in detecting patterns in Java AWT, JHotDraw, Swing, Apache Ant, and many other programs and packages

This paper describes CATAPULTS, a domain-specific language for creating and testing application-specific user level thread schedulers. Using a domain-specific language to write thread schedulers provides three advantages. First, it modularizes the thread scheduler, making it easy to plug in and experiment with different schedulers. Second, using a domain-specific language for scheduling code helps prevent several of the common programming mistakes that are easy to make when programming in low-level C or assembly. Finally, the CATAPULTS translator has multiple backends that generate code for different languages and libraries. This makes it easy to prototype an embedded application on a regular PC, and then develop the final version on the embedded hardware; the CATAPULTS translator will take care of generating the appropriate code for both the PC prototype and the final embedded version of the program. Using our implementation of CATAPULTS for Z-World's embedded Rabbit processors, we obtained a performance gain of about 12.6% at the expense of about 12.7% increase in code size for a fairly typical embedded application.

Abstract Two models of thread execution are the general concurrent programming execution model (CP) and the cooperative multithreading execution model (CM). CP provides nondeterministic thread execution where context switches occur arbitrarily. CM provides threads that execute one at a time until they explicitly choose to yield the processor. This paper focuses on a classic application to reveal the advantages and disadvantages of load balancing during thread execution under CP and CM styles; results from a second classic application were similar. These applications are programmed in two different languages (SR and Dynamic C) on different hardware (standard PCs and embedded system controllers). An SR‐like run‐time system, DesCaRTeS, was developed to provide interprocess communication for the Dynamic C implementations. This paper compares load balancing and non‐load balancing implementations; it also compares CP and CM style implementations. The results show that in cases of very high or very low workloads, load balancing slightly hindered performance; and in cases of moderate workload, both SR and Dynamic C implementations of load balancing generally performed well. Further, for these applications, CM style programs outperform CP style programs in some cases, but the opposite occurs in some other cases. This paper also discusses qualitative tradeoffs between CM style programming and CP style programming for these applications. Copyright © 2004 John Wiley & Sons, Ltd.

Java provides a clean object-oriented programming model and allows for inherently system-independent programs. Unfortunately, Java has a limited concurrency model, providing only threads and remote method invocation (RMI).The JR programming language extends Java to provide a rich concurrency model, based on that of SR. JR provides dynamic remote virtual machine creation, dynamic remote object creation, remote method invocation, asynchronous communication, rendezvous, and dynamic process creation. JR's concurrency model stems from the addition of operations (a generalization of procedures) and JR supports the redefinition of operations through inheritance. JR programs are written in an extended Java and then translated into standard Java programs. The JR run-time support system is also written in standard Java.This paper describes the JR programming language and its implementation. Some initial measurements of the performance of the implementation are also included.

Abstract This paper presents a comparison of the cooperative multithreading model with the general concurrent programming model. It focuses on the execution time performance of a range of standard concurrent programming applications. The overall results are mixed. In some cases, programs written in the cooperative multithreading model outperform those written in the general concurrent programming model. The contributions of this paper are twofold. First, it presents a thorough analysis of the performances of applications in the different models, i.e. to explain the criteria that determine when a program in one model will outperform an equivalent program in the other. Second, it examines the tradeoffs in writing programs in the different programming styles. In some cases, better performance comes at the cost of more complicated code. Copyright © 2003 John Wiley & Sons, Ltd.

Abstract Earlier work suggests that program transformations can simplify program verification. A given program containing complex language features is transformed into a semantically equivalent program containing only simpler language features. The transformed program is proven using a set of proof rules for only the simpler features. That approach was illustrated by transforming a given program that may contain multiple‐level escape statements within nested loops into an equivalent program that contains no escape statements. This paper gives additional transformations, which map a given program that may contain multiple‐level escape statements to a semantically equivalent program (TP) that contains only single‐level escape statements. The proof of TP uses proof rules for single‐level escape statements, or the earlier transformations further map TP to a program with no escape statements, whose proof uses proof rules for loops without escape statements. This paper also discusses escape statements where the number of levels is determined at run‐time. Copyright © 2002 John Wiley & Sons, Ltd.

Java provides a clean object-oriented programming model and allows for inherently system-independent programs. Unfortunately, Java has a limited concurrency model, providing only threads and remote method invocation (RMI). The JR programming language extends Java to provide a rich concurrency model. JR provides dynamic remote virtual machine creation, dynamic remote object creation, remote method invocation, asynchronous communication, rendezvous, and dynamic process creation. JR programs are written in an extended Java and then translated into standard Java programs. The JR run-time support system is also written in standard Java. This paper describes the JR programming language and its implementation. Some initial measurements of the performance of the implementation are also included.

Reproducing the execution of a concurrent program is important in debugging and testing. It requires that, regardless of the actual order in which processes may execute, the reproduced execution is identical, with respect to the order in which certain activities occur, to a previously recorded execution. This paper presents a solution to the reproducibility problem for programs written in the SR concurrent programming language. Our solution transforms an arbitrary SR program into one for recording an event sequence and one for replaying from an event sequence. SR provides a rich collection of synchronization mechanisms, including rendezvous, asynchronous message passing, remote procedure call, and dynamic process creation. SR language features allow: flexible invocation servicing (e.g. use of invocation parameters in selecting an invocation to service in message passing or rendezvous); dynamically created processes and resource (module) instances; dynamic communication paths between processes; and dynamic distribution of programs across multiple machines. Because of these features, adaptations of previous solutions to the reproducibility problem for other languages and notations do not work for SR. Our solution handles all the above features. It results in a naturally distributed control algorithm for programs that are distributed. This paper also describes the implementations of our transformation tools. Copyright © 1999 John Wiley & Sons, Ltd.

Although most typically used in other contexts, program transformations can simplify program verification by transforming a program containing complex language features into a semantically equivalent program containing only simpler language features. The proof of the transformed program can then be performed using a set of proof rules for only the simpler features. There are tradeoffs between the transformational approach and the standard approach to program verification with regard to proof understandability and compactness of programs and assertions, establishing soundness of the program verification method, and providing mechanized support for the method. The transformational approach has clear advantages in some of these aspects. This paper illustrates this transformational approach by considering proof rules for escape statements in iterative constructs, and discusses the tradeoffs with respect to its use. It also suggests how the approach can be applied to other language constructs, including some involving concurrency, and to solving some problems connected with the development of Hoare axiomatizations. Copyright © 1999 John Wiley & Sons, Ltd.

This paper presents a layered verification technique, called LVT, for the verification of distributed computing systems with multiple component layers. Each lower layer in such a system provides services in support of functionality of the higher layer. By taking a very general view of programming languages as interfaces of systems, LVT treats each layer in a distributed computing system as a distributed programming language. Each relatively higher-level language in the computing system is implemented in terms of a lower-level language. The verification of each layer in a distributed computing system can then be viewed as the verification of implementation correctness for a distributed language. This paper also presents the application of LVT to the verification of a distributed computing system, which has three layers: a small high-level distributed programming language; a multiple processor architecture consisting of an instruction set and system calls for inter-process message passing; and a network interface. Programs in the high-level language are implemented by a compiler mapping from the language layer to the multiprocessor layer. System calls are implemented by network services. LVT and its application demonstrate that the correct execution of a distributed program, most notably its inter-process communication, is verifiable through layers. The verified layers guarantee the correctness of (1) the compiled code that makes reference to operating system calls, (2) the operating system calls in terms of network calls, and (3) the network calls in terms of network transmission steps. The specification and verification involved are carried out by using the Cambridge Higher Order Logic (HOL) theorem proving system. Copyright © 1999 John Wiley & Sons, Ltd.

An attractive target for a computer system attacker is the router. An attacker in control of a router can disrupt communication by dropping or misrouting packets passing through the router. We present a protocol called WATCHERS that detects and reacts to routers that drop or misroute packets. WATCHERS is based on the principle of conservation of flow in a network: all data bytes sent into a node, and not destined for that node, are expected to exit the node. WATCHERS tracks this flow, and detects routers that violate the conservation principle. We show that WATCHERS has several advantages over existing network monitoring techniques. We argue that WATCHERS' impact on router performance and WATCHERS' memory requirements are reasonable for many environments. We demonstrate that in ideal conditions WATCHERS makes no false-positive diagnoses. We also describe how WATCHERS can be tuned to perform nearly as well in realistic conditions.

A program that accesses an out-of-bound array element can cause unexpected behaviour that is unacceptable to safety-critical or security-critical systems. Two traditional compile-time approaches to array bound checking are flow analysis and program verification. This paper presents a new approach, IFV, that integrates flow analysis and program verification techniques. IFV is generally about as effective as program verification yet runs in about the same time as flow analysis. Its typical runtime is proportional to the product of the program size and the number of declared variables. IFV matches loops to templates, which represent commonly occurring loop patterns, to discover loop invariants automatically, which it then uses to strengthen flow analysis. With only seven templates, it handles many common array-access patterns. Patterns not verified by flow analysis are processed with verification techniques entirely automatically. This paper also describes a prototype IFV system that performs compile-time array bound checking for programs in a subset of C. © 1997 John Wiley & Sons, Ltd.

We have recently implemented three preprocessors that, respectively, convert conditional critical region (CCR) notation, monitor notation, and Communicating Sequential Processes (CSP) notation into equivalent programs written in the SR concurrent programming language. The three preprocessors were built with \verb-cpp-, the C preprocessor. This paper describes our experience in this use of \verb-cpp- and especially how using \verb-cpp- influenced the design and implementation of the extended notations. This paper also describes the favorable experience obtained in using the preprocessors in several courses. The results should be of interest to others who are contemplating implementing language extensions.

Intrusion detection systems (IDSs) attempt to identify unauthorized use, misuse, and abuse of computer systems. In response to the growth in the use and development of IDSs, the authors have developed a methodology for testing IDSs. The methodology consists of techniques from the field of software testing which they have adapted for the specific purpose of testing IDSs. They identify a set of general IDS performance objectives which is the basis for the methodology. They present the details of the methodology, including strategies for test-case selection and specific testing procedures. They include quantitative results from testing experiments on the Network Security Monitor (NSM), an IDS developed at UC Davis. They present an overview of the software platform that has been used to create user-simulation scripts for testing experiments. The platform consists of the UNIX tool expect and enhancements that they have developed, including mechanisms for concurrent scripts and a record-and-replay feature. They also provide background information on intrusions and IDSs to motivate their work.

Abstract This paper describes a new approach to dynamic link/unlink editing. The basis of this approach is a library of link editing functions that can add compiled object code to or remove such code from a process any time during its execution. Loading modules, searching libraries, resolving external references, and allocating storage for global and static data structures are all performed at run time. This approach provides the efficiency of native machine code execution along with the flexibility to modify a program during its execution, thereby making many new applications possible. This paper also describes three sample applications of these dynamic link editing functions: program customization, incremental program development, and support for debugging and testing. A prototype of this approach is implemented under UNIX as a library package called dld for the C programming language and is available for VAX, Sun 3 and SPARCstation machines.

Abstract This paper describes a novel approach to event‐based debugging. The approach is based on a (coarsegrained) dataflow view of events: a high‐level event is recognized when an appropriate combination of lower‐level events on which it depends has occurred. Event recognition is controlled using familiar programming language constructs. This approach is more flexible and powerful than current ones. It allows arbitrary debugger language commands to be executed when attempting to form higher‐level events. It also allows users to specify event recognition in much the same way that they write programs. This paper also describes a prototype, Dalek, that employs the dataflow approach for debugging sequential programs. Dalek demonstrates the feasibility and attractiveness of the dataflow approach. One important motivation for this work is that current sequential debugging tools are inadequate. Dalek contributes toward remedying such inadequacies by providing events and a powerful debugging language. Generalizing the dataflow approach so that it can aid in the debugging of concurrent programs is under investigation.

Abstract This paper demonstrates the use of the SR concurrent programming language for discrete event simulation. SR provides a rich collection of synchronization mechanisms, whose use can lead to programs that are simpler and more efficient than those constrained to employ only one synchronization mechanism. Several SR solutions to a simulation problem are presented and contrasted with an Ada solution to the same problem. The paper also introduces a technique that exploits asynchronous message passing to program concise solutions to several problems involving lists. In the context of the simulation problem, this technique is used to manage the event list and the list of blocked processes. The technique can also be applied to several other concurrent programming problems. The results of this paper should be of interest both to programmers using concurrent programming languages and to language designers.

Comments are made on the above named work by G.M. Karam, C.M. Stanczyk, and G.W. Bond (see ibid., vol.15, no.11, p.1471-80, 1989), in which the semantics of the Ada rendezvous mechanism are discussed in terms of the critical race problem and a method is proposed for designing critical race-free programs. It is noted that this problem has been well described and numerous solutions have been presented in the literature during the past ten years (1980-90).>

Abstract This paper presents simple techniques that can be used to automate recompilation and avoid unnecessary recompilation in modular programming languages. The basic technique generates a Makefile that reflects the dependencies among modules. This technique is demonstrated for programs written in SR, although it can easily be adapted to other modular languages. The recompilation problem for SR programs is complicated by the flexible way components can be placed in source files and by how an SR module's specification and implementation can be combined. A small modification to the basic technique reduces the amount of unnecessary compilation. This ‘semi‐smart’ approach is worth the small extra effort. The techniques described in this paper should be considered as an inexpensive, yet reasonably effective, alternative to smart recompilation. These techniques are especially applicable when the language's compiler cannot easily be modified.

Abstract High‐level language primitives for concurrent programming exist in languages such as Ada and Modula‐2. However, each of these languages provides only a single means for specifying multitasking and synchronization, essential in the implementation of concurrent systems. The SR language provides several mechanisms for specifying multi‐tasking and synchronization, so it can be used to explore the performance of various communication techniques. This paper presents performance results for SR's multi‐tasking and synchronization mechanisms and discusses the effects of the generated code, the run‐time support and the hardware on these results. These results are compared with those for similar mechanisms in other languages, leading to some general conclusions about the performance of process communication primitives. These performance results can be used by programmers to make design choices that allow systems programs written in high‐level languages to meet real‐time performance specifications.

SR is a language for programming distributed systems ranging from operating systems to application programs. On the basis of our experience with the initial version, the language has evolved considerably. In this paper we describe the current version of SR and give an overview of its implementation. The main language constructs are still resources and operations. Resources encapsulate processes and variables that they share; operations provide the primary mechanism for process interaction. One way in which SR has changed is that both resources and processes are now created dynamically. Another change is that inheritance is supported. A third change is that the mechanisms for operation invocation—call and send—and operation implementation—proc and in—have been extended and integrated. Consequently, all of local and remote procedure call, rendezvous, dynamic process creation, asynchronous message passing, multicast, and semaphores are supported. We have found this flexibility to be very useful for distributed programming. Moreover, by basing SR on a small number of well-integrated concepts, the language has proved easy to learn and use, and it has a reasonably efficient implementation.