Parallel Processing Letters

In this paper we investigate the problem of designing load balancing protocols in distributed systems involving self-interested participants. These participants have their own requirements and objectives and no a-priori motivation for cooperation. Their selfish behavior may lead to poor performance and inefficiency. To address this problem we design a load balancing mechanism with verification that provides incentives to participants to report their true parameters and follow the given algorithm. We prove that our load balancing mechanism is truthful (i.e., agents will be better off by reporting their true parameters) and satisfies the voluntary participation condition (i.e., truthful agents never incur a loss). We present a simulation study to show the performance of our load balancing mechanism.

A new computational paradigm is described which offers the possibility of superlinear (and sometimes unbounded) speedup, when parallel computation is used. The computations involved are subject only to given mathematical constraints and hence do not depend on external circumstances to achieve superlinear performance. The focus here is on geometric transformations. Given a geometric object A with some property, it is required to transform A into another object B which enjoys the same property. If the transformation requires several steps, each resulting in an intermediate object, then each of these intermediate objects must also obey the same property. We show that in transforming one triangulation of a polygon into another, a parallel algorithm achieves a superlinear speedup. In the case where a convex decomposition of a set of points is to be transformed, the improvement in performance is unbounded, meaning that a parallel algorithm succeeds in solving the problem as posed, while all sequential algorithms fail.

In this paper, we consider a parallel algorithm for the patience sorting. The problem is not known to be in the class NC or P-complete. We propose two algorithms for the patience sorting of n distinct integers. The first algorithm runs in time using p processors on the EREW PRAM, where m is the number of decreasing subsequences in a solution of the patience sorting. The second algorithm runs in time using p processors on the EREW PRAM. If is satisfied, the second algorithm becomes cost optimal.

For bidirectional rings, there have been proposed self-stabilizing mutual exclusion protocols, which are either time-adaptive (i.e., efficient in recovery) or 1-latent (i.e., efficient in legal execution) but not both. This paper proposes a randomized self-stabilizing mutual exclusion protocol that inherits both of the advantages from them: It is 1-latent in the sense that the privilege is circulated in a linear round (i.e., very intuitively, the privilege is transferred from a process to another by a "step"), provided that the system always stays in legitimate configurations, and is weakly time-adaptive in the sense that the system stabilizes from any configuration c in O(f) steps with a high probability, where f is the number of corrupted processes in c. It also guarantees with a high probability that there is at most one privilege even while converging to a legitimate configuration.

In this paper, we present a system-level fault identification algorithm, using a parallel genetic algorithm, for diagnosing faulty nodes in large heterogeneous systems. The algorithm is based on a probabilistic model where individual node fails with an a priori probability p. The assumptions concerning test outcomes are the same as in the PMC model, that is, fault-free testers always give correct test outcomes and faulty testers are totally unpredictable. The parallel diagnosis algorithm was implemented and simulated on randomly generated large systems. The proposed parallelization is intended to speed up the performance of the evolutionary diagnosis approach, hence reducing the computation time by evolving various sub-populations in parallel. Simulation results are provided showing that the parallel diagnosis did improve the efficiency of the evolutionary diagnosis approach, in that it allowed faster diagnosis of faulty situations, making it a viable alternative to existing techniques of diagnosis. Moreover, the evolutionary approach still provide good results even when extreme non-diagnosable faulty situations are considered.

In this paper we present new results on sequential and parallel construction of optimal and almost-optimal length-restricted prefix-free codes. We show that length-restricted prefix-free codes with error 1/n^k for any k > 0 can be constructed in O(n log n) time, or in O(log n) time with n CREW processors. A length-restricted code with error 1/n^k for any k ≤ L/ log_Φ n, where , can be constructed in O(log n) time with n/ log n CREW processors. We also describe an algorithm for the construction of optimal length-restricted codes with maximum codeword length L that works in O(L) time with n CREW processors.

A source sends a piece of data (message), relayed to a receiver by n processes, some of which can be faulty. We assume that the number of faulty processes is at most f and that faulty processes exhibit a Byzantine behavior. A deciding agent has to make a decision concerning the source message, on the basis of results obtained from the receiver. The environment is totally asynchronous. An Asynchronous Byzantine Voting Mechanism is a method that enables the deciding agent to always correctly determine the source message in this scenario.

We show that there exists a correct Asynchronous Byzantine Voting Mechanism if and only if f < n/3. If this condition is satisfied, we provide such a mechanism. This result should be contrasted with the feasibility of synchronous voting mechansisms, in which the receiver can wait until all fault-free processes convey their values: for this scenario a correct voting mechanism exists whenever f < n/2.

Structural model abstraction is a powerful technique for reducing the complexity of a state based enumeration analysis. We present in this paper new efficient Petri nets reductions. First, we define "behavioural" reductions (i.e. based on conditions related to the language of the net) which preserve a fundamental property of a net (i.e. liveness) and any formula of the (action-based) linear time logic that does not observe reduced transitions of the net. We show how to replace these conditions by structural or algebraical ones leading to reductions that can be efficiently checked and applied whereas enlarging the application spectrum of the previous reductions. At last, we illustrate our method on a significant and typical example of a synchronisation pattern of parallel programs.

In the model of restricted parallel links, n users must be routed on m parallel links under the restriction that the link for each user be chosen from a certain set of allowed links for the user. In a (pure) Nash equilibrium, no user may improve its own Individual Cost (latency) by unilaterally switching to another link from its set of allowed links. The Price of Anarchy is a widely adopted measure of the worst-case loss (relative to optimum) in system performance (maximum latency) incurred in a Nash equilibrium.

In this work, we present a comprehensive collection of bounds on Price of Anarchy for the model of restricted parallel links and for the special case of pure Nash equilibria. Specifically, we prove:

• For the case of identical users and identical links, the Price of Anarchy is .

• For the case of identical users, the Price of Anarchy is .

• For the case of identical links, the Price of Anarchy is , which is asymptotically tight.

• For the most general case of arbitrary users and related links, the Price of Anarchy is at least m – 1 and less than m.

The shown bounds reveal the dependence of the Price of Anarchy on n and m for all possible assumptions on users and links.

This paper presents, discusses and evaluates parallel implementations of a set of algorithms designed for optimization tasks: Estimation of Bayesian Network Algorithms (EBNAs). These algorithms belong to the family of Evolutionary Computation. Two different APIs have been combined: message passing and threads, with the aim of obtaining good performance levels in a wide range of parallel machines. Our approach has been to analyze the most computationally intensive sections of sequential implementations of EBNAs, and then to parallelize those sections using a master-worker design pattern. This way the resulting program exhibits exactly the same behavior of the sequential one, but runs faster. To evaluate our proposal, we have chosen a complex scenario where EBNAs can be applied: Feature Subset Selection (FSS) for supervised classification problems. For the experiments, three computing systems have been tested: two different clusters built from commodity components, and an 8-way multiprocessor. Programs have been executed on the target machines using different combination of message-passing processes and threads. Achieved performance is excellent, with efficiency around 1. These encouraging results do widen the spectrum of problems (and problem sizes) that can be solved, in reasonable times, with EBNAs.