The scheduling and organization of periodic associative computation: Efficient networks

This paper characterizes the efficient decentralized networks for calculating the associative aggregate of cohorts of data of a fixed size that arrive periodically. Radner (1993) proposed this problem of periodic parallel associative computation as a model of the ongoing information processing and communication by the administrative staff of a large organization. For a simpler model in which the organization processes a single cohort of data – which is equivalent to the periodic model when the agents are paid only when busy – he found that the efficient networks are hierarchical but quite irregular, even though the computation problem and technology are each symmetric. In the periodic model in which managers are paid even when idle, it becomes important to minimize idle time when scheduling managers to processing tasks. Such scheduling appears more difficult when each problem is processed by an irregular hierarchy, which suggest that hierarchies might be more regular in the periodic model. However, we show that in a class of efficient networks for periodic computation that spans the efficiency frontier, the processing of each cohort is similar to the efficient processing of a single cohort, and the overall organizational structure is not even hierarchical. Received: 15 October 1994 / Accepted: 6 March 1997