Associative broadcast and the communication semantics of naming in concurrent systems
Bryan C Bayerdorffer · 1993
Much of the complexity of concurrent program design lies in the specification of patterns of communication: flows of information among objects (e.g. processes) expressed as functions of the global computation state. Underlying the communication mechanisms of every concurrent system is a naming system, which is used to specify the objects participating in each communication. We call those characteristics of naming systems that determine the patterns of communication that can be specified the communication semantics of naming systems. A more expressive naming system allows communication to be specified at a higher level of abstraction. The available communication abstractions are significant in the choice of an algorithm, in which specific patterns of communication are manifest, to solve a particular problem. Thus the choice or design of a naming system often significantly affects the design of concurrent programs. Yet naming systems have not been widely studied as independent components of concurrent systems. This has led to empirical design and inappropriate choices of naming systems, which hinder the specification of complex patterns of communication and constrain algorithm design, yielding awkward programs and inefficient executions. To simplify the use of naming systems in specifying communication, and to make more precise our understanding of their communication semantics, we adopt a twofold approach: The development of a formal taxonomy of naming systems, and the design of a specific naming system and communication primitive, called Associative Broadcast, that enable straightforward specification of complex communication patterns. The taxonomy defines a set of orthogonal properties that characterize the ability of naming systems to express fundamental patterns of communication. Naming systems are classified and ranked in a partially ordered hierarchy according to their properties. The hierarchy allows systematic comparison of naming systems, and selection of naming systems for the solution of problems requiring specific properties. Associative Broadcast resides at the top of the hierarchy, and allows the specification of a dynamic, descriptively named target set of objects as the destination of a message by defining names to be propositional expressions over sets of object attributes, and by using delayed resolution. We apply Associative Broadcast to obtain algorithms with desirable symmetry, robustness, concurrency, and efficiency properties for problems in the areas of distributed constraint reduction, database consistency in the presence of network partition failures, and virtual time synchronization.