Synchronous, with a Chance of Partition Tolerance

Yue Guo; Rafael Pass; Elaine Shi

Paper 2019/179

Synchronous, with a Chance of Partition Tolerance

Yue Guo, Rafael Pass, and Elaine Shi

Abstract

Murphy, Murky, Mopey, Moody, and Morose decide to write a paper together over the Internet and submit it to the prestigious CRYPTO’19 conference that has the most amazing PC. They encounter a few problems. First, not everyone is online every day: some are lazy and go skiing on Mondays; others cannot use git correctly and they are completely unaware that they are losing messages. Second, a small subset of the co-authors may be secretly plotting to disrupt the project (e.g., because they are writing a competing paper in stealth). Suppose that each day, sufficiently many honest co-authors are online (and use git correctly); moreover, suppose that messages checked into git on Monday can be correctly received by honest and online co-authors on Tuesday or any future day. Can the honest co-authors successfully finish the paper in a small number of days such that they make the CRYPTO deadline; and perhaps importantly, can all the honest co-authors, including even those who are lazy and those who sometimes use git incorrectly, agree on the final theorem?

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in CRYPTO 2019
Keywords: synchronous Byzantine Agreement modeling partition tolerance MPC
Contact author(s): runting @ gmail com
History: 2019-05-20: revised; 2019-02-26: received; See all versions
Short URL: https://ia.cr/2019/179
License: CC BY

BibTeX

@misc{cryptoeprint:2019/179,
      author = {Yue Guo and Rafael Pass and Elaine Shi},
      title = {Synchronous, with a Chance of Partition Tolerance},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/179},
      year = {2019},
      url = {https://eprint.iacr.org/2019/179}
}