Communications of the ACM
Home/Magazine Archive/October 2020 (Vol. 63, No. 10)/Technical Perspective: Two for the Price of One/Full Text
Research highlights
Technical Perspective: Two for the Price of One
Sorting and transmitting data are two of the most fundamental tasks for which we have employed digital computers. The following paper proves a remarkable connection between how efficiently computers can perform these two tasks, connecting a longstanding question about the optimality of Merge Sort and another, very different, open problem in the study of network coding for data transmission.
Merge Sort was one of the first programs written for digital computers. Though, as a comparison-based in-memory algorithm, it has since been superseded by other sorting algorithms with better memory usage and by algorithms, such as radix sort, that are faster than any comparison-based algorithm, Merge Sort has remained important for sorting large amounts of data that require external storage. It can be modified to merge multiple streams at once and only requires the sequential access common for many storage media. A natural question to ask is: Is (multiway) Merge Sort an optimal choice for an external-memory sorting algorithm, or can we do much better? With the ubiquity of large datasets, this could have many practical applications.
To answer this question, one needs a suitable cost measure. Computers now have many levels of storage hierarchy and hence many levels of "external" memory; data is transfered between levels in blocks rather than individual data items. The cost of those transfers often dominates the cost of operations in "internal" memory. So, a suitable cost measure for external-memory algorithms is the number of transfers of blocks of size B into an internal memory of size M. In 1988, Aggarwal and Vitter, who developed the cost measure, showed that M/2B-way Merge Sort, which has transfers that mimic comparisons of an in-memory algorithm for input size n/B, is asymptotically optimal for comparison-based sorting algorithms, even for sorting instances that merely convert a matrix from row-major order to column-major order. The challenge they left is to determine whether this also holds for general external-memory sorting algorithms.
For in-memory algorithms, the gulf between the O(n log n) time for comparison-based algorithms and that for general algorithms is quite large: Radix sort, which uses indirect addressing, runs in O(n) time when the bit-length w of keys is O(log n). Also, as the paper notes, other in-memory algorithm that make of use of hashing operations on w-bit words can achieve nearly this level of performance for all values of w. It is plausible that a general O(n) time sorting algorithm is achievable for all w (an open question not considered here). However, the operations of indirect addressing and hashing seem to have no analogue for external-memory algorithms, which makes the optimality of Merge Sort plausible.
The following paper proves a remarkable connection between how efficiently computers can sort data and how efficiently they can transmit it.
Though the theory of coding for a single sender and receiver dates back to the earliest days of computing, network coding is a more recent invention that arises in the context of many sender-receiver pairs in a shared communication network. Ahlswede et al. showed that, in a directed network, it is possible to send data at a higher rate if nodes in the network actively combine the contents of the data they receive, rather than simply forwarding it as indivisible units. Their classic example is given in the network on the left below: s1 and s2 can simultaneously send streams of messages to t1 and t2 respectively if each in-degree 1 node sends its input along both output edges, node u passes on the XOR of its input messages to v, and nodes t1 and t2, in turn, compute the XOR of their input streams.
On the other hand, if the links are undirected, as in the network on the right, one can achieve the same rate without coding (or even using the (u,v) link): each si simply uses half the bandwidth of each of the other links to send xi to ti. (In this example, the links could be used by alternate message streams in consecutive time steps.) This solution is an example of a (fractional) multi-commodity flow on the network with sender-receiver pairs (s1, t1), (s2, t2), unit demands, and unit capacities. Such a flow reserves a fraction of the capacities on each edge for each sender-receiver pair. The undirected k-pairs conjecture, which originated in a 2004 paper of Li and Li, is that such a multi-commodity flow solution is always optimal, so there would never be an advantage to network coding in undirected networks. The surprising result is that if (a weak form of) this network coding conjecture is true, then multiway Merge Sort is asymptotically optimal for external-memory sorting!
Alternatively, it follows from the paper that a better algorithm than Merge Sort would have a second benefit: It could be used to design directed networks for which the rates achievable using network coding are arbitrarily higher than the rates possible without network coding, even with the direction restrictions on the network removed.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found