Synchronized Composition Of Labeled Transition SystemTS

50 %
50 %
Information about Synchronized Composition Of Labeled Transition SystemTS
Education

Published on January 27, 2009

Author: ang.chen

Source: slideshare.net

Description

How to compose labeled transition system to build large distributed system. With the counter example.

Synchronized Composition of Labeled Transition System Ang Chen University of Geneva, Switzerland 17.06.2008

Roadmap Graphical Design Front-End Optimized Process (Visual Language for Abstract CFlow) custom er Stock End Start Receive Send Collect Ship Order Invoices Payments Books Control flow Interaction code generation (optional) transformation ID-Net ID-Net Flow Controlled System refinement check availability DSL ship goods C C C 1 3 5 s Composition & t a ID-Net r t Refinement DSL DSL remaind er CFlow regis ter DSM C C C 2 4 6 DSL verification receive payment send bill composition test

Labeled Transition System

Transition System Transition System. A transition system is a quadruple A =< S, T, α, β > where • S is a finite or infinite set of states, • T is a finite or infinite set of transitions, • α and β are two mappings from T to S which take each transition t in T to the two states α(t) and β(t), respectively the source and the target of the transition t. 4

Labeled Transition System Labeled Transition System. A labeled transition system is a quadruple A =< S, T, A, s0 > where: • S is a set of states, • A is a set of actions names (labels), called alphabet a • T ⊆ S × A × S, denoted as s − s , a ∈ A, s, s ∈ S, is a transition relation. → α : T → S, β : T → S, λ : T → A are mappings from a transition to its source state, target state, and label, respectively, • s0 ∈ S is the initial state. 5

Example: Counter 0 3 t4 LTS of counter t1 t3 1 2 t2 It has 4 states {0, 1, 2, 3}, one action inc, initial state 0, and the following transitions: • t1 : 0 → inc → 1, α(t1) = 0, λ(t1) = inc, β(t1) = 1 • t2 : 1 → inc → 2, α(t2) = 1, λ(t2) = inc, β(t2) = 2 • t3 : 2 → inc → 3, α(t3) = 2, λ(t3) = inc, β(t3) = 3 • t4 : 3 → inc → 0, α(t4) = 3, λ(t4) = inc, β(t4) = 0 6

Different models for the same semantics t1 P0 P1 0+1=1 x 1+1=2 0 inc t4 t2 2+1=3 x+1 3+1=0 t3 P2 P3 Place/Transition Net model of the counter APN (CO-OPN) model of the counter (Places are Safe) They have different labels (action) set The P/T Net can be considered as an unfolded APN model 7

LTS: Summary • LTS: State, Action (names), Transition • Semantics are what we want to have, i.e. LTS • The same semantics can be realized by different DSL with different syntax • Composition of LTS can be independent of DSL • Assumption: LTS transitions are instance of Action (labels). Each LTS transition is always labeled by a label. 8

Model Composition

Model Composition • Synonyms • communication (e.g. in Process Algebra) • synchronization (e.g. Petri Net) • transaction (e.g in CO-OPN) • Composition implies constraints 10

Synchronous Product of Transition Systems • André Arnold • Free Product: no interaction between components • Synchronous product • a subsystem of the free product • synchronization constraints (implied by interaction) 11

Arnold’s Synchronous Product of TS • Only essential synchronization constraints are used e.g. • program/process P is a TS • boolean variable B is a TS • a constraint is : •“P.read” is synchronized with “B.get” 12

Synchronous Product of TS vs. CO-OPN transaction • “when A sends a message to B, B receives it” A.out//B.in A B B.out//A.ackout with CO-OPN, we can do more: “when B receives a message, it send an acknowledgment to A” 13

Proposition Use CO-OPN Transactions operators to specify synchronization constraints for model composition 14

Free product of counters System A System B 0 3 0 3 inc inc LTS inc inc inc inc 1 2 1 2 inc inc x x Model 0 Ainc 0 Binc x+1 x+1 Two simultaneous, independent counters 15

Free Product (interleaving run) Bt4 Bt1 Bt2 Bt3 00 01 02 03 x At1 At1 At1 At1 Bt4 0 Ainc x+1 Bt1 Bt2 Bt3 10 11 12 13 At4 At4 At2 At4 At4 At2 At2 At2 Bt4 x Bt1 Bt2 Bt3 20 21 22 23 0 Binc x+1 At3 At3 At3 At3 Bt4 Bt1 Bt2 Bt3 30 31 32 33 LTS of the composed system 16

Composing the counters: I SA SB x x 0 0 x+1 x+1 y x Ainc Binc y+1 x+1 Ainc//Binc Ainc+//Binc+ 17

Composed LTS: I At4//Bt4 00 Bt1 Bt2 Bt3 01 02 03 SA SB x x At1Bt2 0 At1 0 At1 At1Bt1 At1 At1Bt3 x+1 At1 x+1 At1Bt4 y x Ainc Binc y+1 x+1 10 12 Bt3 Bt1 Bt2 11 13 Ainc//Binc At4Bt1 At2Bt3 At2Bt4 At4Bt3 At2 At2 At2 At2 At2Bt1 At2Bt3 At4Bt2 Ainc+//Binc+ 20 Bt1 Bt2 Bt3 21 22 23 At3 At3 At3Bt4 At3 At3Bt1 At3Bt3 At3Bt2 At3 30 Bt1 Bt2 Bt3 31 32 33 18

Composing the counters: II SA SB x 0 0 x+1 y x Ainc y+1 x+1 Ainc//Binc Ainc+//Binc 19

Composing the counters: III SA SB x 0 0 x+1 y x Binc y+1 x+1 Ainc//Binc Ainc//Binc+ 20

Composed LTS: III At4//Bt4 00 Bt1 Bt2 Bt3 01 02 03 At1Bt2 SA SB At1Bt1 At1Bt3 x At1Bt4 0 0 x+1 10 Bt1 Bt2 Bt3 11 12 13 y x Binc At4Bt1 At2Bt3 At2Bt4 y+1 At2Bt3 x+1 At2Bt1 At4Bt3 At4Bt2 Ainc//Binc 20 Bt1 Bt2 Bt3 21 22 23 At3Bt4 At3Bt1 At3Bt3 At3Bt2 Ainc//Binc+ 30 Bt1 Bt2 Bt3 31 32 33 21

Composed LTS: IV SA SB 0 0 y x Ainc//Binc y+1 x+1 Ainc//Binc At4Bt4 LTS At1Bt1 At2Bt2 At3Bt3 00 11 22 33 22

Conditional Synchronizations I SA=3, SB=3::Ainc // Binc (At4//Bt4) SA=3, SB=3::Ainc // Binc Bt1 Bt2 Bt3 00 01 02 03 SA SB At1 x!=3 At1 At1 At1 x!=3 0 0 x+1 x+1 3 Bt1 Bt2 Bt3 10 11 12 13 3 Ainc Binc 0 At2 0 At2 At2 At2 SA=3, SB=3::Ainc//Binc Bt1 Bt2 Bt3 20 21 22 23 Two counters are At3 At3 At3 At3 synchronized at Bt1 Bt2 Bt3 30 31 32 33 each cycle 23

Conditional Synchronizations II SA=3, SB=3::Ainc // Binc (At4//Bt4) SA=3, SB=3::Ainc+ // Binc Bt1 Bt2 Bt3 00 01 02 03 SA SB At1 At1 At1 At1 x!=3 x 0 0 x+1 x+1 3 Bt1 Bt2 Bt3 10 11 12 13 3 Ainc Binc 0 0 At4 At2 At4 At2 At4 At2 At4 At2 + SA=3, SB=3::Ainc //Binc Bt1 Bt2 Bt3 20 21 22 23 Same as before, but A At3 At3 At3 At3 can resets itself without synchronizing Bt1 Bt2 Bt3 30 31 32 33 with B + 1). SA=3, SB=3::Ainc // Binc 24

Conditional Synchronizations SA=3, SB=3::Ainc // Binc (At4//Bt4) SA=3, SB=3::Ainc+//Binc+ Bt1 Bt2 Bt3 00 01 02 03 SA SB Bt4 x At1 At1 x At1 At1 0 0 x+1 x+1 Bt1 Bt2 Bt3 10 11 12 13 3 3 Ainc Binc Bt4 0 At2 At4 At2 At4 At2 At4 At2 0 At4 SA=3, SB=3::Ainc//Binc Bt1 Bt2 Bt3 20 21 22 23 At3 At3 At3 Bt4 At3 Both A and B can reset Bt1 Bt2 Bt3 30 31 32 33 themselves, or they can Bt4 be synchronized at 0 + + 2). SA=3, SB=3::Ainc //Binc 25

More conditional synchronizations At4//Bt4 SA=3::Ainc//Binc+ Bt1 Bt2 Bt3 00 01 02 03 SA SB At1 At1 At1 At1 x x!=3 0 0 x+1 x+1 Bt1 Bt2 Bt3 10 11 12 13 x 3 Ainc Binc x+1 At4Bt3 At2 At4Bt2 At2 At2 At4Bt1 At2 0 SA=3::Ainc//Binc+ Bt1 Bt2 Bt3 20 21 22 23 At3 At3 At3 At3 A triggers B at Bt1 Bt2 Bt3 30 31 32 33 each cycle of A + 1). SA=3::Ainc//Binc 26

More conditional synchronizations At4//Bt4 SA=3::Ainc//Binc 00 01 02 03 SA SB At1 At1 At1 At1 x!=3 0 0 x+1 10 11 12 13 x 3 Ainc At4Bt3 At2 x+1 At4Bt2 At2 At2 At4Bt1 At2 0 SA=3::Ainc//Binc 20 21 22 23 At3 At3 At3 At3 B is driven by A at 30 31 32 33 each cycle of A 2). SA=3::Ainc//Binc 27

Summary • Use transaction for model composition • Synchronization constraints: extend transaction with modifiers +,- to control the composition • Formalization of these composition operators: ongoing work • Formalism Integration with ID-Net: this summer 28

Add a comment

Related presentations

Related pages

Synchronized I/o | LinkedIn

View 4017 Synchronized I/o posts, presentations, experts, and more. Get the professional knowledge you need on LinkedIn. LinkedIn Home What is LinkedIn?
Read more

HAHAHA, HEHEHE, HIHIHI, or HKHKHK: Influence of Position ...

... + -Labeled Affibody Molecules. ... HIHIHI, or HKHKHK: Influence of Position and Composition of Histidine Containing Tags on Biodistribution of ...
Read more

5.1 Ionization - 道客巴巴 - doc88.com

... we choose here the well-knownmodel of synchronized product of transition ... a network of labeled transition ... transition systemTS ...
Read more

Handbook of Real-Time and Embedded Systems - scribd.com

CRC-C6781 FM. tex 16/6/2007 14: 58 Page i Handbook of Real-Time and Embedded Systems CRC-C6781 FM.tex 16/6/2007 14: 58 Page ii PUBLISHED TITLES ADVERSARIAL ...
Read more

ADA199171.pdf - Scribd

He observed nat the transition between tension and bearing failure modes occurs in the range of bolt pitches between *.3 Hole Size Garbo and Ogonowskl ...
Read more

Algebraic Formalisms - Springer

Algebraic Formalisms. Carlo A. Furia Affiliated with Department of Computer Science, Dino Mandrioli Affiliated with Dipartimento di Elettronica ...
Read more

Internal Audit Handbook - MBA智库文档

Internal Audit Handbook.pdf. Botoxin 上传于 2010-07-28 15:45 | (6人评价) |
Read more