×

How to sign paper contracts? Conjectures and evidence related to equitable and efficient collaborative task scheduling. (English) Zbl 1314.68083

Koç, Çetin Kaya (ed.), Open problems in mathematics and computational science. Based on the presentations at the conference, Istanbul, Turkey, September 18–20, 2013. Cham: Springer (ISBN 978-3-319-10682-3/hbk; 978-3-319-10683-0/ebook). 317-340 (2014).
Summary: This chapter explores ways of performing a kind of commutative task by \(N\) parties, of which a particular scenario of contract signing is a canonical example. Tasks are defined as commutative if the order in which parties perform them 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 of this conjecture. We also explore the most equitable commutative task protocols.
For the entire collection see [Zbl 1314.00108].

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI