We present and evaluate our distributed and self-adaptive vehicle routing guidance approach, termed BeeJamA, which provides drivers safely with routing directions well before each intersection. Our approach is based on a multiagent system, which is inspired by the honey bee foraging behavior. It relies on a distributed vehicle-to-infrastructure architecture. On the basis of microscopic traffic simulations under varying penetration rates, we show that BeeJamA outperforms dynamic shortest path algorithms with respect to average (global) travel times and regarding congestion avoidance.

We present and evaluate our adaptive and distributed vehicle routing approach, termed BeeJamA, which provides drivers safely with routing directions well before each intersection. Our approach is based on a multi-agent system which is inspired by the honey bee behavior and relies on a V2I architecture. We report on our extensive simulation experiments verifying for very large systems that BeeJamA substantially outperforms all A*-based algorithms relying on global information systems, in particular under all degrees of penetration rates as well as considering reactive flexibility and easy scalability.

Commercial transport planning as well as individual intra-city or inter-city traffic in densely populated regions, both in Europe and the US, increasingly suffer from congestion problems, to an extent which e.g. affects predictable transport planning substantially (except - so far - for overnight tours). Due to the highly dynamic character of congestion forming and dissolving, no static approach like shortest path finding, applied globally or individually in car navigators, is adequate here: Its use even makes things worse as can be frequently observed. In this paper we present a completely decentralized multi-agent approach (termed BeeJamA) on multiple layers where car or truck routing are handled through algorithms adapted from the BeeHive algorithms which in turn have been derived from honey bee behavior. We report on extensive distributed simulation experiments in the BeeJamA project which demonstrate a very substantial improvement over traditional congestion handling.

Establishing clean or renewable energy sources involves the problem of adequate management for the networked power sources, in particular since producers are at the same time also consumers, and vice versa. We describe the first phases of the joint R&D project DEZENT between the School of Computer Science and the College of Electrical Engineering at the University of Dortmund, devoted to decentralized and adaptive electric power management through a distributed real-time multi-agent architecture. Unpredictable consumer requests or producer problems, under distributed control or local autonomy will be the major novelty. We present a distributed real-time negotiation algorithm involving agents on different levels of negotiation, on behalf of producers and consumers of electric energy. Despite the lack of global overview we are able to prove that in our model no coalition of malicious users could take advantage of extreme situations like arising from an abundance as much as from any (artificial) shortage of electric power that are typical problems in "free" or deregulated markets. Our multi-agent system exhibits a very high robustness against power failures compared to centrally controlled architectures. In extensive experiments we demonstrate how, in realistic settings of the German power system structure, the novel algorithms can cope with unforeseen needs and production specifics in a very flexible and adaptive way, taking care of most of the potentially hard deadlines already on the local group level (corresponding to a small subdivision). We further demonstrate that under our decentralized approach customers pay less than under any conventional (global) management policy or structure

For a just-in-time production scheme in large manufacturing systems we describe a considerable methodological extension into an integrated automated manufacturing system that is supported by a distributed real-time computer system. This allows for higher flexibility in demand fluctuation as well as for a larger variety of products. At the same time better adaptability of transportation planning and transportation cost reduction are achieved through their integration. For this integrated scheduling we will present new bidding algorithms. Eventually, in an extension of the presented scheduling algorithms, novel fault tolerant strategies are included for overcoming or neutralizing the effect of transient machine failures. These are handled by cooperating local schedulers and managed to guarantee a minimal damage of schedules and its propagation, in the presence of failures. Through their integration into the production and transportation scheduling the advantages of the just-in-time approach (no storage costs) are preserved in principle while a near-optimal way for the affected jobs is found to meet their deadlines. The results of our extensive simulation experiments for a real production scenario are also discussed.

In this paper we present BeeAdHoc, a new routing algorithm for energy efficient routing in mobile ad hoc networks. The algorithm is inspired by the foraging principles of honey bees. The algorithm mainly utilizes two types of agents, scouts and foragers, for doing routing in mobile ad hoc networks. BeeAdHoc is a reactive source routing algorithm and it consumes less energy as compared to existing state-of-the-art routing algorithms because it utilizes less control packets to do routing. The results of our extensive simulation experiments show that BeeAdHoc consumes significantly less energy as compared to DSR, AODV, and DSDV, which are state-of-the-art routing algorithms, without making any compromise on traditional performance metrics (packet delivery ratio, delay and throughput).

In this paper we present an energy efficient routing algorithm, BeeAdHoc, which is inspired from foraging principles of honey bees. The bee behavior was instrumental in designing efficient mobile agents, scouts and foragers, for routing in mobile ad-hoc networks. We did extensive simulations to verify that BeeAdHoc consumes significantly less wireless network card energy as compared to DSR, AODV, and DSDV, which are existing state-of-the-art routing algorithms, but without compromising traditional performance metrics, packet delivery ratio and delay.

In the era of Ubiquitous Computing and world-wide data transfer mobility, as an innovative aspect of professional activities, imposes new andcomplex problems of mobile and distributed access to information,services, and on--line negotiations for this purpose. This paperrestricts itself to presenting a distributed and location--dependentRBAC approach which is multi--layered. Also an adapted form ofAdministration Nets is presented whichallows the scheduling of distributed on--line processes for automatedlocation--dependent negotiating procedures, and for provingtheir correctness. Examples are discussed in some detail.

In large organizations the administration of access privileges (such as the assignment of access rights to a user in a particular role) is handled cooperatively through distributed administrators in various different capacities. A quorum may be necessary, or a veto may be possible for such a decision. In this paper, we present two major contributions: We develop a role-based access control (RBAC) approach for specifying distributed administration requirements, and procedures between administrators, or administration teams, extending earlier work on distributed (modular) authorization. While a comprehensive specification in such a language is conceivable it would be quite tedious to evaluate, or analyze, their operational aspects and properties in practice. For this reason we create a new class of extended Petri Nets called Administration Nets (Adm-Nets) such that any RBAC specification of (cooperative) administration requirements (given in terms of predicate logic formulas) can be embedded into an Adm-Net. This net behaves within the constraints specified by the logical formulas, and at the same time, it explicitly exhibits all needed operational details such as allowing for an efficient and comprehensive formal analysis of administrative behavior. We introduce the new concepts and illustrate their use in several examples. While Adm-Nets are much more refined and (behaviorally) explicit than workflow systems our work provides for a constructive step towards novel workflow management tools as well. We demonstrate the usefulness of Adm-Nets by modeling typical examples of administration processes concerned with sets of distributed authorization rules.

In large organizations the administration of access privileges (such as the assignment of an access right to a user in a particular role) is handled cooperatively through distributed administrators in various different capacities. A quorum may be necessary, or a veto may be possible for such a decision. In this paper we present two major contributions: We develop a Role-Based Access Control (RBAC) approach for specifying distributed administration requirements, and procedures between administrators, or administration teams, extending earlier work on distributed (modular) authorization. While a comprehensive specification in such a language is conceivable it would be quite tedious to evaluate, or analyze, their operational aspects and properties in practice. For this reason we create a new class of extended Petri Nets called Administration Nets such that any RBAC specification of (cooperative) administration requirements (given in terms of predicate logic formulas) can be embedded into an Administration Net. This net behaves within the constraints specified by the logical formulas, and at the same time, it explicitly exhibits all needed operational details such as to allow for an efficient and comprehensive formal analysis of administrative behavior. We introduce the new concepts and illustrate their use in several examples. While Administration Nets are much more refined and (behaviorally) explicit than work flow systems our work provides for a constructive step towards novel work-flow management tools as well.

Read/write conflicts, be it on the task or transaction level, may have harmful consequences for the real-time performance, particularly in distributed systems. Under safety-critical constraints (where task arrival is unpredictable) such conflicts would then impose an unpredictable overhead. Static solutions of conflict handling by utilizing shadow copies have been suggested, even under non-preemptive object access (where shadow copies are almost useless). This paper reports on research concerning adaptive preemptive methods for handling record-based read/write access to objects providing shadow copies. We present a new refined task and resource scheduling method based on measures that take task or transaction criticality into account. A potential advantage with shadow copies stems from the fact that shadow copies are still available to readers once a writer has been preempted whereas otherwise all scheduled (conflicting) readers have to wait until the writer has been finished (unless the write action is rolled back). In our model, readers that are preempted through writers (or writers that are preempted through readers) need not acquire their locks anew after preemption thus allowing for a higher scheduling flexibility and choice through keeping their locks. We study the trade-off between the higher flexibility of preemptive shadow copy models and the higher overhead they incur, due to refreshing shadow copies in due time.

There are three major drawbacks of a centralized security administration in distributed systems: It creates a bottleneck for request handling, it tends to enforce homogeneous security structures in heterogeneous user groups and organizations, and it is a weak point in terms of security attacks, reliability, and fault tolerance. In this paper we introduce a distributed authorization concept which is based on a modular authorization language for supporting cooperatingdistributed authorization teams. These teams are partially ordered into a hierarchy in that they inherit authorization rules from higher order teams but still exercise their autonomy by (dynamically) setting local rules that serve the special local needs in distributed organizations.Conflictsbetween between rules inherited from different higher ranking sources, orviolationsof higher order rules through local rules would be detected, on the logical level or through request evaluation, as contradictions or contradicting results, respectively. Conflict resolution mechanisms are presented, and examples are discussed extensively.

Internal clock synchronization has been investigated, or employed for quite a number of years, under the requirement of good upper bounds for the deviation, or accuracy, between a predefined master node M and slaves S1, S2, etc. It has been tacitly assumed that the accuracy range between slaves SI and S2 was just the same as for the master/slave. In extensive experimental studies of unicast based protocols, however, we found a significantly worse accuracy between the slave nodes. Except for the asymmetry as such (which results in different communication conditions in a logically peer communication structure (like in our MELODY system)), this is particularly undesirable, if not harmful, if one wants to dynamically shift the master role between nodes, for the purpose of achieving fault tolerance. Nearly all previous internal clock synchronization algorithms with high accuracy are based on unicast messages (including our own efforts). We present two new broadcast protocols, the Real-Time Duplex Protocol (RTDP) and the Real-Time Burst Protocol (RTBP). With these we achieve a homogeneous clock deviation structure in that the accuracy between master and slave is the same as between two slaves. Also, despite the fact that the broadcast delay is slightly higher than the unicast transmission time, the accuracy is even better than for a master/slave synchronization under unicast methods. We explain how both algorithms serve both real time and fault tolerance needs. We report on our experimental findings.

Safety-critical systems typically operate in unpredictable environments. Requirements for safety and reliability are in conflict with those for real-time responsiveness. Due to unpredictable environmental needs there is no static trade-off between measures to accommodate the conflicting objectives. Instead every feature or operating system service has to be adaptive. The distributed operating system MELODY was developed for supporting safety-critical applications under such constraints. In earlier phases real-time monitoring features like file monitoring and integration control had been implemented. This paper focuses on distributed task monitoring. In order to as early as possible abort task instances which cannot meet their deadline sub-deadlines for their location, allocation, locking phases are derived. These are used for creating three different monitoring models in which task instances would be aborted whenever they are about to miss the sub-deadline corresponding to the model. Extensive distributed experiments are reported in which a variety of refined models are compared to a Base model. Despite the considerable overhead for task monitoring the results of employing the distributed task monitors are very favorable, with respect to minimizing the total number of deadline failures as well as regarding survivability.

Safety-critical systems typically operate in unpredictable environments, Requirements for safety and reliability are in conflict with those for real-time responsiveness. Due to environmental needs there is no static trade-off between measures to accommodate the conflicting objectives, Instead, every feature or operating system service must be adaptive. MELODY was developed for supporting safety-critical applications under such constraints. This paper gives a brief survey of the different MELODY development phases by utilizing our heuristic design and evaluation methodology, Incremental Experimentation. A particular emphasis is laid on our novel adaptive concept of distributed task monitoring, plus its evaluation, regarding the total number of deadline failures as well as survivability.

Real-time and embedded computing systems pervade all areas of our lives. The characteristics of the eld and its development so far are summarised. As demands for the functionality and dependability of complex real-time systems continue to grow, many challenging problems encountered in their design and development need to be solved. Some of them are addressed in this panel, viz., synchronisation in distributed transaction processing, integration of heterogeneous systems with di erent real-time properties, and application of dynamical principles to provide fault-tolerance in real-

The distributed operating system MELODY, was developed for supporting safety critical applications in unpredictable environments. Requirements for safety and reliability have to be accommodated, as well as things like real time responsiveness. All features have to be adaptive. While developing MELODY through a number of different phases, we created a heuristic experimental, performance-relate methodology termed Incremental experimentation. Based on this novel system building approach as well as on preliminary simulation studies for non critical tasks, the focus of the paper is on different policies of file server and task scheduler integration. This is a central issue in the MELODY concept due to the specific problems of distributed file management (where copies of different "quality" are dynamically distributed over the sites). We establish three integration policies: the Periodic, Joined, and Adjusted models, and we comparatively evaluate them in distributed environments. In particular the significant results for critical task profiles are presented and discussed.

As part of the DRAGON SLAYER project, the adaptive and reliable distributed file system MELODY has emerged for supporting hard real-time applications in unpredictable environments. In MELODY, the time criticality of tasks and their sensitivity with respect to the latest file information are explicitly used for novel, flexible task scheduling algorithms and file replication management policies, featuring dynamic file replication and relocation of file copies as well as offering file versions of varying recency. The achieved adaptability far outweighs the additional overhead in comparison to simpler models, and enhances both reliability and real-time responsiveness for file access. Both the development of the model and the experimental analysis at the various stages were done in an incremental manner. This was necessary in order to cope with the complexity of the problems resulting from conflicting requirements and dynamic trade-offs (e.g. real-time responsiveness vs. reliability). As the next incremental model extension, and as the major contribution of this paper, a series of integration policies are developed for task and resource scheduling, after redefining the role and order of task and resource scheduling: the periodic and dynamic models (and combinations thereof) are used to invoke the task scheduler for a fixed interval of time. All of these policies compare very convincingly against the "classical" model where the task scheduler only schedules tasks after their resources have been allocated. The results are discussed.

The relevance of formal methods for practical software system design is discussed. Prominent representatives of formal approaches present their findings and experience about the use and the usefulness of formal methods. It has been proposed that all programmers would be more productive and produce higher quality products if they would learn two things: predicate calculus; and program correctness (including formal program development). It is argued that the complexity, pervasiveness, and critical nature of modern and future computer systems makes it imperative that such systems be engineered for reliability and maintainability. Formal methods constitute an extremely promising approach to the design of reliable systems. The schedulability aspect of real-time system development is discussed. In general, formal methods should be preferred over other less formal methods since they can provide much better and stronger guarantees on real-time system performance.>

An approach to automated timing analysis of distributed real-time programs is presented. The method is based on the static analysis of the task system and generation of global operation (GO) paths for which the timing analysis is applied. It is shown that a closed form solution algorithm is NP-complete. In order to more efficiently determine maximum waiting times for tasks sharing resources, even for large programs with many tasks, a reduced flow graph problem is defined by neglecting the differences in the execution times of the local operations. A solution for this problem gives an upper bound for the original analysis problem. A conjecture that the reduced problem is NP-complete even for two tasks is disproved by giving a formally correct polynomial time solution algorithm. The maximum number of steps for computing the maximum waiting for the reduced problem is linear with respect to the numbers of task's server requests.>

A novel approach to automating test data generation for distributed programs is presented. The approach is based on actual execution of the program under test, a run-time scheduler, function minimization methods, and dynamic dataflow analysis. Test data are developed for the program using actual values of the input variables. When the program is executed, the program execution flow is monitored. If during program execution an undesirable execution flow is observed then function minimization search algorithms are used to automatically locate the values of input variables for which the selected path is traversed. In addition, dynamic dataflow analysis is used to determine those input variables responsible for the undesirable program behavior, which can lead to significant speed-up of the search process.>

The authors describe the file management system of DRAGON SLAYER, a distributed operating system which provides transparent resource sharing in a heterogeneous local area network with completely decentralized control. Users are able to use any of the system files for which they have authorization, without regard to the individual characteristics of the computers on which the files reside or the physical locations of the users and files. In addition, files can be dynamically fragmented, and the fragments can be replicated and relocated dynamically. Copies are kept mutually consistent while all file operations work either transparently on the whole file or on specific fragments. The DRAGON SLAYER resource management supporting these file system operations is presented. Beyond the obvious advantages of file access reliability and flexibility, the authors present simulation results proving the superior performance of this file system as compared with conventional distributed file systems with non-fragmented files.>

An experimental distributed system based on an integrated system design was built that incorporates user-level or environmental application requirements into the design issues of the distributed operating system Dragon Slayer. The key for making use of the Dragon Slayer services, in supporting applications requesting a high amount of reliability under completely decentralized control, is the definition of the concept of distributed objects. These were used as the basis for a paradigm of distributed computing that allows users to neglect the distribution of services and responses. How distributed objects are managed in Dragon Slayer is outlined. The distributed objects are logical objects which may be partitioned. The parts or fractions may be distributed over several nodes. They may even exist in multiple copies or version. In order to prepare the ground for requirements regarding distributed object management, a taxonomy of object-oriented approaches and their methods of managing distributed object operations is given. A set of necessary conditions for the design of distributed operating system services that are to support such management methods under completely decentralized control is determined.>

Described are the major features of the completely decentralized adaptive file system Melody, which runs on top of the distributed operating system Dragon Slayer. A definition of all major design requirements is presented, along with a heuristic algorithm for resource scheduling which allows for replicating, relocating, or deleting file copies in a local area network. At every site a local task scheduler tries to schedule the arriving critical tasks such that no deadlines are missed, based on the availability of resources at this site. Depending on the task-deadline failure history and file-access request history at each node, file copies may be relocated, replicated to other sites, or deleted. Such copies may also assume a different status (public or private) depending on how recent their information is. Only public copies are maintained under a strong concurrency-control protocol. The idea is to maintain optimal distribution of file copies in the network regarding reliability and real-time responsiveness of the system. Experiments performed to analyze Melody's capability of minimizing deadline failures of time-critical tasks were compared to structurally simpler file-system models. A report is presented on the distributed simulation results which show Melody's superior performance and its built-in sensitivity to changes in the environment.>

The authors analyze current and future needs in building adaptive real-time systems and formulate a series of design requirements for their hardware/interconnection, operating system, and application levels that could be satisfied together only in an integrated system design. They describe the major features of the corresponding model. On the operating-system level, novel services are rendered by their own file system, Dragon Slayer. The file system, in order to both meet real-time constraints and provide for high availability in a hazardous environment, allows for replicating, relocating, or deleting of file copies. A distributed implementation of the integrated system design model is currently being completed in order to serve as a distributed real-time testbed. The authors also report on a sensitivity study that shows how promptly the model file system reacts to changing environmental situations (changing request patterns).>