Defence of Ivo Kubjas' PhD thesis

On 26 October at 10:15 Ivo Kubjas will defend his doctoral thesis “Algebraic approaches to problems arising in decentralized systems” for obtaining the degree of Doctor of Philosophy (in Computer Science). The defence takes place in Zoom.

Supervisor:
Assoc. Prof. Vitaly Skachek, University of Tartu

Opponents:
Prof. Tadashi Wadayama, Nagoya Institute of Technology (Japan)
Prof. Parastoo Sadeghi, University of New South Wales (Australia)

Summary
With the increased usage of cloud hosting platforms and new wireless technologies, the communication paradigm has changed from server-client models to complex decentralized models. The service providers need to distribute their services across different data centers to handle the enormous traffic loads generated by the customers and be close to the clients to provide a low level of latency for a good user experience. However, duplicating the data across multiple servers is resource wasteful and cost-inefficient. We consider three directions that allow reducing the communication between the servers and users. For all directions, we represent the problems as mathematical structures and apply algebraic methods to provide solutions to the related problems.

We first consider the data synchronization problem, where there are nodes with their data sets. Their goal is to obtain the union of the sets. We propose an improvement over an existing method based on invertible Bloom filters, which removes the requirement on the size of the symmetric set difference.

Secondly, we consider the data distribution problem. In data distribution, the graph representing the network topology is an arbitrary strongly connected directed graph. The nodes' goal is to recover particular elements from other nodes. We describe protocols for single- and multi-round network topologies. We show that the single-round protocol is communicationally optimal, and multi-round protocol has a minimal number of rounds.

Finally, we consider the problem of function computation on synchronized data. This problem differs from data synchronization as the nodes' goal is to compute the value of a function on the union of the sets. We see that the change in the problem definition allows achieving a significant reduction in the number of transmitted bits. We give upper and lower bounds on the communication complexity for a family of functions in both deterministic and random models.