@InProceedings{BrodskyPedersen02,
  title =        "{O}n the {C}omplexity of {B}uffer {A}llocation in {M}essage {P}assing {S}ystems",
  author=        "Brodsky,  Alex and Pedersen,  Jan Bækgaard and Wagner,  Alan",
  editor=        "Pascoe,  James S. and Loader,  Roger J. and Sunderam,  Vaidy S.",
  pages =        "79--96",
  booktitle=     "{C}ommunicating {P}rocess {A}rchitectures 2002",
  isbn=          "1 58603 268 2",
  year=          "2002",
  month=         "sep",
  abstract=      "In modern cluster systems message passing functionality is
     often off-loaded to the network interface card for
     efficiency reasons. However, this limits the amount of
     memory available for message buffers. Unfortunately, buffer
     insufficiency can cause an otherwise correct program to
     deadlock, or at least slow down. Hence, given a program
     trace from an execution in an unrestricted environment,
     determining the minimum number of buffers needed for a safe
     execution is an important problem. We present three related
     problems, all concerned with buffer allocation for safe and
     efficient execution. We prove intractability results for the
     first two problems and present a polynomial time algorithm
     for the third."
}