The performance of a parallel skyline solver is characterized analytically based on the average bandwidth, interprocessor communication speed, and the arithmetic processing speed. The formulas developed constitute a good predictor of the actual performance when the solver runs communication bound. This is the most interesting case because operation in this mode occurs for the largest processor configurations, and determines the ultimate performance of the solver. The analysis clearly shows the limiting effects of small-bandwidth coefficient matrices, and the relationship of processing speed and interprocessor communication bandwidth to the global performance. It is also shown that the largest potential gainsfor next generation machines will come from the availability of faster inter processor communication, rather than from enhanced arithmetic capability.