Data Centric Workflows for Crowdsourcing

Pierre Bourhis 1 Loïc Hélouët 2 Rituraj Singh 3 Zoltán Miklós 3
1 SPIRALS - Self-adaptation for distributed services and large software systems
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
2 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Crowdsourcing is a major paradigm to accomplish works that require human skills, by paying a small sum of money and drawing workers all across the globe. However, crowdsourcing platforms are mainly ways to solve large amounts of relatively simple and independent replicated work units. A natural extension of crowdsourcing is to enhance the definition of work, and solve more intricate problems, via orchestrations of tasks, and via higher-order, i.e. allowing workers to suggest a process to obtain data rather than a returning a plain answer. This work proposes complex workflows, a data centric workflow model for crowdsourcing. The model allows orchestration of simple tasks and concurrency. It handles data and crowdworkers and provides high-level constructs to decompose complex tasks into orchestrations of simpler subtasks. We consider termination questions: We show that existential termination (existence of at least one terminating run) is undecidable excepted for specifications with bounded recursion. On the other hand, universal termination (whether all runs of a complex workflow terminate) is decidable (and at least in co−2EXPTIME) when constraints on inputs are specified in a decidable fragment of FO. We then address correctness problems. We use FO formulas to specify dependencies between input and output data of a complex workflow. If dependencies are specified with a decidable fragment of FO, then universal correctness (whether all terminating runs satisfy dependencies) is decidable , and existential correctness (whether some terminating runs satisfy dependencies) is decidable with some restrictions.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-01976280
Contributor : Loic Helouet <>
Submitted on : Sunday, September 15, 2019 - 10:31:54 PM
Last modification on : Wednesday, September 18, 2019 - 1:14:16 AM

File

compwork.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01976280, version 2

Citation

Pierre Bourhis, Loïc Hélouët, Rituraj Singh, Zoltán Miklós. Data Centric Workflows for Crowdsourcing. 2019. ⟨hal-01976280v2⟩

Share

Metrics

Record views

34

Files downloads

232