DISC 2017 October 16-20, 2017 - Vienna, Austria

31st International Symposium on Distributed Computing (DISC 2017)



Andréa W. Richa (Ed.)
ISBN 978-3-95977-053-8, LIPICS Vol. 91 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 30 MB)
Search Publication Server


Authors
  • Abraham, Ittai
  • Afek, Yehuda
  • Aguilera, Marcos K.
  • Arbel-Raviv, Maya
  • Avin, Chen
  • Balakrishnan, Mahesh
  • Balliu, Alkida
  • Becker, Ruben
  • Blin, Lélia
  • Bouchard, Sébastien
  • Bournat, Marjorie
  • Bringmann, Karl
  • Brown, Trevor
  • Burckhardt, Sebastian
  • Cachin, Christian
  • Calciu, Irina
  • Censor-Hillel, Keren
  • Chakrabarti, Dhruva R.
  • Chan, David Yu Cheng
  • Choudhury, Ashish
  • Clementi, Andrea
  • Cooper, Colin
  • Devadas, Srinivas
  • Dieudonné, Yoann
  • Di Luna, Giuseppe A.
  • Dubois, Swan
  • Eguchi, Ryota
  • Emek, Yuval
  • Even, Guy
  • Felber, Pascal
  • Feuilloley, Laurent
  • Fischer, Manuela
  • Fischer, Orr
  • Flocchini, Paola
  • Fraigniaud, Pierre
  • Friedman, Michal
  • Függer, Matthias
  • Garg, Vijay K.
  • Garimella, Gayathri
  • Gelashvili, Rati
  • Ghaffari, Mohsen
  • Ghodselahi, Abdolhamid
  • Gonen, Tzlil
  • Gotsman, Alexey
  • Goussevskaia, Olga
  • Grossman, Ofer
  • Gualà, Luciano
  • Hadzilacos, Vassos
  • Halldórsson, Magnús M.
  • Hazan, Itay
  • Herlihy, Maurice
  • He, Yuan
  • Hirvonen, Juho
  • Imbs, Damien
  • Issa, Shady
  • Izraelevitz, Joseph
  • Izumi, Taisuke
  • Jahja, Irvan
  • Jayanti, Prasad
  • Joshi, Anup
  • Jurdzínski, Tomasz
  • Kanade, Varun
  • Karrenbauer, Andreas
  • Keidar, Idit
  • Kelly, Terence
  • Kermarrec, Anne-Marie
  • Khoury, Seri
  • Kol, Gillat
  • Kolikant, Noa
  • Korhonen, Janne H.
  • Krinninger, Sebastian
  • Kuhn, Fabian
  • Kushilevitz, Eyal
  • Kuznetsov, Petr
  • Lenzen, Christoph
  • Levi, Reut
  • Lymouri, Christiana
  • Lynch, Nancy
  • Malkhi, Dahlia
  • Mallmann-Trenn, Frederik
  • Marathe, Virendra
  • Massoulié, Laurent
  • Matveev, Alexander
  • Maus, Yannic
  • Medina, Moti
  • Mendes, Hammurabi
  • Michael, Ellis
  • Mondal, Kaushik
  • Montealegre, Pedro
  • Morrey III, Charles B.
  • Mostéfaoui, Achour
  • Musco, Cameron
  • Nawab, Faisal
  • Nayak, Kartik
  • Newport, Calvin
  • Nowak, Thomas
  • Nowicki, Krzysztof
  • Olivetti, Dennis
  • Oshman, Rotem
  • Pai, Shreyas
  • Pandurangan, Gopal
  • Parter, Merav
  • Pasquale, Francesco
  • Pass, Rafael
  • Patra, Arpita
  • Paz, Ami
  • Pemmaraju, Sriram V.
  • Peres, Bruna S.
  • Perrin, Matthieu
  • Petit, Franck
  • Petrank, Erez
  • Ports, Dan R. K.
  • Radzik, Tomasz
  • Randall, Dana
  • Rapaport, Ivan
  • Ravi, Divya
  • Ravi, Srivatsan
  • Raynal, Michel
  • Ren, Ling
  • Riaz, Talal
  • Richa, Andréa
  • Rieutord, Thibault
  • Rivera, Nicolás
  • Robinson, Peter
  • Romano, Paolo
  • Rybicki, Joel
  • Sadeh, Dafna
  • Santoro, Nicola
  • Sarkar, Pratik
  • Schmid, Stefan
  • Schwartzman, Gregory
  • Schwarz, Manfred
  • Scornavacca, Giacomo
  • Scott, Michael L.
  • Sen, Siddhartha
  • Sharma, Naveen Kr.
  • Shi, Elaine
  • Shiraga, Takeharu
  • Spiegelman, Alexander
  • Suomela, Jukka
  • Szekeres, Adriana
  • Tixeuil, Sébastien
  • Todinca, Ioan
  • Toueg, Sam
  • Uitto, Jara
  • Varloot, Rémi
  • Verdugo, Victor
  • Viglietta, Giovanni
  • Vukolic, Marko
  • Wattenhofer, Roger
  • Yamashita, Masafumi
  • Yamauchi, Yukiko
  • Yu, Haifeng
  • Zhao, Yuda

  •   
    Front Matter, Table of Contents, Preface, Symposium Organization, Awards
    Authors: Richa, Andréa

    Abstract | Document (1,244 KB) | BibTeX

    Blockchain Consensus Protocols in the Wild (Keynote Talk)
    Authors: Cachin, Christian ; Vukolic, Marko

    Abstract | Document (501 KB) | BibTeX

    Recommenders: from the Lab to the Wild (Keynote Talk)
    Authors: Kermarrec, Anne-Marie

    Abstract | Document (201 KB) | BibTeX

    Phase Transitions and Emergent Phenomena in Random Structures and Algorithms (Keynote Talk)
    Authors: Randall, Dana

    Abstract | Document (262 KB) | BibTeX

    Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors
    Authors: Arbel-Raviv, Maya ; Brown, Trevor

    Abstract | Document (1,811 KB) | BibTeX

    Demand-Aware Network Designs of Bounded Degree
    Authors: Avin, Chen ; Mondal, Kaushik ; Schmid, Stefan

    Abstract | Document (549 KB) | BibTeX

    Certification of Compact Low-Stretch Routing Schemes
    Authors: Balliu, Alkida ; Fraigniaud, Pierre

    Abstract | Document (599 KB) | BibTeX

    Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
    Authors: Becker, Ruben ; Karrenbauer, Andreas ; Krinninger, Sebastian ; Lenzen, Christoph

    Abstract | Document (614 KB) | BibTeX

    Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm
    Authors: Bouchard, Sébastien ; Bournat, Marjorie ; Dieudonné, Yoann ; Dubois, Swan ; Petit, Franck

    Abstract | Document (441 KB) | BibTeX

    Cost of Concurrency in Hybrid Transactional Memory
    Authors: Brown, Trevor ; Ravi, Srivatsan

    Abstract | Document (2,191 KB) | BibTeX

    Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
    Authors: Censor-Hillel, Keren ; Khoury, Seri ; Paz, Ami

    Abstract | Document (631 KB) | BibTeX

    Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
    Authors: Censor-Hillel, Keren ; Parter, Merav ; Schwartzman, Gregory

    Abstract | Document (546 KB) | BibTeX

    On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects
    Authors: Chan, David Yu Cheng ; Hadzilacos, Vassos ; Toueg, Sam

    Abstract | Document (533 KB) | BibTeX

    Fast Plurality Consensus in Regular Expanders
    Authors: Cooper, Colin ; Radzik, Tomasz ; Rivera, Nicolás ; Shiraga, Takeharu

    Abstract | Document (523 KB) | BibTeX

    Meeting in a Polygon by Anonymous Oblivious Robots
    Authors: Di Luna, Giuseppe A. ; Flocchini, Paola ; Santoro, Nicola ; Viglietta, Giovanni ; Yamashita, Masafumi

    Abstract | Document (507 KB) | BibTeX

    Three Notes on Distributed Property Testing
    Authors: Even, Guy ; Fischer, Orr ; Fraigniaud, Pierre ; Gonen, Tzlil ; Levi, Reut ; Medina, Moti ; Montealegre, Pedro ; Olivetti, Dennis ; Oshman, Rotem ; Rapaport, Ivan ; Todinca, Ioan

    Abstract | Document (898 KB) | BibTeX

    Error-Sensitive Proof-Labeling Schemes
    Authors: Feuilloley, Laurent ; Fraigniaud, Pierre

    Abstract | Document (542 KB) | BibTeX

    Improved Deterministic Distributed Matching via Rounding
    Authors: Fischer, Manuela

    Abstract | Document (545 KB) | BibTeX

    Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
    Authors: Fischer, Manuela ; Ghaffari, Mohsen

    Abstract | Document (564 KB) | BibTeX

    Improved Distributed Degree Splitting and Edge Coloring
    Authors: Ghaffari, Mohsen ; Hirvonen, Juho ; Kuhn, Fabian ; Maus, Yannic ; Suomela, Jukka ; Uitto, Jara

    Abstract | Document (869 KB) | BibTeX

    Simple and Near-Optimal Distributed Coloring for Sparse Graphs
    Authors: Ghaffari, Mohsen ; Lymouri, Christiana

    Abstract | Document (491 KB) | BibTeX

    Near-Optimal Distributed DFS in Planar Graphs
    Authors: Ghaffari, Mohsen ; Parter, Merav

    Abstract | Document (986 KB) | BibTeX

    Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
    Authors: Ghodselahi, Abdolhamid ; Kuhn, Fabian

    Abstract | Document (558 KB) | BibTeX

    Consistency Models with Global Operation Sequencing and their Composition
    Authors: Gotsman, Alexey ; Burckhardt, Sebastian

    Abstract | Document (693 KB) | BibTeX

    Improved Deterministic Distributed Construction of Spanners
    Authors: Grossman, Ofer ; Parter, Merav

    Abstract | Document (614 KB) | BibTeX

    An Efficient Communication Abstraction for Dense Wireless Networks
    Authors: Halldórsson, Magnús M. ; Kuhn, Fabian ; Lynch, Nancy ; Newport, Calvin

    Abstract | Document (485 KB) | BibTeX

    Two-Party Direct-Sum Questions Through the Lens of Multiparty Communication Complexity
    Authors: Hazan, Itay ; Kushilevitz, Eyal

    Abstract | Document (475 KB) | BibTeX

    Which Broadcast Abstraction Captures k-Set Agreement?
    Authors: Imbs, Damien ; Mostéfaoui, Achour ; Perrin, Matthieu ; Raynal, Michel

    Abstract | Document (605 KB) | BibTeX

    Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume
    Authors: Issa, Shady ; Felber, Pascal ; Matveev, Alexander ; Romano, Paolo

    Abstract | Document (589 KB) | BibTeX

    Some Lower Bounds in Dynamic Networks with Oblivious Adversaries
    Authors: Jahja, Irvan ; Yu, Haifeng ; Zhao, Yuda

    Abstract | Document (702 KB) | BibTeX

    Recoverable FCFS Mutual Exclusion with Wait-Free Recovery
    Authors: Jayanti, Prasad ; Joshi, Anup

    Abstract | Document (535 KB) | BibTeX

    Interactive Compression for Multi-Party Protocol
    Authors: Kol, Gillat ; Oshman, Rotem ; Sadeh, Dafna

    Abstract | Document (609 KB) | BibTeX

    Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
    Authors: Lenzen, Christoph ; Rybicki, Joel

    Abstract | Document (861 KB) | BibTeX

    Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks
    Authors: Lynch, Nancy ; Musco, Cameron ; Parter, Merav

    Abstract | Document (867 KB) | BibTeX

    How Large Is Your Graph?
    Authors: Kanade, Varun ; Mallmann-Trenn, Frederik ; Verdugo, Victor

    Abstract | Document (610 KB) | BibTeX

    Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems
    Authors: Mendes, Hammurabi ; Herlihy, Maurice

    Abstract | Document (510 KB) | BibTeX

    Recovering Shared Objects Without Stable Storage
    Authors: Michael, Ellis ; Ports, Dan R. K. ; Sharma, Naveen Kr. ; Szekeres, Adriana

    Abstract | Document (525 KB) | BibTeX

    Dalí: A Periodically Persistent Hash Map
    Authors: Nawab, Faisal ; Izraelevitz, Joseph ; Kelly, Terence ; Morrey III, Charles B. ; Chakrabarti, Dhruva R. ; Scott, Michael L.

    Abstract | Document (650 KB) | BibTeX

    Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
    Authors: Pai, Shreyas ; Pandurangan, Gopal ; Pemmaraju, Sriram V. ; Riaz, Talal ; Robinson, Peter

    Abstract | Document (665 KB) | BibTeX

    Hybrid Consensus: Efficient Consensus in the Permissionless Model
    Authors: Pass, Rafael ; Shi, Elaine

    Abstract | Document (560 KB) | BibTeX

    Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution
    Authors: Spiegelman, Alexander ; Keidar, Idit ; Malkhi, Dahlia

    Abstract | Document (630 KB) | BibTeX

    Brief Announcement: Practical Synchronous Byzantine Consensus
    Authors: Abraham, Ittai ; Devadas, Srinivas ; Nayak, Kartik ; Ren, Ling

    Abstract | Document (340 KB) | BibTeX

    Brief Announcement: The Synergy of Finite State Machines
    Authors: Afek, Yehuda ; Emek, Yuval ; Kolikant, Noa

    Abstract | Document (303 KB) | BibTeX

    Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs
    Authors: Blin, Lélia ; Tixeuil, Sébastien

    Abstract | Document (325 KB) | BibTeX

    Brief Announcement: A Note on Hardness of Diameter Approximation
    Authors: Bringmann, Karl ; Krinninger, Sebastian

    Abstract | Document (358 KB) | BibTeX

    Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures
    Authors: Calciu, Irina ; Sen, Siddhartha ; Balakrishnan, Mahesh ; Aguilera, Marcos K.

    Abstract | Document (680 KB) | BibTeX

    Brief Announcement: Crash-Tolerant Consensus in Directed Graph Revisited
    Authors: Choudhury, Ashish ; Garimella, Gayathri ; Patra, Arpita ; Ravi, Divya ; Sarkar, Pratik

    Abstract | Document (341 KB) | BibTeX

    Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors
    Authors: Clementi, Andrea ; Gualà, Luciano ; Pasquale, Francesco ; Scornavacca, Giacomo

    Abstract | Document (408 KB) | BibTeX

    Brief Announcement: Shape Formation by Programmable Particles
    Authors: Di Luna, Giuseppe A. ; Flocchini, Paola ; Santoro, Nicola ; Viglietta, Giovanni ; Yamauchi, Yukiko

    Abstract | Document (328 KB) | BibTeX

    Brief Announcement: Fast Aggregation in Population Protocols
    Authors: Eguchi, Ryota ; Izumi, Taisuke

    Abstract | Document (305 KB) | BibTeX

    Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory
    Authors: Friedman, Michal ; Herlihy, Maurice ; Marathe, Virendra ; Petrank, Erez

    Abstract | Document (360 KB) | BibTeX

    Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks
    Authors: Függer, Matthias ; Nowak, Thomas ; Schwarz, Manfred

    Abstract | Document (407 KB) | BibTeX

    Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem
    Authors: Garg, Vijay K.

    Abstract | Document (391 KB) | BibTeX

    Brief Announcement: Towards Reduced Instruction Sets for Synchronization
    Authors: Gelashvili, Rati ; Keidar, Idit ; Spiegelman, Alexander ; Wattenhofer, Roger

    Abstract | Document (373 KB) | BibTeX

    Brief Announcement: On Connectivity in the Broadcast Congested Clique
    Authors: Jurdzínski, Tomasz ; Nowicki, Krzysztof

    Abstract | Document (405 KB) | BibTeX

    Brief Announcement: Towards a Complexity Theory for the Congested Clique
    Authors: Korhonen, Janne H. ; Suomela, Jukka

    Abstract | Document (371 KB) | BibTeX

    Brief Announcement: Compact Topology of Shared-Memory Adversaries
    Authors: Kuznetsov, Petr ; Rieutord, Thibault ; He, Yuan

    Abstract | Document (435 KB) | BibTeX

    Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem
    Authors: Lenzen, Christoph ; Levi, Reut

    Abstract | Document (414 KB) | BibTeX

    Brief Announcement: Distributed SplayNets
    Authors: Peres, Bruna S. ; Goussevskaia, Olga ; Schmid, Stefan ; Avin, Chen

    Abstract | Document (404 KB) | BibTeX

    Brief Announcement: Rapid Mixing of Local Dynamics on Graphs
    Authors: Massoulié, Laurent ; Varloot, Rémi

    Abstract | Document (323 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI