We propose Sage, a system for uncertain network analysis. Algorithms for uncertain network analysis require large amounts of memory and computing resources as they sample a large number of network instances and run analysis on them. Sage makes uncertain network analysis simple and efficient. By extending the edge-centric programming model, Sage makes writing sampling-based analysis algorithms as simple as writing conventional graph algorithms in Pregel-like systems. Moreover, Sage proposes four optimization techniques, namely, deterministic sampling, hybrid gathering, schedule-aware caching, and copy-on-write attributes, that exploit common properties of uncertain network analysis. Extensive evaluation of Sage with eight algorithms on six real-world networks shows that the four optimizations in Sage jointly improve performance by up to 13.9X and on average 2.7X.

Various transactional systems use out-of-place up-dates such as logging or copy-on-write mechanisms to update data in a failure-atomic manner. Such out-of-place update methods double the I/O traffic due to back-up copies in the database layer and quadruple the I/O traffic due to the file system journaling. In mobile systems, transaction sizes of mobile apps are known to be tiny and transactions run at low concurrency. For such mobile transactions, legacy out-of-place update methods such as WAL are sub-optimal. In this work, we propose a crash consistent in-place update logging method - doubleheader logging (DHL) for SQLite. DHL prevents previous consistent records from being lost by performing a copy-on-write inside the database page and co-locating the metadata-only journal information within the page. This is done, in turn, with minimal sacrifice to page utilization. DHL is similar to when journaling is disabled, in the sense that it incurs almost no additional overhead in terms of both I/O and computation. Our experimental results show that DHL outperforms other logging methods such as out-of-place update write-ahead logging (WAL) and in-place update multi-version B-tree (MVBT).

This paper proposes a prefetch-based disk buffer management algorithm, which we call W²R (Weighing/Waiting Room). Instead of using elaborate prefetching schemes to decide which block to prefetch and when, we simply follow the LRU-OBL (One Block Lookahead) approach and prefetch the logical next block along with the block that is being referenced. The basic difference is that the W²R algorithm logically partitions the buffer into two rooms, namely the Weighing Room and the Waiting Room. The referenced, hence fetched block is placed in the Weighing Room, while the prefetched logical next block is placed in the Waiting Room. By so doing, we alleviate some inherent deficiencies of blindly prefetching the logical next block of a referenced block. Specifically, a prefetched block that is never used may replace a possibly valuable block and a prefetched block, though referenced in the future, may replace a block that is used earlier than itself. Using the DB2 and OLTP traces, we show t...