  Message passing programs commonly use buffers to avoid unnecessary
synchronizations and to improve performance by overlapping communication with
computation. Unfortunately, using buffers makes the program no longer portable,
potentially unable to complete on systems without a sufficient number of
buffers. Effective buffer use entails that the minimum number needed for a safe
execution be allocated.
  We explore a variety of problems related to buffer allocation for safe and
efficient execution of message passing programs. We show that determining the
minimum number of buffers or verifying a buffer assignment are intractable
problems. However, we give a polynomial time algorithm to determine the minimum
number of buffers needed to allow for asynchronous execution. We extend these
results to several different buffering schemes, which in some cases make the
problems tractable.
