TY - GEN
T1 - Data Centric Workflows for Crowdsourcing
AU - Bourhis, Pierre
AU - Hélouët, Loïc
AU - Miklos, Zoltan
AU - Singh, Rituraj
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-030-51831-8_2
DO - 10.1007/978-3-030-51831-8_2
M3 - Conference contribution
AN - SCOPUS:85088265175
SN - 9783030518301
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 24
EP - 45
BT - Application and Theory of Petri Nets and Concurrency - 41st International Conference, PETRI NETS 2020, Proceedings
A2 - Janicki, Ryszard
A2 - Sidorova, Natalia
A2 - Chatain, Thomas
PB - Springer
T2 - 41st International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2020
Y2 - 24 June 2020 through 25 June 2020
ER -