# How to Sign Paper Contracts? Conjectures & Evidence Related to Equitable & Efficient Collaborative Task Scheduling

3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : This paper explores ways of performing commutative tasks by $N$ parties. Tasks are defined as {\sl commutative} if the order at which parties perform tasks can be freely changed without affecting the final result. It is easy to see that arbitrary $N$-party commutative tasks cannot be completed in less than $N-1$ basic time units. We conjecture that arbitrary $N$-party commutative tasks cannot be performed in $N-1$ time units by exchanging less than $4N-6$ messages and provide computational evidence in favor this conjecture. We also explore the most equitable commutative task protocols.
Keywords :
Document type :
Reports

https://hal.inria.fr/hal-00934338
Contributor : David Naccache Connect in order to contact the contributor
Submitted on : Tuesday, January 21, 2014 - 8:38:04 PM
Last modification on : Thursday, June 23, 2022 - 3:49:35 AM

### Identifiers

• HAL Id : hal-00934338, version 1

### Citation

Eric Brier, David Naccache, Li-Yao Xia. How to Sign Paper Contracts? Conjectures & Evidence Related to Equitable & Efficient Collaborative Task Scheduling. [Research Report] IACR Cryptology ePrint Archive 2013: 432 (2013), 2013. ⟨hal-00934338⟩

Record views