Maxim Nikolaevich Nazarov September 21, 1980. “Zoo” of neural networks

Due to the constant expansion of the field of application computer technology And widespread global computer networks One of the current areas of mathematical cybernetics is the problem of optimizing work with distributed information resources. In addition, it should be noted that recently a new scientific direction related to the optimal storage and retrieval of information, called the theory of information retrieval, has been actively developing, one of the main carriers of which is database theory.

The Asilomar Report on Database Research Directions explicitly points to the need to significantly expand the scope of research by addressing the challenges of acquiring, storing, and analyzing enormous volumes of information.

The use of mathematical models that interpret distributed information as a set of Boolean functions implemented by tables makes it particularly relevant to develop and study new algorithms for solving the well-known problem of calculating a Boolean function on several independent sets, as well as obtaining new estimates of the complexity of such algorithms.

Subsequently, under access to distributed information resources As a rule, we will understand the extraction of information from distributed databases by treating the database as a formalized representation of information that is convenient for storing and retrieving data in it.

Despite the significant increase in computer speed, the growth in the volume of processed information requires the development of new approaches to database management. As noted in , in the near future, some organizations will have databases that are measured in petabytes or exabytes. It is clear that the problem of efficient processing of such volumes of information can only be solved by distributed and parallel database systems, which are becoming the dominant tools for creating corresponding applications. Traditional computers are increasingly being replaced by successful parallel database systems built on conventional processors, memory and disks. Moreover, it should be noted that their architecture is based on the idea hardware without sharing resources, that is, in such systems, the tuples of each relation in the database are shared among disk storage devices directly attached to each processor.

Recently, quite a lot of prototypes of distributed and parallel database systems have already been created, however, there are still many unsolved or only partially solved problems in this area.

Let us highlight those that are reflected in this dissertation and consider their relevance.

Let us note, firstly, that on modern stage development computer equipment CPU performance is growing significantly faster bandwidth storage devices. Consequently, multiprocessor systems accessing distributed information resources may soon encounter problems with limited I/O throughput. The relevance of the same problem is stated in the already mentioned Asilomar report: “In addition, although the capacity of disk memory increases very quickly, access time decreases relatively slowly. Consequently, the amount of data that can be transferred to main memory during the average access time also grows rapidly. On the other hand, the relative cost of supplying heads also increases magnetic disk compared to the cost of transmitting one byte of data. Therefore, storage architectures are required that place significantly greater emphasis on optimizing head motion."

Another circle current problems related to the use of distributed and parallel databases is associated with the need to perform a huge number of independent queries from different users to one database. It is known, for example, that some corporations are already deploying databases designed for 50 thousand concurrent users. Moreover, the complexity of solving these problems lies in the use of a parallel model, which allows simultaneous access to any memory module of only one processor. Therefore, it is necessary to overcome the so-called memory contention.

In addition, recently the problem of protecting information stored in databases from unauthorized access has become of great importance. This problem includes many different areas, from which it is necessary, first of all, to highlight cryptographic methods of protection. The use of distributed and parallel databases imposes its own specifics on the possibility of using cryptographic methods, which requires separate research in each specific case.

No less relevant today is a fairly new area of ​​information security, which consists in developing a model and corresponding algorithms that allow users to access a common database while maintaining the secrecy of the requests themselves from other users. For the first time such a problem was formulated in, and further developed in. The relevance and practical significance of the results on this topic are well reflected in. We only note that this area of ​​information protection is directly related to common problem optimal access to distributed information resources.

Thus, the development of new algorithms for parallel calculation of Boolean functions as a model for accessing distributed information resources seems theoretically and practically interesting.

So, three groups of pressing problems were identified: minimizing the number of accesses to storage devices, organizing access to distributed memory, and protecting information. Moreover, the first two of them can be solved by developing algorithms that provide one access to each part of the database partition while simultaneously executing several independent queries. It is clear that this direction is directly related to the problems of the physical organization of databases. In the physical organization of databases, we are not dealing with the presentation of data in application programs, and with their placement on storage devices. According to , when choosing a physical organization, the first place is to ensure optimal search (in particular, optimal data access time), followed by the efficiency of operations for adding and deleting information, and then ensuring data compactness. Some models of physical data organization are well described in.

Recently, a mathematical model has become widespread, representing a database in the form of a table for the Boolean function /: (0,1)" (0,1) (see, for example,). The user's request is interpreted as an input set x e (0,1 )". The result of the query is the value f. The corresponding complexity estimates are obtained. However, when calculating a Boolean function on several independent sets, a problem arises, formulated as follows. Is it true that the complexity of such a calculation of a Boolean function is equivalent to the total complexity of the independent calculation of the specified function on each input, that is, that the individual calculations do not overlap? For the first time such a problem was considered on the basis of schemes from functional elements, and a negative answer was received to the previous question. The general formulation of the described problem was called the Direct Sum Problem and was successfully studied in the literature. In the case of communication complexity, a negative answer to Direct Sum Problem was also received. But in the case of the complexity of monotone circuit size complexity and in the case of the complexity of Boolean decision trees, the answer was positive.

However, a new approach to solving the problem of computing a Boolean function on several independent sets and its interpretation as an algorithm for parallel access to a database was implemented in. In treating the database as a Boolean function, the authors considered a special model, which is computer network, each element of which is called a Boolean processor or simply a processor and is a Boolean circuit of functional elements with complexity equal to some constant. This network can make requests to external memory(i.e. database), spending certain time, denoted extime. Moreover, the main limitation of the considered model is the allowance of a single access by each processor to external memory when executing one request to several addresses. This limitation is due to the fact that in practice, the speed of accessing and reading information from any external media is significantly lower than the speed of the processor (the problem noted in). Therefore, the overall database access time will be minimal with one access to the external storage medium, even if this limitation requires additional calculations.

Obviously, when storing the database in one block (without distributing information), retrieving several unrelated bits in one access is impossible. Moreover, simply splitting the data into parts will not satisfy the main constraint, since it may be necessary to extract several independent bits from one part of the partition. Therefore, it is necessary to introduce a special additional information. An algorithm was built called DPrf> which is maximally parallelized, satisfies the main constraint and has an optimal (relative to extime) running time and an optimal increase in the size of the database when distributing it across various media. For the developed algorithm, estimates of its complexity were obtained: parallel computing time, number of Boolean processors and database size.

Let us note, however, that several more unsolved, but relevant and practically significant problems directly follow from this. First of all, you should consider the possibility of using an algorithm to access a database that is not one, but several Boolean functions in tabular form. That is, in this case, each input set (user request) corresponds not to one bit of information, but to several. In fact, this is the problem of parallel computation of a system of Boolean functions on several independent sets of variables. Next, we note that the algorithm obtained in requires a very large number of parallel processors. Therefore, the task of minimizing the number of processors of the specified algorithm while maintaining all its limitations is very important. Note that one of the possible ways reducing the number of processors, requiring an increase in the database size several times. It is clear that this path is not always possible due to the excessive growth of the database.

In addition, it is desirable to consider the problem of information security while taking into account the specifics of the specified distribution of information resources and the problem of parallel access to data while allowing multiple accesses to external storage media.

Further development methods from received in works. All these works are devoted to the problem of organizing the distribution of a set of data across memory modules in the so-called distributed memory machines (DMM - Distributed Memory Machine) or parallel modular computers (Module Parallel Computer). The main limitation of this task is the allowance of simultaneous access to any memory module by only one processor, that is, the absence of memory access conflicts. It is easy to see that this limitation is very similar to the main limitation of the algorithm from , from which similar methods for solving these problems follow. Previously, the problem of organizing data distribution across memory modules was usually solved by modeling PRAM algorithms on the DMM model, which ensured the effectiveness of the solution only under the assumption of a relatively small amount of distributed data. The methods provide effective solution in the case of a large amount of distributed data, and without memory access conflicts when executing queries. Note that in and the problem of reducing the number of processors in the algorithms used was touched upon, but only for a specific type of task.

In addition, it is indicated that the developed methods can be directly used to build PIR (Private Information Retrieval) protocols for information protection. These protocols must ensure the secrecy of requests from one database user from all other users of the same database. Note, however, that the problem of organization cryptographic protection databases using methods for parallel access to information have not been previously considered. Therefore, the solution to this problem is especially relevant, especially since cryptographic methods can find wide application in the construction of PIR protocols. For example, some cryptographic techniques have already been used to encrypt requests, but not the information itself in . It is also possible to use cryptographic methods for protecting information in symmetric PIR protocols, which should ensure not only the secrecy of each user’s requests, but also will not allow the user to learn anything other than the requested record when performing one request.

The purpose of this dissertation is to research and develop algorithms for parallel calculation of Boolean functions on several independent sets, used as a model for accessing distributed information resources and providing optimal time for obtaining information with a polynomially limited number of processors.

Achieving this goal includes solving the following tasks:

1. Investigate the case of parallel calculation of a system of Boolean functions on several independent input sets of variables. Accordingly, it is necessary to consider a mathematical model in which distributed information is represented by tables for several Boolean functions and each input set (user request) corresponds to a certain binary string, rather than one bit of information. Based on this model, it is necessary to construct an algorithm for accessing distributed resources at several independent addresses and assess its complexity. In this case, the algorithm must be maximally parallelized and ensure a one-time access to external storage media when executing one set of requests (this ensures optimal access time to information).

2. Determine the minimum number of processors required for optimal parallel calculation of a Boolean function on several independent sets of variables while allowing one single access to tables for each input sequence of sets. Develop an appropriate algorithm that provides a minimum number of processors, and estimate the complexity of all algorithms with a limited number of processors.

3. For the mathematical models used, develop and evaluate the complexity of algorithms for parallel retrieval of information from a cryptographically protected distributed database at several independent addresses in one access to external storage media. Algorithms must be maximally parallelized and have optimal access time with a polynomially limited number of processors and an optimal database size.

4. Assess the complexity of algorithms for parallel access to distributed information resources at several independent addresses with advance admission a certain amount access to external storage media.

To solve the problems, the work used methods of discrete mathematics and mathematical cybernetics, parallel computing and parallelization of algorithms, the theory of mathematical modeling, database apparatus and cryptography.

As a result of the research and solution of the assigned tasks, the following are submitted for defense:

1. A parallel algorithm for calculating a system of Boolean functions on several independent sets, taking into account all the introduced restrictions of the model, and estimates of its complexity.

2. Estimates of the complexity of the DPrf algorithm WITH weakened growth in the number of processors.

3. An algorithm for parallel calculation of a Boolean function on several independent sets, providing a minimum number of processors while observing the main constraint of the model and assessing its complexity.

4. A method for distributing information in a cryptographically protected database, providing optimal access time, appropriate access algorithms and estimates of their complexity.

5. Estimates of the complexity of algorithms for parallel access to distributed information resources at several independent addresses while allowing multiple accesses to external storage media.

In general, the work is theoretical in nature, and its results can be used to obtain further estimates of the complexity of parallel algorithms for calculating Boolean functions on several independent sets, the complexity of parallel access to distributed information resources, building models in the theory of information retrieval, developing schemes for eliminating access conflicts to shared information. memory, as well as for the development of PIR protocols for information security. At the same time, all the proposed algorithms can find wide practical application in the design of distributed and parallel databases, as well as in the creation of a system software for modern multiprocessor computing systems.

Note that one of the modern classes of multiprocessor hardware architectures computing systems, called MPP (Massively Parallel Processing), contains systems built from the same type of computing nodes, including one or more central processing units, local memory, communications processor or network adapter And hard drive. Moreover, the total number of processors in such systems can reach several thousand. It is easy to see that the methods of information storage and data access algorithms studied in this dissertation work can be successfully implemented in practice specifically for systems with similar architecture. In addition, as noted above, one of the promising areas in the development of multiprocessor computing systems is parallel database machines. According to Stonebreaker's classification, the hardware architectures of such systems can be divided into three main classes: systems with distributed memory and disks, systems with shared disks, and systems without resource sharing. At the same time, in latest systems Each processor has its own memory, its own disk, and the processors are connected into the system using some kind of connecting network. Note that the mathematical models used in this work describe such systems and can find their application in practice.

In systems with distributed memory and disks, all processors are connected to distributed memory and disks using a common bus. Therefore, with a large number of processors in such systems, memory access conflicts begin to arise, which can be resolved by the methods discussed in this work.

At the moment, among the domestic developments of multiprocessor computing systems, one of the most promising is the MVS-100/1000 computing complex. This complex can be considered as an MMP class system, and before the Stonebreaker classification, as a system without resource sharing, if a separate disk is connected to each processor module. Consequently, the theoretical methods and algorithms studied in the work can be tried to be implemented in practice in the specified complex, especially since “further diverse work is ahead on the technical and mathematical development of the created systems.”

This dissertation consists of four chapters and a conclusion.

The first chapter introduces basic definitions and analyzes some well-known results necessary for further presentation of the material. In particular, a mathematical model of the database is described and the problem of calculating a Boolean function on several independent sets of variables is considered. All auxiliary procedures and the main algorithm DPrj are built.

Further in this chapter we study the case of parallel computation of a system of Boolean functions on several independent input sets of variables. An algorithm for parallel calculation of a system of Boolean functions is constructed as a model for accessing binary rows of a distributed database located at several independent addresses and its complexity is estimated under the condition of maximum parallelization of all procedures and ensuring a one-time access to external storage media to perform one set of queries.

In the second chapter, the minimum number of processors required by the DPrj- algorithm is determined to provide one single access to external storage media when the condition of maximum parallelism of the algorithm is waived. The complexity of this algorithm is estimated for such a limited number of processors. It is proved that with some modification of the original DPrf algorithm the number of processors can be minimized. The specified modified algorithm for calculating a Boolean function on several independent sets is constructed and its complexity is estimated for a limited number of processors.

The third chapter examines the problem of cryptographic protection of a distributed database when using the algorithms described in Chapter 1 to access information. A method has been developed for distributing data during storage, ensuring optimal access time. Both mathematical models from Chapter 1 are considered and two algorithms are constructed for parallel retrieval of information from a cryptographically protected database at several independent addresses in one access to external media. Both algorithms are maximally parallelized, have a polynomially bounded number of processors and an optimal database size. The complexity of each of the resulting algorithms is estimated.

The fourth chapter discusses parallel access to the database when allowing multiple accesses to external storage media. Thus, this chapter cancels the main limitation of all previous chapters. Relationship identified permissible quantity accesses to external media and the minimum number of processors required by the algorithms developed in Chapters 1, 2. The complexity of algorithms for parallel access to the database at several independent addresses is assessed while allowing a predetermined number of accesses to external media.

The conclusion reflects the main results of the dissertation work and their relationship with the overall goal and specific tasks conducted research. The theoretical significance and practical value of the results obtained are indicated.

CONCLUSION

As stated in the introduction, the goal of this dissertation is to research and develop algorithms for parallel calculation of Boolean functions on several independent sets, used as a model for accessing distributed information resources and providing optimal time for obtaining information with a polynomially limited number of processors. In this case, a mathematical model was used that interprets distributed information as a set of Boolean functions implemented by tables, and each set of variable values ​​as an address at which information is stored. Moreover, the main limitation of the studied model is the allowance of a single access by each processor to external memory when executing one set of requests at several independent addresses. This limitation is due to the fact that in practice the speed of accessing and reading information from any external media is significantly lower than the speed of the processor. Therefore, the overall database access time will be minimal with one access to the external storage medium, even if this limitation requires additional calculations.

In accordance with the goal and taking into account the specified limitations in the work, the following tasks were solved:

1. The case of parallel calculation of a system of Boolean functions on several independent input sets of variables has been studied. A parallel algorithm for accessing distributed resources is constructed, represented by tables for several Boolean functions, each input set of which corresponds to a certain binary string. This algorithm is a generalization of the already known algorithm for calculating one Boolean function. At the same time, the algorithm is maximally parallelized and provides a single access for each processor to external storage media when executing one set of requests.

2. The problem of minimizing the number of processors during parallel calculation of a Boolean function on several independent sets of variables is considered, allowing one single access to tables for each input sequence of sets. The minimum number of processors required by the DPgy algorithm to ensure one single access to external storage media is determined, while the condition of its maximum parallelization is waived. The complexity of this algorithm is estimated for a weakened increase in the number of processors. It has been proven that with some modification of the original DPrj-algorithm the number of processors can be minimized. The specified modified access algorithm is constructed, and its complexity is estimated with a minimum number of processors.

3. A method for distributing information in a cryptographically protected database is proposed, providing optimal access time. Algorithms for parallel retrieval of information from a cryptographically protected distributed database at several independent addresses in one access to external storage media have been constructed. The algorithms are maximally parallelized and provide optimal access time with a polynomially limited number of processors and optimal database size.

4. A new limitation of the model is formulated, which consists in allowing several accesses to external media for each processor when executing one set of requests. The complexity of algorithms for parallel access to distributed information resources in new conditions is assessed. The relationship between the permissible number of accesses to external media and the minimum number of processors required by the specified algorithms is determined.

It is the solution of all these tasks that includes achieving the stated goal of the study. Indeed, the four groups of solved problems that we have considered can be represented as four stages in achieving the goal of the work. On initial stage The problem of constructing algorithms for parallel calculation of Boolean functions on several independent sets, used as a model of optimal access to distributed information resources, is considered. It is here that the Boolean model of distributed resources is described, the main limitation of the problem and methods of information distribution are determined. The second stage determines the solution to the problem of minimizing the number of processors while abandoning the condition of maximum parallelization of algorithms and increasing time estimates, but maintaining the overall efficiency of the algorithms. This stage allows us to improve estimates of the complexity of the algorithms used. At the third stage, the specifics of cryptographic protection of distributed databases using optimal access methods of the first stage were investigated. Here, new methods of information distribution are defined that provide the possibility of its cryptographic protection. And finally, at the fourth stage, the possibility of optimizing access algorithms is determined by partially abandoning the main limitation of the first stage. Results this stage allow for a more flexible approach to practical use constructed algorithms. All these stages together constitute the final results of this dissertation research.

Note that in general the work is theoretical in nature, and its results can be used to obtain estimates of the complexity of parallel algorithms for calculating Boolean functions on several independent sets, the complexity of parallel access to databases, building models in the theory of information retrieval, developing schemes for eliminating access conflicts shared memory, as well as for the development of information security protocols.

Continuation of theoretical research on the topic of this dissertation involves considering the possibility of using the obtained algorithms and estimates of their complexity when organizing the distribution of a data set among memory modules in machines with distributed memory (DMM - Distributed Memory Machine) or parallel modular computers (Module Parallel Computer). In addition, theoretical research is needed on the application of the obtained algorithms in the construction of PIR protocols (Private Information Retrieval) for information protection.

Another possible direction for continuing theoretical research on the topic of this dissertation is to build new methods for distributing data across media and developing appropriate access algorithms.

At the same time, all the proposed algorithms can find wide practical application in the design of distributed and parallel databases, as well as in the creation of system software for modern multiprocessor computing systems.

At the moment, among the domestic developments of multiprocessor computing systems, one of the most promising is the MVS-100/1000 computing complex. This complex can be considered as a system built from the same type of computing nodes, including one or more central processors, local memory, a communication processor or network adapter and a hard drive, and all computing nodes are connected into the system using some connecting network. It is easy to see that the methods of information storage and data access algorithms studied in this dissertation work can be successfully implemented in practice specifically for systems with a similar architecture. Therefore, in the future it is possible practical research the possibility of using the algorithms of this dissertation when working with the described computer complex.

Thus, the use of mathematical models that interpret a distributed database as a set of Boolean functions implemented by tables makes it possible to construct new parallel access algorithms that can find not only theoretical but also practical application.

To sum up the final results, we can conclude that the goal of this dissertation research has been achieved, all the considered tasks are relevant and have theoretical and practical significance.

1. Aho A., Hopcroft J., Ullman J. Construction and analysis of computational algorithms. M.: Mir, 1979.

2. Bernstein F. et al. Research program in the field of databases for the next decade. Asilomar Report on Research Directions in the Field of Databases // Open Systems. 1999. - No. 1. -S. 61-68.

3. Brickell E.F., Odlizhko E.M. Cryptanalysis: a review of the latest results // Proceedings of the Institute of Electrical and Radio Electronics Engineers. 1988. - T. 76. - No. 5. - P. 75-93.

4. Gasanov E.E., Kudryavtsev V.B. Theory of information storage and retrieval. M.:FIZMATLIT, 2002.

5. Devitt D., Gray D. Parallel database systems: the future of highly efficient database systems // DBMS. 1995. - No. 2. -S. 8-31.

6. Diffie W. The first ten years of public key cryptography // Proceedings of the Institute of Electrical and Radio Electronics Engineers. 1988. - T. 76. - No. 5. - P. 54-74.

7. Knuth D. The art of computer programming. T. 1. Basic algorithms. M.: Mir, 1976.

8. Kuzminsky M., Volkov D. Modern supercomputers: state and prospects // Open Systems. 1995. - No. 6. -S. 33-40.

9. Kulba V.V., Kovalevsky S.S., Kosyachenko S.A., Sirotyuk V.O. Theoretical foundations designing optimal structures of distributed databases. M.: "Sinteg", 1999.

10. Levin V.K. Domestic supercomputers of the MVS family. http://parallel.ru/mvs/levin.html.

11. Lupanov O.B. On one approach to the synthesis of control systems - the principle of local coding // Problems of cybernetics. -M: Nauka, 1965.-Issue. 14.-S. 31-110.

13. Nigmatulin R.G. Complexity of Boolean functions. M.: Nauka, 1991.

14. Ozzu M., Valduriz P. Distributed and parallel database systems // DBMS. 1996. - No. 4. - P. 4-26.

15. Salomaa A. Public key cryptography. M.: Mir, 1996.-318 p.

16. Ulig D. On the synthesis of self-correcting circuits from functional elements with a small number of dependent elements // Mathematical notes. 1974. - No. 15. - P. 558-562.

17. Tsymbler M.L. Creation of system software for systems with massively parallel architecture // Dissertation for the degree of candidate of physical and mathematical sciences. Chelyabinsk State University, 2000.

18. Sholomov JI.A. On the implementation of underdetermined Boolean functions by circuits of functional elements // Problems of Cybernetics. -M.: Nauka, 1969. Issue. 21. - pp. 215-226.

19. Ambainis A. Upper Bound on the Communication Complexity of Private Information Retrieval // Proc. of 24th 1C ALP. Lecture Notes in Computer Science. - 1997. - Vol. 1256. - P. 401-407.

20. Andreev A.E., Clementi A.E.F., Penna P., Rolim J.D.P. Parallel Read Operations Without Memory Contention // Technical Report TR00-053 of the ECCC.-2000.

21. Andreev A.E., Clementi A.E.F., Rolim J.D.P. On the Parallel Computations of Boolean Functions on Unrelated Inputs // IV IEEE Israel Symposium on Theory of Computing and Systems (ISTCS"96). IEEE. -1996.-P. 155-161.

22. Asonov D. Private Information Retrieval an Overview And Current Trends // Proc. of ECDPvA Workshop, Informatik 2001. Vienna, 2001.

23. Beimel A., Ishai Y. Information-Theoretical Private Information Retrieval: A unified construction // Technical Report TR01-015 of the ECCC.-2001.

24. Chor V., Gilboa N. Computationally Private Information Retrieval // Proc. of 29th ACM STOC. 1997. - P. 304-313.

25. Chor V., Goldreich O., Kushilevitz E., Sudan M. Private Information Retrieval // Proc. of 36th IEEE FOCS. 1995. - P. 41-50.

26. Clementi A.E.F., Bongiovanni G., Penna P. A Note on Parallel Read Operations on Large Public Databases // Intern. Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE"00). Carleton Scientific Press, 2000. - P. 123-133.

27. Feder T., Kushilevitz E., Naor M. Ammortized Communication Complexity//Proc. of 32nd IEEE FOCS. 1991. - P. 239-248.

28. Galbiati G., Fisher M.J. On the Complexity of 2-Output Boolean Networks // Theoretical Computer Science 1981. - 16. - P. 177-185.

29. Gertner Y., Goldwasser S., Malkin T. A Random Server Model for Private Information Retrieval // Technical Report MIT-LCS-TR-715. 1998.

30. Ishai Y., Kushilevitz E. Improved Upper Bounds or Information-Theoretical Private Information Retrieval // Proc. of 31st STOC. 1999. -P. 79-88.

31. Itoh T. Efficient Private Information Retrieval // IEICE Transactions. 1999. - Vol. E82. - No. 1. - P. 11 -20.

32. Itoh T. On Lower Bounds for the Communication Complexity of Private Information Retrieval II IEICE Transactions. 2001. - Vol. E84. -No. 1.-P. 157-165.

33. Karchmer M., Raz R., Wigderson A. On Proving Super-Logarithmic Depth Lower Bounds via the Direct Sum in Communication Complexity // Proc. of 6th IEEE Struct., in Complexity Theory. 1991. -P. 299-304.

34. Karlin A., Upfal E. Parallel Hashing an Efficient Implementation of Shared Memory // Proc. ACM STOC. - 1986. - P. 160-168.

35. Karp R.M., Luby M., Meyer auf der Heide F. Efficient PRAM Simulation on a Distributed Memory Machine // Algoritmica. 1996. - 16. -P. 517-542.

36. Kruskal S.P., Rudolph L., Snir M. A Complexity Theory of Efficient Parallel Algorithms 11 Theoretical Computer Science 1990. - 71. -P. 95-132.

37. Kushilevitz E., Ostrovsky R. Replication is NOT Needed: Single-Database Computationally Private Information Retrieval // Proc. of 38th FOCS.- 1997.-P. 364-373.

38. Mehlhorn K., Vishkin U. Randomized and Deterministic Simulation of PRAM by Parallel Machines with Restricted Granularity of Parallel Memories // ACTA Informatica. 1984. - 21. - P. 339-374.

39. Nisan N., Rudich S., Saks M. Products and Help Bits in Decision Trees // Proc. of 35th IEEE FOCS. 1994. - P. 318-329.

40. Paul W.J. Realizing Boolean Functions on Disjoint Set of Variables // Theoretical Computer Science 1976. - 2. - P. 383-396.

41. Pfister G. Sizing Up Parallel Architectures // Database Programming & Design Online. 1998. - Vol. 11. - No. 5.

42. Pietracaprina A., Preparata F.P. A Practical Constructive Scheme for Deterministic Shared-Memory Access // Proc. of ACM SPAA. 1993. -P. 100-109.

43. Rivest R.L., Shamir A., ​​Adleman L. A Method For Obtaining Digital Signatures And Public Key Cryptosystems // Commun. ACM. 1978. -Vol. 21.-No. 2.-P. 120-126.

44. Stonebraker M. The Case for Shared Nothing // Database Engineering Bulletin. 1986. - Vol. 9. - No. 1. - P. 4-9.

45. Upfal E. Efficient Schemes for Parallel Communication // J. of the ACM. 1984.-31(3).-P. 507-517.

46. ​​Valduriez P. Parallel Database Systems: Open Problems and New Issues // Distributed and Parallel Databases. 1993. - Vol. 1. - No. 2. -P. 137-165.105

47. Wegener I. Switching Functions Whose Monotone Complexity in Nearly Quadratic // Theoretical Computer Science 1979. - No. 9. -P. 83-97.

48. Wegener I. The Complexity of Boolean Functions. Stuttgart, 1987.-469 p.

49. Zabrodin A.V., Levin V.K., Korneev V.V. The Massively Parallel Computer System MBC-100 // Proc. of the Int. Conf. on Parallel Computing Technologies (PaCT"95). Lecture Notes in Computer Science. 1995. - Vol. 964.-P. 342-356.