Mechanism design with partial verification and revelation principle

In the case of mechanism design with partial verification, where agents have restrictions on misreporting, the Revelation Principle does not always hold. Auletta et al. (J Auton Agent Multi-Agent Syst, to appear) proposed a characterization of correspondences for which the Revelation Principle holds, i.e., they described restrictions on misreporting under which a social choice function is implementable if and only if it is truthfully implementable. In this paper, we demonstrate that the characterization proposed in [1] is incorrect, and, building on their work, give a correct characterization. We also provide an example that demonstrates that our characterization is different from that of Auletta et al.     

A new solution to the hyperbolic tangent implementation in hardware: polynomial modeling of the fractional exponential part

The most difficult part of an artificial neural network to implement in hardware is the nonlinear activation function. For most implementations, the function used is the hyperbolic tangent. This function has received much attention in relation to hardware implementation. Nevertheless, there is no consensus regarding the best solution. In this paper, we propose a new approach by implementing the hyperbolic tangent in hardware with a polynomial modeling of the fractional exponential part. The results in the paper then demonstrate, through the use of an example, that this solution is faster than the CORDIC algorithm, but slower than the piecewise linear solution with the same error. The advantage over the piecewise linear approach is that it uses less memory.     

Push: An experimental facility for implementing distributed database services in operating systems

Distributed database systems need speciaal operating system support. Support routines can be implemented inside the kernel or at the user level. Kernel-level functions, while efficient, are hard to implement. User-level implementations are easier but suffer from poor performance and lack of security. This article proposes a new approach to supplement or modify kernel facilities for database transaction processing. Our experimental facility, called Push, is based on an extension language interpreted within the kernel. Our implementation provides the efficiency of kernel-resident code as well as the simplicity and safety of user-level programming. This facility enables experimentation that would be difficult and time-consuming in current environments. The overhead of the Push implementation can be factored out to give a good estimate of the performance of a native kernel implementation. We have used Push to implement several kernel-resident services. In the case of multi-RPC and commit protocols, Push implementations significantly improve performance and scalability over user-level implementations. The experiments show the benefits of Push both as an operational tool for improving transaction processing performance and as an experimental tool for investigating the benefits of operating systems extension without costly implementation.This research is supported by NASA and AIRMICS under grant number NAG-1-676, NSF grant IRI-8821398, and AT&T.     

On the inherent weakness of conditional primitives

Some well-known primitive operations, such as compare-and-swap, can be used, together with read and write, to implement any object in a wait-free manner. However, this paper shows that, for a large class of objects, including counters, queues, stacks, and single-writer snapshots, wait-free implementations using only these primitive operations and a large class of other primitive operations cannot be space efficient: the number of base objects required is at least linear in the number of processes that share the implemented object. The same lower bounds are obtained for implementations of starvation-free mutual exclusion using only primitive operations from this class. For wait-free implementations of a closely related class of one-time objects, lower bounds on the tradeoff between time and space are presented.     

Observational implementation of algebraic specifications

Summary An observational approach to the construction of implementations of algebraic specifications is presented. Based on the theory of observational specifications an implementation relation is defined which formalizes the intuitive idea that an implementation is correct if it produces correct observable output. To be useful in practice proof theoretic criteria for observational implementations are provided and a proof technique (called context induction) for the verification of implementation relations is presented. As an example an abstract specification of (the algebraic semantics of) a small imperative programming language is implemented by a state oriented specification of the language.In order to support the modular construction of implementations the approach is extended to parameterized observational specifications. Based on the notion of observable parameter context a proof theoretic criterion for parametrized observational implementations is presented and it is shown that under appropriate conditions observational implementations compose horizontally. The given implementation criteria are applied to examples.     

Complete deterministic stream X-machine testing

One of the strengths of using stream X-machines to specify a system is that, under certain well defined conditions, it is possible to produce a test set that is guaranteed to determine the correctness of an implementation. However, the existing method assumes that the implementation of each processing function is proved to be correct before the actual testing can take place, so it only test the system integration. This paper presents a new method for generating test sets from a deterministic stream X-machine specification that generalises the existing integration testing method. This method no longer requires the implementations of the processing functions to be proved correct prior to the actual testing. Instead, the testing of the processing functions is performed along with the integration testing.Accepted in revised form 27 February 2004 by D.A. Duce     

Standardized protocol interfaces

A traditional protocol implementation typically consists of at least two distinct parts, a sender and a receiver. Each part runs on a distinct machine, with the implementation provided by a local expert. At best, the two machines are of the same type and the protocol implementations are provided by the same person. More likely, however, the machines are not of the same type and the implementations of the two halves of the protocol are provided by two different people, working from an often loosely defined protocol specification. It seems almost unavoidable that the two implementations are not quite compatible. In this paper we consider an alternative technique. With this method, one of the two implementors can design, formally validate, and implement all the relevant protocol parts, including those parts that are to be executed remotely. Each communication channel is now terminated on the receiving side, by a single standard protocol interface, which can be called a universal asynchronous protocol interface, or UAPI. Though it is likely that the UAPI is most efficiently implemented in hardware, it can also trivially run as a software module, e.g. under a standard UNIX® operating system (in our case under 10th Edition Research Unix). This paper introduces the concept of a UAPI and explains how the sample software controller was constructed.     

On group communication support in CORBA

Current group communication services have mostly been implemented on a homogeneous, distributed computing environment. This limits their applicability because most modern distributed computing environment are heterogeneous in nature. This paper describes the design, implementation, and performance evaluation of a CORBA group communication service. Using CORBA to implement a group communication service enables that group communication service to operate in a heterogeneous, distributed computing environment. To evaluate the effect of CORBA on the performance of a group communication service, this paper provides a detailed comparison of the performance measured from three implementations of an atomic broadcast protocol and a group membership protocol. Two of these implementations use CORBA, while the third uses UDP sockets for interprocess communication. The main conclusion is that heterogeneity can be achieved in group communication services by implementing them using CORBA, but there is a substantial performance cost. This performance cost can be reduced to a certain extent by carefully choosing a design and tuning various protocol parameters such as buffer sizes and timer values     

A formal framework to test soft and hard deadlines in timed systems

This paper introduces a formal framework to specify and test systems presenting both soft and hard deadlines. While hard deadlines must always be met on time, soft deadlines can be sometimes met in a different time, usually greater, from the specified one. It is this characteristic (to formally definetextitsometimes) that produces several reasonable alternatives to define appropriate implementation relations, that is, relations to decide whether an implementation is correct with respect to a specification. In addition to introducing these relations, the paper also presents a formal testing framework to test implementations and provides an algorithm to derive sound and complete test suites with respect to the implementation relations previously defined. That is, an implementation conforms to a specification if and only if the implementation successfully passes all the tests belonging to the suite derived from the specification. Copyright © 2011 John Wiley & Sons, Ltd.     

View-based propagator derivation

When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear constraints both with unit and non-unit coefficients? Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance than resorting to constraint decomposition. This paper shows how to use views to derive propagator variants, combining the efficiency of dedicated propagator implementations with the simplicity and effortlessness of decomposition. A model for views and derived propagators is introduced. Derived propagators are proved to be perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, generalization, specialization, and type conversion are developed. The paper introduces an implementation architecture for views that is independent of the underlying constraint programming system. A detailed evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.     

A CLP framework in Java

This paper discusses some basic ideas about the implementation of GC, a constraint propagation system, with three different implementations of finite variables domains. As it has been our wish to develop a system that uses the OO approach, it is implemented in Java, although other application frameworks are also available for C++.The constraint propagation and variables domains are explained at the application and implementation level and some examples from the litterature are presented in order to clarify the construction of applications with GC.     

Adaptive progress: a gracefully-degrading liveness property

We introduce a simple liveness property for shared object implementations that is gracefully degrading depending on the degree of synchrony in each run. This property, called adaptive progress, provides a gradual bridge between obstruction-freedom and wait-freedom in partially-synchronous systems. We show that adaptive progress can be achieved using very weak shared objects. More precisely, every object has an implementation that ensures adaptive progress and uses only abortable registers (which are weaker than safe registers). As part of this work, we present a new leader election abstraction that processes can use to dynamically compete for leadership such that if there is at least one timely process among the current candidates for leadership, then a timely leader is eventually elected among the candidates. We also show that this abstraction can be implemented using abortable registers.     

Nonintrusive Cloning Garbage Collection with Stock Operating System Support

It is well accepted that automatic garbage collection simplifies programming, promotes modularity, and reduces development effort. However it is commonly believed that these advantages do not counteract the perceived price: excessive overheads, possible long pause times while garbage collections occur, and the need to modify existing code. Even though there are publically available garbage collector implementations that can be used in existing programs, they do not guarantee short pauses, and some modification of the application using them is still required. In this paper we describe a snapshot-at-beginning concurrent garbage collector algorithm and its implementation. This algorithm guarantees short pauses, and can be easily implemented on stock UNIX-like operating systems. Our results show that our collector performs comparable to other garbage collection implementations on uniprocessor machines and outperforms similar collectors on multiprocessor machines. We also show our collector to be competitive in performance with explicit deallocation. Our collector has the added advantage of being non-intrusive. Using a dynamic linking technique and effective root set inferencing, we have been able to successfully run our collector even in commercial programs where only the binary executable and no source code is available. In this paper we describe our algorithm, its implementation, and provide both an algorithmic and a performance comparison between our collector and other similar garbage collectors. ©1997 by John Wiley & Sons, Ltd.     

Distribution and persistence as aspects

This paper reports our experience using AspectJ, a general‐purpose aspect‐oriented extension to Java, to implement distribution and persistence concerns in a Web‐based information system. This system was originally implemented in Java and restructured with AspectJ. Our main contribution is to show that AspectJ is useful for implementing several persistence and distribution concerns in the considered application, but also in similar applications. We have also identified interferences between the implemented aspects and a few drawbacks in the language, so we suggest some minor language modifications that could significantly improve similar implementations. Despite those problems, we argue that the AspectJ implementation is superior to the pure Java implementation. Some of the aspects implemented in our experiment are abstract and constitute a simple aspect framework. The other aspects are application specific but we suggest that different implementations might follow the same aspect patterns. The framework and the patterns allow us to propose architecture‐specific guidelines that provide practical advice for both restructuring and implementing certain kinds of persistent and distributed applications with AspectJ. Copyright © 2006 John Wiley & Sons, Ltd.     

Biologically Inspired Models to Train Neural Networks

A major stumbling block to the successful implementation of neural networks for nonlinear regression models is overtraining. This paper presents two models to combat overtraining, based on the biological concept that the strength of the connection between neurons develops over time. For the problems investigated, the models produce smooth solutions with no sign of overtraining. For the practical Diminishing Returns problem, the Error Constraints Model, because of its mathematical formulation, determines the minimum number of hidden layer neurons. As a result, the present work is important because, if an acceptable level of error can be specified, then the Error Constraints Model can be used to determine the network architecture. Copies of the workbook implementations of all the models presented in this paper may be downloaded from the authors website.     

Portability in MAC protocol and transceiver software implementations for LR‐WPAN platforms

In a variety of emerging networked computing system domains over the years, there have been bursts of activity on new medium access control (MAC) protocols, as new communication transceiver technologies with greater data‐movement performance or lower power dissipation have been introduced. To enable implementations flexible to evolving standards and improving application‐domain insight, such MAC protocols are typically initially implemented in software, and interface between applications or system software, typically executing on an embedded processor or microcontroller, and the evolving radio transceiver hardware. Many challenges exist in implementing MAC protocols across evolving or competing transceiver hardware implementations and processor architectures. Some of these challenges are peculiar to the requirements of MAC protocols, and others are a result of the plethora of system and processor architectures in the embedded systems domain. This article studies the challenges facing software implementations of MAC protocols running on embedded microcontrollers, and interfacing with radio transceiver hardware. Experience with an implementation of the IEEE 802.15.4 MAC across three hardware platforms with different processor, system, and systems software architectures is presented, focusing on implementation approach and interfaces. Pitfalls are pointed out, and guidelines are provided for ensuring that new MAC implementations are easily portable across processor architectures and transceiver hardware. Copyright © 2010 John Wiley & Sons, Ltd.     

Localized algorithms for vlsi processor arrays

In this paper we analyze the algorithms expressed as a system of recurrence equations. The algorithms are called 2^?1 output algorithms if two output values of one function (variable identification) are specified by the system of recurrence equations for each index point in the algorithm. The algorithm is in free form if the indexes of these two values are not dependent. Two standard classes are determined by this criteria: the nearest neighbour and the all pair form. For example the sorting algorithm can be expressed in the all pair form i.e., the linear insertion algorithm or in the nearest neighbour form i.e., the bubble sort algorithm. However these algorithms are different in their nature. A procedure to eliminate the computational broadcast for the all pair 2^?1output algorithm has been proposed by the authors in [1]. The result obtained by implementing this procedure was a localized form of the algorithm and a system of uniform recurrence equations by eliminating the computational and data broadcast. So he data dependence method can be efficiently used for parallel implementations. The proposed procedure cannot be implemented directly on the nearest neighbour form algorithms. Here we show how the algorithm can be restructured into a form where the computational and data broadcast can be eliminated. These transformations result in localized algorithms. A few examples show how these algorithms can be implemented on processor arrays. For example, the Gentleman Kung triangular array [2] can be used for solving the QR decomposition algorithm for both forms of the algorithm. The implementations differ in the order of the data flow and the processor operation. We show that the implementation of the nearest neighbour algorithm is even better than the standard one.     

Ad-hoc网络按需路由协议实现技术研究

文章首先分析了在典型的操作系统中实现移动ad-hoc网络(MANET)按需路由协议所面临的问题及其所需的系统服务。由此,提出了一种在典型操作系统中支持MANET按需路由协议的通用的解决方法。最后,在Linux下实现了此方法,这种实现方法除了装载一个小模块外不需对Linux内核加以改变。这种整洁、灵活并且具有良好扩展性的实现方法会成为研究实现MANET按需路由协议的有力工具。     

A scalable implementation of barrier synchronization using an adaptive combining tree

Barrier synchronization is commonly used for synchronizing processors prior to a join operation and to enforce data dependencies during the execution of parallelized loops. Simple software implementations of barrier synchronization can result in memory hot-spots, especially in large scale shared-memory multiprocessors containing hundreds of processors and memory modules communicating through an interconnection network. A software combining tree can be used to substantially reduce memory contention due to hot-spots. However, such an implementation results inO(logn) latency in recognition of barrier synchronization, wheren is the number of processors. In this paper anadaptive software combining tree is used to implement a scalable barrier withO(1) recognition latency. The processors that arrive early at the barrier adapt the combining tree so that it has a structure appropriate for reducing the latency for the processors that arrive later. We also show how adaptive combining trees can be used to implement the fuzzy barrier. The fuzzy barrier mechanism reduces the idling of processors at the barriers by allowing the processors to execute useful instructions while they are waiting at the barrier.