אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Sketches maintain compact approximate statistics about streams of data, thereby enabling quickly answering queries regarding the data stream without having to reprocess it. In this talk we will present four different papers that studies concurrent sketches and their applications. In particular we looked at these subjects : CRDT sliding window sketch, Multi-Producers Single-Consumer Queue, Limited Associativity Caches and Cache Admission Filter . In first result we introduce the notion of sliding window CRDT sketches where we collect global statistics about the stream in a decentralized manner. In the second result we study the implementation of wait-free multi-producer single-consumer queues. In applications such as sharded data processing systems, data flow programming and load sharing applications, multiple concurrent data producers are feeding requests into the same data consumer. This can be naturally realized through concurrent queues, where each consumer pulls its tasks from its dedicated queue. In the third result we show that limited associativity caches are a promising direction for software caches. Specifically, we demonstrate that limited associativity enables simple yet efficient realizations of multiple cache management schemes that can be trivially parallelized. We show that the obtained hit ratio is usually similar to fully associative caches of the same management policy, but the throughput is improved by up to x5 compared to production-grade caching libraries, especially in multi-threaded executions. In the last result we presented TinyCache - An Effective Cache Admission Filter is a compact table based management policy for datastore caches that is easily parallelizable.