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 de l'École normale supérieure, 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 :
Type de document :
Rapport
[Research Report] IACR Cryptology ePrint Archive 2013: 432 (2013), 2013

https://hal.inria.fr/hal-00934338
Contributeur : David Naccache <>
Soumis le : mardi 21 janvier 2014 - 20:38:04
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

• 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〉

Métriques

Consultations de la notice