Randomized naming using wait-free shared variables

A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives. Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly different: Processes p and q address the register of process r in a way not known to each other. For processes and , the protocol uses a name space of size and running time (read/writes to shared bits) with probability at least , and overall expected running time. The protocol is based on the wait-free implementation of a novel -Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least in the face of the strongest possible adaptive adversary. Received: September 1994 / Accepted: January 1998     

A Timing Assumption and Two t-Resilient Protocols for Implementing an Eventual Leader Service in Asynchronous Shared Memory Systems

This paper considers the problem of electing an eventual leader in an asynchronous shared memory system. While this problem has received a lot of attention in message-passing systems, very few solutions have been proposed for shared memory systems. As an eventual leader cannot be elected in a pure asynchronous system prone to process crashes, the paper first proposes to enrich the asynchronous system model with an additional assumption. That assumption (denoted AWB) is particularly weak. It is made up of two complementary parts. More precisely, it requires that, after some time, (1) there is a process whose write accesses to some shared variables be timely, and (2) the timers of (t−f) other processes be asymptotically well-behaved (t denotes the maximal number of processes that may crash, and f the actual number of process crashes in a run). The asymptotically well-behaved timer notion is a new notion that generalizes and weakens the traditional notion of timers whose durations are required to monotonically increase when the values they are set to increase (a timer works incorrectly when it expires at arbitrary times, i.e., independently of the value it has been set to). The paper then focuses on the design of t-resilient AWB-based eventual leader protocols. “t-resilient” means that each protocol can cope with up to t process crashes (taking t=n−1 provides wait-free protocols, i.e., protocols that can cope with any number of process failures). Two protocols are presented. The first enjoys the following noteworthy properties: after some time only the elected leader has to write the shared memory, and all but one shared variables have a bounded domain, be the execution finite or infinite. This protocol is consequently optimal with respect to the number of processes that have to write the shared memory. The second protocol guarantees that all the shared variables have a bounded domain. This is obtained at the following additional price: t+1 processes are required to forever write the shared memory. A theorem is proved which states that this price has to be paid by any protocol that elects an eventual leader in a bounded shared memory model. This second protocol is consequently optimal with respect to the number of processes that have to write in such a constrained memory model. In a very interesting way, these protocols show an inherent tradeoff relating the number of processes that have to write the shared memory and the bounded/unbounded attribute of that memory.     

A queue based mutual exclusion algorithm

A new elegant and simple algorithm for mutual exclusion of N processes is proposed. It only requires shared variables in a memory model where shared variables need not be accessed atomically. We prove mutual exclusion by reformulating the algorithm as a transition system (automaton), and applying simulation of automata. The proof has been verified with the higher-order interactive theorem prover PVS. Under an additional atomicity assumption, the algorithm is starvation free, and we conjecture that no competing process is passed by any other process more than once. This conjecture was verified by model checking for systems with at most five processes.     

Initializing memory shared by several processors

We examine the use of atomic instructions in implementing barriers that do not require previously initialized memory. We show hown identical processes can use uninitialized shared memory to elect a leader that then initialized the shared memory. The processes first use the uninitialized memory to obtain unique identifiers in the range 0 ton–1 and then meet at a barrier. After passing the barrier, the leader initializes the shared memory. Whenn is not a power of 2 this barrier implementation, a tournament algorithm, avoids extra work by taking advantage of information implicit in the algorithm for obtaining the unique identifiers. The only atomic instruction that we require is one that complements a bit.     

Genetic algorithms combined with discriminant analysis for key variable identification

Many trouble-shooting problems in process industries are related to key variable identification for classifications. The contribution charts, based on principal component analysis (PCA), can be applied for this purpose. Genetic algorithms (GAs) have been proposed recently for many applications including variable selection for multivariate calibration, molecular modeling, regression analysis, model identification, curve fitting, and classification. In this paper, GAs are incorporated with Fisher discriminant analysis (FDA) for key variable identification. GAs are used as an optimization tool to determine variables that maximize the FDA classification success rate for two given data sets. GA/FDA is a proposed solution for the variable selection problem in discriminant analysis. The Tennessee Eastman process (TEP) simulator was used to generate the data sets to evaluate the correctness of the key variable selection using GA/FDA, and the T² and Q statistic contribution charts. GA/FDA correctly identifies the key variables for the TEP case studies that were tested. For one case study where the correlation changes in two data sets, the contribution charts incorrectly suggest that the operating conditions are similar. On the other hand, GA/FDA not only determines that the operating conditions are different, but also identifies the key variables for the change. For another case study where many key variables are responsible for the changes in the two data sets, the contribution charts only identifies a fraction of the key variables, while GA/FDA correctly identifies all of the key variables. GA/FDA is a promising technique for key variable identification, as is evidenced in successful applications at The Dow Chemical Company.     

Distributed shared abstractions (DSA) on multiprocessors

Any parallel program has abstractions that are shared by the program's multiple processes. Such shared abstractions can considerably affect the performance of parallel programs, on both distributed and shared memory multiprocessors. As a result, their implementation must be efficient, and such efficiency should be achieved without unduly compromising program portability and maintainability. The primary contribution of the DSA library is its representation of shared abstractions as objects that may be internally distributed across different nodes of a parallel machine. Such distributed shared abstractions (DSA) are encapsulated so that their implementations are easily changed while maintaining program portability across parallel architectures. The principal results presented are: a demonstration that the fragmentation of object state across different nodes of a multiprocessor machine can significantly improve program performance; and that such object fragmentation can be achieved without compromising portability by changing object interfaces. These results are demonstrated using implementations of the DSA library on several medium scale multiprocessors, including the BBN Butterfly, Kendall Square Research, and SGI shared memory multiprocessors. The DSA library's evaluation uses synthetic workloads and a parallel implementation of a branch and bound algorithm for solving the traveling salesperson problem (TSP)     

The butterfly barrier

We describe and algorithm for barrier synchronization that requires only read and write to shared store. The algorithm is faster than the traditionallocked counter approach for two processors and has an attractive log₂ N time scaling for largerN. The algorithm is free of hot spots and critical regions and requires a shared memory bandwidth which grows linearly withN, the number of participating processors. We verify the technique using both a real shared memory multiprocessor, for numbers of processors up to 30, and a shared memory multiprocessor simulator, for number of processors up to 256.Work performed under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under contract No. W-7405-ENG-48.     

Simulation tools to study a distributed shared memory for clusters of symmetric multiprocessors

Distributed shared memory (DSM) systems have become popular as a means of utilizing clusters of computers for solving large applications. We have developed a high-performance DSM, Strings. In addition, to improve the performance of our DSM, a memory hierarchy simulator has been developed that allows us to compare various techniques very quickly and with much less effort. This paper describes our simulator, DSMSim. We show that the simulator's performance closely matches the real system and demonstrate potential performance gains of up to 60% after adding optimization features to the simulator. The simulator also accepts the same code as the software distributed shared memory.     

A Unified Pilot Training and Control System for Underwater Robotic Vehicles (URV)

This paper introduces the work done to improve on a sophisticated Underwater Robotic Vehicle (URV) inspection and repair system for submerged structures. It is undertaken as part of a research programme grant to pursue research and development of technologies and systems for the advancement of knowledge and for possible commercial exploitation relevant to the oil and gas industry. In particular, the paper focuses on the development of a unified pilot training and controls system that incorporates an advance man–machine interface for improving operator dexterity. Few formalised training procedures exist for URV pilots. In spite of the high cost, most URV pilots receive their training on-the-job. Training simulators can be viewed as a viable solution to this problem. Some attention has been made to address this problem. Notably are efforts by Imetrix URV-Mentor system, which focuses on VE simulation and on-line tutoring. Simulators, however, represents additional costs and in some ways lacks the realism of working on the real system. In the R ² C the researchers proposed a novel simulator configuration. We have developed a dual-purpose topside control system configuration that can be used for training as well as for on-line operation of an actual URV. In the simulator configuration, the physical URV is replaced by a simulator module, which accepts actual commands from the control system and responds with a simulated URV status, using a dynamic model of the URV. The simulator module behaves much like the actual URV accepting commands and responds with status information. The advantage of such a system is perceived to be lower system cost as well as a more realistic testing and simulation of the relevant processes.     

Book Reviews

Abstract

Some concepts within general systems, like autonomy and self-reference, are difficult enough to raise foundational questions. Tarski's foundational work on meaning is reviewed and applied to explain some consistent forms of self-reference. The characteristic circularity is hereby unfolded. This suggests that explicable forms of autonomy and self-reference can always be eliminated in a language of sufficiently high order. Thus, in an explicatory sense, these concepts undoubtedly have a productive value

The notion of relevance within theory-formation processes is another difficult concept, raised by the interdisciplinary character of general systems. For philosophy of science it has generated the paradox of Hempel. A foundational view is given that explains the paradox and provides a further insight into the concept of relevance (and support and confirmation).     

An abort-aware model of transactional programming

There has been a lot of recent research on transaction-based concurrent programming, aimed at offering an easier concurrent programming paradigm that enables programmers to better exploit the parallelism of modern multi-processor machines, such as multi-core microprocessors. We introduce Transactional State Machines (TSMs) as an abstract finite-data model of transactional shared-memory concurrent programs. TSMs are a variant of concurrent boolean programs (or concurrent extended recursive state machines) augmented with additional constructs for specifying potentially nested transactions. Namely, some procedures (or code segments) can be marked as transactions and are meant to be executed “atomically”, and there are also explicit commit and abort operations for transactions. The TSM model is non-blocking and allows interleaved executions where multiple processes can simultaneously be executing inside transactions. It also allows nested transactions, transactions which may never terminate, and transactions which may be aborted explicitly, or aborted automatically by the run-time environment due to memory conflicts. We show that concurrent executions of TSMs satisfy a correctness criterion closely related to serializability, which we call stutter-serializability, with respect to shared memory. We initiate a study of model checking problems for TSMs. Model checking arbitrary TSMs is easily seen to be undecidable, but we show it is decidable in the following case: when recursion is exclusively used inside transactions in all (but one) of the processes, we show that model checking such TSMs against all stutter-invariant ω-regular properties of shared memory is decidable.     

Function simulation,graph grammars and colourings

We prove that to any partial function ? defined on a finite set, there corresponds an infinite class of graphs that could be generated by a graph grammar such that each graph in the class represents the function in the sense that evaluation of the function at any point x of its domain can be simulated by finding the unique extension of a partial vertex colouring of the graph specified by x. We show that in the proposed setup, generating such simulator graphs as well as finding the colouring extensions can be computed effectively in polynomial time. We also discuss some applications of this scenario in producing instances of the graph colouring problem near its phase transition that can be applied in a cryptographic setting.     

Membrane Systems with Peripheral Proteins: Transport and Evolution

Transport of substances and communication between compartments are fundamental biological processes, often mediated by the presence of complementary proteins attached to the surfaces of membranes. Within compartments, substances are acted upon by local biochemical rules. Inspired by this behaviour we present a model based on membrane systems, with objects attached to the sides of the membranes and floating objects that can move between the regions of the system. Moreover, in each region there are evolution rules that rewrite the transported objects, mimicking chemical reactions. We first analyse the system, showing that interesting qualitative properties can be decided (like reachability of configurations) and then present a simulator based on a stochastic version of the introduced model and show how it can be used to simulate relevant quantitative biological processes.     

The space complexity of unbounded timestamps

The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events throughout the system with timestamps that provide information about the real-time ordering of those events. We consider the space complexity of wait-free implementations of timestamps from shared read-write registers in a system of n processes. We prove an lower bound on the number of registers required. If the timestamps are elements of a nowhere dense set, for example the integers, we prove a stronger, and tight, lower bound of n. However, if timestamps are not from a nowhere dense set, this bound can be beaten: we give an implementation that uses n − 1 (single-writer) registers. We also consider the special case of anonymous implementations, where processes are programmed identically and do not have unique identifiers. In contrast to the general case, we prove anonymous timestamp implementations require n registers. We also give an implementation to prove that this lower bound is tight. This is the first anonymous timestamp implementation that uses a finite number of registers.     

Light-Weight Leases for Storage-Centric Coordination

Reaching agreement among processes sharing read/write memory is possible only in the presence of an eventual unique leader. A leader that fails must be recoverable, but on the other hand, a live and well-performing leader should never be decrowned. This paper presents the first leader algorithm in shared memory environments that guarantees an eventual leader following global stabilization time. The construction is built using light-weight lease and renew primitives. The implementation is simple, yet efficient. It is uniform, in the sense that the number of potentially contending processes for leadership is not a priori known.     

The Unique Horn-Satisfiability problem and quadratic Boolean equations

The unique satisfiability problem for general Boolean expressions has attracted interest in recent years in connection with basic complexity issues [12,13]. We investigate here Unique Horn-Satisfiability, i.e. the subclass of Unique-Sat restricted to Horn expressions. We introduce two operators,reduction andshrinking, each transforming a given Horn expression into another Horn expression involving strictly fewer variables and preserving the unique satisfiability property, if present.Uniquely satisfiable Horn expressions are then characterized as those Horn expressions which can be converted into a formula composed of an empty set of clauses on an empty set of free variables through finitely many applications of the shrink-and-reduce operator.Finally, an algorithm for testing whether a given irreducible Horn formula is uniquely satisfiable is described. Data structures for its implementation are discussed, leading toO(mn) complexity for the general case (m=number of clauses,n=number of variables), hence to linear complexity for dense formulae.     

Coupling of quantum angular momenta: an insight into analogic/discrete and local/global models of computation

In the past few years there has been a tumultuous activity aimed at introducing novel conceptual schemes for quantum computing. The approach proposed in (Marzuoli and Rasetti, 2002, 2005a) relies on the (re)coupling theory of SU(2) angular momenta and can be viewed as a generalization to arbitrary values of the spin variables of the usual quantum-circuit model based on ‘qubits’ and Boolean gates. Computational states belong to finite-dimensional Hilbert spaces labelled by both discrete and continuous parameters, and unitary gates may depend on quantum numbers ranging over finite sets of values as well as continuous (angular) variables. Such a framework is an ideal playground to discuss discrete (digital) and analogic computational processes, together with their relationships occurring when a consistent semiclassical limit takes place on discrete quantum gates. When working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum finite states-machines which in turn represent discrete versions of topological quantum computation models. We argue that our model embodies a sort of unifying paradigm for computing inspired by Nature and, even more ambitiously, a universal setting in which suitably encoded quantum symbolic manipulations of combinatorial, topological and algebraic problems might find their ‘natural’ computational reference model.     

On WLCDs and the Complexity of Word-Level Decision Diagrams—A Lower Bound for Division

Several types of Decision Diagrams (DDs) have been proposed for the verification of Integrated Circuits. Recently, word-level DDs like BMDs, *BMDs, HDDs, K*BMDs and *PHDDs have been attracting more and more interest, e.g., by using *BMDs and *PHDDs it was for the first time possible to formally verify integer multipliers and floating point multipliers of significant bitlengths, respectively.On the other hand, it has been unknown, whether division, the operation inverse to multiplication, can be efficiently represented by some type of word-level DDs. In this paper we show that the representational power of any word-level DD is too weak to efficiently represent integer division. Thus, neither a clever choice of the variable ordering, the decomposition type or the edge weights, can lead to a polynomial DD size for division.For the proof we introduce Word-Level Linear Combination Diagrams (WLCDs), a DD, which may be viewed as a generic word-level DD. We derive an exponential lower bound on the WLCD representation size for integer dividers and show how this bound transfers to all other word-level DDs.     

On the power of shared object types to implement one-resilient Consensus

Abstract. In this paper we study the ability of shared object types to implement Consensus in asynchronous shared-memory systems where at most one process may crash. More specifically, we consider the following question: Let and be a set of object types that can be used to solve one-resilient Consensus among n processes. Can always be used to solve one-resilient Consensus among n - 1 processes? We prove that for n = 3 the answer is negative, even if consists only ofdeterministic types. (This strengthens an earlier result by the first author proving the same fact for nondeterministic types.) We also prove that, in contrast, for the answer to the above question is affirmative. Received: July 1997 / Accepted: May 2000