Coins, weights and contention in balancing networks

Abstract

A novel combinatorial approach to wait-free loadbalancing, counting, synchronization and buffer management in distributed systems, was recently introduced by Aspnes, Herlihy and Shavit. They proposed balancing and counting networks, networks that attempt to equalize their input elements (tokens) on their output wires, regardless of the arrival time and pattern. Here we address three new basic notions regarding balancing networks: (1) randomized design techniques, (2) balancing the weights of elements (rather than their count), and (3) achieving bounded-event analysis of contention, namely contention which is measured after a relatively small bound on the system's operation time (events). We present both new optimal constructions and tools for analysis. Our goal is to construct simple, practical networks with both depth and latency small. We show that randomization is quite useful to this end. We introduce randomizing balancers and use them to construct a simple butterfly-based network of depth log N (plus a small error term) which balances the tokens on its output wires to within one or two with probability 1-1/superpoly(N) With simple modifications, this holds even for adversaries who see all or part of the past network coin-flips. Also, we present optimal depth deterministic and randomized counting networks. In many applications, the tokens (e.g., jobs) may have weights (e.g., loads). To handle this, we define deterministic and randomized weight balancers. We exhibit a network that balances weights on its output wires to within M log log N where M is the largest (possibly unknown) weight of a token to pass through the network. These on-line "bin-packing" networks may be used for memory/load balancing, and more generally for weighted producer/consumer buffers in shared-memory MIMD machines or other multi-server queueing systems. Besides small depth, fast asynchronous processing requires also small contention of processors within the system's data structures. Dwork, Herlihy and Waarts proposed amortizing the contention over a number of tokens. Our technique here enables calculating contention/latency in all known deterministic or randomizing balancing networks in a bounded-event fashion: the bounds apply after a small number of tokens have passed through every network element. The original contention notion was only asymptotic (i.e., as achievable eventually).