Chad Yoshikawa
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well
Ken Berman
Computing and Combinatorics, Springer Berlin Heidelberg, 12715 NE 81st PL (2009), pp. 368-377
Preview abstract
Maximal flows reach at least a 1/2 approximation of the maximum flow in client-server networks. By adding only 1 additional time round to any distributed maximal flow algorithm we show how this 1/2-approximation can be improved on bounded-degree networks. We call these modified maximal flows ‘locally fair’ since there is a measure of fairness prescribed to each client and server in the network. Let N = (U,V,E,b) represent a client-server network with clients U, servers V, network links E, and node capacities b, where we assume that each capacity is at least one unit. Let d(u) denote the b-weighted degree of any node u ∈ U ∪ V, Δ = max {d(u) | u ∈ U } and δ = min { d(v) | v ∈ V }. We show that a locally-fair maximal flow f achieves an approximation to the maximum flow of min{1,Δ2−δ2Δ2−δΔ−Δ }, and this result is sharp for any given integers δ and Δ. This results are of practical importance since local-fairness loosely models the steady-state behavior of TCP/IP and these types of degree-bounds often occur naturally (or are easy to enforce) in real client-server systems.
View details
Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well
Kenneth A. Berman
Lecture Notes in Computer Science, Springer Verlag, Tiergartenstraße 17, 69121 Heidelberg, Germany (2009), 368–377
Distributed Hash Queues: Architecture and Design
The lonely NATed node
Brent N. Chun
Amin Vahdat
Fred S. Annexstein
Kenneth A. Berman
ACM SIGOPS European Workshop (2004), pp. 36
WebOS: Operating System Services for Wide Area Applications
Amin Vahdat
Thomas E. Anderson
Michael Dahlin
E. Belani
David E. Culler
P. Eastham
HPDC (1998), pp. 52-63
