A peer‐to‐peer distributed selection algorithm for the Internet

Heretofore, it has been extremely expensive to install and use distributed databases. With the advent of Java, JDBC and other Internet technologies, it has become easy and inexpensive to connect multiple databases and form distributed databases, even where the various host computers run on different platforms. These types of databases can be used in many peer‐to‐peer applications which are now receiving much attention from researchers. Although it is easy to form a distributed database via Internet/intranet, effective sharing of information continues to be problematic. We need to pay more attention to the enabling algorithms, as dedicated links between computers are usually not available in peer‐to‐peer systems. The lack of dedicated links can cause poor performance, especially if the databases are connected via Internet. Discusses the problems of distributed database operation with reference to an example. Presents two statistical selection algorithms which are designed to select the jth smallest key from a very large file distributed over many computers. The objective of these algorithms is to minimise the number of communication messages necessary to the selection operation. One algorithm is for the intranet with broadcast/multicast facilities while the other is for Internet without broadcast/multicast facilities.