Search

The topology of a MANET is maintained enduring transmission failures by suitably selecting multiple coordinators among the nodes constituting the MANET. The basic philosophy behind the algorithm is to isolate four coordinators based on positional data. Once elected, they are entrusted with the responsibility to emit signals of different frequencies while the other nodes individually decide the logic they need to follow in order to maintain the topology, thereby eliminating the need for routing. The algorithm is going to be formulated in such a way, that the entire network is going to move in one direction while each node can move freely. As far as our knowledge goes, we are the first ones to conceive the concept of multiple coordinators. The simulation results prove the efficacy of the scheme in topology maintenance. [ABSTRACT FROM AUTHOR]

In this paper, a storage mechanism is devised to balance the load and to provide immediate service to the clients with a start-up delay of 2ms to 7 ms. The video storage is based on the probability of the clients requesting for the video. Videos with higher probability of being requested are stored and replicated to ensure guaranteed retrieval. Parity generation scheme is employed to provide reliability to non-popular videos. The system is also capable of handling disk failures transparently and thereby providing a reliable service to the clients. [ABSTRACT FROM AUTHOR]

This paper proposes a new top-down hierarchical, multi-hop, routing protocol for the wireless sensor networks. The proposed solution is appropriate for random deployment and suitable for different sizes of target areas. This protocol forms clusters in which each cluster member is at one hop distance from the cluster head. This protocol ensures the participation of all the cluster heads in hierarchical topology formation. The proposed protocol is also capable of handling dynamic nature of the wireless sensor networks. The simulation results show the scalability of the proposed approach. [ABSTRACT FROM AUTHOR]

An interesting and useful application in ad hoc wireless mobile community is searching and locating information in a distributed and decentralized manner. Locating and collecting information in a highly dynamic network while minimizing the consumption of scarce resources such as bandwidth and energy is the main challenge in this domain. In this paper we present a radically new location aided content searching mechanism that can determine the location and the content as well of the information searched that incurs minimum overhead. Here we have used a stable geographically clustered network that enables us to distribute the search message in a location-aided manner. In disastrous scenarios the access of emergency information, services or resources is considered to be of special interest to the user groups. Mobile terminals are there to gather information from sensors and other sources. The location-Aided content searching mechanism discussed here is concerned with efficiently delivering this information together with the geographical location of the information to the person in the field on need basis. The mobility tolerant clusters structures are used to lower the proactive traffic while minimizing the query cost. We present results from detailed simulations that demonstrate the efficiency of our mechanism and discuss the scalability of this model to larger networks. [ABSTRACT FROM AUTHOR]

In today's broadband communication optical network is mostly used for backbone network establishment. In optical networks, it's the advent of wavelength division multiplexing, WDM, not only helps us to properly utilize available bandwidth of optical fiber but also helps us to manage the optical fiber medium in better way. Continuous lightpath would be treated as solution for lightpath establishment. And availability of the same wavelength throughout the whole path would be, only, cause of a lightpath establishment. It's the unavailability of the same wavelength throughout a path would cause lightpath not to be established and that would increase call blocking probability. Wavelength conversion in limited manner, one step wavelength conversion, is one solution to minimize call blocking probability. Here one wavelength assignment and one routing algorithm have been proposed which give us better results in terms of call blocking probability and processing time for wavelength assignment. [ABSTRACT FROM AUTHOR]

We study routing algorithms for three-dimensional ad hoc networks that guarantee delivery and are k-local, i.e., each intermediate node v's routing decision only depends on knowledge of the labels of the source and destination nodes, of the subgraph induced by nodes within distance k of v, and of the neighbour of v from which the message was received. We model a three-dimensional ad hoc network by a unit ball graph, where nodes are points in ℝ3, and nodes u and v are joined by an edge if and only if the distance between u and v is at most one. The question of whether there is a simple local routing algorithm that guarantees delivery in unit ball graphs has been open for some time. In this paper, we answer this question in the negative: we show that for any fixed k, there can be no k-local routing algorithm that guarantees delivery on all unit ball graphs. This result is in contrast with the two-dimensional case, where 1-local routing algorithms that guarantee delivery are known. Specifically, we show that guaranteed delivery is possible if the nodes of the unit ball graph are contained in a slab of thickness $1/\sqrt{2}$. However, there is no k-local routing algorithm that guarantees delivery for the class of unit ball graphs contained in thicker slabs, i.e., slabs of thickness $1/\sqrt{2} + \epsilon$ for some ε> 0. The algorithm for routing in thin slabs derives from a transformation of unit ball graphs contained in thin slabs into quasi unit disc graphs, which yields a 2-local routing algorithm. We also show several results that further elaborate on the relationship between these two classes of graphs. [ABSTRACT FROM AUTHOR]

Motivated by reducing communication overhead and prolonging network lifetime in wireless ad hoc and sensor networks, we propose an energy-efficient dominating tree construction (EEDTC) algorithm to construct a dominating tree that can serve as a communication backbone in wireless infrastructures. The algorithm has a theoretical approximation factor of at most 9, and has O(n) message complexity and O(n) time complexity. Due to the low message complexity, EEDTC performs well on energy consumption. The energy-aware ranking technique introduced can also balance energy consumption in the network, and hence reduce the probability of network failures caused by energy depletion of backbone nodes. [ABSTRACT FROM AUTHOR]

This paper deals with multimedia channel assignment in a hexagonal cellular network with two-band buffering. After deriving a lower bound on the minimum bandwidth for real-life situations, we present an algorithm for assigning channels using Genetic Algorithm (GA). We also propose an elegant technique for re-use of the channels, using only eighteen distinct frequency bands on a nine-node subgraph of the network, and then extend it for assignment of the complete network. The proposed algorithm converges very rapidly with required bandwidth close to the derived lower bound. [ABSTRACT FROM AUTHOR]

To extend the coverage area of conventional WLANs and to provide better mobility support, multi-hop WLANs are emerging as a viable and cost-effective solution. A possible way to construct such a multi-hop WLAN system is to employ an ad hoc routing protocol to discover and maintain the multi-hop paths between the clients and the access points. A prerequisite of proper routing is that all the nodes have a unique network-layer identifier. However, traditional autoconfiguration protocols commonly used in infrastructure-based WLANs, such as DHCP, are not directly applicable in this context due to multi-hop relaying between hosts. In this paper we propose an enhancement of DHCP to enable dynamic address allocation of mobile nodes in multi-hop WLAN systems, without changing the legacy implementation of the DHCP servers. We have implemented a prototype of our solution, and we have measured the maximum delay needed to configure an IP address under various topology configurations and network loads. Our experimental results indicate that the proposed mechanism is quite fast in lightly loaded networks, while the contention between data traffic and control messages may significantly increase the configuration delay. [ABSTRACT FROM AUTHOR]

Overloading is a technique to accommodate more number of users than the spreading factor N. This is an efficient way to increase the number of users in a fixed bandwidth, which is of practical interest to mobile system operators. In this paper we have reviewed the different overloading schemes proposed in the literature for the DS-CDMA systems. The performance of an Orthogonal/Orthogonal (O/O) overloading scheme, using two sets of orthogonal codes (O/s-O) has been evaluated. Iterative multistage detector (IMSD) is used to reduce the multiple access interference between the users of two sets. The BER performance of IMSD is evaluated with hard and soft decisions functions using Monte-Carlo simulations. It is found that, this scheme provides 19% and 11% channel overloading for synchronous DS-CDMA system in an AWGN channel, with a SNR degradation of less than 0.5 dB at a BER of 10− 5 compared to single user bound for N=16 and 64 respectively. [ABSTRACT FROM AUTHOR]

In this paper, we determine class specific optimal minimum contention window (CWmin) values that simultaneously maximizes aggregate saturation throughput and provides proportional throughput differentiation meeting deterministic target throughput ratios among multiple priority classes in IEEE 802.11 wireless LAN (WLAN). We show that, with the current default CWmin setting, IEEE 802.11e Enhanced Distributed Channel Access (EDCA) cannot provide satisfactory throughput differentiation among multiple priority classes. Compared to EDCA, the proportional throughput differentiation can provide consistent and adjustable differentiation among different service classes. With these optimal CWmin values, the aggregate throughput remains maximum and insensitive to the number of active nodes in the network, thus improving the scalability of the protocol. [ABSTRACT FROM AUTHOR]

The paper describes a policy-based model for cost-effective ‘data connectivity' provisioning between session-level end-points. Data flows with closely-similar QoS needs are aggregated over an end-to-end logical path. The available infrastructure bandwidth is apportioned between various paths that carry (aggregated) data flows with distinct QoS levels. Flow aggregation over a path allows reaping the statistical multiplexing gains in bandwidth. Whereas, a path-level bandwidth allocation allows meeting the QoS needs of data flows sharing this path. The SP installs policy functions at the end-points that can make the connectivity provisioning cost-optimal in different operating regions of the system. [ABSTRACT FROM AUTHOR]

Several analytical performance models for Circuit Switching (CS) in k-ary n-cubes have been reported in the literature. However, to the best of our knowledge, the performance properties of CS have not been investigated in the mesh networks. To address this shortcoming, this paper proposes the first analytical modeling approach to predict the mean message latency in 2-D mesh interconnect networks using CS augmented with virtual channels. Analytical approximations of the model are confirmed by comparing with those obtained through simulation experiments. [ABSTRACT FROM AUTHOR]

A desirable property of any system is that if a user is ready to pay for a specific level of service, the system should be able to meet his requirement. Currently, Internet does not provide a standard mechanism to price its resources. A multi level pricing scheme is proposed to reflect the hierarchical structure of the Internet, care being taken to ensure that it requires minimal changes to the Internet protocols. Data statistics are maintained as an aggregate, thus reducing the load on intermediate routers in the Internet. The proposed mechanism performs the dual functions of providing service differentiation according to budgets, and doing congestion control through feedback at time scale comparable to a round trip time. We investigate stability issues of the multi level pricing scheme. Simulation results for the different traffic scenarios show that the proposed pricing model increases the aggregate user utility function while adequately responding to congestion and providing service differentiation. [ABSTRACT FROM AUTHOR]

We address the problem of message authentication in communication networks which are resource constrained or are performance bound. Recent research has focused on development of symmetric key protocols for authentication in such networks. In these protocols, the sender generates a pool of keys -used to sign the messages, and distributes a different subset of keys -used to verify the signatures, to each user. However, in these protocols, users can collude to combine their keys and impersonate the sender by generating the sender signatures. In this work, we describe a family of collusion resistant symmetric key distribution protocols for authentication which address the problem of collusion. We show that the collusion resistance achieved using our protocols is practical (and hence, sufficient) for networks whose communication diameter is known or is within fixed bounds. Furthermore, we show that some existing protocols in literature are members of our family of protocols. [ABSTRACT FROM AUTHOR]

This paper presents a novel approach to processing continuous aggregate queries in sensor networks, which lifts the assumption of tree-based routing. Given a query workload and a special-purpose gateway node where results are expected, the query optimizer exploits query correlations in order to generate an energy-efficient distributed evaluation plan. The proposed optimization algorithms identify common query sub-aggregates, and propose common routing structures to share the sub-aggregates at an early stage. Moreover, they avoid routing sub-aggregates of the same query through long-disjoint paths, thus further reducing the communication cost of result propagation. The proposed algorithms are fully-distributed, and are shown to offer significant communication savings compared to existing tree-based approaches. A thorough experimental evaluation shows the benefits of the proposed techniques for a variety of query workloads and network topologies. [ABSTRACT FROM AUTHOR]

This paper proposes fault detection and localization scheme to handle multiple failures in the optical network using wavelength-division multiplexing (WDM) technology. This proposed scheme is two-phased scheme containing (a) the detection of faults through monitoring devices raising alarms (fault detection) and (b) subsequently the localization of these faults (fault localization) by invoking an algorithm. The later phase will obtain a set of potential faulty nodes (links). We demonstrate the performance of the scheme on 14-node NSFNet and 28-node EuroNet. We compare our scheme with an existing algorithm [1] for locating faulty nodes (links). Our scheme outperforms the existing one. [ABSTRACT FROM AUTHOR]

Wavelength Division Multiplexing (WDM) offers the capability to handle the increasing demand of network traffic in a manner that takes the advantage of already deployed optical fibers. A lightpath is an all optical communication path between end-to-end over a same wavelength used on each intermediate link. Wavelengths are the main resources in WDM optical networks. The wavelength assignment problem has been solved by mapping it to a heuristic based clique partitioning problem under the wavelength continuity constraint. For routing, Dijkstra's shortest-path algorithm is used. Here, we propose two new polynomial time heuristics for wavelength assignment called CPWA1 and CPWA2, based on clique partitioning concepts for static traffic demand with the objective of minimizing the number of wavelengths. The performance of our proposed algorithms are analyzed through extensive simulations on different set of traffic demands under a wide range of network topologies. The results show that proposed mechanism requires less number of wavelengths per fiber for a given set of traffic demand as compared to an existing well known algorithms. [ABSTRACT FROM AUTHOR]

In WDM optical networks, prior to data transfer, lightpath establishment between source and destination nodes is usually carried out through a Wavelength Reservation Protocol (WRP), for which there are different approaches, such as Source Initiated Reservation Protocol (SIRP), Destination Initiated Reservation Protocol (DIRP) and Intermediate node Initiated Reservation Protocol (IIRP). At high load, due to scarcity of resources, a request is blocked primarily due to two important factors, namely ‘outdated link information' (in case of DIRP) and ‘over reservation' (in case of SIRP). To minimize the effect of both the factors (as attempted in IIRP), we propose to split a probe attempt into two concurrent (upstream and downstream) reservation attempts at some intermediate points (selected adaptively). This novel WRP, termed as Split Reservation Protocol (SRP) in the paper, is a potential competitor for IIRP. So we analyze SRP at length and compare it with IIRP for different network situations. The comparative results show that, for SRP, the blocking probability improves by even 90% in some cases, and the control overhead decreases by 29% sometimes. However, the average setup latency increases by 10% in most cases. So the proposed scheme appears quite promising especially for the applications (such as short messaging) where the blocking probability is the most important criteria. [ABSTRACT FROM AUTHOR]

Optimization in energy consumption of the existing synchronization mechanisms can lead to substantial gains in terms of network life in Wireless Sensor Networks (WSNs). In this paper, we analyze ERBS and TPSN, two existing synchronization algorithms for WSNs which use widely different approach, and compare their performance in large scale WSNs each of which consists of different type of platform and has varying node density. We, then, propose a novel algorithm, PROBESYNC, which takes advantage of differences in power required to transmit and receive a message on ERBS and TPSN and leverages the shortcomings of each of these algorithms. This leads to considerable improvement in energy conservation and enhanced life of large scale WSNs. [ABSTRACT FROM AUTHOR]

As sensor network applications often involve remote, distributed monitoring of inaccessible and hostile locations, they are vulnerable to both physical and electronic security breaches. The sensor nodes, once compromised, can send erroneous data to the base station, thereby possibly compromising network effectiveness. We consider sensor nodes organized in a hierarchy where the non-leaf nodes serve as the aggregators of the data values sensed at the leaf level and the Base Station corresponds to the root node of the hierarchy. To detect compromised nodes, we use neural network based learning techniques where the nets are used to predict the sensed data at any node given the data reported by its neighbors in the hierarchy. The differences between the predicted and the reported values is used to update the reputation of any given node. We compare a Q-learning schemes with the Beta reputation management approach for their responsiveness to compromised nodes. We evaluate the robustness of our detection schemes by varying the members of compromised nodes, patterns in sensed data, etc. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSN) are attractive for information gathering in large-scale data rich environments. In order to fully exploit the data gathering and dissemination capabilities of these networks, energy-efficient and scalable solutions for data storage and information discovery are essential. In this paper, we formulate the information discovery problem as a load-balancing problem, with the combined aim being to maximize network lifetime and minimize query processing delay resulting in QoS improvements. We propose a novel information storage and distribution mechanism that takes into account the residual energy levels in individual sensors. Further, we propose a hybrid push-pull strategy that enables fast response to information discovery queries. Simulations results prove the proposed method(s) of information discovery offer significant QoS benefits for global as well as individual queries in comparison to previous approaches. [ABSTRACT FROM AUTHOR]

Intrusion detection systems are increasingly a key part of systems defense. Various approaches to intrusion detection are currently being used, but they are relatively ineffective. Constructing and maintaining a misuse detection system is very labor-intensive since attack scenarios and patterns need to be analyzed and categorized, and the corresponding rules and patterns need to be carefully hand-coded. Thus data mining can be used to ease this inconvenience. This paper proposes a multiple level hybrid classifier for an intrusion detection system that uses a combination of tree classifiers which rely on labeled training data and applies an Ant colony clustering algorithm for mixed data. The main advantage of this approach is that the system can be trained with unlabelled data and is capable of detecting previously "unseen" attacks. Verification tests have been carried out by using the 1999 KDD Cup data set. From this work, it is observed that significant improvement has been achieved from the viewpoint of both high intrusion detection rate and reasonably low false alarm rate. [ABSTRACT FROM AUTHOR]

In this paper, we describe SuperTrust, a novel framework designed to handle trust relationships in Super peer networks. What distinguishes SuperTrust from other contributions is that trust reports remain encrypted and are never opened during the submission or aggregation processes, thus guaranteeing privacy and anonymity of transactions. As reputations of peers influence their future interactions, we argue that such systems must have properties like fairness and soundness, persistence, eligibility and unreusability of reports, similar to the properties of current electronic voting systems. SuperTrust is a decentralized protocol, based on K-redundant Super peer networks, that guarantees the aforementioned properties and is in some sense complementary to the models proposed for building trust among peers. Additionally the framework is very efficient and minimizes the effects of collusion of malicious Super peers/aggregators. We have tested the framework on a large subset of peers and demonstrated via simulations its superior performance when compared to the other proposed protocols. [ABSTRACT FROM AUTHOR]

The stretched hypercube has recently been introduced as an attractive alternative to the well-known hypercube. Previous research on this network topology has mainly focused on topological properties, VLSI and algorithmic aspects of this network. Several analytical models have been proposed in the literature for different interconnection networks, as the most cost-effective tools to evaluate the performance merits of such systems. This paper proposes an analytical performance model to predict message latency in wormhole-switched stretched hypercube interconnection networks with fully adaptive routing. The analysis focuses on a fully adaptive routing algorithm which has been shown to be the most effective for stretched hypercube networks. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy under different operating conditions. [ABSTRACT FROM AUTHOR]

Peer to Peer (P2P) communities (or "interest groups") are referred to as nodes that share a common interest. Each peer in the system claims to have some interests and, accordingly, would like to become a member of these groups. The available interest groups are arranged according to a hierarchical semantics ontology, and managed with a semantic overlay network. P2P community structure is highly dynamic: a peer may be added to or deleted from a community; communities may be added or deleted; communities may be merged or split; and sub-communities may become parent-level communities and vice versa. In this paper, we propose a highly flexible multi-level data structure to capture the visibility aspect of P2P communities. The data structure is simple, facilitates dynamic changes easily and efficiently in a decentralized fashion, and is highly scalable. [ABSTRACT FROM AUTHOR]

Protocols for Generalized Oblivious Transfer(GOT) were introduced by Ishai and Kushilevitz [10]. They built it by reducing GOT protocols to standard 1-out-of-2 oblivious transfer protocols based on private protocols. In our protocols, we provide alternative reduction by using secret sharing schemes instead of private protocols. We therefore show that there exist a natural correspondence between GOT and general secret sharing schemes and thus the techniques and tools developed for the latter can be applied equally well to the former. [ABSTRACT FROM AUTHOR]

In this paper, we propose an efficient authenticated key establishment scheme for self-organizing sensor networks. The proposed scheme has low communication cost and eliminates expensive operations required by most ID-based schemes, such as sensor nodes calculating bilinear maps. Additionally, the proposed scheme provides perfect forward secrecy. [ABSTRACT FROM AUTHOR]

This paper presents a tree-based anycast (TBA) protocol designed for wireless sensor/actuator networks. Contrary to existing work, TBA allows forming an anycast address from multiple attributes which describe the destination node. TBA uses spanning trees for query propagation. The usefulness of such a solution is validated by simulations, which show that under certain conditions significant energy gain compared to flooding can be expected. [ABSTRACT FROM AUTHOR]

For multi-hop wireless sensor networks, this paper presents a simple, loop-free, distributed algorithm to select path for data gathering from each sensor node to the sink node that attempts to balance the load in terms of power dissipation in communication at individual nodes with 100% data aggregation to enhance the lifetime of the network as a whole. It requires just a one-time computation during the initialization of the network, and the paths remain static unless the routing tree gets partitioned due to faults etc. The performance of the proposed scheme has been compared with some conventional centralized routing techniques, namely the minimum hop routing, the shortest power path routing and the minimum spanning tree routing by simulation. In all the cases, the proposed algorithm results improved lifetime. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new deterministic key predistribution scheme for secure communication in wireless sensor networks. Our scheme provides better trade-off among scalability, computation overhead, connectivity and resilience against node captures than existing key predistribution schemes, particularly in situations where the nodes in the network are highly mobile. [ABSTRACT FROM AUTHOR]

We consider the rendezvous problem which requires k mobile agents that are dispersed in a ring of size n, to gather at a single node of the network. The problem is difficult to solve when the agents are identical (i.e. indistinguishable), they execute the same deterministic algorithm, and the nodes of the ring are unlabelled (i.e. anonymous). In this case, rendezvous can be achieved by having each agent mark its starting location in the ring using a token. This paper focusses on fault tolerant solutions to the problem when tokens left by an agent may fail unexpectedly. Previous solutions to the problem had several limitations—they either assumed a completely synchronous setting or were restricted to few specific instances of the problem where the value of n is such that $\gcd(n,k')=1$ ∀ k′ ≤ k. We improve on these results, solving rendezvous in asynchronous rings for arbitrary values of n and k, whenever it is solvable. [ABSTRACT FROM AUTHOR]

This paper present a framework for describing distributed algorithms for mobile agents in an anonymous network. We make use of the high level encoding of these algorithms as transitions rules. The main advantage of this uniform and formal approach is the proof correctness of the distributed algorithms. We illustrate this approach by giving examples of distributed computations of a spanning tree by mobile agents in anonymous network. [ABSTRACT FROM AUTHOR]

The algorithms dealing with the galled tree problem mostly use a conflict graph as the major tool and the construction of the conflict graph has been the central computation in these algorithms. In this paper, we present a parallel algorithm for the construction of a conflict graph. Given a set of n binary sequences, each of size m, our algorithm is mapped on an OTIS-Triangular array and requires 4m + 2n/k -7 electronics moves + 2 OTIS moves, where k = m (m -1)/2. The algorithm is shown to be scalable with respect to n. [ABSTRACT FROM AUTHOR]

We present a wait-free solution to the generalized dining philosophers problem under eventual weak exclusion in environments subject to crash faults. Wait-free dining guarantees that every correct hungry process eventually eats, regardless of process crashes. Eventual weak exclusion ($\diamondsuit \mathcal{WX}$) actually allows scheduling mistakes, whereby mutual exclusion may be violated finitely-many times; for each run, however, there must exist a convergence point after which live neighbors never eat simultaneously. Wait-free dining under $\diamondsuit \mathcal{WX}$ is particularly useful for synchronization tasks where eventual safety is sufficient for correctness (e.g., duty-cycle scheduling, self-stabilizing daemons, and contention managers). Unfortunately, wait-free dining is unsolvable in asynchronous systems. As such, we characterize sufficient conditions for solvability under partial synchrony by presenting a wait-free dining algorithm for $\diamondsuit \mathcal{WX}$ using a local refinement of the eventually perfect failure detector $\diamondsuit \mathcal{P}_1$. [ABSTRACT FROM AUTHOR]

In this paper, we investigate an efficient deadlock-free shortest path routing algorithm for WK-recursive mesh networks which has been shown that possess several advantages like suitable to be manufactured by VLSI technology and easy to be expanded. It will be shown that the proposed algorithm requires O($\sqrt{n}$) routing steps (where N is the network size) to route the entire network by exploiting either the self-routing or second order routing scheme. [ABSTRACT FROM AUTHOR]

The NAS Conjugate Gradient (CG) benchmark is an important scientific kernel used to evaluate machine performance and compare characteristics of different programming models. CG represents a computation and communication paradigm for sparse linear algebra, which is common in scientific fields. In this paper, we present the porting, performance optimization and evaluation of CG on Cell Broadband Engine (CBE). CBE, a heterogeneous multi-core processor with SIMD accelerators, is gaining attention and being deployed on supercomputers and high-end server architectures. We take advantages of CBE's particular architecture to optimize the performance of CG. We also quantify these optimizations and assess their impact. In addition, by exploring distributed nature of CBE, we present trade-off between parallelization and serialization, and Cell-specific data scheduling in its memory hierarchy. Our final result shows that the CG-Cell can achieve more than 4 times speedup over the performance of single comparable PowerPC Processor. [ABSTRACT FROM AUTHOR]

We present a compile time list heuristic scheduling algorithm called Low Cost Critical Path algorithm (LCCP) for the distributed memory systems. LCCP has low scheduling cost for both homogeneous and heterogeneous systems. In some recent papers list heuristic scheduling algorithms keep their scheduling cost low by using a fixed size heap and a FIFO, where the heap always keeps fixed number of tasks and the excess tasks are inserted in the FIFO. When the heap has empty spaces, tasks are inserted in it from the FIFO. The best known list scheduling algorithm based on this strategy requires two heap restoration operations, one after extraction and another after insertion. Our LCCP algorithm improves on this by using only one such operation for both the extraction and insertion, which in theory reduces the scheduling cost without compromising the scheduling performance. In our experiment we compare LCCP with other well known list scheduling algorithms and it shows that LCCP is the fastest among all. [ABSTRACT FROM AUTHOR]

Association rule mining is one of the most researched areas because of its applicability in various fields. We propose a novel data structure called Sequence Pattern Count, SPC, tree which stores the database compactly and completely and requires only one scan of the database for its construction. The completeness property of the SPC tree with respect to the database makes it more suitable for mining association rules in the context of changing data and changing supports without rebuilding the tree. A performance study shows that SPC tree is efficient and scalable. We also propose a Doubly Logarithmic-depth Tree, DLT, algorithm which uses SPC tree to efficiently mine the huge amounts of geographically distributed datasets in order to minimize the communication and computation costs. DLT requires only O(n) messages for support count exchange and it takes only O(loglogn) time for exchange of messages, which increases its efficiency. [ABSTRACT FROM AUTHOR]

This paper presents a distributed Grid-based Density Clustering using Triangle-subdivision (DGDCT), capable of identifying arbitrary shaped embedded clusters as well as multi density clusters over large spatial datasets. Experimental results are presented to establish the superiority of the technique in terms of scale-up, speedup as well as cluster quality. [ABSTRACT FROM AUTHOR]

The chromatic sum of a graph G is the minimum sum of colors in a vertex coloring of G. This problem has many interests like in networks, where it models the minimization of the total charge of a network. As systems are more and more large and dynamic, distributed approaches are needed to manage them. In this paper we present a self-stabilizing algorithm to determine a minimal sum of colors for a graph. Such a coloring is determined with at most O(nΔ2) changes of colors, where Δ is the maximum degree of the graph. [ABSTRACT FROM AUTHOR]

Fixed Task Priority (FTP) scheduling algorithms are priority-driven scheduling algorithms in which all jobs generated by each recurrent task are restricted to have the same priority. The multiprocessor FTP scheduling of sporadic task systems is studied in this paper. A new sufficient schedulability test is presented and proved correct. It is shown that this test offers non-trivial quantitative guarantees, including a processor speedup bound. [ABSTRACT FROM AUTHOR]

Data Grids seek to harness geographically distributed resources for large-scale data-intensive problems. The issues that need to be considered in the Data Grid research area include resource management for computation and data. Computation management comprises scheduling of jobs, load balancing, fault tolerance and response time; while data management includes replication and movement of data at selected sites. As jobs are data intensive, data management issues often become integral to the problems of scheduling and effective resource management in the Data Grids. Therefore, integration of data replication and scheduling strategies is important. Such an integrating solution is either non-existent or work in a centralized manner which is not scalable. The paper deals with the problem of integrating the scheduling and replication strategies in a distributed manner. As part of the solution, we have proposed a Distributed Replication and Scheduling Strategy (DistReSS) which aims at an iterative improvement of the performance based on coupling between scheduling and replication, which is achieved in distributed and hierarchical fashion. Results suggest that, in the context of our experiments, DistReSS performs comparable to the centralized approach when the parameters are tuned properly in addition to being more scalable to the centralized approach. [ABSTRACT FROM AUTHOR]

Switching between protocols based on environment is an elegant idea of enabling adaptation in distributed systems. Also self-stabilizing algorithms have been proposed as a mechanism to handle transient failures in distributed systems. In this work we illustrate self-stabilizing distributed protocol switching by proposing a self-stabilizing algorithm for dynamically switching between a BFS tree and a DFS tree. At low network load, the BFS tree may be used for broadcasting messages since it also minimizes delay. At higher network load, the DFS tree may be used to reduce the load on any one node. Both trees are rooted at the common broadcast source. Different properties relating to the delivery of broadcast messages under different failure conditions are investigated. [ABSTRACT FROM AUTHOR]

The k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most k different values are decided. It has been shown that any algorithm that solves the k-set agreement problem in synchronous systems that can suffer up to t crash failures requires $\lfloor \frac{t}{k} \rfloor +1$ rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after $\min\big( \lfloor \frac{f}{k} \rfloor +2, \lfloor \frac{t}{k} \rfloor +1\big)$ rounds, where f is the number of actual crashes in a run (0 ≤ f ≤ t). This paper explores a new direction to solve the k-set agreement problem in a synchronous system. It considers that the system is enriched with base objects (denoted [m,ℓ]_SA objects) that allow solving the ℓ-set agreement problem in a set of m processes (m < n). The paper has several contributions. It first proposes a synchronous k-set agreement algorithm that benefits from such underlying base objects. This algorithm requires $O(\frac{t \ell}{m k})$ rounds, more precisely, $R_t= \lfloor \frac{t}{\Delta} \rfloor +1$ rounds, where $\Delta= m \lfloor \frac{k}{\ell} \rfloor + (k\mbox{ mod } \ell)$. The paper then shows that this bound, that involves all the parameters that characterize both the problem (k) and its environment (t, m and ℓ), is a lower bound. The proof of this lower bound sheds additional light on the deep connection between synchronous efficiency and asynchronous computability. Finally, the paper extends its investigation to the early deciding case. It presents a k-set agreement algorithm that directs the processes to decide and stop by round $R_f=\min\big(\lfloor \frac{f}{\Delta} \rfloor +2, \lfloor \frac{t}{\Delta} \rfloor +1\big)$. These bounds generalize the bounds previously established for solving the k-set problem in pure synchronous systems. [ABSTRACT FROM AUTHOR]

Consensus is an important building block for building replicated systems, and many consensus protocols have been proposed. In this paper, we investigate the building blocks of consensus protocols and use these building blocks to assemble a skeleton that can be configured to produce, among others, three well-known consensus protocols: Paxos, Chandra-Toueg, and Ben-Or. Although each of these protocols specifies only one quorum system explicitly, all also employ a second quorum system. We use the skeleton to implement a replicated service, allowing us to compare the performance of these consensus protocols under various workloads and failure scenarios. [ABSTRACT FROM AUTHOR]

The current state of the art of workflow composition over web services employ a centralized composite process to coordinate the constituent web services. Therefore, the coordinator process is complex, less scalable, and bulky. This paper introduces an architecture and associated techniques for distributed coordination of these workflows, and a prototype system, namely BondFlow system, with capability to control workflow execution using a handheld device. We distribute the centralized coordination logic of traditional workflows by (i) extending the stateless web services into self-coordinating entities using coordinator proxy objects, and (ii) creating the workflow over these entities by interconnecting them into a distributed network of objects using web bond primitives. Previously, we have developed web bond primitives to enforce interdependencies among autonomous entities. The prototypedr BondFlow systeh provides a platform to configure such distributed workflows, producing coordination components with a footprint small enough to be executed on a handheld (footprint no larger than 150 KB). [ABSTRACT FROM AUTHOR]

We propose the first snap-stabilizing wave algorithm for anonymous networks. In the worst case, a process decides in O(n + D) time units, where n and D are the number of process and the diameter of the network, respectively. The proposed algorithm uses a self-stabilizing underlying unison protocol. If the underlying unison is stabilized when a process request a wave, then a decide event occurs in an optimal time, i.e., O(D) time units. The proposed solution is generic in the sense that, it can be used for any static or dynamic scheme which is feasible in an anonymous network. In particular, as an application of our scheme, we provide a snap-stabilizing causal atomic broadcast for anonymous networks, which can be used as a pipeline of messages. [ABSTRACT FROM AUTHOR]

We propose a generalized scheme that can convert any algorithm that self-stabilizes under an unfair central daemon into a randomized one that self-stabilizes under a distributed daemon, using only constant extra space and without IDs. If the original algorithm is anonymous the resulting self-stabilizing algorithm is also anonymous. We provide a detailed complexity analysis that show that the expected slowdown is upper bounded by O(n3). [ABSTRACT FROM AUTHOR]

A Distributed Shared Memory (DSM) system logically implements the shared-memory model on a physically distributed-memory system. Jackal is an open source [2] fine grained distributed shared memory implementation of the Java programming language. Java inherently supports parallel programming with the use of multi-threading. Jackal exploits this property and allows users to run multi-threaded programs unmodified on a distributed memory environment such as a cluster. Since the built-in language support for threads is insufficient for many programming tasks, Java-1.5 introduces concurrent utilities [4]. Concurrent utilities of Java are classes that are designed as building blocks in making concurrent classes or applications. These utilities provide reduce programming effort, increase performance, increase reliability, improve maintainability and increase productivity. In this work we implement a subset of these utilities in Jackal. [ABSTRACT FROM AUTHOR]