@Article{durand:edge-coloring,
  author = {Dannie Durand and Ravi Jain and David Tseytlin},
  title = {Parallel I/O scheduling using randomized, distributed edge coloring
  algorithms.},
  journal = {Journal of Parallel and Distributed Computing},
  year = {2003},
  month = {June},
  volume = {63},
  number = {6},
  pages = {611--618},
  institution = {Telcordia Technol, Appl Res, 445 South St, Morristown, NJ
  07960 USA; Telcordia Technol, Appl Res, Morristown, NJ 07960 USA},
  publisher = {Academic Press, 2003},
  copyright = {(c)2004 IEE; Institute for Scientific Information, Inc.},
  URL = {http://dx.doi.org/10.1016/S0743-7315(03)00015-7},
  keywords = {randomized edge coloring, scheduling algorithms, bipartite
  graphs, parallel I/O, pario-bib},
  abstract = {A growing imbalance in CPU (central processing unit) and I/O
  (input/output) speeds has led to a communications bottleneck in distributed
  architectures, especially for data intensive applications such as multimedia
  information systems, databases, and grand challenge problems. Our solution is
  to schedule parallel I/O operations explicitly. We present a class of
  decentralized scheduling algorithms that eliminate contention for I/O ports
  while maintaining an efficient use of bandwidth. These algorithms based on
  edge coloring and matching of bipartite graphs, rely upon simple heuristics
  to obtain shorter schedules. We use simulation to evaluate the ability of our
  algorithms to obtain near optimal solutions in a distributed context, and
  compare our work with that of other researchers. Our results show that our
  algorithms produce schedules within 5% of the optimal schedule, a substantial
  improvement over existing algorithms. (20 refs.)}
}