Search

An alternator is a network of concurrent nodes, which satisfies the following conditions: (i) if one node enters its critical section, no neighboring nodes could enter their critical sections at the same computing phase; (ii) along any infinite computing phases, each node enters its critical section infinitely often. An alternator is said to exhibit strong fairness if condition (ii) is changed to: between any two consecutive critical steps of a node, all neighbors enter their critical sections exactly once. In this paper, we propose a state-optimal alternator algorithm for uniform rings with n nodes, where n is any positive integer greater than one. The proposed algorithm operates correctly for synchronous mode. Every node maintains only a two-state variable. The proposed algorithm has the snap property that the system always satisfies condition (i) of the alternator even if some transient fault occurs. The stabilization time of the proposed alternator algorithm is O(n) phases. After stabilization, the system satisfies the strong fairness property and achieves the maximal performance. We say that an alternator achieves the maximal performance if a node is allowed to enter its critical section when both its neighbors do not enter their critical sections. In the worst case, the proposed algorithm allows each node to enter its critical section every three phases. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring the content to a wider readership. The Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the Department of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM AUTHOR]

Vulnerability localization can assist security professionals in vulnerability validation and analysis. This study proposes an intelligent vulnerability localization method based on fine-grained program representation and feature fusion. Firstly, we generate efficient fine-grained program representations of the program. This involves transforming the source code into intermediate code. We use abstract syntax tree characteristics to correspond to the points of interest of the intermediate code. We slice the intermediate code file based on the point of interest and program dependency relationships. Subsequently, we use the word2vec model to the vectorization of the intermediate code slices. Then, we propose a vulnerability localization framework based on a feature fusion method, which can better combine the advantages of bidirectional gate recurrent unit and convolutional neural network to capture the syntax and semantics of program representation. Through comparing different program representations, we have discovered that the fine-grained representation based on intermediate code in this study provides a more accurate portrayal of program semantics. By comparing various methods, the proposed feature fusion approach in this paper improves vulnerability localization. We also conducted a visualization display of vulnerability localization. Furthermore, we have validated the effectiveness of this method in localizing vulnerabilities across five common vulnerability types. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue, in order to bring the content to a wider readership. This issue's Capsule Reviews were compiled by Fairouz Kamarreddine. Professor Kamarreddine is an Associate Editor of The Computer Journal and is based in the Department of Computing and Electrical Engineering at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue, in order to bring the content to a wider readership. This issue's Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the School of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM PUBLISHER]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue, in order to bring the content to a wider readership. This issue's Capsule Reviews were compiled by Fairouz Kamarreddine. Professor Kamarreddine is an Associate Editor of The Computer Journal and is based in the Department of Computing and Electrical Enigneering at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM PUBLISHER]

The past five decades have witnessed the unprecedented contribution of arboviral diseases towards global morbidity and disability. It is primarily attributed due to unplanned urbanization, population explosion and globalization. Out of these, dengue is considered the most important arboviral disease because of its predominant growth in the past. The presented study explores the immense potential of Internet of things (IoT), fog and cloud computing for providing technology-based healthcare solutions for dengue virus (DENV) infection. In this paper, a hierarchical healthcare computing system for controlling DENV infection using fog–cloud-assisted IoT is proposed. This system provides a real-time remote diagnosis of DENV infection in individuals and monitors and predicts their health sensitivity during its infection period. The system uses fog computing to diagnose the DENV infection status of the individuals using |$k$| -means clustering and generates immediate diagnostic alerts to individuals, at the fog layer. Furthermore, the system uses cloud computing to monitor and predict the probabilistic health sensitivity of the DENV-infected individuals using Bayesian belief network and artificial neural network, respectively, at the cloud layer. The prediction of health sensitivity in the proposed system helps the infected individuals and healthcare agencies in determining the health vulnerability of DENV-infected individuals and preventing severe or permanent health losses in the future. The proposed system is experimentally evaluated using well-defined approaches, which conform to its validity and applicability. The results obtained from the experimental evaluations of the proposed system acknowledge the performance superiority and high efficiency of the system in delivering DENV-related healthcare services in real time. [ABSTRACT FROM AUTHOR]

This paper presents a new unreliable failure detector, called the Impact failure detector (FD), that, contrarily to the majority of traditional FDs, outputs a trust level value which expresses the degree of confidence in the system. An impact factor is assigned to each process and the trust level is equal to the sum of the impact factors of the processes not suspected of failure. Moreover, a threshold parameter defines a lower bound value for the trust level, over which the confidence in the system is ensured. In particular, we defined a flexibility property that denotes the capacity of the Impact FD to tolerate a certain margin of failures or false suspicions, i.e. its capacity of considering different sets of responses that lead the system to trusted states. The Impact FD is suitable for systems that present node redundancy, heterogeneity of nodes, clustering feature and allow a margin of failures which does not degrade the confidence in the system. The paper also includes a timer-based distributed algorithm which implements an Impact FD, as well as its proof of correctness, for systems whose links are lossy asynchronous or for those whose all (or some) links are eventually timely. Performance evaluation results, based on PlanetLab (Planetlab. http://www.planet-lab.org. 'Online. Access date: 16 September 2016') traces, confirm the degree of flexible applicability of our FD and that, due to the accepted margin of failure, both failures and false suspicions are more tolerated when compared to traditional unreliable FDs. [ABSTRACT FROM AUTHOR]

Leakage of private information, such as the secret keys, has become a threat to the security of computing systems. It has become a common requirement that cryptographic schemes should withstand various leakage attacks, including the continuous leakage attacks. Although some research progresses have been made toward this area, there are still some unsolved issues. In the literature, the public-key encryption (PKE) constructions with (continuous) leakage resilience normally require the upper bound of leakage to be fixed. However, in many real-world applications, this requirement cannot provide sufficient protection against leakage attacks. In order to mitigate these problems, this paper demonstrates how to design a leakage amplified PKE scheme with continuous leakage resilience and chosen-plaintext attacks security. In our proposed PKE scheme, the leakage parameter can have an arbitrary length. Moreover, the length of permitted leakage in our scheme can be flexibly adjusted according to the leakage requirements of application environment. Its security is formally proved under the classic static assumption. [ABSTRACT FROM AUTHOR]

This paper discusses the validation, by simulation, of Behavioural Models of computer systems that are developed as part of a whole lifecycle approach to product development (model-based object oriented systems engineering (MOOSE)). The paper summarizes the MOOSE approach and introduces its notation for defining Behavioural Models, which are logical models of a system, uncommitted to hardware or software implementation. In the MOOSE approach, a Behavioural Model is transformed into a Committed Model of the system that identifies the hardware and software components that make up the system's implementation. This paper concentrates on the dynamics of these models, viewed both as paper models and as executing simulations. It considers the validation techniques that can be employed for both types of model and discusses the design of the software necessary to support the executable simulations. The paper is illustrated by an example model of a video controller system. [ABSTRACT FROM AUTHOR]

The Real-Time Specification for Java (RTSJ) is silent on multiprocessor issues. It attempts not to preclude multiprocessor implementations but provides no direct support. Many areas of the RTSJ leave an implementation considerable freedom on how it provides the defined functionality. One such area is the asynchronous event handling (AEH) model. Events are fired and associated handlers are scheduled for execution in response; handlers have defined scheduling parameters and deadlines. The primary goal of the AEH model is to support a lightweight real-time concurrency model. Hence handlers, in general, do not have dedicated threads. Rather, the implementation is responsible for ensuring that all handlers meet their deadlines. Typically real-time threads are assigned to execute handlers by the implementation. This paper discusses the issues associated with implementing the AEH model on multiprocessor systems. The emphasis here is on achieving a lightweight model. A model is lightweight if it is able to meet the deadlines of all handlers with as few as possible real-time threads. In the RTSJ this is made more complicated because asynchronous event handlers are allowed to suspend themselves (for example, by waiting on a monitor condition). Such handlers are called blocking handlers. Most of an implementation's freedom comes from being able to optimize the support for those handlers that do not block. The paper first examines all possible releasing sequences of non-blocking handlers on multiprocessor systems. Based on this, it proposes an efficient and scalable AEH mapping model for multiprocessor systems, which limits the number of real-time threads even in the worst case while retaining the schedulability of the system. The proposed model is then examined to prove its safety and liveness requirements using a model checking tool, UPPAAL. The verification and simulation results of the model indicate that the safety and liveness requirements are satisfied. Most importantly, this paper derives the proposed model's greatest lower and least upper bounds of real-time threads required to execute a given number of non-blocking handlers. The greatest lower bound is equal to the number of processors, and the least upper bound is equal to the number of processors times that of the priority levels in the system. In the model, the number of real-time threads required to execute a given number of non-blocking handlers is restricted to between these two bounds depending on the releasing sequence of handlers. Even in the worst case, the model requires the least upper bound of real-time threads which is, in most cases, considerably less than the actual number of handlers in the system. This, in turn, enables the proposed model to be efficient and scalable by reducing time and space overheads, compared with a traditional 1:1 AEH mapping model where each handler is mapped to a single thread. [ABSTRACT FROM AUTHOR]

Pervasive computing is the next generation computing environment with information and communication technology everywhere, for everyone, at any time. There are many methods proposed to reach the ultimate design goals of pervasive computing. Most of them are still at the hypothesis and early stages. In this paper, an initial investigation has been carried out to use active networks as the operating platforms for pervasive computing. Upon taking advantage of the active network paradigm, which offers flexibility and extensibility within networks, the active pervasive network infrastructure (APNI) framework is proposed. An additional feature known as `adaptiveness' is recommended to work in pervasive computing. Primarily, the integrity of information content can be retained and adapted to available network resources, even if an end user moves to an unfavourable network environment as long as the user approves and accepts appropriate modifications of receiving content. Furthermore, information transfer can be sustained through different extensible mechanisms on the network layer in active networks. As a result, information can be sent through the APNI with low packet loss rate. The functional objectives of proposed designs in the paper have been verified through thorough experiments in an active network prototype. [ABSTRACT FROM AUTHOR]

Caches hide the growing latency of accesses to the main memory from the processor by storing the most recently used data on-chip. To limit the search time through the caches, they are organized in a direct mapped or set-associative way. Such an organization introduces many conflict misses that hamper performance. This paper studies randomizing set index functions, a technique to place the data in the cache in such a way that conflict misses are avoided. The performance of such a randomized cache strongly depends on the randomization function. This paper discusses a methodology to generate randomization functions that perform well over a broad range of benchmarks. The methodology uses profiling information to predict the conflict miss rate of randomization functions. Then, using this information, a search algorithm finds the best randomization function. Due to implementation issues, it is preferable to use a randomization function that is extremely simple and can be evaluated in little time. For these reasons, we use randomization functions where each randomized address bit is computed as the XOR of a subset of the original address bits. These functions are chosen such that they operate on as few address bits as possible and have few inputs to each XOR. This paper shows that to index a 2m-set cache, it suffices to randomize in + 2 or m + 3 address bits and to limit the number of inputs to each XOR to 2 bits to obtain the full potential of randomization. Furthermore, it is shown that the randomization function that we generate for one set of benchmarks also works well for an entirely different set of benchmarks. Using the described methodology, it is possible to reduce the implementation cost of randomization functions with only an insignificant loss in conflict reduction. [ABSTRACT FROM AUTHOR]

The provision of many VCR-like user interactions, e.g. reverse, skip, freeze-restart and scale, makes multimedia applications more flexible and useful to users. However, due to the unpredictable and uncontrollable network delay and jitter, the provision of VCR-like functions complicates the processing of multimedia synchronization a lot. The main reason is that (i) those media units stored in the client buffers and transmitting in the networks may be either useful or useless and (ii) the servers' media transmission should be adjusted when the corresponding presentation is resumed. Additionally, different VCR-like user interactions have their own processing considerations, which require different control schemes. In this paper, we propose some control schemes that are based on the feedback-adaptive mechanism. Based on the control schemes, we developed a Multimedia-on-Demand system in which text, image, graphics, audio and video media are transmitted from the server site to the client site through text, image, graphics, audio and video communication channels respectively. Some performance measurements of the proposed control schemes are also given in this paper. [ABSTRACT FROM AUTHOR]

The prevalence of heterogeneous manycore processors has been shown as a promising alternative to web-based data parallel MapReduce applications. The differences of manycore from multicore raise new challenges to designing and implementing efficient and scalable MapReduce applications, such as memory access congestion. This paper argues that it is more efficient using multiple small groups of cores than using a single group with all cores to address these challenges. We propose a group-based MapReduce implementation, called Grouped-MapReduce (GMR). It uses grouping to align tasks so that the tasks in each group are congestion-free. Further, it uses multiplexing to control the implementation of groups so that multiple groups can efficiently share the limited memory bandwidth without causing serious memory access congestion. We have implemented a prototype of GMR based on Phoenix++, an already highly optimized MapReduce runtime. Experiments on six benchmarks show that GMR implements and scales well on manycore systems and obtains an impressive improvement over Phoenix++ from 1.04x to 1.77x without artificially tuning the existing application code. [ABSTRACT FROM AUTHOR]

For a graph G and a connected subgraph H of G , denote by ℋ (G ; H) the set of subgraphs of G which are isomorphic to H and denote by ℋ S (G ; H) the union of sets of subgraphs of T , where T ranges over all the elements in ℋ (G ; H) ⁠. An H -structure-cut (respectively, H -substructure-cut) of G is a subset of ℋ (G ; H) (respectively, ℋ S (G ; H) ⁠), if any, whose removal disconnects G. The H -structure connectivity (respectively, H -substructure connectivity) is the cardinality of a minimum H -structure-cut (respectively, H -substructure-cut) of G. The hypercube is one of the most attractive interconnection networks for large-scale multiprocessor computer systems. In this paper, we will characterize the minimum H -structure-cuts and the minimum H -substructure-cuts of hypercubes for H ∈ { K 1,1 , K 1,2 , K 1,3 , C 4 } ⁠. [ABSTRACT FROM AUTHOR]

Cryptocurrencies based on blockchain infrastructures have shown their advantages such as double-spending resistance and decentralization. Each transaction of cryptocurrency requires a certain amount of computation and attracts transaction fees. Often, in practice, many transactions are small; therefore, they add computation and transmission overheads to the system. In this paper, we introduce a cost-saving approach, which significantly reduces transaction time and storage for small amount of payment, i.e. micropayment. In our approach, with the notion of 'transaction commitment', the computation of each transaction is much more efficient. Therefore, our approach has advantages in comparison of other cryptocurrency systems such as the bitcoin system. Our approach can be applied to other existing cryptocurrency systems. [ABSTRACT FROM AUTHOR]

A major factor affecting the readability of a graph drawing is its resolution. In the graph drawing literature, the resolution of a drawing is either measured based on the angles formed by consecutive edges incident on a common vertex (angular resolution) or by the angles formed at edge crossings (crossing resolution). In this paper, we introduce the notion of ‘total resolution’, that is, the minimum of the angular and crossing resolution. To the best of our knowledge, this is the first time where the problem of maximizing the total resolution of a graph over all its drawings is studied. The main contribution of the paper consists of drawings of asymptotically optimal total resolution for complete graphs (circular drawings) and for complete bipartite graphs (two-layered drawings). In addition, we present and experimentally evaluate a force-directed-based algorithm that constructs drawings of large total resolution. [ABSTRACT FROM AUTHOR]

Causal discovery is highly desirable in science and technology. In this paper, we study a new research problem of discovery of causal relationships in the context of streaming features, where the features steam in one by one. With a Bayesian network to represent causal relationships, we propose a novel algorithm called causal discovery from streaming features (CDFSF) which consists of a two-phase scheme. In the first phase, CDFSF dynamically discovers causal relationships between each feature seen so far with an arriving feature, while in the second phase CDFSF removes the false positives of each arrived feature from its current set of direct causes and effects. To improve the efficiency of CDFSF, using the symmetry properties between parents (causes) and children (effects) in a faithful Bayesian network, we present a variant of CDFSF, S-CDFSF. Experimental results validate our algorithms in comparison with the existing algorithms of causal relationship discovery. [ABSTRACT FROM PUBLISHER]

Energy efficiency is increasingly important for future information and communication technologies (ICT), because the increased usage of ICT, together with increasing energy costs and the need to reduce green house gas emissions call for energy-efficient technologies that decrease the overall energy consumption of computation, storage and communications. Cloud computing has recently received considerable attention, as a promising approach for delivering ICT services by improving the utilization of data centre resources. In principle, cloud computing can be an inherently energy-efficient technology for ICT provided that its potential for significant energy savings that have so far focused on hardware aspects, can be fully explored with respect to system operation and networking aspects. Thus this paper, in the context of cloud computing, reviews the usage of methods and technologies currently used for energy-efficient operation of computer hardware and network infrastructure. After surveying some of the current best practice and relevant literature in this area, this paper identifies some of the remaining key research challenges that arise when such energy-saving techniques are extended for use in cloud computing environments. [ABSTRACT FROM PUBLISHER]

There are two types of dynamic elements in a pervasive system: the first is where a context varies with shifting environments, and the second is where variables are defined by the dynamic requirements of an application. This makes improving adaptability to dynamic change an important topic in pervasive systems research. Currently, most of the efforts targeting improvements in adaptability focus on context-related issues, other variables being simply encoded in the program directly. This ignores the dynamic complexity of a pervasive system, resulting in poor system adaptability. In this paper, we propose a rule-based method in which the two types of change are separated from the program code. The changes are then stored and processed by means of corresponding rules. In our new method when a change occurs, the system needs only to modify the rules rather than the program code. This makes a pervasive system more robust in its adaptability to dynamic change. Experiments and examples are provided to evaluate the feasibility of the proposed method. [ABSTRACT FROM PUBLISHER]

YAWL (Yet Another Workflow Language) workflow language supports the most frequent control-flow patterns found in the current workflow practice. As a result, most workflow languages can be mapped onto YAWL without the loss of control-flow details, even languages allowing for advanced constructs such as cancellation regions and OR-joins. Hence, a verification approach for YAWL is desirable, because such an approach could be used for any workflow language that can be mapped onto YAWL. Unfortunately, cancellation regions and OR-joins are ‘non-local’ properties, and in general we cannot even decide whether the desired final state is reachable if both patterns are present. This paper proposes a verification approach based on (i) an abstraction of the OR-join semantics; (ii) the relaxed soundness property; and (iii) transition invariants. This approach is correct (errors reported are really errors), but not necessarily complete (not every error might get reported). This incompleteness can be explained because, on the one hand, the approach abstracts from the OR-join semantics and on the other hand, it may use only transition invariants, which are structural properties. Nevertheless, our approach can be used to successfully detect errors in YAWL models. Moreover, the approach can be easily transferred to other workflow languages allowing for advanced constructs such as cancellations and OR-joins. [ABSTRACT FROM AUTHOR]

It is well known that errors caught in the early stages of system development life cycle greatly helped reduce the expense for later error fixing and mitigate risks and complications. Performance analysis is one of the methods to ensure satisfactory system performance that can avoid redesign and patch in the later stage of system development when performance problems emerge. Much work has been done to address such concerns collectively known as the ‘performance engineering’ problem. However, a comprehensive method is still needed to provide an end-to-end support for performance evaluation on software architecture design. Automated tools to support the method must be developed, and its validation must be carefully planned and conducted. In response to this need, we propose our approach, PSIM (performance simulation and modeling). PSIM is a performance simulation and modeling tool that integrated performance properties into software architecture specifications expressed in several major UML diagrams. PSIM models can be transformed into Colored GSPN (colored generalized stochastic Petri nets) via an automated tool. As a result, the Colored GSPN models can be simulated to perform model-based performance evaluation. In this paper PSIM is first briefly reviewed and illustrated through modeling a web-based electronic conferencing system, called M-Net, to derive performance metrics. We then conduct runtime performance testing to the implementation of M-Net and compare the simulation results against the runtime testing data. PSIM is shown to be effective in predicting system performance and in identifying system performance bottlenecks through this experimentation. [ABSTRACT FROM AUTHOR]

By its very nature, a non-authenticated multi-party key agreement protocol cannot provide participant and message authentication, so it must rely on an authenticated network channel. This paper presents the inability of two famous multi-party key agreement protocols to withstand malicious participant attacks, even though their protocols are based on the authenticated network channel. This attack involves a malicious participant disrupting the multi-party key agreement among honest participants. In this case, other honest participants do not correctly agree on a common key. Obviously, the malicious participant cannot obtain the common key either, and the communication confidentiality among participants is not breached. However, in some emergency situations or applications, a multi-party key agreement protocol design that is resistant to malicious participants is useful. Therefore, in this paper, a non-authenticated multi-party key agreement protocol resistant to malicious participants is proposed. The proposed robust protocol requires constant rounds to establish a common key. Each participant broadcasts a constant number of messages. Under the assumption of the Decision Diffie–Hellman problem and the random oracle model, we will show that the proposed protocol is provably secure against passive adversaries and malicious participants. [ABSTRACT FROM PUBLISHER]

Current computer architecture research relies heavily on architectural simulation to obtain insight into the cycle-level behavior of modern microarchitectures. Unfortunately, such architectural simulations are extremely time-consuming. Sampling is an often-used technique to reduce the total simulation time. This is achieved by selecting a limited number of samples from a complete benchmark execution. One important issue with sampling, however, is the unknown hardware state at the beginning of each sample. Several approaches have been proposed to address this problem by warming up the hardware state before each sample. This paper presents the boundary line reuse latency (BLRL) which is an accurate and efficient warmup strategy. BLRL considers reuse latencies (between memory references to the same memory location) that cross the boundary line between the pre-sample and the sample to compute the warmup that is required for each sample. This guarantees a nearly perfect warmup state at the beginning of a sample. Our experimental results obtained using detailed processor simulation of SPEC CPU2000 benchmarks show that BLRL significantly outperforms the previously proposed memory reference reuse latency (MRRL) warmup strategy. BLRL achieves a warmup that is only half the warmup for MRRL on average for the same level of accuracy. [ABSTRACT FROM PUBLISHER]

Increasingly frequently, Grid software is being proposed as a software platform for operational management of enterprise computing systems, including desktops, data centres and business applications. We argue in this paper that the challenge for future management software is ‘enabling automated and business-driven management, for systems with increasing scale, heterogeneity and federation challenges’. Among the currently available middlewares, the Grid platform is undoubtedly best positioned to respond to this challenge, and we review several recent technologies that utilize Grid software for management purposes. However, Grid software also has its limitations. Its software architecture provides no particular support to building self-managing distributed systems and is therefore most viable for traditional hierarchical management systems, providing rudimentary self-management capabilities through control loops. [ABSTRACT FROM PUBLISHER]

This paper describes a way of managing the modeling and analysis of Scheduled Maintenance Systems (SMSs) within an analytically tractable context. We chose a significant case study having a variety of interesting features like a heavily redundant architecture and a test and maintenance policy whose execution is made on-line without halting the system. We applied a methodology we previously developed based on the Deterministic Stochastic Petri Net (DSPN) approach, where the underlying stochastic process is Markov regenerative (MRGP) solved in our setting using an efficient analytical solution method. This methodology is implemented by the DEEM tool specifically developed for modeling and evaluating the dependability of Phased Mission Systems (PMSs). We test our methodology with such a case study to check whether it can master real and complex SMS problems and to compare its efficacy with traditional approaches (fault trees). The paper also investigates the problem of the optimal tuning of a maintenance program, giving a useful decision support tool for evaluating the system performance from the early design stage. [ABSTRACT FROM AUTHOR]

Real-time databases (RTDBs) are increasingly being used as an integral part of many computer systems. During normal operation, transactions in RTDBs must be executed in such a way that transaction timing and data time validity constraints can be met. RTDBs must also prepare for possible failures and provide fault tolerance capability. Principles for fault tolerance in RTDBs must take timing requirements into consideration and are distinct from those for conventional databases. We discuss these issues in this paper and describe a logging and recovery technique that is time- cognizant and is suitable for an important class of RTDB applications. The technique minimizes normal runtime overhead caused by logging and has a predictable impact on transaction timing constraints. Upon a failure, the system can recover critical data to a consistent and temporally valid state within predictable time bounds. The system can then resume its major functioning while non- critical data are being recovered in the background. As a result, the recovery time is bounded and shortened. In short, we are providing a bounded and predictable logging and recovery technique for critical transactions accessing critical variant and invariant data, while the database may consist of all kinds of data. Our performance evaluation via simulation shows that logging overhead has a small effect on missing transaction deadlines while adding recovery capability. In addition, our algorithm scales well with respect to large I/O page sizes, indicating that it can be adapted to future generations of storage devices with larger I/O page sizes. We compare our algorithm with another approach that does more frequent checkpointing for data with certain special characteristics. Simulation results disclose conditions under which each approach performs better than the other. Experiments also show that recovery using our approach is 3-6 times faster than traditional recovery. [ABSTRACT FROM AUTHOR]

Bluetooth has a master-slave configuration called a piconet. Unspecified in the Bluetooth standard, the link polling policy adopted by a master may significantly influence the bandwidth utilization of a piconet. Several works have been dedicated to this issue. However, none of them addresses the asymmetry of traffics between masters and slaves, and the different data packet types provided by Bluetooth are not fully exploited. In this paper, we propose an efficient pattern matching polling (PMP) policy for data link scheduling that properly resolves these deficiencies. A polling pattern is a sequence of Bluetooth packets of different type combinations (e.g. DH1IDH3IDH5IDM1IDM3IDMS) to be exchanged by a master-slave pair that can properly reflect the traffic ratio (i.e. asymmetry) of the pair. By judiciously selecting a proper polling pattern together with polling times for the link, the precious wireless bandwidth can be better utilized. The ultimate goal is to reduce the unfilled, or even null, payloads in each busy slot. In addition, an overflow mechanism is included to handle unpredictable traffic dynamics. Extensive simulations are presented to justify the capability of PMP in handling regular as well as bursty traffics. [ABSTRACT FROM AUTHOR]

This paper investigates the implementation of video servers employing multi-zone disks. A multi- zone disk consists of a set of concentric disk zones with non-uniform storage capacities and data transfer rates. Superimposing a customized region layout on the top of such a disk is essential for facilitating the video server design and improving the disk resource utilization. This paper develops theories concerning the optimal region layouts for implementing the region-based data placement Based on them, two efficient region layout algorithms are proposed, namely, the free-it scheme and fixed-it scheme. The former can achieve better resource utilization than the latter, but the latter requires a simpler timing control than the former. Extension of the fixed-it scheme to perform the disk striping in a disk array platform is also investigated. A spiral synchronization scheme is proposed to improve the system scalability by alleviating the disk bus congestion problem, caused by variable data transfer rates from individual disks. The analytical results reveal that the proposed schemes can effectively customize region layouts to achieve 85-99% resource utilization. By considering the region layout together with other design factors, an efficient configuration strategy is proposed for building a cost-effective server subject to the performance requirements of a target application. [ABSTRACT FROM AUTHOR]

Reverse engineering in distributed systems is essential to recovering the designs of large and complex distributed systems that evolve often without proper documentation. This paper proposes rules for the automated construction of deadlock-free designs of communication protocols from the execution histories of existing systems, defines the properties of the constructed designs and identifies the conditions for a constructed design to be equivalent to the presumed design implied by the given set of global observations. [ABSTRACT FROM PUBLISHER]

A processor array with a reconfigurable bus system is a parallel computation model that consists of a processor array and a reconfigurable bus system. In this paper, a constant-time algorithm is proposed on this model for finding the cycles in an undirected graph. We can use this algorithm to decide whether a specified edge belongs to the minimum spanning tree of the graph or not. This cycle-finding algorithm is designed on a two-dimensional $n\times n$ processor array with a reconfigurable bus system, where $n$ is the number of vertices in the graph. Based on this cycle-finding algorithm, the minimum spanning tree problem and the spanning tree problem can be solved in O(1) time by using fewer processors than before, O($n\times m\times n$) and O($n^3$) processors respectively. This is a substantial improvement over previous known results. Moreover, we also propose two constant-time algorithms for solving the minimum spanning tree verification problem and spanning tree verification problem by using O($n^3$) and O($n^2$) processors, respectively. [ABSTRACT FROM PUBLISHER]

Global software stacks on scientific cluster computing resources are required to provide a homogeneous software environment which is typically inflexible. Efforts to integrate Virtual Machines (VMs), in order to abstract the software environment of various scientific applications, suffer from performance limitations and require systems administration expertise to maintain. However, the motivation is clear; in addition to increasing resource utilization, the burden of supporting new software installations on existing systems can be reduced. In this paper, we introduce the Virtual Container Cluster (VCC) that encapsulates a typical HPC software environment within Docker containers. The novel component cluster-watcher enables context aware discovery and configuration of the virtual cluster. Containers offer a lightweight alternative to VMs that more closely match the native performance, and presents a solution that is more accessible to customization by the average user. Combined with a Software Defined Networking (SDN) technology, the VCC enables dynamic features such as transparent scaling and spanning across multiple physical resources. Although SDN introduces an additional performance limitation, within the context of a parallel communication network, the benchmarking demonstrates that this cost is application dependent. The Linpack benchmarking shows that the overhead of container virtualization and SDN interconnect is comparable to the native performance. [ABSTRACT FROM AUTHOR]

Hardware performance monitoring counters (PMCs) have proven effective in characterizing application performance. Because PMCs can only be accessed directly at the OS privilege level, kernellevel tools must be developed to enable the end-user and userspace programs to access PMCs. A large body of work has demonstrated that the OS can perform effective runtime optimizations in multicore systems by leveraging performance-counter data. Special attention has been paid to optimizations in the OS scheduler. While existing performance monitoring tools greatly simplify the collection of PMC application data from userspace, they do not provide an architecture-agnostic kernel-level mechanism that is capable of exposing high-level PMC metrics to OS components, such as the scheduler. As a result, the implementation of PMC-based OS scheduling schemes is typically tied to specific processor models. To address this shortcoming we present PMCTrack, a novel tool for the Linux kernel that provides a simple architecture-independent mechanism that makes it possible for the OS scheduler to access per-thread PMC data. Despite being an OSoriented tool, PMCTrack still allows the gathering of monitoring data from userspace, enabling kernel developers to carry out the necessary offline analysis and debugging to assist them during the scheduler design process. In addition, the tool provides both the OS and the user-space PMCTrack components with other insightful metrics available in modern processors and which are not directly exposed as PMCs, such as cache occupancy or energy consumption. This information is also of great value when it comes to analyzing the potential benefits of novel scheduling policies on real systems. In this paper, we analyze different case studies that demonstrate the flexibility, simplicity and powerful features of PMCTrack. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of building reliable computing programs over remote procedure call (RPC) systems by using replication and transaction techniques. We first establish the computational model: the RPC transactions. Based on this RPC transaction model, we present the design of our system for managing RPC transactions in the replicated-server environment. Finally, we present some results of a correctness study on the system and two examples of the system. [ABSTRACT FROM AUTHOR]

Distributed programs often follow some bounded global predicates, for example, the total number of certain tokens is always the same or bounded in a range. In order to detect bounded global predicates, we can first derive the minimum and maximum global snapshots and then check if the minimum and maximum are out of the range. Recently, Chase and Garg proposed an efficient method to derive the minimum global snapshot by reducing this problem to a maximum network flow problem. A restriction of this method is that all message values (e.g., the token number in messages) must be zero and all process state values (e.g., the token number in processes) must be non-negative. In this paper, we propose an elegant technique, called normalization. By using this technique, we can remove the above restriction and also derive the minimum and maximum global snapshots at the same time. [ABSTRACT FROM AUTHOR]

The need to use partial functions arises frequently in formal descriptions of computer systems. However, most proof assistants are based on logics of total functions. One way to address this mismatch is to invent and mechanize a new logic. Another is to develop practical workarounds in existing settings. In this paper we take the latter course: we survey and compare methods used to support partiality in a mechanization of a higher order logic featuring only total functions. The techniques we discuss are generally applicable and are illustrated by relatively large examples. [ABSTRACT FROM AUTHOR]

This paper is concerned with the demonstration of an analogy between classical electrical circuits and computer systems with executing programs. The analogy is based on a Markov process framework for the mathematical formulation. The transition weights represent a set of measure one although they are not necessarily probabilities in the stochastic sense. Examples are included to show the analogies at a level that should be easily understood by an electrical engineer. [ABSTRACT FROM AUTHOR]

The author reflects on the benchmarking and performance analysis of supercomputer. He states that several challenges are involved in supercomputing design including the programmability of the architecture, power for running the supercomputer, and the sustained performance of a scientific application. He further informs that performance analysis and benchmarking study of OP2 active library ensures code longevity and successful performance through successive generations of systems.

Datagram congestion control protocol (DCCP) is an unreliable transport layer protocol with a congestion control mechanism used for multimedia streaming. In order to use multiple network interfaces to transmit streaming data smoothly, a multipath datagram congestion control protocol (MP-DCCP) is proposed and presented in this paper. Video streaming transmission through multipath faces three problems: (1) unordered and untimely received packets at the receiver side, (2) the importance of frames/packets are different and (3) the stability of the total throughput of a multipath transmission. This work proposes the adaptive ordering predicting scheduling (AOPS) scheme to relieve the first two problems. AOPS estimates packets’ arrival orders at the receiver side through these multiple paths and then derives packets’ transmission schedule at the sender side. A flow-sharing congestion control (FSCC) mechanism for MP-DCCP is proposed in this work to tackle the third problem i.e., the total throughput's stability. From the simulation results, we illustrated that the packets’ disorder and received situations in MP-DCCP can be improved using our proposed AOPS scheme and the unstable condition of the total throughput in MP-DCCP can also be relieved using the proposed FSCC mechanism. [ABSTRACT FROM AUTHOR]

Increasingly, large-scale computing systems are consuming more power each passing year. As power consumption is on the rise, concern has been raised over the growing implications on power bills, carbon emissions and power supply limitations for data centers. Computing systems use hardware components that are not power proportional and machines comprising large systems tend to be underutilized, resulting in great wastage of energy. Motivated by this fact, researchers aim to improve the energy efficiency of these systems by increasing resource utilization and exploiting system characteristics in order to achieve power proportionality. However, many challenges burden the task of producing a power-aware, energy-efficient large-scale system that provides the same performance as today's systems. Particularly, storage systems are of great concern since storage consumes a large amount of power in the data center. This paper outlines the main problems and challenges of delivering power-efficient storage solutions, and proposes a taxonomy of power-aware techniques. This work aims to provide a detailed exposition of current trends in power-aware storage systems in a comprehensive and organized manner, outlining and comparing current solutions and challenges. [ABSTRACT FROM AUTHOR]

This paper combines symmetry reduction with generalized symbolic trajectory evaluation (GSTE) to tackle state explosion. The inherent correlation between structure symmetry and property symmetry is formalized as a theorem, which provides the soundness of our symmetry reduction method. We introduce a practical strategy to effectively integrate the symmetry-reduction approach in a hybrid verification environment which combines theorem proving and GSTE. The effectiveness of our method is demonstrated by case studies. [ABSTRACT FROM AUTHOR]

Advancing technologies have enabled simple mobile robots that collaborate to perform complex tasks. Understanding how to achieve such collaboration with simpler robots leverages these advances, potentially allowing more robots for a given cost and/or decreasing the cost of deploying a fixed number of robots. This paper is a step toward understanding the algorithmic strengths and weaknesses of robots that are identical mobile finite-state machines (FSMs)—FSMs being the avatars of simple, yet non-trivial, discrete control structures. We study the ability of (teams of) FSMs to identify and search varied-size quadrants of square (i.e. n×n) meshes of tiles—such meshes being the avatars of simple tesselated geographically constrained environments. Each team must be able to accomplish its assigned tasks in arbitrarily large meshes—i.e. for arbitrarily large values of n. Partitions of a mesh into quadrants are specified via pairs of rational numbers 〈 ϕ, ψ 〉, where 0 < ϕ, ψ < 1, chosen from a fixed, finite repertoire of such pairs. The quadrants specified by a pair 〈 ϕ, ψ 〉 are delimited by a horizontal line and a vertical line that that cross at the anchor mesh-tile v = 〈 ⌊ ϕ (n−1) ⌋, ⌊ ψ (n−1) ⌋ 〉. The following results are established.A single FSM cannot identify anchor tiles in meshes of arbitrary sizes, even for a single pair 〈 ϕ, ψ 〉—except when the anchor tile resides on an edge of the mesh.A pair of identical FSMs can identify anchor tiles in meshes of arbitrary sizes, for arbitrary fixed finite sets of k pairs {〈 ϕi, ψi 〉}i=1k. After identifying an anchor tile, the pair can sweep each of the resulting quadrants in turn.Single FSMs can verify—for arbitrary fixed finite sets of pairs and for meshes of arbitrary sizes—that all of the tiles of each quadrant are labeled in a way that is unique to that quadrant. Deploying multiple FSMs for this task achieves linear parallel speedup. [ABSTRACT FROM AUTHOR]

This work describes a novel approach for the reduction of energy consumption in data centres (DCs) that will yield benefits both in terms of running costs and its environmental impact. The method is based on the introduction of collaborative interactions and flexibility clauses in contracts between all the DC ecosystem entities. The included entities are all the actors along the energy production–consumption chain, from the energy provider to the Information Technology customer. The collaborative approach also integrates the interaction between federated DCs. In this paper, we find a detailed description of the architecture that enables interaction between the DC ecosystem parties, which is designed to be progressively deployed, allowing traditional and ‘greened’ services to coexist, and without modification of the existing DC automation and framework systems. [ABSTRACT FROM AUTHOR]

For open-ended computational growth, we argue that: (i) instead of hardwiring and hiding component spatial relationships, computer architecture should soften and expose them; and (2) instead of relegating reliability to hardware, robustness must climb the computational stack toward the end users. We suggest that eventually all truly large-scale computers will be robust spatial computers—even if intended neither for spatial tasks nor harsh environments. This paper is an extended introduction for the spatial computing community to the Movable Feast Machine (MFM), a computing model in the spirit of an object-oriented asynchronous cellular automata. We motivate the approach and then present the model, touching on robustness mechanisms such as redundancy, compartmentalization and homeostasis. We provide simulation data from prototype movable elements such as self-healing wire for data transport and movable ‘membrane’ rings for spatial segregation, and illustrate how some larger computations like sorting or evaluating a lambda expression can be reconceived for robustness and movability within a spatial computing architecture. [ABSTRACT FROM AUTHOR]

Nowadays, networks are almost ubiquitous. In the past decade, community detection received an increasing interest as a way to uncover the structure of networks by grouping nodes into communities more densely connected internally than externally. Yet most of the effective methods available do not consider the potential levels of organization, or scales, a network may encompass and are therefore limited. In this paper, we present a method compatible with global and local criteria that enables fast multi-scale community detection on large networks. The method is derived in two algorithms, one for each type of criterion, and implemented with six known criteria. Uncovering communities at various scales is a computationally expensive task. Therefore, this work puts a strong emphasis on the reduction of computational complexity. Some heuristics are introduced for speed-up purposes. Experiments demonstrate the efficiency and accuracy of our method with respect to each algorithm and criterion by testing them against large generated multi-scale networks. This study also offers a comparison between criteria and between the global and local approaches. In particular, our results suggest that global criteria seem to be more robust to noise and thus more accurate than local criteria. [ABSTRACT FROM PUBLISHER]

Our aim is to realize semantic face image retrieval (FIR)\ by bridging the semantic-gap between low-level visual features of images and the high-level labels that describe facial features. This allows a user to retrieve face images based on a description of face features rather than an example image. We approach the semantic-gap problem by developing a fuzzy-based method of finding a mapping between the low-level features and the vocabulary that describes the semantics of the face features. The contribution of this paper is a new method of using fuzzy clustering and fuzzy inference methods to derive the degree of membership for each semantic label to a new image. Our experiments show that our approach has good results for annotating images, and provides a sound foundation for local face feature-based FIR systems. We have made available a demonstration system online. Further, our system is not domain specific and can be generalized and applied to other problems in the field of image retrieval. [ABSTRACT FROM PUBLISHER]

In this paper we report on progress in the use of stochastic process algebras for representing systems which contain many replications of components such as clients, servers and devices. Such systems have traditionally been difficult to analyse even when using high-level models because of the need to represent the vast range of their potential behaviour. Models of concurrent systems with many components very quickly exceed the storage capacity of computing devices even when efficient data structures are used to minimize the cost of representing each state. Here, we show how population-based models that make use of a continuous approximation of the discrete behaviour can be used to efficiently analyse the temporal behaviour of very large systems via their collective dynamics. This approach enables modellers to study problems that cannot be tackled with traditional discrete-state techniques such as continuous-time Markov chains. [ABSTRACT FROM PUBLISHER]

Although analyzing complex systems could be a complicated process, current approaches to quantify system security or vulnerability usually consider the whole system as a single component. In this paper, we propose a new compositional method to evaluate the vulnerability measure of complex systems. By the word composition we mean that the vulnerability measure of a complex system can be computed using pre-calculated vulnerability measures of its components. We define compatible systems to demonstrate which components could combine. Moreover, choice, sequential, parallel and synchronized parallel composition methods are defined and the measurement of the vulnerability in each case is presented. Our method uses a state machine to model the system. The model considers unauthorized states and attacker capabilities. Furthermore, both the probability of attack and delay time to reach the target state are used to quantify vulnerability. The proposed approach would be useful to analyze complex systems which may have complicated models. This approach reduces the state space and complexity of computation. On the other hand, if a component is replaced by another one, the vulnerability measures of other components do not change. Thus, these quantities are reused in new computation. Therefore, the calculation of the vulnerability measure for a new system is simplified. [ABSTRACT FROM AUTHOR]

Service composition allows distributed application, such as multimedia application, to be composed from atomic service units and to adapt dynamically to users' requirements and environment conditions in pervasive computing system. It augments the adaptation action space for the application of pervasive computing. According to the multidimensional QoS (Quality of Service) requirement of pervasive computing system, we proposed a comprehensive service composition method to enhance the capability of application adaptation. First, according to a hierarchy policy model and a policy specification language, strengthened by event calculus, service discovery policy action integrating the situation of user, application, environment and resource can be triggered. Secondly, the proposed physical space model can support the location-aware service discovery and explicit range query to improve the efficiency of the query. To the end, an adaptation policy evaluation model is utilized to maximize an evaluation criterion–quality of satisfaction of users and environment by optimizing the optional service selection and the composition path. Through experiment and discussion of the algorithm, the paper further illustrates the great potential advantage of the solution to service composition. [ABSTRACT FROM PUBLISHER]