A peer-to-peer network over an ad hoc infrastructure is a powerful combination that provides users with means to access different kinds of information anytime and anywhere. In this paper we study the (re)configuration...
详细信息
A peer-to-peer network over an ad hoc infrastructure is a powerful combination that provides users with means to access different kinds of information anytime and anywhere. In this paper we study the (re)configuration issue in this highly dynamic scenario. We propose three (re)configuration algorithms especially concerned with the constraints of the environment presented. The algorithms aim to use the scarce resources of the network in an efficient way, improving the performance and the network lifetime. The algorithms were simulated and we used a simple Gnutella-like algorithm as comparison. The results show that the algorithms achieved their goals, presenting a good cost-benefit relation. (C) 2004 Elsevier Inc. All rights reserved.
Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target con...
详细信息
ISBN:
(纸本)3540304673
Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk slides in the plane without intersecting any other disk, so that its center moves along an arbitrary (open) continuous curve. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii and disk placements. For example, with n congruent disks, 3n/2 + O(root n log n) moves always suffice for transforming the start configuration into the target configuration;on the other hand, (1 + 1/15) n - O(root n) moves are sometimes necessary.
Achieving fault tolerance through incorporation of redundancy and reconfiguration is quite common. In this paper we study the fault tolerance of linear arrays of N processors with k bypass links whose maximum length i...
详细信息
Achieving fault tolerance through incorporation of redundancy and reconfiguration is quite common. In this paper we study the fault tolerance of linear arrays of N processors with k bypass links whose maximum length is g. We consider both arrays with bidirectional links and unidirectional links. We first consider the problem of testing whether a set of n faulty processors is catastrophic, i.e., precludes reconfiguration. We provide new testing algorithms which Improve and generalize known testing algorithms. For bidirectional arrays we provide an O(kn) time testing algorithm and for unidirectional arrays we provide an O(n) time algorithm for the case k=1, and an O(kn log k) time algorithm, for the case k>1, When the fault pattern is not catastrophic we study the problem of finding an optimal reconfiguration of the array. We consider optimality with respect to two parameters: the size of the reconfigured array and the number of redundant links to activate. Considering optimality with respect to the size of the reconfigured array, we prove that the problem is NP-hard in the strong sense if the bypass links are bidirectional, while it can be solved in O(kng) time if the bypass links are unidirectional. Considering optimality with respect to the number of bypass links to activate, we prove that the problem can be solved in O(kn) time if the bypass links are bidirectional, and in O(kng) lime if the bypass links are unidirectional. (C) 1998-Elsevier Science B.V. All rights reserved.
Recently, several strategies have been studied to recover faulty processing elements on mesh arrays. S. Y. Kung et al. propose 1 1/2 track model for reconfiguration of mesh arrays and the reconfiguration algorithm bas...
详细信息
ISBN:
(纸本)0818674601
Recently, several strategies have been studied to recover faulty processing elements on mesh arrays. S. Y. Kung et al. propose 1 1/2 track model for reconfiguration of mesh arrays and the reconfiguration algorithm based on graph theory by finding compensation paths. However, compensation path scheme does not perform reconfiguration efficiently since the strategy only focuses on faulty processing elements and require global information. In this paper, we propose a new reconfiguration strategy named recursive shift to recover faulty processing elements on mesh arrays. It is confirmed that out strategy obtain much higher array yield than the previous works without global information on identical redundant processing element.
暂无评论