Skip to Main content Skip to Navigation
Reports

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

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/hal-00934338
Contributor : David Naccache <>
Submitted on : Tuesday, January 21, 2014 - 8:38:04 PM
Last modification on : Thursday, July 1, 2021 - 5:58:06 PM

Identifiers

  • HAL Id : hal-00934338, version 1

Collections

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⟩

Share

Metrics

Record views

260