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

The bulk of the talk will deal with space requirements of reliable storage algorithms in asynchronous distributed systems. A number of recent works have used codes in order to achieve a better storage cost than the well-known replication approach. However, a closer look reveals that they incur extra costs in certain scenarios. Specifically, if multiple clients access the storage concurrently, then existing asynchronous code- based algorithms may store a number of copies of the data that grows linearly with the number of concurrent clients. We will show that this is inherent. Given three parameters, (1) the data size - D bits, (2) the concurrency level - c, and (3) the number of storage node failures that need to be tolerated - f, we show a lower bound of Ω(min(f,c)*D) bits on the space complexity of asynchronous distributed storage algorithms. Intuitively, this implies that the asymptotic storage cost is either as high as with replication, namely O(fD), or as high under concurrency as with the aforementioned code-based algorithms, i.e., O(cD). We further present a technique for combining erasure codes with replication so as to obtain the best of both. We present an adaptive f - tolerant storage algorithm whose storage cost is O(min(f, c)*D). Together, the results show that the space complexity of providing reliable storage in asynchronous distributed systems is Θ(min(f,c) * D).

I will then briefly present some results on game theoretic analysis of multi-miner multi blockchain settings. We consider a model with coins and rational miners, in which each coin divides a reward to the miners that mine for it. The payoff of each miner is proportional to the miner's power, and miners are free to change coins in order to increase their payoffs. We show that every game in this setting has an equilibrium, and moreover, every better respond dynamic leads to an equilibrium. Then, we also give a mechanism reward design to move the system between equilibriums.

Based on joint works with Yuval Cassuto, Gregory Chockler, Idit Keidar, and Moshe Tennenholtz.