Paper Details

%T On the Complexity of Buffer Allocation in Message Passing Systems
%A Alex Brodsky, Jan Bækgaard Pedersen, Alan Wagner
%E James S. Pascoe, Roger J. Loader, Vaidy S. Sunderam
%B Communicating Process Architectures 2002
%X 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.

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.