%T On the Complexity of Buffer Allocation in Message Passing Systems
%A Alex Brodsky, Jan Baekgaard 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.
Pages © WoTUG, or the indicated author. All Rights Reserved.
Comments on these web pages should be addressed to: www at wotug.org