## 3 The CPN Model
### The CPN Formalism
#### 3.1.1 Data Extensions  
In this paragraph, we discuss the first extension of Petri nets, where the tokens are distinguished through the assignment of specific values to each one of them. This value is named color, hence the name Colored Petri nets. When modeling a system as a simple Petri net, the system's elements are represented by _tokens_, _places_, and _transitions_ (definitions for the places and transitions are given later in this paragraph). A token is a dynamic element of a Petri net, and it is used to define the network's state. A token can model an object or a set of objects and also states and conditions. For example, in a cloud system a token may model a user job that is CPU intensive (requires more CPU processing resources) while another token may model a memory intensive job (requires more memory). In a simple Petri net, it is impossible to distinguish between these two tokens and describe their attributes. With the CPN formalism, each token carries a value. Other token attributes may include the arrival time, the mean service time, and so forth. We can describe a job with the five attributes: Job_Id, Job_Priority, Arrival_Time, Service_Time, and Type_of_Resources_Requested, as will be discussed when we describe our model. Then, each token will have its own values, like:  
1, 1, 10, 50, [1,1,1] or 2, 1, 20, 60, [1,1,0]  
To describe the network structure and the behavior of CPNs in a formal way, we need to define the notions of _places_ and _transitions_. A place is represented by circles and they are the containers of tokens. The number and type of tokens inside a place define a network's state. In other words, a place represents a system's state, which is defined by the number and type of tokens it contains. For example, if a place has two jobs <1, 1, 10, 50, [1,0,0]> and <2, 1, 20, 60, [1,0,0]> then it represents a state where two user jobs have been generated, one with Id = 1, Priority = 1, generated at time = 10, scheduled to be served after 50 time units, and requesting only the dominant resource and another one with Id = 2, Priority = 1, generated at time = 20 and scheduled to be served after 60 time units, and also requesting only the dominant resource. A monitor, which is transparent to the core generates these tokens (see Section 4.1). A place can only accept tokens of one form: this can include a certain type of token (for example job tokens) or a _union_ of tokens (tokens which are formed by the union of two or more tokens). A transition represents an event that, whenever triggered, it may change the system's state, that is, the system may transition from one state to another. Transitions are represented by rectangles. Generally, we use the verb \"fire\" to indicate that an event has occured. In order for a transition to fire, all its conditions must be satisfied. In this case, we say that the transition is enabled. We use the example of Figure 3 to show these considerations. In this figure (as well as in all the others), the types of tokens are colored for clarity of the presentation. Figure 3 shows 5 positions, \(p_{1}\) and \(p_{3}\) which accommodate only red tokens and \(p_{2}\), \(p_{5}\) which accommodates only black tokens, and \(p_{4}\) which accommodates red-black tokens (union of reds and blacks). Also, there is one transition \(t_{1}\) that is fed by \(p_{1}\) and \(p_{2}\) and transition \(t_{2}\) which is fed by \(p_{4}\). Transition \(t_{1}\) is enabled when its inputs \(p_{1},p_{2}\) have at least one token. The inputs to a transition are indicated by arrows originating from one or more place to this transition. Thus, the existence of at least one token to the transition's input place forms the _condition_ that must hold before it fires. When firing, a transition will change the system's state. Then, one token from each input place is removed and placed to the transition's output place, in our example \(p_{4}\). In the context of CPN, the two different types are united.