Record/replay is one essential tool in clouds to provide many capabilities such as fault tolerance, software debugging, and security analysis by recording the execution into a log and replaying it deterministically later on. However, in virtualized environments, the log file increases heavily due to saving a considerable amount of I/O data, finally introducing significant storage costs. To mitigate this problem, this paper proposes RR-Row, a redirect-on-write based virtual machine disk for record/replay scenarios. RR-Row appends the written data into new blocks rather than overwrites the original blocks during normal execution so that all written data are reserved in the disk. In this way, the record system only saves the block id instead of the full content, and the replay system can directly fetch the data from the disk rather than the log, thereby reducing the log size a lot. In addition, we propose several optimizations for improving I/O performance so that it is also suitable for normal execution. We implement RR-Row for QEMU and conduct a set of experiments. The results show that RR-Row reduces the log size by 68% compared to the currently used Raw/QCow2 disk without compromising I/O performance.

The previous communication-induced checkpointing may considerably induce worthless forced checkpoints because each process receiving messages cannot obtain sufficient information related to non-causal Z-paths. This paper presents an enhanced sender-based message logging protocol applicable to any communication-induced checkpointing to lead to a high decrease of the forced checkpointing overhead of communication-induced checkpointing in an effective way while permitting no useless checkpoint. The protocol allows each process sending a message to know the exact timestamp of the receiver of the message in its logging procedures without any extra message. Simulation verifies their great efficiency of overhead alleviation regardless of communication patterns.

As NAND flash-based storage has been settled, a flash translation layer (FTL) has been in charge of mapping data addresses on NAND flash memory. Many FTLs implemented various mapping schemes, but the amount of mapping data depends on the mapping level. However, the FTL should contemplate mapping consistency irrespective of how much mapping data dwell in the storage. Furthermore, the recovery cost by the inconsistency needs to be considered for a faster storage reboot time. This letter proposes a novel method that enhances the consistency for a page-mapping level FTL running a legacy logging policy. Moreover, the recovery cost of page mappings also decreases. The novel method is to adopt a virtually-shrunk segment and deactivate page-mapping logs by assembling and storing the segments. This segment scheme already gave embedded NAND flash-based storage enhance its response time in our previous study. In addition to that improved result, this novel plan maximizes the page-mapping consistency, therefore improves the recovery cost compared with the legacy page-mapping FTL.

Logging is a practical and useful way of diagnosing failures in software systems. The logged events are crucially important to learning what happened during a failure. If key events are not logged, it is almost impossible to track error propagations in the diagnosis. Tracking an error propagation becomes utterly complicated if inter-thread data dependency is involved. An inter-thread data dependency arises when one thread accesses to share data corrupted by another thread. Since the erroneous state propagates from a buggy thread to a failing thread through the corrupt shared data, the root cause cannot be tracked back solely by investigating the failing thread. This paper presents the design and implementation of K9, a tool that inserts logging code automatically to trace inter-thread data dependencies. K9 is designed to be “practical”; it scales to one million lines of code in C, causes negligible runtime overheads, and provides clues to tracking inter-thread dependencies in real-world bugs. To scale to one million lines of code, K9 ditches rigorous static analysis of pointers to detect code locations where inter-thread data dependency can occur. Instead, K9 takes the best-effort approach and finds out “most” of those code locations by making use of coding conventions. This paper demonstrates that K9 is applicable to Linux and captures relevant code locations, in spite of the best-effort approach, enough to provide useful clues to root causes in real-world bugs, including a previously unknown bug in Linux. The paper also shows K9 runtime overhead is negligible. K9 incurs 1.25% throughput degradation and 0.18% CPU usage increase, on average, in our evaluation.

File systems based on persistent memory deploy Copy-on-Write (COW) or logging to guarantee data consistency. However, COW has a write amplification problem and logging has a double write problem. Both COW and logging increase write traffic on persistent memory. In this work, we present adaptive differential logging and zero-copy logging for persistent memory. Adaptive differential logging applies COW or logging selectively to each block. If the updated size of a block is smaller than or equal to half of the block size, we apply logging to the block. If the updated size of a block is larger than half of the block size, we apply COW to the block. Zero-copy logging treats an user buffer on persistent memory as a redo log. Zero-copy logging does not incur any additional data copy. We implement adaptive differential logging and zero-copy logging on both NOVA and PMFS file systems. Our measurement on real workloads shows that adaptive differential logging and zero-copy logging get 150.6% and 149.2% performance improvement over COW, respectively.

In this paper, we present a hybrid message logging protocol consisting of three modules for two-level hierarchical and distributed architectures to address the drawbacks of sender-based message logging. The first module reduces the number of in-group control messages and, the rest, the number of inter-group control messages while localizing recovery. In addition, it can distribute the load of logging and keeping inter-group messages to group members as evenly as possible. The simulation results show the proposed protocol considerably outperforms the traditional protocol in terms of message logging overhead and scalability.

In Twitter-like services, countless messages are being posted in real-time every second all around the world. Timely knowledge about what kinds of information are diffusing in social media is quite important. For example, in emergency situations such as earthquakes, users provide instant information on their situation through social media. The collective intelligence of social media is useful as a means of information detection complementary to conventional observation. We have developed a system for monitoring and analyzing information diffusion data in real-time by tracking retweeted tweets. A tweet retweeted by many users indicates that they find the content interesting and impactful. Analysts who use this system can find tweets retweeted by many users and identify the key people who are retweeted frequently by many users or who have retweeted tweets about particular topics. However, bursting situations occur when thousands of social media messages are suddenly posted simultaneously, and the lack of machine resources to handle such situations lowers the system's query performance. Since our system is designed to be used interactively in real-time by many analysts, waiting more than one second for a query results is simply not acceptable. To maintain an acceptable query performance, we propose a capacity control method for filtering incoming tweets using extra attribute information from tweets themselves. Conventionally, there is a trade-off between the query performance and the accuracy of the analysis results. We show that the query performance is improved by our proposed method and that our method is better than the existing methods in terms of maintaining query accuracy.

All the existing sender-based message logging (SBML) protocols share a well-known limitation that they cannot tolerate concurrent failures. In this paper, we analyze the cause for this limitation in a unicast network environment, and present an enhanced SBML protocol to overcome this shortcoming while preserving the strengths of SBML. When the processes on different nodes execute a distributed application together in a broadcast network, this new protocol replicates the log information of each message to volatile storages of other processes within the same broadcast network. It may reduce the communication overhead for the log replication by taking advantage of the broadcast nature of the network. Simulation results show our protocol performs better than the traditional one modified to tolerate concurrent failures in terms of failure-free execution time regardless of distributed application communication pattern.

Sentiment analysis of microblogging has become an important classification task because a large amount of user-generated content is published on the Internet. In Twitter, it is common that a user expresses several sentiments in one tweet. Therefore, it is important to classify the polarity not of the whole tweet but of a specific target about which people express their opinions. Moreover, the performance of the machine learning approach greatly depends on the domain of the training data and it is very time-consuming to manually annotate a large set of tweets for a specific domain. In this paper, we propose a method for sentiment classification at the target level by incorporating the on-target sentiment features and user-aware features into the classifier trained automatically from the data createdfor the specific target. An add-on lexicon, extended target list, and competitor list are also constructed as knowledge sources for the sentiment analysis. None of the processes in the proposed framework require manual annotation. The results of our experiment show that our method is effective and improves on the performance of sentiment classification compared to the baselines.

Social media such as microblogs have become so pervasive such that it is now possible to use them as sensors for real-world events and memes. While much recent research has focused on developing automatic methods for filtering and summarizing these data streams, we explore a different trend called social curation. In contrast to automatic methods, social curation is characterized as a human-in-the-loop and sometimes crowd-sourced mechanism for exploiting social media as sensors. Although social curation web services like Togetter, Naver Matome and Storify are gaining popularity, little academic research has studied the phenomenon. In this paper, our goal is to investigate the phenomenon and potential of this new field of social curation. First, we perform an in-depth analysis of a large corpus of curated microblog data. We seek to understand why and how people participate in this laborious curation process. We then explore new ways in which information retrieval and machine learning technologies can be used to assist curators. In particular, we propose a novel method based on a learning-to-rank framework that increases the curator's productivity and breadth of perspective by suggesting which novel microblogs should be added to the curated content.

Logging the execution process of a program is a popular activity for practical program understanding. However, understanding the behavior of a program from a complete execution trace is difficult because a system may generate a substantial number of runtime events. To focus on a small subset of runtime events, a dynamic object process graph (DOPG) has been proposed. Although a DOPG can potentially facilitate program understanding, the logging process has not been adapted for DOPGs. If a developer is interested in the behavior of a particular object, only the runtime events related to the object are necessary to construct a DOPG. The vast majority of runtime events in a complete execution trace are irrelevant to the interesting object. This paper analyzes actual DOPGs and reports that a logging tool can be optimized to record only the runtime events related to a particular object specified by a developer.

This paper presents a new scalable method to considerably reduce the rollback propagation effect of the conventional optimistic message logging by utilizing positive features of reliable FIFO group communication links. To satisfy this goal, the proposed method forces group members to replicate different receive sequence numbers (RSNs), which they assigned for each identical message to their group respectively, into their volatile memories. As the degree of redundancy of RSNs increases, the possibility of local recovery for each crashed process may significantly be higher. Experimental results show that our method can outperform the previous one in terms of the rollback distance of non-faulty processes with a little normal time overhead.

Information affects almost all aspects of life, and thus the Quality of Information (IQ) plays a critical role in businesses and societies; It can have significant positive and negative impacts on the quality of life of citizens, employees and organizations. Over many years aspects and challenges of IQ have been studied within various contexts. As a result, the general approach to the study of IQ has offered numerous management and measurement approaches, IQ frameworks and list of IQ criteria. As the volume of data and information increases, IQ problems become pervasive. Whereas earlier studies investigated specific aspects of IQ, the next phase of IQ research will need to examine IQ in a wider context, thus its impact on the quality of life and societies. In this paper we apply an IQ oriented framework to two cases, cloud computing and lifelogging, illustrating the impact of IQ on the quality of life. The paper demonstrates the value of the framework, the impact IQ can have on the quality of life and in summary provides a foundation for further research.

As an increasing number of businesses and services depend on the Internet, protecting them against DDoS (Distributed Denial of Service) attacks becomes a critical issue. A traceback is used to discover technical information concerning the ingress points, paths, partial paths or sources of a packet or packets causing a problematic network event. The traceback mechanism is a useful tool to identify the attack source of the (DDoS) attack, which ultimately leads to preventing against the DDoS attack. There are numerous traceback mechanisms that have been proposed by many researchers. In this paper, we analyze the existing traceback mechanisms, describe the common security capabilities of traceback mechanisms, and evaluate them in terms of the various criteria. In addition, we identify typical application of traceback mechanisms.

Sender-based message logging (SBML) with checkpointing has its well-known beneficial feature, lowering highly failure-free overhead of synchronous logging with volatile logging at sender's memory. This feature encourages it to be applied into many distributed systems as a low-cost transparent rollback recovery technique. However, the original SBML recovery algorithm may no longer be progressing in some transient communication error cases. This paper proposes a consistent recovery algorithm to solve this problem by piggybacking small log information for unstable messages received on each acknowledgement message for returning the receive sequence number assigned to a message by its receiver. Our algorithm also enables all messages scheduled to be sent, but delayed because of some preceding unstable messages to be actually transmitted out much earlier than the existing ones.

This paper presents a fault-tolerance scheme based on mobile agents for the reliable mobile computing systems. Mobility of the agent is suitable to trace the mobile hosts and the intelligence of the agent makes it efficient to support the fault tolerance services. This paper presents two approaches to implement the mobile agent based fault tolerant service and their performances are evaluated and compared with other fault-tolerant schemes.

Fault-tolerance is an important design issue in building a reliable mobile computing system. This paper considers checkpointing recovery services for a mobile computing system based on the ad-hoc network environment. Since potential problems of this new environment are insufficient power and limited storage capacity, the proposed scheme tries to reduce disk access frequency for saving recovery information, and also the amount of information saved for recovery. A brief simulation study has been performed and the results show that the proposed scheme takes advantage of the existing checkpointing recovery schemes.

Because it has desirable features such as no cascading rollback, fast output commit and asynchronous logging, causal message logging needs a consistent recovery algorithm to tolerate concurrent failures. For this purpose, Elnozahy proposed a centralized recovery algorithm to have two practical benefits, i.e. reducing the number of stable storage accesses and imposing no restriction on the execution of live processes during recovery. However, the algorithm with independent checkpointing may force the system to be in an inconsistent state when processes fail concurrently. In this paper, we identify these inconsistent cases and then present a recovery algorithm to have the two benefits and ensure the system consistency when integrated with any kind of checkpointing protocol. Also, our algorithm requires no additional message compared with Elnozahy's algorithm.

We propose a new effective method of managing flash memory space for flash memory-specific file systems based on a log-structured file system. Flash memory has attractive features such as non-volatility and fast I/O speed, but it also suffers from inability to update in situ and from limited usage (erase) cycles. These drawbacks necessitate a number of changes to conventional storage (file) management techniques. Our focus is on lowering cleaning cost and evenly utilizing flash memory cells while maintaining a balance between these two often-conflicting goals. The proposed cleaning method performs well especially when storage utilization and the degree of locality are high. The cleaning efficiency is enhanced by dynamically separating cold data and non-cold data, which is called 'collection operation.' The second goal, that of cycle-leveling, is achieved to the degree that the maximum difference between erase cycles is below the error range of the hardware. Experimental results show that the proposed technique provides sufficient performance for reliable flash storage systems.

Causal message logging has many benefits such as nonblocking message logging and no rollback propagation. In this paper, we consider the problem of the recovery in causally-logged distributed system and give a condition for consistent recovery. We then show that, based on the impossibility of the consensus, the consistent causal recovery cannot be solved in asynchronous systems.