A randomized, O(log w)-depth 2-smoothing network
Ημερομηνία
2009Συγγραφέας
Mavronicolas, MariosSauerwald, T.
ISBN
978-1-60558-606-9Source
Annual ACM Symposium on Parallelism in Algorithms and Architectures21st Annual Symposium on Parallelism in Algorithms and Architectures, SPAA'09
Pages
178-187Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
A K-smoothing network is a distributed, low-contention data structure where tokens arrive arbitrarily on w input wires and reach w output wires via their completely asynchronous propagation through the network. The maximum discrepancy among the numbers of tokens arriving at the ouput wires, called smoothness, is at most K. It has been a long-standing open problem to construct a K-smoothing network with (i) optimal K, (ii) optimal Θ(lgw) depth (called small-depth), (iii) no use of the AKS sorting network, and (iv) no reliance on global initialization. In this work, we present a very simple, randomized network which meets all four desiderata: • It is the cascade of a reasonably small number (about 150) of copies of the simple block network [6] hence, it is small-depth and does not use the AKS sorting network. • It achieves smoothness K = 2 hence, it is optimal with respect to smoothness due to a recent improbability result about randomized, small-depth, 1-smoothing networks from [14]. • The network is randomized : each balancer is oriented independently and uniformly at random, thus requiring no global initialization. Cascaded before the Θ(lgw)-depth 2-counter network due to Klugerman and Plaxton [13], which does use the AKS sorting network as a building block, our 2-smoothing network yields a new, randomized counting network with depth Θ(lg w). The new network is a much simpler alternative to the classical, small-depth counting networks from [12, 13]. Copyright 2009 ACM.