Käesolevas projektis pakume me uurimiseks kahte seotud koodide perekonda: pakk-koode ja koode privaatseks infootsinguks. Need kaks koodide perekonda on sobivad saavutamaks koormuse tasakaalustamist mitmik-serveri süsteemides, andmete privaatseks juurdepääsuks hajutatud andmetalletussüsteemides ja efektiivseks andmepakkide ümbersuunamiseks kommutaatorites. Me kavatseme ühendada lokaalselt parandatavate koodide valdkonnas kasutatavad analüütilised tehnikad täiendavate uudsete ideedega. Väljapakutud teadustöö viib uute peaaegu optimaalsete koodide projekteerimiseni, nende koodide fundamentaalsetest piiridest arusaamiseni ja efektiivsetele nendel koodidel põhinevatele praktiliste skeemideni.
In this project, we propose to study two related families of codes: batch codes and codes for private information retrieval. These two families of codes are suitable for achieving load balancing in multi-server systems, for private access to the data in distributed data storage systems, and for efficient redirection of data packets in network switches. We propose to combine the analytical techniques used in the area of locally repairable codes with additional novel ideas. The proposed research will lead to design of new close-to-optimal codes, to better understanding of the fundamental limits on their parameters, and to efficient practical schemes based on such codes.
Consider a large distributed data storage system. Assume that some servers contain more popular data files. In that case, most of the user reading requests will be directed to these few servers. This situation leads to uneven load between various servers, and to sub-optimal performance. In order to overcome this limitation, it was suggested by Ishai et al. to represent the data by using so-called "batch codes". Under this model, the requested data can be read from a number of groups of servers. In particular, by using servers with a lower load, the system performance could be improved. The original model of batch codes assumes that all user requests are taken care of at the same time, in synchronous way. In this project, we observed that this strategy is not always optimal. In particular, when the processing times vary, it is beneficial to use a modified model of so-called "asynchronous batch codes". In this new model, the requests are treated immediately when they arrive, and so waiting times are reduced. However, the design and analysis of asynchronous batch codes is more involved than in the regular batch code case. In the course of the project, we analyzed asynchronous batch codes, provided constructions of new codes, and derived fundamental limits on their parameters. Additionally, we showed connections of their parameters to those of the regular batch codes, and to the so-called private information retrieval (PIR) codes, which are a related family of codes.