Data Centric Workflows for Crowdsourcing
- 30 June 2020
- book chapter
- conference paper
- Published by Springer Science and Business Media LLC
- Vol. 12152, 24-45
- https://doi.org/10.1007/978-3-030-51831-8_2
Abstract
Crowdsourcing consists in hiring workers on internet to perform large amounts of simple, independent and replicated work units, before assembling the returned results. A challenge to solve intricate problems is to define orchestrations of tasks, and allow higher-order answers where workers can suggest a process to obtain data rather than a plain answer. Another challenge is to guarantee that an orchestration with correct input data terminates, and produces correct output data. This work proposes complex workflows, a data-centric model for crowdsourcing based on orchestration of concurrent tasks and higher order schemes. We consider termination (whether some/all runs of a complex workflow terminate) and correctness (whether some/all runs of a workflow terminate with data satisfying FO requirements). We show that existential termination/correctness are undecidable in general excepted for specifications with bounded recursion. However, universal termination/correctness are decidable when constraints on inputs are specified in a decidable fragment of FO, and are at least in \(co\!-\!2EXPTIME\).
Keywords
This publication has 27 references indexed in Scilit:
- A Holistic Approach for Soundness Verification of Decision-Aware Process ModelsPublished by Springer Science and Business Media LLC ,2018
- Petri Nets with Structured DataFundamenta Informaticae, 2016
- Challenges in Data CrowdsourcingIEEE Transactions on Knowledge and Data Engineering, 2016
- Collaborative data-driven workflowsPublished by Association for Computing Machinery (ACM) ,2013
- Artifact systems with data dependencies and arithmeticACM Transactions on Database Systems, 2012
- Static analysis of active XML systemsACM Transactions on Database Systems, 2009
- Verification of communicating data-driven web servicesPublished by Association for Computing Machinery (ACM) ,2006
- Coloured petri nets: A high level language for system design and analysisLecture Notes in Computer Science, 1991
- Dual regularization of linear programming problemsUSSR Computational Mathematics and Mathematical Physics, 1980
- Guarded commands, nondeterminacy and formal derivation of programsCommunications of the ACM, 1975