Authors
James Aspnes, He Yang Er, Hagit Attiya, Constantin Enea, Mirza Ahad Baig, Danny Hendler, Alessia Milani, Corentin Travers, Ruben Becker, Yuval Emek, Mohsen Ghaffari, Christoph Lenzen, Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman, Shimon Bitton, Taisuke Izumi, Shay Kutten, Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal, Janna Burman, Joffroy Beauquier, Devan Sohier, Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic, Shiri Chechik, Doron Mukhtar, Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky, Pierluigi Crescenzi, Pierre Fraigniaud, Ami Paz, Michael Dinitz, Magnús M Halldórsson, Calvin Newport, Alex Weaver, Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, Pawel Garncarek, Tomasz Jurdzinski, Dariusz R Kowalski, Julian Portmann, Seth Gilbert, James Maguire, Wei Quan Lim, Éric Goubault, Marijana Lazic, Jérémy Ledent, Sergio Rajsbaum, Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Dragos-Adrian Seredinschi, Kristian Hinnenthal, Christian Scheideler, Martijn Struijs, Artem Khyzha, Alexey Gotsman, Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Christian Konrad, Sriram V Pemmaraju, Talal Riaz, Peter Robinson, Giuliano Losa, Eli Gafni, David Mazières, Ruslan Nikolaev, Thomas Nowak, Joel Rybicki, Merav Parter, Adones Rukundo, Aras Atalar, Philippas Tsigas, Nobutaka Shimizu, Takeharu Shiraga, Hsin-Hao Su, Hoa T Vu, Mohammad Taheri, Arash Pourdamghani, Mohsen Lesani, Chen Avin, Iosif Salem, Stefan Schmid, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Publication date
2019
Publisher
Schloss Dagstuhl-Leibniz-Zentrum für Informatik GmbH
Description
We consider the problem of implementing randomized wait-free consensus from max registers under the assumption of an oblivious adversary. We show that max registers solve m-valued consensus for arbitrary m in expected O (log^* n) steps per process, beating the Omega (log m/log log m) lower bound for ordinary registers when m is large and the best previously known O (log log n) upper bound when m is small. A simple max-register implementation based on double-collect snapshots translates this result into an O (n log n) expected step implementation of m-valued consensus from n single-writer registers, improving on the best previously-known bound of O (n log^ 2 n) for single-writer registers.
Scholar articles
J Suomela, J Aspnes, HY Er, H Attiya, C Enea, MA Baig… - 2019