Next:
Acknowledgments
Up:
Automatic Generation of an
Previous:
Automatic Generation of an
Contents
1. Introduction
1.1 Motivation
1.1.1 First Position: Standards in Open Distributed Systems
1.1.2 Second Position: Mobile Agent Systems
1.1.3 Third Position: Interconnected Embedded Systems
1.2 Thesis
1.2.1 Thesis Goal
1.2.2 Methodology
1.2.3 Case & Thesis Statement: Concurrency Conflicts
1.3 A Preliminary Example
1.3.1 What is an Interface ?
1.3.2 A Syntactical Conflict
1.3.3 Conflicting Semantics
1.3.4 What is a Conflict ?
1.3.5 What Are the Requirements ?
1.4 Structure of Our Work
1.4.1 Adaptors
1.4.2 The Enforce-Action Module
1.4.3 The Liveness Module
1.4.4 The Concurrency Module
1.4.5 Formal Documentation
1.5 Scientific Approach
1.5.1 Publications
1.6 Related Work
1.6.1 Similar Approaches
1.6.2 Alternative Approaches
1.7 Roadmap
1.7.1 Chronology
1.7.2 Storyline
1.7.3 Conventions
I. Preliminaries
2. Event Based Models for Distributed Systems
2.1 History
2.1.1 Borg
2.1.2 SEESCOA
2.2 The Model
2.3 Naming & Finding Services
2.4 Connecting & Deployment
2.5 Communication
2.5.1 Sending and Receiving Messages
2.5.2 Message Representation
2.5.3 Syntactical Annotation
2.5.4 Motivation
2.6 Sessions
2.6.1 Non-Blocking
2.6.2 Session Tracking
2.7 Concurrency
2.8 Writing Adaptors
2.8.1 Flow Control by Means of Adaptors
2.8.2 Placing the control flow regulators at runtime
2.9 Summary
3. Describing Interfaces by means of Petri-nets
3.1 Introduction
3.2 Formal Interface Descriptions
3.3 Petri-Nets
3.3.1 Related work
3.4 Colored Petri-Nets
3.4.1 Informal Discussion
3.4.2 Formal Definition
3.4.3 Simple Petri-Nets
3.4.4 A Note on Implementation
3.5 The Expression Language
3.6 The Language used to Express Petri-Nets
3.6.1 The Basic Language
3.6.2 Linking Components Petri-Nets
3.6.3 In/Out Transitions
3.7 Two More Complex Examples
3.7.1 Interface Description of a Blocking Layered Concurrency Strategy
3.7.2 Description of a Non-blocking Rollback-able Concurrency Strategy
3.8 The Do-Not 's of Interface Petri-Net Descriptions
3.9 Defining Conflicts
3.10 A Word on Formal Analysis of Petri-Nets
3.11 Summary
4. Learning Algorithm
4.1 A World of Variations
4.2 Mapping our Problem onto a Learning Algorithm
4.3 Genetic Algorithms
4.3.1 Genetic Algorithms as Representational Testers
4.3.2 Classifier Systems
4.4 Reinforcement learning
4.4.1 A Typical Reinforcement Learner
4.4.2 Episodic versus Continual tasks
4.4.3 Elements of a Reinforcement Learning Problem
4.4.4 Markov Decision Processes
4.4.5 The Value Function & Policy
4.4.6 Exploration versus Exploitation
4.5 Summary
II. The Case: Conflicting Concurrency Interfaces
5. Introducing the Case: Concurrent Systems
5.1 Introduction
5.2 Concurrency
5.3 The Whiteboard Case
5.3.1 The Interface
5.3.2 The Horizontally Moving Dot Actor
5.3.3 The Moving Line Actor
5.3.4 The Floodfill Actor
5.4 Race Conditions
5.4.1 A Selection of Race Conditions
5.4.2 Different Solutions towards Race Conditions
5.5 Centralized Atomic Operations
5.6 Non-Waiting Atomic Operations & Starvation
5.6.1 Non-Reentrant Synchronization Semantics
5.6.2 Reentrant Synchronization Semantics
5.6.3 Discussion
5.7 Waiting Atomic Operations & Deadlocks
5.7.1 Non-Reentrant Synchronization Semantics
5.7.2 Reentrant Synchronization Semantics
5.7.3 Discussion
5.7.4 Different Solutions to Deadlocks
5.8 Locking Resources & Livelocks
5.8.1 Granular Operations: Locks
5.8.2 Problems of Fine Grained Locks: Livelocks
5.8.3 Solutions to Livelocks
5.9 Transactions & Partial Failure
5.10 Peer to Peer Concurrency & Distributed Transactions
5.11 Commonalities & Variabilities
5.12 Summary
6. Conflicting Interfaces
6.1 The Nature of Interface Conflicts
6.1.1 Interface Usage is of Vital Importance
6.1.2 Not All Conflicts can be Mediated
6.1.3 Adaptors Need to Cooperate
6.1.4 Brief Summary
6.2 A Selection of Interface Conflicts
6.2.1 Selecting a Set of Interface Conflicts
6.2.2 Designing a Representative Subset of Conflicts
6.3 One-One Conflicts on One Variability
6.3.1 Syntax
6.3.2 Reentrancy
6.3.3 Control Flow
6.3.4 Granularity
6.3.5 Layering
6.3.6 Transition
6.4 One-Multi Conflicts
6.4.1 The Empty Server 1-x Conflict
6.4.2 An Up-scale 1-x Granularity Conflict
6.4.3 A Down-scale 1-x Granularity Conflict
6.4.4 A Non Waiting Server 1-x Conflict
6.5 Multi-Multi Conflicts
6.6 Summary
III. Solution
7. Our Approach
7.1 Assumptions about Petri-Nets and Components
7.2 Requirements for the Adaptor
7.2.1 The No-Conflict Requirement
7.2.2 The No-Races Requirement
7.2.3 The Liveness Requirement
7.3 Pure Approaches
7.3.1 Automatic Deduction of an Adaptor
7.3.2 Applicability of Pure Learning Algorithms
7.4 Modularizing The Adaptor
7.4.1 An Enforce-Action Module
7.4.2 A Liveness Module
7.4.3 A Concurrency Module
7.5 Argumentation of a Correct Construction
7.5.1 Satisfying the No-Conflict Requirement
7.5.2 Satisfying the No-Races Requirement
7.5.3 Satisfying the Liveness Requirement
7.6 Summary
8. Module 1: The Enforce-Action Module
8.1 Introduction
8.2 Formal Analysis
8.3 Converting a Petri-Net Description to Prolog Rules
8.4 Predicting the Future & Deducing the Past
8.5 Reachability Analysis: Forward and Backward Tracing
8.6 Discussion
8.6.1 Implementation Notes & Performance
8.6.2 Verifying Places versus Verifying Enabled Transitions
8.7 Summary
9. Module 2: The Liveness Module
9.1 A Petri-Net Representation
9.1.1 Requirements for a Petri-net Representation
9.1.2 Runtime Creating of Transitions
9.2 Runtime Feedback
9.2.1 Check-pointing the Component's Source
9.2.2 Correlation
9.3 Reinforcement Learning
9.3.1 A Markov Decision Process
9.3.2 -learning
9.3.3 State Space Compaction
9.3.4 Structural Aspects of this Compaction
9.4 Discussion
9.4.1 Experiments
9.4.2 Bypassing a Concurrency Strategy
9.4.3 Comparison with Classifier Systems and the BBA
9.5 Summary
10. Module 3: The Concurrency Module
10.1 Resources
10.2 The Requirement: What is a Race-Condition ?
10.3 Control
10.4 Choice-Points
10.5 Avoiding Race Conditions
10.5.1 Handling Incoming Requests
10.5.2 Handling Incoming Requests
10.6 Discussion
10.6.1 Server Requirements
10.6.2 Unmanaged Concurrency
10.6.3 Livelocks
10.6.4 Deadlocks
10.6.5 Implicit Requirements
10.6.6 Virtual Resources
10.6.7 Implementation Issues
10.7 Summary
IV. Validation
11. Experiments
11.1 Introduction
11.2 Experimental Setup
11.3 Measuring Technique
11.4 Experiment 1: A Scheme Representation
11.4.1 Description
11.4.2 Results
11.5 Experiment 2: Classifier System Representation
11.5.1 Description
11.5.2 Results
11.6 Experiment 3: A Petri-Net Representation
11.6.1 Description
11.6.2 Results
11.7 Experiment 4: Bypassing a Provided Concurrency Strategy
11.8 Experiment 5: Liveness and the Bucket Brigade
11.9 Experiment 6: The Liveness Module and a Petri-net Representation
11.10 Implementation
11.10.1 The Component System
11.10.2 The Petri-net Evaluator Code
11.10.3 The Adaptor Code
11.10.4 The Actor Components
11.11 Summary
12. Discussion
12.1 Introduction
12.2 Observations about the Concurrency Adaptors
12.3 Concurrency Strategies are Very Simple
12.4 Technical Observations
12.4.1 Non-Incremental Approach: The Problem of Late Joiners
12.4.2 The Component System
12.4.3 Thread based versus Event Based systems
12.4.4 Learning Algorithms
12.5 Observations about Petri-net Interface Descriptions
12.6 Performance
12.6.1 The Liveness Module
12.6.2 The Enforce Action Module
12.6.3 The Concurrency Module
12.6.4 Message Sends
12.6.5 Overall Performance
12.7 Motivation vs Solution
12.7.1 Open Distributed Systems
12.7.2 Mobile Multi Agent System
12.7.3 Embedded Systems
13. Conclusions
13.1 Technical Summary
13.2 Thesis Statement
13.2.1 Abstract Requirements
13.3 Contributions
13.4 Limitations
13.5 Application Scope of our Adaptor
13.5.1 Truly Open Systems: Feasible ?
13.5.2 Then: Why Do We Need Adaptors ?
13.5.3 Impact on Component Development
13.5.4 Decoupling Client / Server
13.6 Some Practical Applications
13.6.1 Collaborative Computer Supported Work
13.6.2 Databases Access
13.6.3 Frequently Changing interfaces: TCP/IP Sockets
13.7 Guidelines
13.7.1 Explore the Environment
13.7.2 Goal & Reference Frame
13.7.3 Identify Necessary Extra Information
13.7.4 State the Adaptor Requirements Explicitly
13.7.5 Correctly Represent Missing Information
13.7.6 Create the Adaptor
13.8 Future Work
13.8.1 Meta-conflicts
13.8.2 The problem of checkpoints
13.8.3 Other Learning Approaches ?
13.8.4 Peer to Peer Concurrency
13.8.5 Learning an Interface Description
13.8.6 Determinism versus Non-Determinism
14. Thread Based Models for Distributed Systems
14.1 Naming/Finding services
14.2 Communication
14.3 Openness & Remote Objects
14.4 Java Threads
14.5 Error handling: Exceptions
14.6 Java RMI and Concurrency
14.6.1 Concurrency Primitives
14.6.2 Java RMI
14.7 Writing Adaptors
Bibliography
Subsections
Acknowledgments
General Glossary
1
. Introduction
1
.
1
Motivation
1
.
1
.
1
First Position: Standards in Open Distributed Systems
1
.
1
.
1
.
1
There cannot be
one
standard.
1
.
1
.
1
.
2
Open Distributed Systems require Interface Adaptors
1
.
1
.
2
Second Position: Mobile Agent Systems
1
.
1
.
3
Third Position: Interconnected Embedded Systems
1
.
2
Thesis
1
.
2
.
1
Thesis Goal
1
.
2
.
2
Methodology
1
.
2
.
3
Case & Thesis Statement: Concurrency Conflicts
1
.
3
A Preliminary Example
1
.
3
.
1
What is an Interface ?
1
.
3
.
1
.
1
The Interface of the Server Component
1
.
3
.
1
.
2
The Interface of the Client Component
1
.
3
.
2
A Syntactical Conflict
1
.
3
.
3
Conflicting Semantics
1
.
3
.
4
What is a Conflict ?
1
.
3
.
5
What Are the Requirements ?
1
.
4
Structure of Our Work
1
.
4
.
1
Adaptors
1
.
4
.
2
The Enforce-Action Module
1
.
4
.
3
The Liveness Module
1
.
4
.
4
The Concurrency Module
1
.
4
.
5
Formal Documentation
1
.
5
Scientific Approach
1
.
5
.
1
Publications
1
.
6
Related Work
1
.
6
.
1
Similar Approaches
1
.
6
.
1
.
1
Adaptor Generation by Means of Finite Automata
1
.
6
.
1
.
2
Software Integration: Adaptor Repositories
1
.
6
.
2
Alternative Approaches
1
.
6
.
2
.
1
Undecidability & Possibilities
1
.
6
.
2
.
2
Version Control and Software Evolution
1
.
6
.
2
.
3
A Common Language: Ontologies
1
.
6
.
2
.
4
Adaptor Writing
1
.
7
Roadmap
1
.
7
.
1
Chronology
1
.
7
.
2
Storyline
1
.
7
.
3
Conventions
Werner 2004-03-07
