Search

The significant proliferation of research papers in both conferences and journals has made it difficult for researchers to easily access relevant scholarly papers for academic learning. This has been a substantial problem for many researchers. Conferences, in comparison with journals, have an aspect of social learning and networking, which leads to personal familiarisation through various interactions among researchers. In this paper, we improve the social awareness of conference participants by proposing a novel folksonomy-based paper recommendation algorithm, called socially aware recommendation of scholarly papers (SARSP). SARSP recommends papers issued by active participants (APs), to other Group Profile Participants at the same conference based on preference similarity of their research interests. In addition, SARSP computes the social ties between an AP and other conference participants to effectively generate social recommendations of scholarly papers. We evaluate our proposed algorithm using a real-world data-set. Our experimental results confirm that SARSP has significant improvement over other existing methods. [ABSTRACT FROM AUTHOR]

This paper proposes an unconventional architecture and algorithm for implementing reservoir computing on FPGA. An architecture-oriented algorithm with improved throughput and architecture designed to reduce memory and hardware resource requirements are presented. The proposed architecture exhibits good performance in terms of benchmarks for reservoir computing. A prediction accelerator for reservoir computing that operates on 55.45 mW at 450 K fps with <3000 LEs is realized by implementing the architecture on FPGA. The proposed approach presents a novel FPGA implementation of reservoir computing focussing on both algorithms and architecture that may serve as a basis for applications of AI at network edge. [ABSTRACT FROM AUTHOR]

Smart device networks form the backbone of many Internet of Things (IoT) applications. The performance of these systems depended on many factors. This includes their ability to connect to each other and network latency. In this paper, two algorithms are discussed that build a Peer-to-peer (P2P) overlay network. The focus is on real-time end-to-end remote instrumentation for IoT applications. P2P overlay networks are used for various purposes from content distribution through to media sharing. In contrast to traditional P2P systems, IoT systems can be highly sensitive to network latency and require low bandwidth. The main contributions of this paper are two algorithms to create overlay networks that assign peer nodes to super-peer nodes. The network contains a large number of smart devices and the key aim is to minimize system wide network latency. Other constraints regarding the nodes ability include the ability to become a super-peer node such as connectivity and limited processing capacities of the smart devices are also considered in context of a P2P remote instrumentation system. Both algorithms create a 3-hop network where the latency is lowered as much as possible with the given set of nodes. The algorithms have been validated through simulation. [ABSTRACT FROM AUTHOR]

In Wireless Rechargeable Sensor Networks (WRSNs), wireless chargers can recharge batteries of sensor nodes so that they can operate sustainably. Since wireless chargers are costly and have limited charging distances and angles, how to apply as few as possible chargers to cover all sensor nodes and satisfy their energy requirements is thus an important and challenging problem. This paper introduces the PSCD (Particle Swarm Charger Deployment) algorithm and the IPSCD (Improved PSCD) algorithm using the Particle Swarm Optimization (PSO) concept to nearly optimize WRSN charger deployment. PSCD and IPSCD estimate charging efficiency according to the distance and angle between chargers and sensor nodes. They then, on the basis of PSO, utilize the local optimum and the global optimum to adjust locations and antenna orientations of chargers to make WRSNs sustainable. We perform experiments using practical wireless chargers to obtain charging efficiency data. Based on the data, PSCD and IPSCD are simulated for obtaining the best parameter setting, and compared with two related greedy algorithms to show their superiority. This paper introduces the PSCD (Particle Swarm Charger Deployment) algorithm and the IPSCD (Improved PSCD) algorithm, which utilize the Particle Swarm Optimization (PSO) concept to deploy as few as possible wireless chargers with adjusted positions and antenna directions to fulfill the energy requirement of sensor nodes of a WRSN (Wireless Rechargeable Sensor Network) inside a cuboid with length L, width W and height H. [ABSTRACT FROM AUTHOR]

This paper proposed a new electrical synaptic transmission-based Spiking Neural P system (SNP system) based on SNP systems. Some new elements are added into the original definition of SNP systems, such as new synapses, bidirectional model, two types of neurons and cancelling the delay of axon. Because SNP system is easy to express the logical relationship between graphics and has strong ability to process information in parallel, the bidirectional characteristics of electrical synaptic transmission is effectively combined with the electrical quantity (direction of current) for fault location of distribution network with distributed generations (DGs) in this paper. The fault location model and reasoning algorithm of the electrical synaptic transmission-based SNP system are studied with the advantages of high accuracy, less computation, simple and intuitive model and reasoning. Furthermore, the algorithm is applied reasonably in the bidirectional power flow characteristics of a distribution network with DGs. Finally, this paper verifies the effectiveness, accuracy and reliability of the method through two cases which involve the single fault, multiple fault and misinformation fault. With the large-scale DGs (distributed generation) access to the distribution network, which changes the power flow structure and operation mode, the traditional protection strategy of the passive distribution network is no longer applicable. The fault location problem of distribution network with DGs is carried out. Firstly, Many fault location methods in the existing literatures have been anaylsised in this paper, then the electrical synaptic transmission-based spiking neural P system (ESSNP) has been proposed to solve the fault location problem. Foremore, the fault diagnosis mode for the power outage section with ESSNP has been established, which construct with Network description matrix and Fault current matrix. In order to verify the accuracy of the method in this paper, three cases have been studied, which the single fault, multiple faults and misinformation faults in each case. Finally, conclusions have been discussed. [ABSTRACT FROM AUTHOR]

Nowadays computational complexity of fast Walsh Hadamard transform and non-linearity for Boolean functions and large cryptographic substitution boxes is a major challenge of modern cryptography research on strengthening encryption schemes against linear and differential attacks. Time and memory complexities of the best existing algorithm for computing fast Walsh Hadamard transform and non-linearity for n × m substitution boxes is O (2 n + m). This paper proposes three new innovation in acceleration methods that improve the computation time for paralleled Walsh matrix up to 68 folds and the evaluation time for non-linearity degree up to 1021 folds. These methods include defining and accessing Walsh matrix transpose and combining an important part of evaluation process of non-linearity in the computation algorithm of Walsh matrix. The validity of the proposed algorithms is verified by means of simulation and experiments.The overall analysis of resource consumption of proposed algorithms is compared with previous ones. [ABSTRACT FROM AUTHOR]

Energy optimisation is one of the important issues in the research of wireless sensor networks (WSNs). In the application of monitoring, a large number of sensors are scattered uniformly to cover a collection of points of interest (PoIs) distributed randomly in the monitored area. Since the energy of battery-powered sensor is limited in WSNs, sensors are scheduled to wake up in a large-scale sensor network application. In this paper, we consider how to reduce the energy consumption and prolong the lifetime of WSNs through wake-up scheduling with probabilistic sensing model in the large-scale application of monitoring. To extend the lifetime of sensor network, we need to balance the energy consumption of sensors so that there will not be too much redundant energy in some sensors before the WSN terminates. The detection probability and false alarm probability are taken into consideration to achieve a better performance and reveal the real sensing process which is characterised in the probabilistic sensing model. Data fusion is also introduced to utilise information of sensors so that a PoI in the monitored area may be covered by multiple sensors collaboratively, which will decrease the number of sensors that cover the monitored region. Based on the probabilistic model and data fusion, minimum weight probabilistic coverage problem is formulated in this paper. We also propose a greedy method and modified genetic algorithm based on the greedy method to address the problem. Simulation experiments are conducted to demonstrate the advantages of our proposed algorithms over existing work. [ABSTRACT FROM AUTHOR]

In this paper, classes of automata that perform distributed computations with unconventional interaction are described and studied. These automata are called selective machines and they are more powerful than Turing machines while their high computing and recognising power can be achieved exclusively by interaction when a system of recursive algorithms (automata) becomes super-recursive due to their interaction. Computations of selective machines are described by selective algorithms, which are super-recursive allowing computations of functions that are incomputable by Turing machines. Examples of selective algorithms are grammars with prohibition, correction grammars and grammars with exclusion. The study of selective machines and selective algorithms is based on the axiomatic theory of algorithms, in which the results are obtained in the general situation of axiomatically defined classes of automata and algorithms. Then these results are specified for many concrete classes of automata and algorithms, such as finite automata or Turing machines, by checking the necessary axioms. [ABSTRACT FROM AUTHOR]

Over the last few years, there has been a rising trend towards the field of distributed testing where the implementation under test (IUT) has physical distributed ports. However, running several testers in such ports can lead to a number of coordination and synchronisation issues between these remote testers. We suggest in previous works to cope with these problems by enhancing the test architecture with some timing constraints. In this paper, we introduce a new algorithm to generate local timed test sequences so as to describe the behaviour of the test at each port. We aim through this algorithm to reduce the number of messages exchanged among the testers. Moreover, we illustrate our approach through a case study using MapReduce architecture with several worker components. These systems commonly encounter failures as a result of several circumstances, such as hardware faults, power outages, or network connection delays. To this end, we set the temporal properties in the specification of these systems. Then, we apply our algorithm to derive the related timed local test sequences. Furthermore, we explain how to apply our approach in the case of MapReduce testing to identify faulty workers, in order to reschedule their tasks to a healthy worker. [ABSTRACT FROM AUTHOR]

In this paper, eight variants of the Whale Optimisation Algorithm (WOA), that are based on eight different transfer functions, are introduced and used as search strategies in a wrapper feature selection model. Feature selection is a challenging task in machine learning process. It aims to minimise the size of a dataset by removing redundant and/or irrelevant features, with no information loss, to improve the efficiency of the learning algorithms. The used transfer functions belong to two different families; S-shaped and V-shaped. The proposed approaches have been tested on nine different high-dimensional medical datasets, with a low number of samples and multiple classes. The results revealed a superior performance for the V-shaped based approaches over the the S-shaped approaches. Moreover, the results of the V-shaped approach is compared with well-known feature selection approaches, and the superiority of the proposed approach is proven. [ABSTRACT FROM AUTHOR]

The emergence of chip-multiprocessor systems has dramatically increased the performance potential of computer systems. However, harnessing the full potential of these systems depends largely on the effectiveness of system software, such as compilers, in exploiting the on-chip parallelism. Additionally, since the amount of parallelism extracted by a compiler is directly influenced by the selection of the algorithm, algorithmic choice also plays a critical role in achieving a high fraction of peak performance. Hence, in the era of multicore computing, it is imperative that we re-evaluate and rethink algorithms for key problem domains. This paper investigates the impact of algorithmic choice on the performance of parallel implementations of the integral knapsack problem on multicore architectures. The study considers two classes of algorithms and several algorithmic variants and evaluates each implementation based on a variety of performance metrics including data locality and sharing, granularity of parallelism and scalability. The paper presents experimental results that show how each performance factor is affected by the selection of algorithm, changes in the input data-set and variations in architectural characteristics such as cache capacity and degree of cache sharing. [ABSTRACT FROM PUBLISHER]

Service level agreements (SLAs) are currently one of the major research topics in grid computing. Among many system components for supporting SLA-aware grid-based workflow, the SLA mapping mechanism receives a prominent position. It is responsible for assigning sub-jobs of the workflow to grid resources in a way that meets the user's deadline and minimises costs. Assuming many different kinds of sub-jobs and resources, the process of mapping a light communication workflow within an SLA context defines an unfamiliar and difficult problem. This paper presents a mapping algorithm, which can cope with this problem. The quality and efficiency of the algorithm is demonstrated through performance measurements. [ABSTRACT FROM AUTHOR]

Nowadays, large cities face numerous problems caused by the rapidly increasing number of vehicles on road. Carpooling has been shown as an efficient solution to ease the traffic pressure. The objective of our carpool scheduling problem is to minimise the number of carpools needed to transport users. Previous research on the similar topic introduces static capacity constraint which limits the carpool size to the vehicle's capacity. However, it is unnecessary since a seat in the vehicle can be occupied by several passengers if their routes are not overlapped. In this paper, we remove this constraint, which allows a vehicle to serve more users than its capacity. We propose a greedy approach based on the iterative matching and merging. Specifically, starting from a set of single-user carpools, the algorithm iteratively checks the merge-ability between carpools, and then applies the maximum matching algorithm to maximise the number of carpools merged. In addition, two methods are proposed to reduce the time complexity of merge-ability checking process. Furthermore, we improve the time efficiency of our algorithms by exploiting geometry properties. Experimental results on synthetic and real-world datasets show that our algorithms have better performances than baseline. [ABSTRACT FROM AUTHOR]

As an effective blind source separation method, non-negative matrix factorization has been widely adopted to analyze mixed data in hyperspectral images. To avoid trapping in local optimum, appropriate constraints are added to the objective function of NMF, whose reflections of image essential attribute determine the performance finally. In this paper, a new NMF-based mixed data analysis algorithm is presented, with maximum overall coverage constraint introduced in traditional NMF. The new constraint was proposed using data geometrical properties in the feature space to maximizes the number of pixels contained in the simplex constructed by endmembers compulsorily and introduced in objective function of NMF, named maximum overall coverage constraint NMF (MOCC-NMF), to analyze mixed data in highly mixed hyperspectral data without pure pixels. For implementing easily, multiplicative update rules are applied to avoid step size selection problem occurred in traditional gradient-based optimization algorithm frequently. Furthermore, in order to handle huge computation involved, parallelism implementation of the proposed algorithm using MapReduce is described and the new partitioning strategy to obtain matrix multiplication and determinant value is discussed in detail. In the numerical experiments conducted on real hyperspectral and synthetic datasets of different sizes, the efficiency and scalability of the proposed algorithm are confirmed. [ABSTRACT FROM AUTHOR]

The optical bus based arrays have recently shown many applications. In this paper we use the pipelining ability of the LARPBS to solve the repetitions detection problem. We propose an algorithm that finds all kind of repetitions in a string including k-power repetitions, overlapping repetitions and non-contiguous repetitions. For a given distance, this operation is performed in O(1) communication cycle with a constant computation time processors on a O(n) processors LARPBS for a string of length n. For all the periods, it is O(n) bus cycle. No previous algorithms were known for this problem on the LARPBS. [ABSTRACT FROM AUTHOR]

One of the most important issues in the design of distributed systems is process scheduling, which maps applications to resources in an attempt to reduce the application execution time or maximise resource utilisation. The complexity involved in finding good scheduling solutions has motivated the design of several heuristics and approximation algorithms. Although heuristics aim at finding good solutions within acceptable time constraints, they do not guarantee solution quality. On the other hand, approximation-based algorithms provide optimal solution bounds, but they are usually designed to address simple scenarios. In an attempt to combine the best of both algorithmic approaches, this paper proposes the min-heap-based scheduling algorithm (MHSA), which finds solutions for homogeneous and heterogeneous distributed environments within acceptable time constraints and optimal solution bounds. MHSA considers applications that can be bag-of-tasks or which communicate among each other. Such solutions minimise the application execution time and maximise resource utilisation; therefore, MHSA is a system-oriented scheduling algorithm. Results confirm that MHSA provides better solutions than schedulers such as Random, Round-Robin, Workload-Queue and List-Scheduling. In addition, MHSA provides an-approximation ratio for reaching optimal solution bounds. [ABSTRACT FROM AUTHOR]

In this paper, two modifications are proposed to the Progressive Random Walk (PRW) algorithm in order to address its potentially insufficient search space coverage. The first modification replaces the Pseudo-Random Number Generator (PRNG) with the uniform distribution by the chaotic map based PRNG for generating of the offset values and the second modification is called direction switching and is based on experiment observation. The modifications are implemented into the PRW and the resulting algorithm is called modified Progressive Random Walk. The search space coverage of the two algorithms is compared. Both algorithms are used in macro ruggedness estimation of the CEC2015 benchmark set and the results are discussed. [ABSTRACT FROM AUTHOR]

Each generation of CPU provides more resources and new features. These increase the ability to perform algorithms faster and with a higher degree of parallelism. The article discusses methods used to optimise CRC generation algorithms for long data blocks with consideration of the capabilities of contemporary systems. We analysed known software CRC algorithms and combined all known principles into a solution scalable in multiple CPU cores on single and multi-socket systems. Various algorithms were evaluated on contemporary multicore systems with 1 × 4, 1 × 64, 2 × 12, and 4 × 26 cores. The results show how the performance is affected by the architecture of the memory subsystem. Compared to the original sequential Sarwate algorithm, our algorithms are 48.0, 51.1, 38.0, and 28.8 times faster. [ABSTRACT FROM AUTHOR]

This study addresses the problem of 'Circle Formation on an Infinite Grid by Fat Robots' ( $ CF\_FAT\_GRID $ CF _FAT _GRID). Unlike prior work focused solely on point robots in discrete domain, it introduces fat robots to circle formation on an infinite grid, aligning with practicality as even small robots inherently possess dimensions. The algorithm, named $ CIRCLE\_FG $ CIRCLE _FG , resolves the $ CF\_FAT\_GRID $ CF _FAT _GRID problem using a swarm of fat luminous robots. Operating under an asynchronous scheduler, it achieves this with five distinct colors and by leveraging one-axis agreement among the robots. [ABSTRACT FROM AUTHOR]

Detection of an environmental phenomenon, e.g. air pollution and oil spills, occurs when a group of sensors continuously produces similar readings (i.e. data streams) over a period of time. Thus, detection of environmental phenomena is basically a process of clustering the sensors' data streams, which commonly involves the processing of hundreds and maybe thousands of data streams in real time. Since the sensor network environment is wireless, energy conservation of the sensors would be the main concern. Thus in this paper, we propose an efficient and energy friendly distributed scheme to detect phenomena in a wireless sensor network (WSN). To achieve fast response, the proposed algorithms reduce the dimensionality of the streams. Then, each stream is represented by a point in a multi-dimensional grid. The algorithm uses a grid-based clustering technique to detect clusters of similar stream values. The processing of the algorithm is distributed among different elements of the WSN in a hierarchical topology for more energy efficiency. The paper shows the feasibility of the proposed fully distributed scheme by comparing it with three other WSN schemes in terms of clustering accuracy and energy consumption. [ABSTRACT FROM PUBLISHER]

In this paper, we present a new centralised algorithm to detect and resolve generalised deadlock in distributed systems. The initiator of this algorithm induces a directed spanning tree by diffusing the probe messages among its dependent processes. It then collects replies that carry the dependency information of the dependent process to determine a deadlock. Moreover, the initiator of this algorithm performs reduction once it receives a reply from an active process unlike the existing algorithms. Hence, it terminates the execution when it detects a deadlock without waiting for termination detection. We have asserted the correctness of the algorithm formally. It has a worst-case time complexity of d+2 time units, message complexity of e+2n messages and message size of O(n), where n is the number of nodes, e is the number of edges and d is the diameter in the wait-for graph. The performance of the proposed algorithm is compared with that of the existing centralised algorithms in terms of deadlock duration, message traffic and message size using simulation. Numerical results reveal that the performance of the proposed algorithm is equal or better than that of the existing algorithms. [ABSTRACT FROM PUBLISHER]

Delay tolerant network (DTN) is a sparse wireless mobile network that does not guarantee a path between a source and a destination at any time. In DTN, one critical issue is to reliably deliver data with low latency. In an N-node network, naive forwarding approaches such as flooding and its derivatives make the routing cost very high ( ). Recently, an approach called delegation forwarding (DF) caught significant attention in the research community because it reduces the cost to while maintaining good performance. In this paper, we enhance the DF algorithm by proposing a probability delegation forwarding (PDF) that further reduces the cost to and a threshold-based probability delegation forwarding (TPDF) that closes the latency gap between DF and PDF. Simulation results show that both PDF and TPDF can achieve similar delivery ratio as DF at a lower cost if p is not too small. [ABSTRACT FROM AUTHOR]

Snapshot algorithms are fundamental algorithms in recording consistent global states of a distributed system. They find a large class of important applications such as monitoring and debugging of distributed systems and detection of stable properties (e.g. deadlock, termination and loss of tokens). Unfortunately, most existing snapshot algorithms were designed for static network systems and cellular systems only. They cannot be applied directly in recent emerging ad hoc network systems, which usually have no fixed infrastructure and may experience dynamic topology changes in the mid of execution. This paper presents a snapshot algorithm that can work in an ad hoc network system. Compared to the traditional snapshot algorithms, the proposed algorithm can guarantee both the causal consistency and the topological consistency. Simple methods are also discussed to reduce logged system states and exchanged message timestamps when applying the algorithm. [ABSTRACT FROM AUTHOR]

Distributed storage systems have become popular for handling the enormous amount of data in network-centric systems. A distributed storage system provides client processes with the abstraction of a shared variable that satisfies some consistency and reliability properties. Typically, the properties are ensured through a replication-based implementation. This paper presents an algorithm for a replicated read/write register that can tolerate f Byzantine-faulty servers when there are at least a total of 3f+1 replica servers. The targeted consistency condition is weaker than the more frequently supported condition of atomicity, but it is still strong enough to be useful in some important applications. By weakening the consistency condition, the algorithm can support multiple writers more efficiently and more simply than the known multi-writer algorithms for atomic consistency. [ABSTRACT FROM AUTHOR]

In this paper, we study the potential performance improvements for catastrophe (CAT) modelling systems that can be achieved through parallelisation on a cell processor [Cell Broadband Engine Architecture (Cell/BE)]. We studied and parallelised a critical section of CAT modelling, the so-called inner loop and implemented it on a Cell/BE running on a regular Playstation 3 platform. The Cell/BE is known to be a challenging environment for software development. In particular, the small internal storage available at each synergistic processing element (SPE) of the Cell/BE is a considerable challenge for CAT modelling because the CAT-modelling algorithm requires frequent accesses to large lookup tables. Our parallel solution is a combination of multiple techniques: streaming data to the SPEs and parallelising inner loop computations, building caches on the SPEs to store parts of the large CAT modelling lookup tables, vectorising the computation on the SPEs and double-buffering the file I/O. On a (Playstation 3) Cell/BE with six active SPEs and four-way vectorisation on each SPE, we were able to measure a sustained 16 × speedup for our parallel CAT-modelling code over a wide range of data sizes for real-life Japanese earthquake data. [ABSTRACT FROM AUTHOR]

Random walk (RW) based algorithms are often proposed to solve many problems in wireless networks. The implementation of such algorithms are usually done at the application layer so that many characteristics of the wireless transmissions are not exploited. In this paper, we show that we can greatly reduce the energy requirements to perform a RW by better exploiting the broadcast nature of the transmissions. We propose a broadcast based distributed next hop selection algorithm and compare it with a standard unicast based next hop selection algorithm. To evaluate the algorithms, we present a simulation study performed with ns-2. We found that the proposed algorithm is energy efficient, results in less source to destination delay, incurs less number of hops or transmissions and more robust in mobility as compared to a standard unicast based implementation of next hop selection algorithm for RW. [ABSTRACT FROM AUTHOR]

On the basis of image processing technology and characteristics of web pages, a new web segmentation method - iterated shrinking and dividing is proposed in this paper. Dividing conditions and concept of dividing zone are introduced, based on which web page image is divided into visually consentaneous sub-images by shrinking and splitting iteratively. First, the web page is saved as image that is preprocessed by edge detection algorithm such as Canny. Then dividing zones are detected and the web image is segmented repeatedly until all blocks are indivisible. This method can be used to analyse the web pages such as detecting similar visual layout. Experiments show that the algorithm is suitable for web page segmentation, and does well in expansibility and performance. [ABSTRACT FROM AUTHOR]

In this paper, we present a solution to a resource allocation problem in a mobile ad hoc environment: the k-exclusion problem where k nodes are allowed to use a shared resource. We use a k tokens based circulation algorithm. Each token circulates continuously through the network according to a random walk policy. A node can enter the critical section if it owns one of the k tokens. The algorithm is decentralised - no node needs to be distinguished - adaptive to dynamical topology changes and self-stabilizing under a flexible mobility constraint. [ABSTRACT FROM AUTHOR]

Flooding with a time-to-live constraint is a popular algorithm in unstructured peer-to-peer (P2P) networks. However, blind flooding may cause a large amount of network traffic. Moreover, it cannot guarantee acquiring all required data objects, especially for rare ones. To mitigate these problems, this paper proposes PercolationNET, a multi-tree sub-overlay, which is built on top of an existing P2P overlay (named original overlay). PercolationNET organises peers in a tree-based structure which facilitates reliable and efficient message dissemination for search. The search process is divided into two stages. A query message is first propagated on the original overlay, and then broadcast along the sub-overlay PercolationNET. PercolationNET combines the advantages of fast coverage speed in flooding-based scheme and low traffic cost in tree-based scheme. The experimental results of PercolationNET compared with FloodNet confirm the superiority of PercolationNET in achieving faster coverage speed and lower message cost. [ABSTRACT FROM AUTHOR]

Generalised matching network (GMN) is a newly introduced kind of interconnection network, which generalises hypercube-like network. This paper addresses the fault Hamiltonicity and fault Hamiltonian-connectivity of GMNs. Let G be a GMN with at least four building graphs, each of which is f-fault Hamiltonian-connected and [image omitted] -fault Hamiltonian. We prove that if G satisfies two more specified assumptions, then G is [image omitted] -fault Hamiltonian-connected and [image omitted] -fault Hamiltonian. [ABSTRACT FROM AUTHOR]

Checkpointing and rollback recovery are widely used techniques to handle failures in distributed computing systems. If there is no coordination among processes during checkpointing, processes may take useless checkpoints. Useless checkpoints are checkpoints that cannot be part of any consistent global checkpoint. In this paper, we propose a Communication-Induced checkpointing algorithm that prevents useless checkpoints by directing processes to take forced checkpoints more efficiently whenever a communication pattern that may lead to a Z-Cycle (ZC) is observed. Existence of ZC among checkpoints is known to be necessary and sufficient for making a checkpoint useless. The basic idea behind our algorithm can be extended to existing model-based checkpointing algorithms to reduce the number of forced checkpoints. We also compare the performance of our algorithm with an existing well-known algorithm. [ABSTRACT FROM AUTHOR]

Partially reconfigurable devices allow the execution of multiple tasks simultaneously on the same chip. To schedule a set of tasks in a small amount of time, the scheduling algorithm will need to represent the free space efficiently. A data structure to represent free space should allow the scheduler to identify free space in which to place a new task and admit efficient updates after placing or removing a task. In this paper, we review some existing data structures and analyse their time complexity. We propose a new structure using maximal horizontal and vertical strips (MHVS) to represent the free space. These strips start and stop at task boundaries. Simulation and time analysis showed that this method has better time complexity than many other free space data structures and at the same time has a very reasonable rejection ratio on real-time tasks compared to other methods. [ABSTRACT FROM AUTHOR]

Caravela is a computing platform that has been designed in academia to implement distributed stream-based computing based on the flow-model. This paper is focused on the new meta-pipeline execution mechanism, which allows to set up a pipeline of flow-models to be executed in parallel but with data streams flowing in sequence along them. A model and programming tools are presented to develop the proposed meta-pipeline in the Caravela platform. These tools are important, namely to tackle the deadlock problem that can occur due to uninitialised input data streams. A new efficient algorithm is also proposed to identify off-line the uninitialised edges in a 'pipeline graph'. Moreover, optimisation techniques are also proposed to reduce the computation time and the amount of memory required to implement the proposed algorithm, and a graphical user interface (GUI) was implemented to facilitate the programming of applications with the meta-pipeline approach. The experimental results presented in this paper show the practical interest of the meta-pipeline approach for stream-based computing and the effectiveness of both the proposed algorithm and the developed GUI for programming the Caravela platform. [ABSTRACT FROM AUTHOR]

Due to the dynamic nature of peer-to-peer (P2P) systems, it is impossible to keep an accurate history of the transactions that take place while avoiding security attacks such as whitewashing and collusion, and abuse such as freeriding. This is why it is important to develop a mechanism that both rewards cooperative peers and punishes misbehaving peers. Modelling P2P networks as social structures can allow incentive mechanisms to be developed that prevent the negative behaviours mentioned. In a social structure, peers make and receive payments for services provided to and from each other. In this paper, we extend a social network algorithm to include the transfer of credit between peers to reduce the path length in queries. We also develop a selection strategy that involves different aspects of peer interactions in P2P networks and a credit transfer mechanism that helps to discourage misbehaving peers by taking away credits that they have with good peers and transferring them to more cooperative ones. The simulation results show that our algorithm is effective in reducing the amount of debt between peers, meaning that peers become more cooperative, and shortening the average path length to a satisfied query, while increasing delivery ratio. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new architecture to solve the problem of mutual exclusion in mobile ad hoc networks (MANET). The architecture is composed of two layers: (i) a middleware layer that contains a token-based distributed mutual exclusion algorithm (DMEA) and (ii) a network layer that includes two routing forwarding strategies: one to route request messages and the other to route the token message. We also propose a request ordering policy that ensures the usual mutual exclusion properties and reduces the number of hops traversed per critical section (CS) access. The paper also addresses the problem of network partitioning and unreachable nodes. The proposed mutual exclusion algorithm is further enhanced to provide fault tolerance by preventing the loss of the token and generating a new token if the token loss event occurs. The performance complexity as well as the experimental results show that the proposed algorithm experiences low number of hops per CS access. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of fault identification in large diagnosable systems under the PMC model. Recently, genetic algorithms have been successfully used to solve this system-level fault diagnosis problem; however, they have one major drawback, i.e. even though they have been shown to perform better than the existing diagnosis algorithms, they are still time-consuming especially for large systems composed of hundreds or thousands of nodes. In this paper, we describe a new parallel version of the existing evolutionary diagnosis algorithm, which exploits competing sub-populations to speed up the diagnosis algorithm. The new approach has been implemented using the parallel virtual machine (PVM) environment and has been evaluated on a workstation network using randomly generated large diagnosable systems. Experimental results showed that the new parallel version considerably improved the response time of the diagnosis algorithm, hence, allowing for fast identification of faulty nodes. [ABSTRACT FROM AUTHOR]

In-Memory Databases (IMDBs), such as SAP HANA, enable new levels of database performance by removing the disk bottleneck and by compressing data in memory. The consequence of this improved performance means that reports and analytic queries can now be processed on demand. Therefore, the goal is now to provide near real-time responses to compute and data intensive analytic queries. To facilitate this, much work has investigated the use of acceleration technologies within the database context. While current research into the application of these technologies has yielded positive results, they have tended to focus on single database tasks or on isolated single user requests. This paper uses SHEPARD, a framework for managing accelerated tasks across shared heterogeneous resources, to introduce acceleration into an IMDB. Results show how, using SHEPARD, multiple simultaneous user queries all receive speed-up by using a shared pool of accelerators. Results also show that offloading analytic tasks onto accelerators can have indirect benefits for other database workloads by reducing contention for CPU resources. Interaction of the SHEPARD management framework to process user queries from an in-memory database system. [ABSTRACT FROM AUTHOR]

Particle swarm optimization (PSO) has recently been extended in several directions. Heterogeneous PSO (HPSO) is one of such recent extensions, which implements behavioural heterogeneity of particles. In this paper, we propose a further extended version, Hierarchcial Heterogeenous PSO (HHPSO), in which heterogeneous behaviors of particles are enforced through interactions among hierarchically structured particles. Two algorithms have been developed and studied: multi-layer HHPSO (ml-HHPSO) and multi-group HHPSO (mg-HHPSO). In each HHPSO algorithm, stagnancy and overcrowding detection mechanisms were implemented to avoid premature convergence. The algorithm performance was measured on a set of benchmark functions and compared with performances of standard PSO (SPSO) and HPSO. The results demonstrated that both ml-HHPSO and mg-HHPSO performed well on all testing problems and significantly outperformed SPSO and HPSO in terms of solution accuracy, convergence speed and diversity maintenance. Further computational experiments revealed the optimal frequencies of stagnation and overcrowding detection for each HHPSO algorithm. [ABSTRACT FROM PUBLISHER]

A method for image segmentation based on improved hybrid particle swarm optimisation (PSO) is proposed. In view of the shortcoming that the traditional PSO algorithm is easy to fall into local optimal solution, we update the particle velocity based on the combination of global optimisation, region equilibrium and compression factor. By this way, the searchability of the particle and optimisation performance of the improved PSO is improved. Experiments results on three classic test functions show that the algorithm can greatly improve the searchability. Experiments also show that it performs well on image segmentation. [ABSTRACT FROM AUTHOR]

Graphics processing units (GPUs) offer parallel computing power that usually requires a cluster of networked computers or a supercomputer to accomplish. While writing kernel code is fairly straightforward, achieving efficiency and performance requires very careful optimisation decisions and changes to the original serial algorithm. We introduce a parallel canonical ensemble Monte Carlo (MC) simulation that runs entirely on the GPU. In this paper, we describe two MC simulation codes of Lennard-Jones particles in the canonical ensemble, a single CPU core and a parallel GPU implementations. Using Compute Unified Device Architecture, the parallel implementation enables the simulation of systems containing over 200,000 particles in a reasonable amount of time, which allows researchers to obtain more accurate simulation results. A remapping algorithm is introduced to balance the load of the device resources and demonstrate by experimental results that the efficiency of this algorithm is bounded by available GPU resource. Our parallel implementation achieves an improvement of up to 15 times on a commodity GPU over our efficient single core implementation for a system consisting of 256k particles, with the speedup increasing with the problem size. Furthermore, we describe our methods and strategies for optimising our implementation in detail. [ABSTRACT FROM AUTHOR]

Cloud computing offers new computing paradigms, capacity and flexible solutions to high performance computing (HPC) applications. For example, Hardware as a Service (HaaS) allows users to provide a large number of virtual machines (VMs) for computation-intensive applications using the HaaS model. Due to the large number of VMs and electronic components in HPC system in the cloud, any fault during the execution would result in re-running the applications, which will cost time, money and energy. In this paper we presented a proactive fault tolerance (FT) approach to HPC systems in the cloud to reduce the wall-clock execution time and dollar cost in the presence of faults. We also developed a generic FT algorithm for HPC systems in the cloud. Our algorithm does not rely on a spare node prior to prediction of a failure. We also developed a cost model for executing computation-intensive applications on HPC systems in the cloud. We analysed the dollar cost of provisioning spare nodes and checkpointing FT to assess the value of our approach. Our experimental results obtained from a real cloud execution environment show that the wall-clock execution time and cost of running computation-intensive applications in cloud can be reduced by as much as 30%. The frequency of checkpointing of computation-intensive applications can be reduced up to 50% with our FT approach for HPC in the cloud compared with current FT approaches. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new type of sensor: cable sensor. Unlike traditional point sensors, this type of sensor has a rectangular sensing region with a processor installed on it to do processing and communication. The wireless network formed by this kind of sensor is called wireless cable sensor network (WCSN). We study energy-efficient communication algorithms in WCSNs. We address it in two ways: one is through reducing the total transmission power of processors while maintaining the connectivity of the network and the other is through scheduling cable sensors to let them take turns to go to sleep without affecting the coverage and connectivity of the network. In the first approach, we initially develop a distributed algorithm called DTRNG based on the relative neighbourhood graph. Later we enhance it to Algorithm determine the transmission power by removing the largest edge in CYCles (DTCYC). Mathematical proofs show that Algorithm DTCYC provides an optimal solution that can not only minimise the total processor transmission power but maintain the connectivity of the network as well. In the second approach, we propose a cable mode transition algorithm which determines the minimum number of active sensors to maintainK-coverage as well asK-connectivity required by the application. We discuss the relationship between coverage and connectivity and prove the theorems that lay the foundation for our algorithm. Simulation results demonstrate that our algorithm is efficient in saving energy. [ABSTRACT FROM PUBLISHER]

As the number of electric vehicles (EVs) grows, their electricity demands may have significant detrimental impacts on electric power grid when not scheduled properly. In this paper, we model an EV charging system as a cyber-physical system, and design a decentralised online EV charging scheduling algorithm for large populations of EVs, where the EVs can be highly heterogeneous and may join the charging system dynamically. The algorithm couples a clustering-based strategy that dynamically classifies heterogeneous EVs into multiple groups and a sliding-window iterative approach that schedules the charging demand for the EVs in each group in real time. Extensive simulation results demonstrate that our approach provides near-optimal solutions at significantly reduced complexity and communication overhead. It flattens the aggregated load on the power grid and reduces the costs of both the users and the utility. [ABSTRACT FROM PUBLISHER]

In typical mobile wireless sensor networks, flows sent from collecting sensors to a sink could traverse inefficient resource expensive paths and experience arbitrary delays. This is particularly problematic in event-based sensor network where flows are of great importance. In this paper, we are interested in energy-aware routing algorithms that explicitly take advantage of node mobility to improve energy consumption of computed paths. Mobility is a two-sword edge however. Moving a node may render the network disconnected and results in early termination of information delivery. To mitigate these problems, we propose a family of routing algorithm called Connectivity preservation Mobile routing protocols for actuator and sensor NETworks (CoMNet), that uses local information and modifies the network topology to support resource efficient transmissions. Our extensive simulations show that CoMNet has high energetic performance improvement compared to existing routing algorithms. More importantly, we show that CoMNet guarantees network connectivity and efficient resource consumption. [ABSTRACT FROM PUBLISHER]

In a vehicular ad hoc network (VANET), a road-side infrastructure or road-side unit (RSU) is anticipated to be installed at some road-side location. This exposes the VANET to several different adversaries. In this paper, we present an authentication scheme for infrastructure-generated safety messages using an identity (ID)-based proxy signature and verification mechanism. An ID-based technique offers a certificate-less public key verification, while a proxy signature provides flexibility in message authentication and trust management. We incorporate an ID-based proxy signature framework with the standard elliptic curve digital signature algorithm for safety application messages from RSU. We also provide forwarding of safety message components ensuring the accountable authentication of RSU's application messages. Security analysis and network simulation prove that our scheme is resilient to all major security threats, compatible to standards and efficient in terms of computation complexity. We also conduct simulation experiments to determine the most suitable access classes for on-board unit and RSU. [ABSTRACT FROM PUBLISHER]

Coverage is an important parameter to determine the effectiveness of wireless sensor networks. In this paper, we present a new algorithm called uncovered region exploration algorithm (UREA) to enhance the coverage after an initial random deployment using binary and probabilistic sensor detection models. UREA decides a new location based on an uncovered region around a node. Once the effective sensor positions are identified, a one-time movement of each node is carried out to redeploy a sensor at its new position. This one-time displacement of sensor benefits a deployed network to improve coverage. UREA is found to be consistent, robust and versatile to achieve multi-level coverage and suit non-homogeneous sensor deployments. The extensive simulation results show that UREA performs better than the existing deployment algorithms. [ABSTRACT FROM PUBLISHER]

This paper proposes an offline wavelength assignment technique for de Bruijn (d, k) optical wavelength division multiplexing (WDM) networks having nodal degree d and diameter k that can support lightpaths between pair of nodes. Each lightpath uses a channel (wavelength) along each link in its route. An efficient algorithm is proposed that can be used to assign wavelengths to lightpath requests in O(k|V|) time, where |V| represents the number of nodes of the de Bruijn network and V represents the set of nodes. The proposed algorithm can be efficiently used for wavelength assignment in de Bruijn WDM networks having limited wavelength conversion capabilities. This work shows that de Bruijn graph can be expressed as union of edge-disjoint rings. Wavelengths are assigned for the individual rings in the graph thus resulting in the assignment for the graph itself. Results are shown for a given de Bruijn graph and for an arbitrary request. The proposed algorithm is compared with two other algorithms, which use two other known works of wavelength assignment on ring topology. Comparisons of the time complexity and the type of wavelength conversion required for these algorithms clearly show that the proposed algorithm is a faster and more efficient way of assigning wavelengths. [ABSTRACT FROM PUBLISHER]

This paper proposes a new variant of parallel particle swarm optimisation (PPSO) known as small population-based modified PPSO (SPMPPSO) for fast motion estimation. The proposed technique is used to reduce computational time for block motion estimation in video. In the said technique, the velocity and position equations of PPSO are modified to achieve adaptive step size for getting true motion vector. The new position of swarm depends on previous motion vector, time decreasing inertia weight and on time-varying acceleration coefficient. The best matching block is predicted by step size/position equation of SPMPPSO. The Von Neumann topology is used as search pattern in the SPMPPSO. In SPMPPSO, small population, i.e. five swarms with which two-step search are used to find best matching block. Zero motion prejudgement is used leads to faster convergence for getting the motion vector. The results of SPMPPSO are compared with those of PPSO and with those of other motion estimation algorithms. The limitations such as computational time, search parameter, initial search and search space are overcome in SPMPPSO. The proposed technique saves computational time up to 94% when compared with other published methods. [ABSTRACT FROM PUBLISHER]

The goal of the t/k-diagnosis is to isolate all faulty processors (nodes) in a multiprocessor system to within a set of nodes in which at most k nodes are correct, provided the number of faulty nodes does not exceed t. As compared to the classical precise diagnosis strategy, the t/k-diagnosis strategy can significantly improve the self-diagnosing capability of multiprocessor system. The generalised cube network (GCN), or equivalently the BC graphs, is a regular topology, which provides a unified view of the hypercube and some of its variants. This paper addressed the t/k-diagnosis of GCNs. By exploring the relationship between the size of a largest connected component of the 0-test subgraph of a faulty GCN and the distribution of the faulty nodes over the network, an [image omitted] time (4n - 9)/3 diagnosis algorithm on an n-dimensional GCN is presented, where N = 2n is the total number of the nodes of the network being diagnosed. To our knowledge, this is the first time to give a t/k-diagnosis algorithm for GCNs and [image omitted] . [ABSTRACT FROM AUTHOR]

In this paper, we present an efficient causal algorithm that can be used in multicast communication environments, in particular the overlapping multi-channel case, where a participant can belong to and communicate through more than one multicast channel. The causal algorithm is built on the paradigm of group communication. The groups are established according to the participant channel subscription. In order to reduce the amount of control information (CI), we propose an extension of the immediate dependency relation (IDR), which was introduced by Peterson in the context of one group. This IDR extension allows us to define necessary and sufficient CI to ensure causal delivery in a multi-group environment. We show that through the use of the IDR extension, we reduce the amount of CI sent per message without imposing restrictions on interaction or execution (e.g. network topology, rediffusion servers, execution models, etc.). These characteristics allow our algorithm to be suitable for use in large distributed decentralised systems. We show the efficiency of our causal algorithm in terms of the overhead timestamped per message. [ABSTRACT FROM AUTHOR]