A model for distributed sorting on a local area network (LAN) is presented. This model, contrary to the conventional model, takes into account both local processing time and communication time. This model is intended to provide a framework within which the performances of various distributed sorting algorithms are analyzed and implemented on Ethernet-connected Sun workstations. The empirical results by and large agree with the predictions derivable from the model. They show that local processing, particularly sorting of local subfiles, dominates the whole process, as far as response time is concerned. All algorithms examined have similar asymptotic behavior for large files. For medium-sized files, the degree of communication parallelism has a great impact on algorithm performance.>

Various communication aspects of locally distributed database processing are studied, using some distributed sorting and distributed hash-based join algorithms as examples. The algorithms are implemented on diskless workstations connected by an Ethernet network to simulate a distributed main memory system environment. This experimental testbed is described. Raw communication performance data (i.e. memory-to-memory data transfer timing) are presented. The effects of the underlying distributed operating system and the speed of the processor on the communication performance are shown. Two distributed sorting algorithms are used as examples to study the issue of concurrent transmissions of messages. Distributed hash join is used as a case study for communication/local-processing tradeoff. The idea of load sharing among a number of sites to speed up the join operation is introduced.>