Safe states in banker-like resource allocation problems (Q580968)

This paper is concerned with methods of describing the set of safe states in the Banker's problem. Using a Petri net model, formulas for this set (SAFE) and for its subset of minimal elements (MIN) are derived. Moreover, by partitioning MIN into subclasses such that elements of the same subclass differ only by a permutation of their components, an even smaller representation is given by a set SORT. Lower and upper bounds for the size of SORT are calculated. Since we give an algorithm which computes SORT in time linear to its size, these bounds are also applicable to the time complexity of computing SORT. Finally, some of the results are extended to the multidimensional Banker's problem with different currencies, whereas other properties are shown to be not extendible to this case.