# US 2020/0004903 A1 · Workflow Simulation Using Provenance Data Similarity and Sequence Alignment

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0004903 A1
- Document ID: US20200004903A1
- Status: Published application
- Kind: A1
- Application number: 16/023,116
- Filed: 2018-06-29
- Published: 2020-01-02
- Earliest claimed: 2018-06-29
- Assignees: EMC IP Holding Company LLC
- Applicants: EMC IP Holding Company LLC
- Inventors: Vinícius Michel Gottin; Daniel Sadoc Menasché; Alex Laier Bordignon; Eduardo Vera Sousa; Manuel Ramón Vargas Avila
- Web page: https://patentgrep.com/patent/US20200004903A1

## CPC

- G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30)
- G06Q 10/06334: {using forecasting or predicting}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

Techniques are provided for workflow simulation using provenance data similarity and sequence alignment. An exemplary method comprises: obtaining a state of workflow executions of concurrent workflows with multiple resource allocation configurations, wherein the state comprises provenance data of the concurrent workflows; obtaining execution traces of the concurrent workflows representing different resource allocation configurations; identifying a set of states in a first execution trace and a set of states in a second execution trace as corresponding anchor states; mapping a first intermediate state to a second intermediate state between a pair of anchor states using the provenance data; generating a simulation model of the workflow executions representing the different configurations of the resource allocation; and generating new simulation traces of the workflow executions with resource allocation configurations that are not represented in the provenance data.

## Claims

### Claim 1

A method, comprising:
obtaining a state of one or more workflow executions of a plurality of concurrent workflows in a shared infrastructure environment with a plurality of different resource allocation configurations, wherein said state comprises provenance data of said concurrent workflows;
obtaining a first execution trace of the concurrent workflows representing a first resource allocation configuration, and a second execution trace of the concurrent workflows representing a second resource allocation configuration;
identifying a first set of first states in said first execution trace and a second set of second states in said second execution trace as corresponding anchor states;
mapping, using at least one processing device, a first intermediate state between a pair of said anchor states in said first execution trace to a second intermediate state between a pair of said anchor states in said second execution trace using the provenance data such that said second intermediate state is between the anchor states in said second execution trace that correspond to said pair of anchor states in the first execution trace;
generating a simulation model of said one or more workflow executions representing a plurality of the different configurations of the resource allocation; and
generating, using the at least one processing device, one or more new simulation traces of said one or more workflow executions with one or more resource allocation configurations that are not represented in the provenance data.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first intermediate state and the second intermediate state are between two anchor states that satisfy predefined task completion criteria and the mapping of the first intermediate state to the second intermediate state is based on a linear mapping between the two anchor states.

### Claim 3 (depends on 1)

The method of claim 1, wherein the mapping is based on a completion of tasks, obtained from an analysis of the provenance data, of the plurality of concurrent workflows.

### Claim 4 (depends on 1)

The method of claim 1, wherein the provenance data indicates a number of substantially completed tasks of each type for each of the plurality of concurrent workflows, and wherein the mapping is based on a partial completion of tasks, obtained from an analysis of the provenance data, of the plurality of concurrent workflows based on a task completion cost function.

### Claim 5 (depends on 1)

The method of claim 1, wherein the provenance data additionally comprises telemetry data, and wherein the mapping is further based on a predefined similarity metric with respect to a consumption of one or more resources by the first intermediate state and the second intermediate state.

### Claim 6 (depends on 5)

The method of claim 5, wherein the consumption of resources by the first intermediate state and the second intermediate state correlate with a type of work being executed for the first state and the second state, and wherein the mapping further comprises the step of aligning the telemetry data for two different workflow executions.

### Claim 7 (depends on 1)

The method of claim 1, wherein said mapping is performed for a first plurality of said intermediate states in said first execution trace to a second plurality of said intermediate states in said second execution trace such that ordering relations between states in said first plurality of intermediate states is preserved in said second plurality of intermediate states.

### Claim 8

A system, comprising:
a memory; and
at least one processing device, coupled to the memory, operative to implement the following steps:
obtaining a state of one or more workflow executions of a plurality of concurrent workflows in a shared infrastructure environment with a plurality of different resource allocation configurations, wherein said state comprises provenance data of said concurrent workflows;
obtaining a first execution trace of the concurrent workflows representing a first resource allocation configuration, and a second execution trace of the concurrent workflows representing a second resource allocation configuration;
identifying a first set of first states in said first execution trace and a second set of second states in said second execution trace as corresponding anchor states;
mapping, using the at least one processing device, a first intermediate state between a pair of said anchor states in said first execution trace to a second intermediate state between a pair of said anchor states in said second execution trace using the provenance data such that said second intermediate state is between the anchor states in said second execution trace that correspond to said pair of anchor states in the first execution trace;
generating a simulation model of said one or more workflow executions representing a plurality of the different configurations of the resource allocation; and
generating, using the at least one processing device, one or more new simulation traces of said one or more workflow executions with one or more resource allocation configurations that are not represented in the provenance data.

### Claim 9 (depends on 8)

The system of claim 8, wherein the first intermediate state and the second intermediate state are between two anchor states that satisfy predefined task completion criteria and the mapping of the first intermediate state to the second intermediate state is based on a linear mapping between the two anchor states.

### Claim 10 (depends on 8)

The system of claim 8, wherein the mapping is based on a completion of tasks, obtained from an analysis of the provenance data, of the plurality of concurrent workflows.

### Claim 11 (depends on 8)

The system of claim 8, wherein the provenance data indicates a number of substantially completed tasks of each type for each of the plurality of concurrent workflows, and wherein the mapping is based on a partial completion of tasks, obtained from an analysis of the provenance data, of the plurality of concurrent workflows based on a task completion cost function.

### Claim 12 (depends on 8)

The system of claim 8, wherein the provenance data additionally comprises telemetry data, and wherein the mapping is further based on a predefined similarity metric with respect to a consumption of one or more resources by the first intermediate state and the second intermediate state.

### Claim 13 (depends on 12)

The system of claim 12, wherein the consumption of resources by the first intermediate state and the second intermediate state correlate with a type of work being executed for the first state and the second state, and wherein the mapping further comprises the step of aligning the telemetry data for two different workflow executions.

### Claim 14 (depends on 8)

The system of claim 8, wherein said mapping is performed for a first plurality of said intermediate states in said first execution trace to a second plurality of said intermediate states in said second execution trace such that ordering relations between states in said first plurality of intermediate states is preserved in said second plurality of intermediate states.

### Claim 15

A computer program product, comprising a tangible machine-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed by at least one processing device perform the following steps:
obtaining a state of one or more workflow executions of a plurality of concurrent workflows in a shared infrastructure environment with a plurality of different resource allocation configurations, wherein said state comprises provenance data of said concurrent workflows;
obtaining a first execution trace of the concurrent workflows representing a first resource allocation configuration, and a second execution trace of the concurrent workflows representing a second resource allocation configuration;
identifying a first set of first states in said first execution trace and a second set of second states in said second execution trace as corresponding anchor states;
mapping, using the at least one processing device, a first intermediate state between a pair of said anchor states in said first execution trace to a second intermediate state between a pair of said anchor states in said second execution trace using the provenance data such that said second intermediate state is between the anchor states in said second execution trace that correspond to said pair of anchor states in the first execution trace;
generating a simulation model of said one or more workflow executions representing a plurality of the different configurations of the resource allocation; and
generating, using the at least one processing device, one or more new simulation traces of said one or more workflow executions with one or more resource allocation configurations that are not represented in the provenance data.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein the first intermediate state and the second intermediate state are between two anchor states that satisfy predefined task completion criteria and the mapping of the first intermediate state to the second intermediate state is based on a linear mapping between the two anchor states.

### Claim 17 (depends on 15)

The computer program product of claim 15, wherein the mapping is based on a completion of tasks, obtained from an analysis of the provenance data, of the plurality of concurrent workflows.

### Claim 18 (depends on 15)

The computer program product of claim 15, wherein the provenance data indicates a number of substantially completed tasks of each type for each of the plurality of concurrent workflows, and wherein the mapping is based on a partial completion of tasks, obtained from an analysis of the provenance data, of the plurality of concurrent workflows based on a task completion cost function.

### Claim 19 (depends on 15)

The computer program product of claim 15, wherein the provenance data additionally comprises telemetry data, and wherein the mapping is further based on a predefined similarity metric with respect to a consumption of one or more resources by the first intermediate state and the second intermediate state.

### Claim 20 (depends on 15)

The computer program product of claim 15, wherein said mapping is performed for a first plurality of said intermediate states in said first execution trace to a second plurality of said intermediate states in said second execution trace such that ordering relations between states in said first plurality of intermediate states is preserved in said second plurality of intermediate states.
