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 ﬂow Interaction code generation (optional) transformation ID-Net ID-Net Flow Controlled System reﬁnement check availability DSL ship goods C C C 1 3 5 s Composition & t a ID-Net r t Reﬁnement DSL DSL remaind er CFlow regis ter DSM C C C 2 4 6 DSL veriﬁcation 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 ﬁnite or inﬁnite set of states, • T is a ﬁnite or inﬁnite 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 modiﬁers +,- to control the composition • Formalization of these composition operators: ongoing work • Formalism Integration with ID-Net: this summer 28

 User name: Comment:

Related presentations

TIM HIEU VE KEM CHONG NANG

December 14, 2017

6 months CCNA training in Noida word

December 14, 2017

Best Suggestions for Qualify NDA Entrance Test

December 14, 2017

ISL - A Perfect App to Search International School...

December 14, 2017

Lake Forest Mall Redevelopment Market Analysis - G...

December 14, 2017

MRCP Part 1 Question Bank Best of Five

December 14, 2017

Related pages

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

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 ...

5.1 Ionization - 道客巴巴 - doc88.com

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

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 ...