Search

Presents the special issue in the journal "Parallel Processing Letters," which contains the best papers from the Centre Interantional de Rencontres Mathématiques workshopin October 2001. "Scheduling Issues in Survivality Applications Using Hybrid Fault Models," by A. W. Krings, W. S. Harrison, A. Azadmanesh and M. McQueen"; "Parallel Tabu Search Approaches for Two-Dimensional Cutting," by J. Blazewicz, A. Moret-Salvador and R. Walkowiak"; "Strategies for Workload Balancing in Cluster-Based Image Databases," by F. Drews, K. Ecker, O. Kao and S. Schomann.

The object deployment of a distributed software has a great impact on its performance. In this paper an analytical model for performance evaluation of different object deployments, is presented. The key advantage of the proposed model over the traditional Queuing Network models is the usefulness in the deployment optimization when the search space is huge and automatic instantiation of Queuing performance models corresponding to an object deployment is costly. Since our model produces an optimal deployment corresponding to each input load separately, the runtime behavior of the software corresponding to each input load should be profiled using simulation first. In this paper a translation scheme for generating the simulate-able Labeled Transition Systems (LTS) from scenarios is also presented. Moreover, two deployment algorithms (a GA-based and an INLP-based) are implemented and the results are compared. [ABSTRACT FROM AUTHOR]

This paper focuses on the traceability issue as key element in systems design and management of system. The work is presented through the system engineering framework with a main emphasis on requirements process. Effectively in decision making, the need for traceability model is often required in order to find out the link for a considered decision and often the semantics of such link. With the advent for information technology and integrating technical needs and business goal, the traceability find its essence and many models can now be easily implemented automatically. The paper is based on many experiences carried out ranging from audit to requirement evolution issues for impact analysis. [ABSTRACT FROM AUTHOR]

In this paper, we focus on convergence packet routing techniques in an all-optical network, obtained from an Eulerian routing in the digraph modeling the target network. Given an Eulerian circuit C in a digraph C, we deal with the maximal number diamWC of arcs that a packet has to follow on C from its origin to its destination (we talk about the ending guarantee of the routing). We consider the Eulerian diameter of C as defined by E(C) = mm C ∈ Eul(G) diamWc, where E(G) is the set of all the Eulerian circuits in C. After giving a preliminary result about the complexity of finding ((C) for any digraph G, we give some lower and upper bounds of this parameter. The main part of the paper is devoted to the description of a combinatorial design of various network topologies having good Eulerian diameters. [ABSTRACT FROM AUTHOR]

We discuss nearest neighbor load balancing schemes on processor networks which are represented by a cartesian product of graphs and present a new optimal diffusion scheme for general graphs. In the first part of the paper, we introduce the Alternating-Direction load balancing scheme, which reduces the number of load balance iterations by a factor of 2 for cartesian products of graphs. The resulting flow is theoretically analyzed and can be very high for certain cases. Therefore, we further present the Mixed-Direction scheme which needs the same number of iterations but computes in most cases a much smaller flow. In the second part of the paper, we present a simple optimal diffusion scheme for general graphs, calculating a balancing flow which is minimal in the l2 norm. It is based on the spectra of the graph representing the network and needs only m — 1 iterations to balance the load with m being the number of distinct eigenvalues. Known optimal diffusion schemes have the same performance, however the optimal scheme presented in this paper can be implemented in a very simple manner. The number of iterations of optimal diffusion schemes is independent of the load scenario and, thus, they are practical for networks which represent graphs with known spectra. Finally, our experiments exhibit that the new optimal scheme can successfully be combined with the Alternating-Direction and Mixed-Direction schemes for efficient load balancing on product graphs. [ABSTRACT FROM AUTHOR]

The rupture degree of an incomplete connected graph G is defined by where w(G − S) denotes the number of components in the graph G − S and m(G − S) is the order of the largest component of G − S. This parameter can be used to measure the vulnerability of a graph. In this paper, some bounds consisted of the relationships between the rupture degree and some vulnerability parameters on the rupture degree of a graph are given. [ABSTRACT FROM AUTHOR]

In this paper, we propose an approximation algorithm for the Fault-Tolerant Metric Facility Location problem which can be implemented in a distributed and asynchronous manner within O(n) rounds of communication, where n is the number of vertices in the network. Given a constant size set $\mathcal{R}$ which represents distinct levels of fault-tolerant requirements of all cities, as well as the two-part (facility and connection) cost of the optimal solution, i.e. F* + C*, the cost of our solution is no more than $|\mathcal{R}|\, \cdot \,F^* \, + \,2C^* $ for the general case, and less than F* + 2C* for the special case where all cities have a uniform connectivity requirement. Extensive numerical experiments showed that the quality of our solutions is comparable (within 4% error) to the optimal solution in practice. [ABSTRACT FROM AUTHOR]

A self-stabilizing algorithm is a distributed algorithm that can start from any initial (legitimate or illegitimate) state and eventually converge to a legitimate state in finite time without being assisted by any external agent. In this paper, we propose a self-stabilizing algorithm for finding the 3-edge-connected components of an asynchronous distributed computer network. The algorithm stabilizes in O(dnΔ) rounds and every processor requires O(nlogΔ) bits, where Δ(≤ n) is an upper bound on the degree of a node, d(≤ n) is the diameter of the network, and n is the total number of nodes in the network. These time and space complexity are at least a factor of n better than those of the previously best-known self-stabilizing algorithm for 3-edge-connectivity. The result of the computation is kept in a distributed fashion by assigning, upon stabilization of the algorithm, a component identifier to each processor which uniquely identifies the 3-edge-connected component to which the processor belongs. Furthermore, the algorithm is designed in such a way that its time complexity is dominated by that of the self-stabilizing depth-first search spanning tree construction in the sense that any improvement made in the latter automatically implies improvement in the time complexity of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of k-out-of-ℓ exclusion, a generalization of the mutual exclusion problem, in which there are ℓ units of a shared resource, and any process can request up to k units (1 ≤ k ≤ ℓ). A protocol is self-stabilizing if, starting from an arbitrary configuration, be it initial state or after a corrupted state, the protocol can start behaving normally within a finite time. We propose the first deterministic self-stabilizing distributed k-out-of-ℓ exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process. [ABSTRACT FROM AUTHOR]

The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) of memory per processor used by a leader election algorithm. We first observe that Ω(M + log d) bits are necessary and then show that O(n log d) bits are sufficient to construct a leader election algorithm that works on any network, where n, d and M are the number of processors, the maximum number of adjacent processors, and the maximum size (in bits) of a message, respectively. We next show that, for any arbitrarily fixed constant n, O(1) bits are sufficient to construct a leader election algorithm that works in any network of size n. [ABSTRACT FROM AUTHOR]

Software systems can be modeled as complex networks in which software components are abstract nodes and their interactions are abstract edges. This paper attempts to characterize the structural quality of complex software networks. We propose to use a novel statistical measure, called average propagation ratio, to characterize the structural quality of general complex software networks, such as software adaptivity and maintainability. Several real-world complex software networks are analyzed in some depth to demonstrate the application of average propagation ratios. Furthermore, we investigate the key factors that determine the average propagation ratios of general complex software networks, resulting in a set of guiding principles that can be used in practical network design for improving the structural quality of complex software systems. [ABSTRACT FROM AUTHOR]

Sense of direction is a property of the edge-labeling of a network whose availability facilitates computations and often decreases their complexity. In this paper we consider the problem of providing a sense of direction to an anonymous, unoriented torus. The edges of the torus are initially labeled arbitrarily, and they have to be relabeled with a classical compass sense of direction. We first describe an algorithm where the relabeling of the edges is performed by a mobile agent that carries a token. The algorithm is optimal both in terms of number of tokens (with no tokens the task cannot be performed), and in terms of number of moves. We then show that the same technique can be used to orient the torus in the classical message-passing environment, thus obtaining an orientation algorithm that improves all the existing ones in this setting. [ABSTRACT FROM AUTHOR]

It is well known that a solution for the Firing Squad Synchronization Problem (FSSP) takes time 2n - 1, n being the number of soldiers. It is also known that a solution on a square of n × n soldiers takes the same time. The main result of this paper is a new solution for the FSSP on networks shaped as squares. Our solution is optimal in two aspects: it is communication optimal (the so-called 1-bit solution) and is also time optimal, as it takes 2n - 1 time. It is also used as a building block to construct a very efficient solution on the square torus. Our approach applies also to linearly shaped networks and yields on the ring almost optimal time & communication solutions. In particular, for the square torus with n rows and rings of n processors, if n is even our solution is time & communication optimal. Otherwise, it is communication-optimal but does not match the lower bound on the time of a synchronization just by 1 time unit. [ABSTRACT FROM AUTHOR]

This paper proposes an adaptive network architecture, which can emulate the human knowledge as the fuzzy logic rule, and its applications as the controller for nonlinear systems. The structure of this proposed network, multi-input Fuzzy Rule Emulated Network or FREN, is derived based on human knowledge in the form of fuzzy IF-THEN rules. The initial setting of its parameters can be intuitively chosen from expert's experience. During the learning phase based on the gradient search, the learning rate can be adapted itself to remain the stability with the Lyapunov method. The performance of our network is presented by using this network as controller for the single invert pendulum plant and the water bath temperature control system. The comparison results with other conventional control algorithms such as artificial neural networks and PID controllers can be illustrated in each example. [ABSTRACT FROM AUTHOR]

Multicasting protocols deliver data packets from a source node to multiple receivers, and serve a very important function in mobile ad-hoc networks (MANETs). In this paper, a novel receiver-initiated soft-state probabilistic multicasting protocol (RISP) for MANETs is proposed. RISP is inspired by the ant colony's route-seeking mechanism, in which an individual ant chooses the optimal path to its destination through cooperation with others in a totally distributed manner. Imitating the behaviour of ants in nature, RISP introduces probabilistic forwarding and soft-state for making relay decisions that are automatically adaptive to node mobility in MANETs. Compared with other protocols, we show by computer simulations that RISP has lower delivery redundancy, while achieving higher delivery ratio at all mobility scenarios. Furthermore, RISP has lower control overhead. [ABSTRACT FROM AUTHOR]

This research addresses scheduling issues in networked computer systems with survivability requirements, i.e. systems in which essential services must survive malicious acts. In order to achieve survivability based on spatial redundancy, agreement algorithms are needed as a mechanism to consolidate results of individual replicas. The potentially enormous overhead associated with communication and voting schemes of the algorithms put unique burdens on the scheduler as the efficiency of scheduling determines the suitability of the agreement algorithm. This paper derives agreement task graphs, representing computations, and inter-process communication based on phantom tasks. Task graph primitives are identified and it is shown how their scheduling directly influences the performance of the agreement algorithm. Finally, the notion of dynamic k-of-N precedence is introduced and its impact on resource reclaiming for early stopping algorithms is discussed. [ABSTRACT FROM AUTHOR]

In this paper we study the square grid area required for laying out H[sub l], the Boolean hypercube of N=2[sup l] vertices. It is shown that this area is [formula]. We describe a layout which occupies this much area and prove that no layout of less area exists. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of constructing a multicast tree in star interconnection networks under the single-port communication model. Unlike previous schemes for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme of [formula] time units for the star graph of dimension n. [ABSTRACT FROM AUTHOR]