### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# SEMINAR IN COMPUTER SCIENCE CS 260

UCR

GPA 3.88

### View Full Document

## 16

## 0

## Popular in Course

## Popular in ComputerScienence

This 111 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 260 at University of California Riverside taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/231750/cs-260-university-of-california-riverside in ComputerScienence at University of California Riverside.

## Reviews for SEMINAR IN COMPUTER SCIENCE

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Approximation Algorithms Chapter 9 Bin Packing Presented By Piyush Ranjan Satapathy Class CS260 By Dr Neal Young Original Slides From Nobuhisa Ueda s Webpage Overview 14 I Main issue Asymptotic approximation algorithms for NPhard problems Ideal case Given an instance we can always obtain its solution with any approximation ratio PTAS Polynomial Time Approximation Scheme See section 8 of the textbook Better case For almost all instances we can obtain its solution with any approximation ratio Bin Packing problem Minimum approximation ratio 32 if bin is 2 Overview2 4 I PTAS Time bounded by a polynomial in n the problem size For any 8 gt 0 for a problem instance I the performance guarantee is AI S 1 8 OPTI I FPTAS Time bounded is polynomial in both problem sizen and l 8 We saw the Knapsack which is On2 n 8 I FPTAAS Time bounded is polynomial in both problem size and l 8 and having a hidden constant in the order of 8 AI s 1 8 OPTI 081 Overview 34 PTAS There is a polynomialtime algorithm that always nds a solution within a given approximation factor 8 Asymptotic PTAS There is a polynomialtime algorithm for any largesized instances that always nds a solution within a given approximation factor 8 Score of solution found Gradient TAS 1 8 Gradient 1 8 ptimal solution OPT Overview 44 I Bin packing problem An example The FirstFit algorithm Approximation factor is 2 No approximation algorithm having a guarantee of 32 Reduction from the set partition an NPcomplete problem Asymptotic PTAS A8 The minimum size of binsg distinct sizes of bins K Exact algorithm Where 8 and K are constants Approximation algorithm Where 8lS constant Bin packing problem I Input n items with sizes a1 an O lt al S 1 I Task Find a packing in unitsized bins that minimizes the number of bins used Bin packing problem I Input n items with sizes a1 an O lt al S 1 I Task Find a packing in unitsized bins that minimizes the number of bins used Bins Overview 34 I Bin packing problem An example The FirstFit algorithm Approximation factor is 2 No approximation algorithm having a guarantee of 32 Reduction from the set partition an NPcomplete problem Asymptotic PTAS A8 Lower bound of bins 8 distinct sizes of bins K Exact algorithm Where 8 and K are constants Approximation algorithm Where 8lS constant The FirstF it algorithm 14 I This algorithm puts each item in one of partially packed bins If the item does not t into any of these bins it opens a new bin and puts the item into it The FirstF it algorithm 24 I This algorithm puts each item in one of partially packed bins If the item does not t into any of these bins it opens a new bin and puts the item into it Items Bins The FirstF it algorithm 34 V I This algorithm puts each item in one of partially packed bins If the item does not t into any of these bins it opens a new bin and puts the item into it The FirstF it algorithm 44 I This algorithm puts each item in one of partially packed bins If the item does not t into any of these bins it opens a new bin and puts the item into it FirstFit nds a ZOPT solution 12 I OPT bins used in the optimal solution I Proof Suppose that FirstFit uses m bins Then at least ml bins are more than half full We never have two bins less than half full If there are two bins less than half full items in the second bin can be substituted into the rst bin by FirstFit FirstFit nds a ZOPT solution 22 I Suppose that FirstFit uses m bins I Then at least ml bins are more than half full Sum of sizes I l 39 of the items 39 1 OPTzial gt quot7 1 i1 2OPT gt m 1 T1164 of 39 Since m and OPT are integers gt 2 m Overview 34 I Bin packing problem An example The FirstFit algorithm Approximation factor is 2 No approximation algorithm having a guarantee of 32 Reduction from the set partition an NPcomplete problem Asymptotic PTAS A8 Lower bound of bins 8 distinct sizes of bins K Exact algorithm Where 8 and K are constants Approximation algorithm Where 8lS constant No factor 32 approx algorithms I Sketch of Proof Suppose that we have a factor 32 approximation algorithm A Then A can nd the optimal solution for the set partition problem in polynomial time Partitioning n Ve integers into two sets each adding up to half of the summation of all n numbers This is Equivalent to 11 items to be packed in 2 bins Note that the set partition problem is NPcomplete The result from the above assumption contradicts with P 7E NP Overview 34 I Bin packing problem An example The FirstFit algorithm Approximation factor is 2 No approximation algorithm having a guarantee of 32 Reduction from the set partition an NPcomplete problem Asymptotic PTAS A8 The minimum size of bins g distinct sizes of bins K Exact algorithm Where 8 and K are constants Approximation algorithm Where 8lS constant Theorem 93 I We can nd an approx solution with factor 12 8 OPT1 Where 0 lt 8lt12 FirstFit is available if 8 12 The factor 12 8 OPT1 gt 20PT1 ing 12 3 bins are required if OPT2 Consistent with the previous inapproximable result 1001 bins are sufficient for an instance with OPT1000 0 by setting 814000 Note Its computation time is polynomial time but huge I We will follow the algorithm and proofs Algorithm 1 Remove items of size lt 8 from the list 2 Partition all the items into groups of k Where k1 82 Round items of each group to the largest size of the item belonging in it 3 Find an optimal packing 4 Use this packing for original item sizes 5 Pack items of size lt 8 using FirstFit Lemma 94 I Consider bin packing with constraints BPl The minimum size 8 of items is a constant distinct sizes of bins K is a constant I There eXists a polynomialtime algorithm for BPl that nds the best solution The algorithm searches for the solution exhaustively combinations of items in a bin denotes R combinations of n bins such that R distinct bins are available denotes P P is upperbounded by a polynomial of n 0nR Lemma 94 I Bin packing with constraints The minimum size 8 of items is a constant distinct bins K is a constant There are K distinct items At most 18 10 items are in a bin If803 lgj333j3 M is the max of items in a bin How many combinations of items are possible in a bin R combinations of items in a bin I Pack M items in a bin from K 1 different items K 1 items with K sizes empty unselected Eg K 3a M 3 a1 a3 unselected 392 mom 3 M partitions are selected from 6 K M elements a1 is selected doom a1 a2 a3 ololo M M and K are constants gt R is also constant P combinations of bins I combinations of bins with R different bins We can nd P in a similar way P can be bounded by a function of n Eg R3 n 3 191 was selected 11 R R P S n R a 212 doom R 0nR b1 b3 Nobln t poss1ble comblnatlon b1 93 5 39039 d is bounded by a polynomial of n We can find the best packing by exhaustive search in polynomial time Examples of nR I a min size of items K different items 803 M 3 K3 R 6C320 computation time 0n20 801 M 10 K3 R 10C3120 computation time 002120 8005 M 20 K3 R 20C31140 computation time 0n1140 Lemma 95 I Bin packing with less constraints The minimum size 8 of items is a constant I There eXists a factor 18 approximation algorithm It first modi es the sizes of items into only K different ones It uses the exhaustive search used in Lemma 94 IREed QLne Q items with the same size in a group How to modify the sizes of items I I the original input J its modi ed one I J consists of Q groups I The size of each item is set to the maximum size of items in its group Let Q3 I w Sort them by size 3 There are at most K different item sizes How to pack items I From Lemma 94 the optimal packing for J can be found in polynomial time I The packing for J is also valid for the original item sizes I l l what about approx factor Z Where The opt1ma1 b1ns CPR S Z OPTU denotes OPTD For evaluating OPTD I We prepare another modi ed instance J I J consists of Q groups I Each item size is set to the minimum in its group Suppose Q3 39 I An item in J is the I M 39 y same as or smaller Sort them by size than the original item in I OPTJ s OPTI Diff between OPTJ and OPTJ basis of size for modi cation Any item in J Q is always not smaller than Each of the biggest Q items packed into Q bins in J OPTJ S OPTJQQ one in JQ 0PTJQ OPTJ Q I J 54 J contains every item in J Q I Q items I J U OPTJ Q S OPTJ Mao 51mm I 39 39 g l a r sule115 51 I 39 51mm 50m 1 5mc10 5fld0 39 af 5471mm 8916 55 ii 315 Jld0 pm Dido Hem 1961 395qu 55rndo fld0 Relation between Q and OPTD I Q ne2 sineeQ teQJ I OPTI gt 118 since 8 any item size mg the total item size n items The total item size bins that is OPTI I Then Q S r162 8018 S aOPTU PTJ OPT1Q s 15OPT1 I vi 3 1 quot1391 Theorem 93 I We can nd an approx solution with factor 12 8 OPT1 Where 0 lt 8ltl2 FirstFit is available if 8 12 The factor 12 3 OPT1 gt ZOPTH if g 12 3 bins are required if OPT2 Consistent with the previous inapproximable result 1001 bins are suf cient for an instance with OPT1000 by setting 814000 Algorithm A 8 Input Items I Procedure in Lemma 95 1 OPT 9 L S 1 OPTI Output L bins Pack items in I I into bins of I by FirstFit l l I We consider two exclusive case to nd the upper bound of L Evaluation of A8 12 I Consider two exclusive cases 1 No extra bin was required for packing items in I 1 L S 18 OPTI S 18OPTI Since there are more items in I than in I 2 Extra bins were required for packing items in I 1 In each of Ll bins room is smaller than 8 n OPTzzaigtL 1l 5 11 f Item Slze 1n I I otal sum 0 item sizes 39 1 T Then we have 1 2 L 1 8 Evaluation of algorithm A8 22 M 1m W 53 33 w lag LL1 g12g 1 1 8 1 18 282 1 18 i1 2g20 Olt8Sl 1 8 2 Thenwehave 1 2 gt 1 O lt 1 35 I 12I 39 g 18 lt8E 3 11X Therefore 25 L lt OPT 1g12gOPT1oggglj 239 1 8 2 1 011 012 013 014 015 016 07 Security Aspects of Napster and Gnutella Steven M Bellovin smbresearchattcom httpwww researchattcomsmb Common Functions 0 Share les 0 Peer to peer les don t reside on a central server 0 Each user decides which les to offer to others Protocol supplies index and connectivity information Data transfer is end to end and does not use central server Napster 0 Everyone connects to central server 0 Server compiles and distributes index 0 Server also provides chat room function independent of le sharing aspect 0 Protocol details reverse engineered Gnutella o No central server 0 No index 0 Users send queries to a neighbor neighbors answer ifthey can and also forward query to their neighbors Note must know DNS name or IP address of some starting point 0 Client retrieves le directly from one answerer 0 Open protocol speci cation Gnutella Protocol Details 0 Simple protocol 5 messages Ping pong push query query hits 0 Uses ooding protocol speak to all neighbors o H1TP used for actual content transfer 0 No login no authentication no central authority of any type Gnutella Topology Gnutella Topology Gnutella Topology Gnutella Topology Gnutella Topology Common Header o 16 byte Windows GUID Clients must drop messages if GUID seen recently a Message type c Time to live limits maximum spread of message o Hop count how far away the sender is o Payload length Ping and Pong 0 Used for topology discovery ask who s out there 0 Nodes that choose to reply with their IP address plus the amount of data they re sharing 0 Provides new connection points for nodes 0 But what if they lie about their IP address Query and Query Reply 0 Query lists search terms minimum server speed acceptable o Query response gives IP address port speed les that satisfy query GUID of querier Querier then connects to offerer and requests le Push o Intended to bypass rewall you can t serve a le ifyou re behind a rewall o If requester can t connect it sends a push command instead with its IP address and port number 0 Offerer does an outbound connect to that host and sends the le Gnutella Analysis o Gives away topology information 0 Hard to control via rewalls o Unchecked IP address and port number announcements can be used to generate ooding attacks and possibly worse 0 GUID may be usable to trace back Gnutella messages GUID Tracing o On Windows 95 98 NT GUID contains the hardware MAC address which is constant over time 0 Privacy violation can be used to link requests over time 0 Windows 2000 and the UNIX clients I ve looked at use random appearing GUIDs Is there some hidden linkage Leakage o Announces IP addresses 0 Appears to announce full path names o Announces Gnutella topology which may or may not re ect real world patterns of association 0 Can use any port number hard to detect hard to control outbound via rewalls o Nosy node can record queries responses Flooding o Pong messages contain IP addresses and port numbers will other nodes auto connect What ifa node claims to be port 80 on wwwcnncom o QueryPush pair is worse an attacker can induce many sites to try to send a large le to so me arbitrary destination Similar to FTP Bounce attack Content Issues o What if I send you fake content 0 What ifl send obscene content in response to innocent queries 0 Note falsely advertising a high speed link can be used to attract clients UI Issues o Gnutella can be used to share arbitrary les 0 Some Uls provide an easy way to open les 0 Is this mechanism safe How does it decide how to open a le If done wrong this is as dangerous as email attachments Can I get a EXE or a VBS le when I asked for an MP3 0 Again fake line speed announcements can ho Ilcnrl 39l39n nH rar39l39 rlinn39l39c 6 Napster Protocol Details 0 Complex clientserver protocol with central site 0 Users can register log in etc Registration message includes age income and education Central site can bounce users ban them etc 0 Different message groups for chat rooms searchingbrowsing uploaddownload 0 File transfer is direct and doesn t go through napstercom s site Napster Topology o Napster Topology o Napster Topology o Napster Topology Napster Topology Searching and Indexing 0 Client sends search or browse requests to central site Can browse some other user s les Response come back from central site 0 Only explicitly shared les should be retrievable 0 Only handles MP3 Wrapster can package other file types in MP3 envelope Chat Rooms 0 Conversations among users Nominally moderated o All traf c ows toofrom central site Central site not working that well right now there are several servers that don t share status information 0 Multiple topics etc 0 Clients can have hot lists of their friends Privacy issues 20 File Transfers 0 Transfer request goes to central site 0 Data transfer is direct Client and server both notify central site of status to support load limits 0 Clients can use any port numbers 0 Firewall bypass mechanisms reverse who does active connect 2 UI Issues 0 Less opportunity for auto exec of nasty programs What if Wrapster functionality becomes common o Is browsing more intrusive than queryresponse 22 Napster Analysis 0 Much harder for clients to lie can t give fake IP addresses port numbers etc 0 Central site can exert much more control 0 Privacy issues central site knows almost all 0 Fake content and fake line speed attacks still apply but in theory are more traceable Napster versus Gnutella o Napster is more centralized easier to monitor and control for good or bad purposes o Gnutella can probablyscale further if better topology reconstruction algorithms are developed 0 Only Gnutella can easily share arbitrary les but that s a likely growth direction for Napster o Gnutella is probably the style of the future avoid central sites 24 binary decision diagrams Question What is a BDD Binary Decision Diagram What is the most cited computer science document in citeseer httpciteseernjneccom Answer 3 Most cited source documents in the Researchlndex database as of February 2005 This list only includes documents in the Researchlndex database Citations Where one or more authors of the citing and cited articles match are not included The data is automatically generated and may contain errors The list is generated in batch mode and citation counts may differ from those currently in the Researchlndex database because the database is continuously updated 1 GraphBased Algorithms for Boolean Function Manipulation Bryant 1986 In this paper we present a new data structure for representing Boolean functions and an associated set of 2 A Method for Obtaining Digital Signatures and PublicKey Cryptosystems Rivest Shamir Adleman 19 78 An encryption method is presented With the novel property that publicly revealing an encryption key does not Reduced ordered binary decision diagrams BDDs quotGraphbased algorithms for boolean function manipulation Randy Bryant Carnegie Mellon University IEEE Transactions on Computers 1986 CiteSeer most cited document X4X3X2X1 i X4 i X3X2 i X1 v v a 4 BDDs are a canonical representation of boolean functions f BL gt B Eg the root node encodes the function moot such that UrootX40X31X21X10 UrootX40X31X21X11 1 Ordered binary decision diagrams BDDs 5 A BDD is an acyclic directed edgelabeled graph where o The only terminal nodes can be 0 and 1 and are at level 0 0lvl 1lvl 0 o A nonterminal nodep is at a level k with L 2 k 2 1 plvl k 0 A nonterminal node p has two outgoing edges labelled 0 and 1 pointing to children p0 and pm 0 The level of the children is lowerthan that ofp p0lvl lt plvl p1lvl lt plvl o A node p at level k encodes the function Up BL gt B defined recursively by p ifk0 U ZELZE1 p vpxkxLx1 ifk gt 0 Instead of levels we can also talk of variables 0 The terminal nodes are associated with the range variable 130 o A nonterminal node is associated with a domain variable 3 with L 2 k 2 1 Canonical versions of BDDs e For canonical BDDs we further require that 0 There are no duplicates ifplvl qlvl and p0 q0 and p1 q1 thenp q Then if the BDD is quasireduced there is no level skipping o The only root nodes with no incoming arcs are at level L o The children p0 and M1 of a nodep are at level plvl 1 Or if the BDD is fullyreduced there is maximum level skipping 0 There are no redundant nodes p satisfying p0 p1 Both versions are canonical thus if functions f and g are encoded using BDDs o Satisfiability f 7E 0 or equivalence f 9 01 0 Conjunction f g disjunction f V g gtlt if fullyreduced 27421621 0llfllk X llgllk ifquasireduced number of nodes in the BDD encoding f lk number of nodes at level k in the BDD encoding f Quasireduced vs fullyreduced BDDs 7 4 4 3214321 x3 T32132 1 2 1 2 1 Fullyreduced BDDs each node in the BDD encodes a different function Quasireduced BDDs each node at a given level of the BDD encodes a different function Using BDDs to encode sets We can encode a set 3 Q BL as a BDD p through its characteristic function i iLi1 E 3 ltgt UpiLi1 1 The size of the set encoded by BDD p is not directly related to the size of the BDD itself Indeed any set requires as many nodes as its complement 0 2 4 0011010101100111 1001 000000010010 1010 101111011110 1111 010010001100 4 3 2 1 Properties of fullyreduced ordered BDDs 9 Given a boolean expression or a function f BL gt B there is a unique BDD encoding it for a fixed variable order 361 361 Many functions have a very compact BDD encoding The constant functions 0 and 1 are represented by the nodes 0 and 1 respectively Given the BDD encoding boolean expression f test whether f E 0 or f E 1 in 01 time Given the BDDs encoding boolean expressions f and g test whether f E g in 01 time The variable ordering affects the size of the BDD consider xL yL x1 yl 0L nodes 02L nodes 0 with the order xLyL 711317391 levyLa Hayl The BDD encoding of some functions is exponentially large for any order 0 with the order xL o the expression for bit 32 of the 64bit result of the multiplication of two 32bit integers Finding the optimal ordering that minimizes the BDD size is an NPcomplete problem Union Or and Intersection And for fullyreduced BDDs 10 bdd Unionbdd p bdd q is local bdd 7 ifp 0 org 2 1 then return q ifq 0 orp 1 then return p ifp q then return 19 if Cache contains entry UnionCODE 19 q 7 then return 7 ifpl39ol qle then mummth x O 11 2 else ifpl Ul gt ql39Ul then else since plvl lt ql39Ul then enter UnionCODE 19 q 7 in Cache return 7 fullyreduced version 7 lt UniqueTableInsertplvl Unionp0q0 Unionp1q1 7 lt UniqueTableInsertplvl Unionp0q Unionp1 q 7 lt UniqueTableInsertql39ol Unionpq0 Unionpq1 Intersectionp q differs from Unionp q only in the terminal cases Union ifp 0 orq 1 then return q Intersection if q 0 orp 1 then return p complexity 0product of the numbers of nodes in p and q ifp 1 or q 0 then return q if q 1 orp 0 then return 19 Computing the relational product symbolically Given an Llevel BDD on xL 1c1 rooted atp encoding a set 3 g 2 Given a 2Llevel BDD on xL x1 rooted at 71k encoding a function N 2 gt 2X RelationalProductp n returns the root of the BDD encoding the set sziEijENm 1 00IO JU IPQgtIJ bdd RelationalProductbdd p bdd2 7 is local bdd q q1 q2 quasireduced version ifp 0 orr 0 then return 0 ifp 1 and 7 1 then return 1 if Cache contains entry RelationalProductCODEp r q then return q qo lt Uni0nRelati0nalPr0ductp0 r0 0 RelationalProductp1 r1 0 q1 lt Uni0nRelati0nalPr0ductp0 r0 1 RelationalProductp1 r1 1 q lt Um39queTableInsertplvl qo q1 enter RelationalProductCODEp 7 q in Cache return q Efficiency of BDDs 12 The efficient manipulation of BDDs relies on the idea of dynamic programming More specifically on the use of an operation cache Given enough memory for cache entries we never recompute an operation on the same operands The operation cache is implemented as a hash table with entries of the form lt key result gt 0 given the key operator operand operand c we can retrieve the result if it was previously computed In practice we can store 0 either ltV a b egt in the Operation cache boolean OR is commutative c or lta b cgt in the OR or UNION cache 0 either ltgt a b egt in the Operation cache boolean IMPLIES is not commutative c or a b cgt in the IMPLIES cache discretestate models Structured discretestate models 14 A structured discretestate model is specified by 0 a potential state space 2 26 X X 261 o the type of the global state 0 26k is the discrete local state space for the kth submodel o if 26k is finite we can map it to 0 1 nk 1 71k might be unknown a priori o a set of initial states Xim39t Q X 0 often there is a single initial state iinit o a set of events 5 defining a disjunctivelypartitioned nextstate function or transition relation 0 Na 2 gt 22 j E Nai iff statej can be reached by firing event or in state i o N 2 e 2 Ni Uaeg Nan o naturally extended to sets of states N040 Uiey Nai and NO Uiey o 04 is enabled in i iff Nai 7E 0 othenNise it is disabled 0 i is absorbing or dead ifNi 0 Using BDDs to build the state space XML 15 An Llevel BDD encodes a set of states 3 as a subset of the potential state space 2 BL i E 23913 2391 E 7 ltgt the corresponding path from the root leads to terminal 1 A 2Llevel BDD encodes the nextstate function N 2 gt 22 j E ltgt the system can go from itoj in one step The state space th is the fixpoint of the iteration Xinit U NXz39m39t U U U Standard method Alternative All method ExploredeXmitV is AllExploredeXmitV is 1 3 lt Xim39t known states 1 3 lt Xim39t 2 H lt Xz m t unexplored states 2 repeat 3 repeat 3 O lt 3 old states 4 W lt NU potentially new states 4 I lt C U NO new states 5 L lt W 3 truly new states 5 umquot O 2 y 6 y lt 3 U u 6 return 3 7 until u J 8 return 3 Chaining the nextstate function N Roi995 1e IfN is stored in a disjunctiver partitioned form as N U Na using 5 BDDs the effect of 0465 W lt N01 potentialy new states Ll lt W 3 truly new states is exactly achieved with the statements Wlt for each 04 E 5 do Wlt WUNaaI U lt Wy However if we do not require strict breadthfirst order we can use chaining and do for each 04 E 5 do ult UUNQU ueuw Symbolic SsGen breadthfirst vs chaining new vs all states 17 BszGenX m39t Na or E 5 CthGeMXm Na 07 E 5 1 3 lt Xim39t known states 1 3 lt XZ39mt known states 2 LI lt Xim39t unexplored known states 2 LI lt Xim39t unexplored known states 3 repeat 3 repeat 4 Wlt 4 foreacha E5do 5 foreachaE5do 5 UEUUNQUl 6 W lt WUNaUl 6 Ult U trulynewstates 7 L lt W trulynewstates 7 3 you 8 N yUZl 8untiIU 9 until U V 9 return 3 10 return 2 AlleSsGeMXmZ39t Na 07 E 5 AllChSSGBMXmu Na 2 a E 5 1 3 lt Xim39t known states 1 y lt Xinz39t known States 2 repeat 2 repeat 3 O lt 3 save old state space 3 O lt 3 save Old state space 4 Wlt 4 foreacha E5do 5 foreachaE5do 5 DW yUVaoj 6 WHWUNO O 6 until 032 7 y lt O U W 7 return 3 8 until 9 3 9 return 2 Comparing the four approaches Time sec Memory MB N thl Bf Alle Ch AllCh Bf Alle Ch AllCh final Dining Philosophers LN2 XM 34 for all k 50 22gtlt1031 376 368 13 13 1468 1316 22 22 lt01 100 50gtlt1062 6441 6304 54 53 gt9999 gt9999 89 89 lt01 1000 92gtlt10626 8954 9155 8952 8950 03 Slotted Ring Network L N lel 15 for all k 5 53gtlt104 02 03 01 01 08 11 03 02 lt01 10 83gtlt109 215 241 21 12 390 450 57 33 lt01 15 15gtlt1015 7454 7715 185 89 3443 3754 351 202 lt01 Round Robin Mutual Exclusion LN l 1 XM 10 for all k except X1N1 10 23gtlt104 02 03 01 01 06 12 01 01 lt01 20 47gtlt107 27 44 03 03 59 128 05 05 lt01 50 13gtlt1017 2632 4276 29 28 1267 2577 43 38 01 FMS L 19 XM N l l for all k except X174 X123 X72 5 29gtlt106 07 07 01 01 26 22 04 02 lt01 10 25gtlt109 70 58 05 03 182 147 23 13 lt01 25 85gtlt1013 6772 4379 129 51 3197 2453 427 212 01 mdd Ordered multiway decision diagrams MDDs 20 Assumeadomain 2 26 X gtlt X1where 26k 0 1nk 1forsome 7 E N Assume the range 260 B An MDD is an acyclic directed edgelabeled graph where o The only terminal nodes can be 0 and 1 and are at level 0 0lvl 1lvl 0 o A nonterminal nodep is at a level k with L 2 k 2 1 plvl k c For each z39k E 2 a nonterminal nodep at level k has an outgoing edge pointing to child o The level ofa child is lower than that ofp piklvl lt plvl o A nodep at level k encodes the function Up 2 gt B defined recursively by p ifkr0 U ZELZE1 p vpxkxLx1 ifkrgt0 Instead of levels we can also talk of variables 0 The terminal nodes are associated with the range variable x0 0 A nonterminal node is associated with a domain variable ark with L 2 k 2 1 Canonical versions of MDDs 21 For canonical MDDs we further require that 0 There are no duplicates ifplvl qlvl k and forall z39k E 26k then p q Then if the MDD is quasireduced there is no level skipping o The only root nodes with no incoming arcs are at level L o If a nodep is at level k3 each child is at level k 1 Or if the MDD is fullyreduced there is maximum level skipping 0 There are no redundant nodes p at level k satisfying q for all ik E 26k Quasireduced vs fullyreduced MDDs 22 quasireduced fullyreduced 4 full storage full storage 553 2 1 554 We may not know the range 26k of each 3 A L x3 We can simply assume 6 N All but a finite number of edges point to 0 52 Only nodes encoding 0 are redundant 1 Fullyreduced MDDs each node in the MDD encodes a different function Quasireduced MDDs each node at a given level of the MDD encodes a different function Union Or and Intersection And for quasireduced MDDs 23 mdd Unionl39ol k mdd p mdd q is works also if jumptoO is allowed local mdd rrornk1 ifp 0 then return q 2 ifq 0 then return 19 3 ifp q then return 19 4 if Cache contains entry UnionCODE 19 q 7 then return 7 5 foreach ik E Xk do 6 wk lt Unionk 1pikqik 7 8 9 0 end for 7 lt UniqueTableInsertk To 7ink 1 enter UnionCODE 19 q 7 in Cache 1 return 7 Intersectionkp q differs from Unionlltp q only in the terminal cases Union ifp 0 then return q Intersection ifp 1 then return q if q 0 then return 19 if q 1 then return 19 complexity O ZLZkZl nodes at level k in p X nodes at level k in 1 Computing the relational product symbolically 24 Given an Llevel MDD on xL 1c1 rooted atp encoding a set 3 Q 2 Given a 2Llevel MDD on 3 x1 rooted at n encoding a function N 2 gt 2X RelationalProductLpr returns the root of the MDD encoding j 3i E 3 j E mdd RelationalProductU39Ul k mdd p mdd2 7 is quasireduced version local mdd 1 go an l 1 ika Othen returnp 7 2 if Cache contains entry RelationalProductCODEp r q then return q 3 foreach jk 6 26k do 4 Mk 0 5 foreach Zk such that 7E 0 do 6 ij lt Um onqjkRelationalProductk 1p7ikr7ikjk 7 q lt UniqueTableInsertkq0an1 8 enter RelationalProductCODEp 7 q in Cache 9 return q General disjunctivethenconjunctive decomposition 25 A piece of a selfmodifying Petri net Equnvalent pseudocode snmultaneous statements ifpgtrq2s 4qgt0rq 4then PC Oq r1 lt23 pep H1 ql qlt q28 SO 0 Assume Xp012 Xq01234 Xr0123 Xs012 Intersection special reduction rule and interpretation of skipped levels Identityreduced rule for MDDs 26 In addition to the o quasireduced form 0 fullyreduced form we need an o identityreduced form to be used for to or primed levels Identityreduced level k Identityreduced level k and fullyreduced level k canonical even if we use different reduction rules for each level 27 saturation Saturation an iteration strategy based on the model structure 28 Let T0pa and B0ta be the highest and lowest levels on which event 04 depends respectively MDD node p at level k is saturated if it encodes a fixed point wrt any event 04 st T0pa g k gt all MDD nodes reachable from p are also saturated 0 build the Llevel MDD encoding of Xim39t if lXimtl 1 there is one node per level 0 saturate each node at level 1 fire in them all events 04 st T0pa 1 o saturate each node at level 2 fire in them all events 04 st T0pa 2 if this creates nodes at level 1 saturate them immediately upon creation saturate each node at level 3 fire in them all events 04 st T0pa 3 if this creates nodes at levels 2 or 1 saturate them immediately upon creation saturate the root node at level L fire in it all events 04 st T0pa L if this creates nodes at levels L 1 L 2 1 saturate them immediately upon creation states are not discovered in breadthfirst order enormous time and memory savings for asynchronous systems SaturationOTF in action initial setup 29 lt42gt m lt32gt m lt22gt m lt12gt m a be I I I I 2544291 E 0 2C3q07 0 E 0 X230 E 0 251 Et0 E 0 SaturationOTF in action confirm initial state 30 lt42gt m lt32gt m lt22gt m lt12gt m a be 6 01 02 I 01 0 0 01 I I O I I 26442132907292 E 97172 X3qoroaqlro E 97 X2 7 81 E 97 1 X1 t1 2 91 SaturationOTF in action saturate lt112gt lt212gt lt312gt no firing 31 a be d e 0 1 02 I I 0 1 0 0 I 01 0 I I O 1 0 I I lt42gt X4p17p0792 97172 lt32gt m X3q0r0q1r0 E 91 lt2I2gt m X2 81 2 91 lt12gt E 951 v 151 E 97 1 SaturationOTF in action saturate lt4 2 fire a 32 a be d 6 01 02 I I 01 0 0 I 021 0 I I 01 0 I I 26442132907292 E 97172 X3qoroaqlro E 97 X2 7 81 E 97 1 X1 t1 2 91 SaturationOTF in action confirm 51 E 1 33 a be 6 01 02 I 01 0 0 021 O 122 I 10 I 01 0 I I 26442132907292 E 97172 X3q07 0q17 0 E 971 X2 7i782 E Qvlv2 X1 t1 E 91 SaturationOTF in action saturate lt2 3 fire d a be d 01 I I 01 0 I 01 0 122 I 10 01 I I 26442132907292 E 97172 X3q07 0q17 0 E 971 X2 7i782 E Qvlv2 X1 t1 2 91 SaturationOTF in action confirm t1 E 1 a be 01 I 01 0 01 12 I I I CD 26442132907292 E 97172 X3q07 0q17 0 E 971 X2 7i782 E Qvlv2 2CV1 7 7 t2 E 97 la 2 35 SaturationOTF in action saturate lt113gt no firing 36 a be d e 01 02 I I 01 O 0 I 01 0 1392 I 10 I 01 0 I I 12 10 26442132907292 E 97172 X3q07 0q17 0 E 971 X2 7i782 E Qvlv2 2CV1 7 7 t2 E 97 la 2 SaturationOTF in action confirm qlro E 1 37 a be d e 01 02 I I 01 0 O 122 13 I 139 021 0 1392 I 10 I 01 O I I 12 10 254P17290p2 E 912 2PHOTOQ17 0q27 0qov 1 E 9123 2CV2 7 7 82 E 97 la 2 2CV1 7 7 t2 E 97 la 2 SaturationOTF in action saturate lt313gt fire be 38 a be d e 01 02 I I 01 0 O 122 13 I 139 021 0 1392 I 10 I 01 O I I 12 10 254P17290p2 E 912 2PHOTOQ17 0q27 0qov 1 E 9123 2CV2 7 7 82 E 97 la 2 2CV1 7 7 t2 E 97 la 2 SaturationOTF in action confirm 1071 E 3 39 a be d e 01 02 I I 01 O 0 12 13 I 1 34 31 30 01 0 12 I 10 I 01 0 I I 12 10 2CV2 7 7 82 E 97 la 2 2Cl 7 7 t2 E 97 la 2 SaturationOTF in action confirm p0 E 1 4o a be d 6 01 02 1 I I 10 01 0 0 12 13 I 1 34 31 30 01 0 12 I 10 I 01 0 I I 12 10 2CV2 7 7 82 E 97 la 2 2C1 7 7 t2 E 97 la 2 SaturationOTF in action saturate lt412gt fire 6 41 a be d e 01 02 1 I I 1390 01 0 0 12 13 I 1 34 31 30 01 0 12 I 10 I 01 0 I I 12 10 2CV2 7 7 82 E 97 la 2 2Cl 7 7 t2 E 97 la 2 SaturationOTF in action remap confirmed indices 42 a be d 6 01 0 139 I I 10 01 0 0 1 12 I 1 2 21 20 01 0 1 I 10 I 01 0 I I 1 10 Saturation behavior and properties 43 Traditional approaches apply the global nextstate function N once to each node at each iteration and make extensive use of the unique table and operation caches We exhaustively fire each event or in each node p at level k T0pa from k 1 up to L We must consider redundant nodes as well thus we prefer quasireduced MDDs Once node p at level k is saturated we never fire an event or with k T0pa on p again The recursive Fire cas stop at level B0ta although the Union calls can go deeper Only saturated nodes are placed in the unique table and in the union and firing caches Many most nodes we insert in the MDD will still be present in the final MDD Firing oz in p benefits from having saturated the nodes below p finds more states usually enormous memory and time savings

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.