Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Data Centric Workflows for Crowdsourcing

Loïc Hélouët 1 Rituraj Singh 2 Zoltán Miklós 2
1 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 [20 references]  Display  Hide  Download
Contributor : Loic Helouet <>
Submitted on : Wednesday, January 9, 2019 - 9:45:55 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:43 PM


Files produced by the author(s)


  • HAL Id : hal-01976280, version 1


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



Record views


Files downloads