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
The lonely NATed node
Brent N. Chun
Amin Vahdat
Fred S. Annexstein
Kenneth A. Berman
ACM SIGOPS European Workshop (2004), pp. 36
Distributed Hash Queues: Architecture and Design
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
