39 Search Results for "Pedone, Fernando"

Volume

LIPIcs, Volume 70

20th International Conference on Principles of Distributed Systems (OPODIS 2016)

OPODIS 2016, December 13-16, 2016, Madrid, Spain

Editors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.8
Robust and Fast Blockchain State Synchronization

Authors: Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
State synchronization, the process by which a new or recovering peer catches up with the state of other operational peers, is critical to the operation of blockchain-based systems. Existing approaches to state synchronization typically involve downloading snapshots of system state. Such approaches introduce an attack vector from malicious peers that can significantly degrade performance. Moreover, the process of creating snapshots leads to performance hiccups. This paper presents a technique for peers to catch up with operational peers without trusting any particular peer and gracefully recover from misbehavior during the process. We have integrated our design into a production blockchain middleware. Our evaluation shows that during operation, the transaction throughput is consistently higher without pauses for snapshot construction. Moreover, the time it takes for a new peer to join the blockchain is halved, while at the same time tolerating Byzantine peers.
Cite as

Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone. Robust and Fast Blockchain State Synchronization. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fynn_et_al:LIPIcs.OPODIS.2022.8,
  author =	{Fynn, Enrique and Buchman, Ethan and Milosevic, Zarko and Soul\'{e}, Robert and Pedone, Fernando},
  title =	{{Robust and Fast Blockchain State Synchronization}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.8},
  URN =		{urn:nbn:de:0030-drops-176280},
  doi =		{10.4230/LIPIcs.OPODIS.2022.8},
  annote =	{Keywords: state synchronization, replication, blockchain}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2016
LIPIcs, Volume 70, OPODIS'16, Complete Volume

Authors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
LIPIcs, Volume 70, OPODIS'16, Complete Volume
Cite as

20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{fatourou_et_al:LIPIcs.OPODIS.2016,
  title =	{{LIPIcs, Volume 70, OPODIS'16, Complete Volume}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016},
  URN =		{urn:nbn:de:0030-drops-71111},
  doi =		{10.4230/LIPIcs.OPODIS.2016},
  annote =	{Keywords: Distributed Systems, Performance of Systems, Concurrent Programming, Data Structures, Modes of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2016.0
Front Matter, Table of Contents, Preface, Committees, List of Authors

Authors: Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Front Matter, Table of Contents, Preface, Committees, List of Authors
Cite as

20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.OPODIS.2016.0,
  author =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  title =	{{Front Matter, Table of Contents, Preface, Committees, List of Authors}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.0},
  URN =		{urn:nbn:de:0030-drops-70699},
  doi =		{10.4230/LIPIcs.OPODIS.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committees, List of Authors}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.1
High Throughput Connectomics (Keynote Abstract)

Authors: Nir Shavit

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Connectomics is an emerging field of neurobiology that uses cutting edge machine learning and image processing to extract brain connectivity graphs from electron microscopy images. It has long been assumed that the processing of connectomics data will require mass storage and farms of CPUs and GPUs and will take months if not years. This talk will discuss the feasibility of designing a high-throughput connectomics-on-demand system that runs on a multicore machine with less than 100 cores and extracts connectomes at the terabyte per hour pace of modern electron microscopes. Building this system required solving algorithmic and performance engineering issues related to scaling machine learning on multicore architectures, and may have important lessons for other problem spaces in the natural sciences, where until now large distributed server or GPU farms seemed to be the only way to go.
Cite as

Nir Shavit. High Throughput Connectomics (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{shavit:LIPIcs.OPODIS.2016.1,
  author =	{Shavit, Nir},
  title =	{{High Throughput Connectomics}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.1},
  URN =		{urn:nbn:de:0030-drops-70705},
  doi =		{10.4230/LIPIcs.OPODIS.2016.1},
  annote =	{Keywords: Machine learning, multicore architectures}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.2
Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract)

Authors: Christian Cachin

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A blockchain is a public ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Distributed protocols tolerating faults and adversarial attacks, coupled with cryptographic tools are needed for this. The recent interest in blockchains has revived research on consensus protocols, ranging from the proof-of-work method in Bitcoin's "mining" protocol to classical Byzantine agreement. Going far beyond its use in cryptocurrencies, blockchain is today viewed as a promising technology to simplify trusted exchanges of data and goods among companies. In this context, the Hyperledger Project has been established in early 2016 as an industry-wide collaborative effort to develop an open-source blockchain. This talk will present an overview of blockchain concepts, cryptographic building blocks and consensus mechanisms. It will also introduce Hyperledger Fabric, an implementation of blockchain technology intended for enterprise applications. Being one of the key partners in the Hyperledger Project, IBM is actively involved in the development of this blockchain platform.
Cite as

Christian Cachin. Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cachin:LIPIcs.OPODIS.2016.2,
  author =	{Cachin, Christian},
  title =	{{Blockchain - From the Anarchy of Cryptocurrencies to the Enterprise}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.2},
  URN =		{urn:nbn:de:0030-drops-70719},
  doi =		{10.4230/LIPIcs.OPODIS.2016.2},
  annote =	{Keywords: consensus, cryptographic, distributed protocols}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.3
Really Big Data: Analytics on Graphs with Trillions of Edges (Keynote Abstract)

Authors: Willy Zwaenepoel

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Big graphs occur naturally in many applications, most obviously in social networks, but also in many other areas such as biology and forensics. Current approaches to processing large graphs use either supercomputers or very large clusters. In both cases the entire graph must reside in memory before it can be processed. We are pursuing an alternative approach, processing graphs from secondary storage. While this comes with a performance penalty, it makes analytics on very large graphs feasible on a small number of commodity machines. We have developed two systems, one for a single machine and one for a cluster of machines. X-Stream, the single machine solution, aims to make all secondary storage access sequential. It uses two techniques to achieve this goal, edge-centric processing and streaming partitions. Chaos, the cluster solution, starts from the observation that there is little benefit to locality when accessing data from secondary storage over a high-speed network. As a result, Chaos spreads graph data uniformly randomly over storage devices, and uses randomized access to achieve I/O balance. Chaos furthermore uses work stealing to achieve computational load balance. By using these techniques, it avoids the need for expensive partitioning during pre-processing, while still achieving good scaling behavior. With Chaos we have been able to process an 8-trillion-edge graph on 32 machines, a new milestone for graph size on a small cluster. I will describe both systems and their performance on a number of benchmarks and in comparison to state-of-the-art alternatives. This is joint work with Laurent Bindschaedler (EPFL), Jasmina Malicevic (EPFL) and Amitabha Roy (Intel Labs).
Cite as

Willy Zwaenepoel. Really Big Data: Analytics on Graphs with Trillions of Edges (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{zwaenepoel:LIPIcs.OPODIS.2016.3,
  author =	{Zwaenepoel, Willy},
  title =	{{Really Big Data: Analytics on Graphs with Trillions of Edges}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.3},
  URN =		{urn:nbn:de:0030-drops-70724},
  doi =		{10.4230/LIPIcs.OPODIS.2016.3},
  annote =	{Keywords: large graphs}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.4
Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract)

Authors: Faith Ellen

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The participating set problem can be solved in an asynchronous system using only registers. I will gently explain this problem and its solution, followed by a new extension, called consistent ordered partition. Next, I will present a wait-free simulation by f + 1 processes of any setconsensus algorithm that tolerates f faults. I will also describe how to extend this simulation using consistent ordered partition. Finally, I will discuss how this extension can be used to prove that, within every level m > 1 of the consensus hierarchy, there is an infinite sequence of increasingly more powerful deterministic objects.
Cite as

Faith Ellen. Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ellen:LIPIcs.OPODIS.2016.4,
  author =	{Ellen, Faith},
  title =	{{Participating Sets, Simulations, and the Consensus Hierarchy}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.4},
  URN =		{urn:nbn:de:0030-drops-70736},
  doi =		{10.4230/LIPIcs.OPODIS.2016.4},
  annote =	{Keywords: Consensus, shared-memory systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.5
Bounded Disagreement

Authors: David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A well-known generalization of the consensus problem, namely, set agreement (SA), limits the number of distinct decision values that processes decide. In some settings, it may be more important to limit the number of "disagreers". Thus, we introduce another natural generalization of the consensus problem, namely, bounded disagreement (BD), which limits the number of processes that decide differently from the plurality. More precisely, in a system with n processes, the (n, l)-BD task has the following requirement: there is a value v such that at most l processes (the disagreers) decide a value other than v. Despite their apparent similarities, the results described below show that bounded disagreement, consensus, and set agreement are in fact fundamentally different problems. We investigate the relationship between bounded disagreement, consensus, and set agreement. In particular, we determine the consensus number for every instance of the BD task. We also determine values of n, l, m, and k such that the (n, l)-BD task can solve the (m, k)-SA task (where m processes can decide at most k distinct values). Using our results and a previously known impossibility result for set agreement, we prove that for all n >= 2, there is a BD task (and a corresponding BD object) that has consensus number n but can not be solved using n-consensus and registers. Prior to our paper, the only objects known to have this unusual characteristic for n >= 2 (which shows that the consensus number of an object is not sufficient to fully capture its power) were artificial objects crafted solely for the purpose of exhibiting this behaviour.
Cite as

David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. Bounded Disagreement. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{yuchengchan_et_al:LIPIcs.OPODIS.2016.5,
  author =	{Yu Cheng Chan, David and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{Bounded Disagreement}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.5},
  URN =		{urn:nbn:de:0030-drops-70742},
  doi =		{10.4230/LIPIcs.OPODIS.2016.5},
  annote =	{Keywords: Consensus, Set Agreement, Asynchronous System, Distributed Algorithms, Shared Memory}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.6
Read-Write Memory and k-Set Consensus as an Affine Task

Authors: Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.
Cite as

Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord. Read-Write Memory and k-Set Consensus as an Affine Task. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gafni_et_al:LIPIcs.OPODIS.2016.6,
  author =	{Gafni, Eli and He, Yuan and Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Read-Write Memory and k-Set Consensus as an Affine Task}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.6},
  URN =		{urn:nbn:de:0030-drops-70759},
  doi =		{10.4230/LIPIcs.OPODIS.2016.6},
  annote =	{Keywords: iterated affine tasks, k-set consensus, k-concurrency, simplicial complexes, immediate snapshot}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.7
Set-Consensus Collections are Decidable

Authors: Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection C of (l, j)-set consensus objects, for various l (the number of processes that can invoke the object) and j (the number of distinct outputs the object returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n^2) decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its set-consensus power.
Cite as

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Set-Consensus Collections are Decidable. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{delportegallet_et_al:LIPIcs.OPODIS.2016.7,
  author =	{Delporte-Gallet, Carole and Fauconnier, Hugues and Gafni, Eli and Kuznetsov, Petr},
  title =	{{Set-Consensus Collections are Decidable}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.7},
  URN =		{urn:nbn:de:0030-drops-70761},
  doi =		{10.4230/LIPIcs.OPODIS.2016.7},
  annote =	{Keywords: Decidability, distributed tasks, set consensus, Knapsack problem}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.8
k-Set Agreement in Communication Networks with Omission Faults

Authors: Emmanuel Godard and Eloi Perdereau

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
We consider an arbitrary communication network G where at most f messages can be lost at each round, and consider the classical k-set agreement problem in this setting. We characterize exactly for which f the k-set agreement problem can be solved on G. The case with k = 1, that is the Consensus problem, has first been introduced by Santoro and Widmayer in 1989, the characterization is already known from [Coulouma/Godard/Peters, TCS, 2015]. As a first contribution, we present a detailed and complete characterization for the 2-set problem. The proof of the impossibility result uses topological methods. We introduce a new subdivision approach for these topological methods that is of independent interest. In the second part, we show how to extend to the general case with k in N. This characterization is the first complete characterization for this kind of synchronous message passing model, a model that is a subclass of the family of oblivious message adversaries.
Cite as

Emmanuel Godard and Eloi Perdereau. k-Set Agreement in Communication Networks with Omission Faults. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{godard_et_al:LIPIcs.OPODIS.2016.8,
  author =	{Godard, Emmanuel and Perdereau, Eloi},
  title =	{{k-Set Agreement in Communication Networks with Omission Faults}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.8},
  URN =		{urn:nbn:de:0030-drops-70775},
  doi =		{10.4230/LIPIcs.OPODIS.2016.8},
  annote =	{Keywords: k-set agreement, message passing, dynamic networks, message adversary, omission faults}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.9
Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

Authors: Sriram Pemmaraju and Talal Riaz

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Until recently, the fastest distributed MIS algorithm, even for simple graph classes such as unoriented trees that can contain large independent sets within neighborhoods, has been the simple randomized algorithm discovered independently by several researchers in the late 80s. This algorithm (commonly called Luby’s algorithm) computes an MIS of an n-node graph in O(log n) communication rounds (with high probability). This situation changed when Lenzen and Wattenhofer (PODC 2011) presented a distributed (randomized) MIS algorithm for unoriented treesrunning in O( sqrt (log n * log log n)) rounds. This algorithm was slightly improved by Barenboim et al. (FOCS 2012), resulting in an O( sqrt (log n * log log n))-round (randomized) MIS algorithm for trees. At their core, these algorithms still run Luby's algorithm, but only up to the point at which the graph has been "shattered" into small connected components that can be independently processed in parallel. The analyses of these tree MIS algorithms critically depends on "near independence" among probabilistic events, a feature that arises from the tree structure of the network. In their paper, Lenzen and Wattenhofer express hope that their algorithm and analysis could be extended to graphs with bounded arboricity. We show how to do this in the current paper. By using a new tail inequality for read-k families of random variables due to Gavinsky et al. (Random Struct Algorithms, 2015), we show how to deal with dependencies induced by the recent tree MIS algorithms when they are executed on bounded arboricity graphs. Specifically, we analyze a version of the tree MIS algorithm of Barenboim et al. and show that it runs in O(poly(a) * sqrt ( log n * log log n)) rounds in the CONGEST model for graphs with arboricity a. While the main thrust of this paper is the new probabilistic analysis via read-k inequalities, we point out that for small values of a, this algorithm is faster than the MIS algorithm of Barenboim et al. specifically designed for bounded arboricity graphs. In this context, it should be noted that recently (in SODA 2016) Ghaffari presented a novel distributed MIS algorithm for general graphs that runs in O (log d) + 2^O(sqrt(log log n)) rounds and a corollary of this algorithm is an O(log d + sqrt (log n))-round MIS algorithm on graphs with arboricity a.
Cite as

Sriram Pemmaraju and Talal Riaz. Using Read-k Inequalities to Analyze a Distributed MIS Algorithm. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{pemmaraju_et_al:LIPIcs.OPODIS.2016.9,
  author =	{Pemmaraju, Sriram and Riaz, Talal},
  title =	{{Using Read-k Inequalities to Analyze a Distributed MIS Algorithm}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.9},
  URN =		{urn:nbn:de:0030-drops-70784},
  doi =		{10.4230/LIPIcs.OPODIS.2016.9},
  annote =	{Keywords: Bounded Arboricity Graphs, CONGEST model, Luby’s Algorithm, Maximal Independent Set, Read-k Inequality}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.10
Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps

Authors: Stéphane Devismes, David Ilcinkas, and Colette Johnen

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks under the distributed unfair daemon (the most general daemon) without requiring any a priori knowledge about global parameters of the network. This is the first algorithm for this problem that is proven to achieve a polynomial stabilization time in steps. Namely, we exhibit a bound in O(W_{max} * n_{maxCC}^3 * n), where W_{max} is the maximum weight of an edge, n_{maxCC} is the maximum number of non-root processes in a connected component, and n is the number of processes. The stabilization time in rounds is at most 3n_{maxCC} + D, where D is the hop-diameter of V_r.
Cite as

Stéphane Devismes, David Ilcinkas, and Colette Johnen. Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{devismes_et_al:LIPIcs.OPODIS.2016.10,
  author =	{Devismes, St\'{e}phane and Ilcinkas, David and Johnen, Colette},
  title =	{{Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.10},
  URN =		{urn:nbn:de:0030-drops-70792},
  doi =		{10.4230/LIPIcs.OPODIS.2016.10},
  annote =	{Keywords: distributed algorithm, self-stabilization, routing algorithm, shortest path, disconnected network, shortest-path tree}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.11
Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3

Authors: Johanne Cohen, Khaled Maâmra, George Manoussakis, and Laurence Pilard

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
We present the first polynomial self-stabilizing algorithm for finding a (2/3)-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne et al. and has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a time complexity in O(n^3) moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne et al. algorithm, it only requires a constant amount of memory space (three identifiers and two booleans per node).
Cite as

Johanne Cohen, Khaled Maâmra, George Manoussakis, and Laurence Pilard. Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2016.11,
  author =	{Cohen, Johanne and Ma\^{a}mra, Khaled and Manoussakis, George and Pilard, Laurence},
  title =	{{Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.11},
  URN =		{urn:nbn:de:0030-drops-70808},
  doi =		{10.4230/LIPIcs.OPODIS.2016.11},
  annote =	{Keywords: Self-Stabilization, Distributed Algorithm, Fault Tolerance, Matching}
}
  • Refine by Author
  • 3 Pedone, Fernando
  • 2 Cachin, Christian
  • 2 Fatourou, Panagiota
  • 2 Gafni, Eli
  • 2 Jiménez, Ernesto
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Availability
  • 1 Computer systems organization → Redundancy
  • 1 Computer systems organization → Reliability
  • 1 Computing methodologies → Distributed algorithms

  • Refine by Keyword
  • 3 Consensus
  • 2 Decidability
  • 2 Simulation
  • 2 Verification
  • 2 consensus
  • Show More...

  • Refine by Type
  • 38 document
  • 1 volume

  • Refine by Publication Year
  • 38 2017
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact