Product configuration is a major industrial application domain for constraint satisfaction techniques. Conditional constraint satisfaction problems (CCSPs) have been developed to represent configuration problems in a natural way. CCSPs are like constraint satisfaction problems (CSPs), but they may also include potential variables, which might or might not exist in any given solution, as well as classical variables, which are required to take a value in every solution. CCSPs model, for example, options on a car, for which the style of sunroof (a variable) only makes sense if the car has a sunroof at all. We show that existing techniques from formal methods and answer set programming can be used to naturally model CCSPs. We demonstrate configurators in both approaches. An advantage of these approaches is that the model builder does not have to reformulate the CCSP into a classic CSP, converting potential variables into classical variables by adding a ¿does not exist¿' value and modifying the problem constraints. Our configurators automatically reason about the model itself, enumerating all solutions and discovering several kinds of model flaws.

Abstract Logic programming requires that the programmer convert a problem into a set of constraints based on predicates. Choosing the predicates and introducing appropriate constraints can be intricate and error prone. If the problem domain is structured enough, we can let the programmer express the problem in terms of more abstract, higher‐level constraints. A compiler can then convert the higher‐level program into a logic‐programming formalism. The compiler writer can experiment with alternative low‐level representations of the higher‐level constraints in order to achieve a high‐quality translation. The programmer can then take advantage of both a reduction in complexity and an improvement in runtime speed for all problems within the domain. We apply this analysis to the domain of tabular constraint‐satisfaction problems. Examples of such problems include logic puzzles solvable on a hatch grid and combinatorial problems such as graph coloring and independent sets. The proper abstractions for these problems are rows, columns, entries, and their interactions. We present a higher‐level language, Constraint Lingo, dedicated to problems in this domain. We also describe how we translate programs from Constraint Lingo into lower‐level logic formalisms such as the logic of propositional schemata. These translations require that we choose among competing lower‐level representations in order to produce efficient results. The overall effectiveness of our approach depends on the appropriateness of Constraint Lingo, our ability to translate Constraint Lingo programs into high‐quality representations in logic formalisms, and the efficiency with which logic engines can compute answer sets. We comment on our computational experience with these tools in solving both graph problems and logic puzzles. Copyright © 2004 John Wiley & Sons, Ltd.

Unix administration in large sites must maintain a coherent organization of software across many machines of different architectures and operating systems. This paper describes the Sat package of tools intended for system administrators. The Sat package is centered around a distributed database manager that stores data pertaining to machines and users. The database provides replication, access control, and locking. It can be queried directly by programs in the Sat package and by programs written in scripting languages like Sal and Perl. When data change, programs run automatically on each host to rebuild its configuration files based on the data, the architecture of the host, and any host-specific requirements. The paper shows how these tools have been used in practice, and how various features have been reworked, enhanced, de-emphasized, or abandoned through ten years of experience. This package is currently in heavy use at the University of Kentucky Department of Computer Science. Copyright © 1999 John Wiley & Sons, Ltd.

Many problems can crop up unexpectedly on Unix computers, and the administrator must be able to detect and react to these problems quickly. If a site has more than a few computers, the effort needed to keep abreast of problems can lead to unresponsive administration. Pulse monitors form a simple but effective tool to assist the administrator in this task. This paper describes the Pulsar pulse-monitor package. It is composed of a presenter, which provides a graphical user interface to the administrator, a set of individual pulse monitors, which examine aspects of the status on a host and communicate their results to the presenter, and a scheduler, which executes pulse monitors according to the frequency specified by its configuration files. The set of pulse monitors is easily extended by the administrator to provide warnings about any situation that can be algorithmically detected. © 1997 John Wiley & Sons, Ltd.

This paper presents PCSMA, an extension to the CSMA/CD protocol (used in the Ethernet) to support both conventional datagram traffic and real-time traffic. The protocol provides predictable packet-delivery bounds for real-time traffic. It does not require changes to existing Ethernet controllers for datagram traffic. Under the new protocol, periodic sources follow a variation of the CSMA protocol that requires them to reserve transmission slots before they can begin transmission. This protocol is intended particularly for use in the integrated network in a manufacturing shop. Periodic sources include multiple sensors generating disparate types and rates of data. We have carried out an extensive performance evaluation of the protocol using a simulation model. The results are impressive: PCSMA shows fewer collisions than CSMA, equivalent delays for conventional traffic, and no failures to meet deadlines for periodic traffic.>

Abstract Most distributed operating systems are built with a kernel replicated in each machine that supports only basic interprocess communication (IPC) and process control. All other system services, such as memory management, file system, and name service, are distributed in a set of utility servers, which are ordinary processes (except perhaps for some privileges) residing at various machines. Design and implementation of such utility servers in distributed environments are far different from those in a centralized system. This paper presents our experience in building utility servers in Charlotte, a message‐based distributed operating system running on a loosely‐coupled multicomputer. Utility services in Charlotte are provided by server squads. Each member in a squad covers services to its own community. The squad as a whole co‐operatively provides services to the entire system. These servers are designed with the goals of simplicity, efficiency and robustness. They are intended to support a multiprogramming system for the development of distributed algorithms and other distributed applications. We address several major issues in developing a utility server, including the server structure, the management of message buffers, deadlock, and the robustness of server processes. Several utility servers in the Charlotte system are discussed as real examples.

A retrospective view is presented of the Charlotte distributed operating system, a testbed for developing techniques and tools to solve computation-intensive problems with large-grain parallelism. The final version of Charlotte runs on the Crystal multicomputer, a collection of VAX-11/750 computers connected by a local area network. The kernel/process interface is unique in its support for symmetric, bidirectional communication paths (called links), and synchronous nonblocking communications. Several lessons were learned in implementing Charlotte. Links have proven to be a useful abstraction, but the primitives do not seem to be at quite the right level of abstraction. The implementation uses finite-state machines and a multitask kernel, both of which work well. It also maintains absolute distributed information which is more expensive that using hints. The development of high-level tools, particularly the Lynx distributed programming language, has simplified the use of kernal primitives and helps to manage concurrency at the process level.>

The authors describe a tool called TAP, which is defined to aid the programmer in discovering the causes of timing errors in running programs. TAP is similar to a postmortem debugger, using the history of interprocess communication to construct a timing graph, a directed graph where an edge joins node x to node y if event x directly precedes event y in time. The programmer can then use TAP to look at the graph to find the events that occurred in an unacceptable order. Because of the nondeterministic nature of distributed programs, the authors feel a history-keeping mechanism but always be active so that bugs can be dealt with as they occur. The goal is to collect enough information at run time to construct the timing graph if needed. Since it is always active, this mechanism must be efficient. The authors also describe experiments run using TAP and report the impact that TAP's history-keeping mechanism has on the running time of various distributed programs.>

A simple technique is described that detects structural-type clashes across compilation units with an arbitrarily high degree of confidence. The type of each external object is described in canonical form. A hash function compresses the description into a short code. If the code is embedded in a symbol-table name, then consistency can be checked by an ordinary linker. For distributed programs, run-time checking of message types can be performed with very little overhead.>

DIB is a general-purpose package that allows a wide range of applications such as recursive backtrack, branch and bound, and alpha-beta search to be implemented on a multicomputer. It is very easy to use. The application program needs to specify only the root of the recursion tree, the computation to be performed at each node, and how to generate children at each node. In addition, the application program may optionally specify how to synthesize values of tree nodes from their children's values and how to disseminate information (such as bounds) either globally or locally in the tree. DIB uses a distributed algorithm, transparent to the application programmer, that divides the problem into subproblems and dynamically allocates them to any number of (potentially nonhomogeneous) machines. This algorithm requires only minimal support from the distributed operating system. DIB can recover from failures of machines even if they are not detected. DIB currently runs on the Crystal multicomputer at the University of Wisconsin-Madison. Many applications have been implemented quite easily, including exhaustive traversal ( N queens, knight's tour, negamax tree evaluation), branch and bound (traveling salesman) and alpha-beta search (the game of NIM). Speedup is excellent for exhaustive traversal and quite good for branch and bound.

This paper presents an overview of the hardware and software components of the Crystal multicomputer project. The goal of the Crystal project is to design and implement a vehicle that serves a variety of research projects involving distributed computation. Crystal can be used simultaneously by multiple research projects by partitioning the available processors according to the requirements of each project. Users can employ the Crystal multicomputer in several ways. Projects such as operating systems and database machines that need direct control of processor resources (clock, memory management, communication devices) can be implemented using a reliable communication service (the "nugget" that resides on each node processor. Projects that prefer a higher-level interface can be implemented using the Charlotte distributed operating system. Finally, users interested in Crystal principally as a cycle server can run UNIX® jobs on node machines using the "remote" unix service. Development, debugging, and execution of projects can take place remotely under the control of any of several UNIX hosts. Acquiring a partition of machines, resetting each machine, and then loading an application onto each machine is performed by invoking a UNIX-resident program (the "nuggetmaster"). Communication with node machines in a partition is facilitated by a virtual terminal and window mechanism. Crystal is fully operational and has been used to support a variety of research projects. To illustrate the flexibility provided by the Crystal environment, four of these projects are described.

In this paper we investigate the ``mandatory-work-first'' approach to parallel alpha-beta search first proposed by Akl, Barnard, and Doran. This approach is based on a version of alpha-beta search without deep cutoffs and a two-stage evaluation process, the second stage of which is often pruned. Our analysis shows that for best-first ordering on the lookahead tree, this approach provides greater speedup than the Palphabeta tree-splitting technique, and that for worst-first ordering, mandatory work first provides only slightly worse speedup than Palphabeta.

A large-network algorithm solves a problem of size N on a network of N processors. We present a method for transforming certain large networks into quotient networks that emulate those large networks with fewer processors. Large-network algorithms are easily modified to execute on the quotient network. The emulations result in no loss in execution efficiency. Quotient networks allow algorithms to be designed assuming any number of processors and executed efficiently at a great savings in hardware cost.

In this paper we describe a new family of topologies for interconnecting many identical processors to form an MIMD multiprocessor. It extends to arbitrarily many processors while keeping the number of neighbors of any one processor fixed. We show that this family behaves very well with respect to uniformity of bus load, simplicity of routing algorithms, and distance between processors.

Gary Knott has presented algorithms for computing a bljectton between the set of binary trees on n nodes and an mmal segment of the posmve integers Rotem and Varol presented a more complicated algorithm that computes a different bljectmn, clmmmg that thetr algorithm is more efficient and has advantages ff a sequence of several consecutive trees is reqmred A modlficatmn of Knott's algorithm that ts simpler than Knott's and as effioent as Rotem and Varol's is presented Also given is a new hnear-time algorithm for transforming a tree mto ~ts successor m the natural ordering of binary trees

In this paper, we describe four families of topologies for interconnecting many identical processors into a computer network. Each family extends to arbitrarily many processors while keeping the number of neighbors of any one processor fixed. These families are investigated with respect to bus load, routing algorithms, and the relation between the average interprocessor distance and the size of the network.

Roscoe is an operating system implemented at the University of Wisconsin that allows a network of microcomputers to cooperate to provide a general-purpose computing facility. After presenting an overview of the structure of Roscoe, this paper reports on experience with Roscoe and presents several problems currently being investigated by the Roscoe project.

An algorithm and data structure are presented for searching a file containing N records, each described by k real valued keys, for the m closest matches or nearest neighbors to a given query record. The computation required to organize the file is proportional to kNlogN. The expected number of records examined in each search is independent of the file size. The expected computation to perform each search is proportional-to 1ogN. Empirical evidence suggests that except for very small files, this algorithm is considerably faster than other methods.