ASYNCHRONOUS DISCRETE EVENT SYSTEMS AND EMERGENCE OF COMPUTATIONAL CHAOS Sarit Barhen Jacob Barhen Vladimir Protopopescu Center for Engineering Science Advanced Research Oak Ridge National Laboratory Oak Ridge, TN 37831-6355 barhenj@ornl.gov Abstract. Asynchronous computing environments provide an ideal framework for conceptual modeling and simulation of large scale, distributed discrete event systems. Such environments may, however, exhibit an aperiodic oscillatory behavior referred to as “computational chaos”, which impedes the correct processing of quantities of interest. In this paper, we illustrate the emergence of computational chaos from fixed point and limit cycle attractors for a simple network model. In particular, the complete Lyapunov spectrum associated with the network dynamics is computed, and conditions that prevent its emergence are briefly discussed. Keywords: asynchronous computing, computational chaos, discrete event systems, Lyapunov spectrum. 1. INTRODUCTION Over the past twenty years, distributed computation has emerged and developed into a very exciting area. Two driving forces are behind this development. One is the desire within the scientific community to solve, in ever greater details, highly complex problems such as controlling the behavior of materials at the molecular level [1], modeling the climate, or weather prediction. The other arises from ever more rapid progress in electronic circuit integration at the nanoscale, production of faster and larger memories, and the availability of very high bandwidth communication networks. This has resulted in the development of massively parallel systems that enable the solution of such problems, and, in turn, is opening the possibility of addressing new problems, hitherto considered intractable. A distributed computing system is defined as a set of cooperating processes that evolve on multiprocessor architectures without a common memory [2]. Each processor and its local memory form a unit known as a node. Nodes are connected by physical communication channels (networks), which allow any two processors to ___________________________ Emory University, Atlanta, GA; also with the University of Tennessee (JB: Computer Science, VP: Mathematics), Knoxville, TN. exchange information (directly or indirectly) via message passing. The overarching paradigm of process cooperation to achieve a common goal has often been interpreted as requirement for processes to synchronize with each other. Since the inception of distributed computing (see [3] for historical references), considerable resources have been devoted to the development of efficient synchronization tools. Two approaches were followed. One consisted of maintaining a single process, the controller, which through message exchanges would coordinate the activities of the individual processes in the system. Such a “centralized control” solution clearly failed because (1) the precedence constraints implied by such message exchanges with the controller slowed down each process, and (2) if the node containing the controller failed, the entire system had to halt. The alternative approach, distributed control, installed a local process controller at each node. But, even here, local algorithms had to wait at predetermined points for predetermined messages to become available [4]. This gave rise to load imbalance across the system and often resulted in severe processor underutilization. The concept of asynchronous computing emerged from an attempt to overcome these constraints, by creating a distributed environment that enables uncoordinated, system-wide activity, while ultimately producing a correct solution, i.e., a solution that would have been obtained had synchronization been enforced. One area that may directly benefit from such a paradigm is the modeling and simulation of discrete event systems (DES). The DES paradigm deals with processes whose output is a dynamic function of time [5]. In a traditional discrete event specification (DEVS), one approximates the input, output, and state trajectories through piecewise constant segments defined over discrete time intervals of varying length. The accurate modeling of many realistic processes, however, had long been recognized to pose significant challenges to this conventional approach. The G-DEVS formalism [5] models the trajectories in terms of a piecewise polynomial representation, yielding higher accuracies in simulating continuous processes as .....