38 Search Results for "Bessani, Alysson"

Volume

LIPIcs, Volume 95

21st International Conference on Principles of Distributed Systems (OPODIS 2017)

OPODIS 2017, December 18-20, 2017, Lisbon, Portugal

Editors: James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.53
Brief Announcement: Auditable Register Emulations

Authors: Vinicius Vielmo Cogo and Alysson Bessani

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We initiate the study of auditable storage emulations, which provide the capability for an auditor to report the previously executed reads in a register. We define the notion of auditable register and its properties, and establish tight bounds and impossibility results for auditable storage emulations in the presence of faulty base storage objects. Our formulation considers registers that securely store data using information dispersal (each base object stores only a block of the written value) and supporting fast reads (that complete in one communication round-trip). In such a scenario, given a maximum number f of faulty storage objects and a minimum number τ of data blocks required to recover a stored value, we prove that (R1) auditability is impossible if τ ≤ 2f; (R2) implementing a weak form of auditability requires τ ≥ 3f+1; and (R3) a stronger form of auditability is impossible. We also show that (R4) signing read requests generically overcomes the lower bound of weak auditability, while (R5 and R6) totally ordering operations or using non-fast reads enables strong auditability. These results establish that practical storage emulations need f to 2f additional objects compared to their original lower bounds to support auditability.
Cite as

Vinicius Vielmo Cogo and Alysson Bessani. Brief Announcement: Auditable Register Emulations. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 53:1-53:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cogo_et_al:LIPIcs.DISC.2021.53,
  author =	{Cogo, Vinicius Vielmo and Bessani, Alysson},
  title =	{{Brief Announcement: Auditable Register Emulations}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{53:1--53:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.53},
  URN =		{urn:nbn:de:0030-drops-148558},
  doi =		{10.4230/LIPIcs.DISC.2021.53},
  annote =	{Keywords: Auditability, Secure Storage, Information Dispersal}
}
Document
DOI: 10.4230/LITES.7.1.1
Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication

Authors: Kristin Krüger, Nils Vreman, Richard Pates, Martina Maggio, Marcus Völp, and Gerhard Fohler

Published in: LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1

Abstract
Time-triggered real-time systems achieve deterministic behavior using schedules that are constructed offline, based on scheduling constraints. Their deterministic behavior makes time-triggered systems suitable for usage in safety-critical environments, like avionics. However, this determinism also allows attackers to fine-tune attacks that can be carried out after studying the behavior of the system through side channels, targeting safety-critical victim tasks. Replication -- i.e., the execution of task variants across different cores -- is inherently able to tolerate both accidental and malicious faults (i.e. attacks) as long as these faults are independent of one another. Yet, targeted attacks on the timing behavior of tasks which utilize information gained about the system behavior violate the fault independence assumption fault tolerance is based on. This violation may give attackers the opportunity to compromise all replicas simultaneously, in particular if they can mount the attack from already compromised components. In this paper, we analyze vulnerabilities of time-triggered systems, focusing on safety-certified multicore real-time systems. We introduce two runtime mitigation strategies to withstand directed timing inference based attacks: (i) schedule randomization at slot level, and (ii) randomization within a set of offline constructed schedules. We evaluate these mitigation strategies with synthetic experiments and a real case study to show their effectiveness and practicality.
Cite as

Kristin Krüger, Nils Vreman, Richard Pates, Martina Maggio, Marcus Völp, and Gerhard Fohler. Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication. In LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1, pp. 01:1-01:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{kruger_et_al:LITES.7.1.1,
  author =	{Kr\"{u}ger, Kristin and Vreman, Nils and Pates, Richard and Maggio, Martina and V\"{o}lp, Marcus and Fohler, Gerhard},
  title =	{{Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication}},
  booktitle =	{LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security},
  pages =	{01:1--01:29},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2021},
  volume =	{7},
  number =	{1},
  editor =	{Kr\"{u}ger, Kristin and Vreman, Nils and Pates, Richard and Maggio, Martina and V\"{o}lp, Marcus and Fohler, Gerhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.7.1.1},
  doi =		{10.4230/LITES.7.1.1},
  annote =	{Keywords: real-time systems, time-triggered systems, security}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2017
LIPIcs, Volume 95, OPODIS'17, Complete Volume

Authors: James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
LIPIcs, Volume 95, OPODIS'17, Complete Volume
Cite as

James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão. LIPIcs, Volume 95, OPODIS'17, Complete Volume. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{aspnes_et_al:LIPIcs.OPODIS.2017,
  title =	{{LIPIcs, Volume 95, OPODIS'17, Complete Volume}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017},
  URN =		{urn:nbn:de:0030-drops-86786},
  doi =		{10.4230/LIPIcs.OPODIS.2017},
  annote =	{Keywords: Distributed Systems, Performance of Systems, Concurrent Programming, Data Structures, Modes of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2017.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão. Front Matter, Table of Contents, Preface, Conference Organization. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 0:i-0:xx, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.OPODIS.2017.0,
  author =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.0},
  URN =		{urn:nbn:de:0030-drops-86236},
  doi =		{10.4230/LIPIcs.OPODIS.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.1
Causality for the Masses: Offering Fresh Data, Low Latency, and High Throughput

Authors: Luís Rodrigues

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
The problem of ensuring consistency in applications that manage replicated data is one of the main challenges of distributed computing. Among the several invariants that may be enforced, ensuring that updates are applied and made visible respecting causality has emerged as a key ingredient among the many consistency criteria and client session guarantees that have been proposed and implemented in the last decade. Techniques to keep track of causal dependencies, and to subsequently ensure that messages are delivered in causal order, have been widely studied. It is today well known that, in order to accurately capture causality one may need to keep a large amounts of metadata, for instance, one vector clock for each data object. This metadata needs to be updated and piggybacked on update messages, such that updates that are received from remote datacenters can be applied locally without violating causality. This metadata can be compressed; ultimately, it is possible to preserve causal order using a single scalar as metadata, i.e., a Lamport’s clock. Unfortunately, when compressing metadada it may become impossible to distinguish if two events are concurrent or causally related. We denote such scenario a false dependency. False dependencies introduce unnecessary delays and impair the latency of update propagation. This problem is exacerbated when one wants to support partial replication. Therefore, when building a geo-replicated large-scale system one is faced with a dilemma: one can use techniques that maintain few metadata and that fail to capture causality accurately, or one can use techniques that require large metadata (to be kept and exchanged) but have precise information about which updates are concurrent. The former usually offer good throughput at the cost of latency, while the latter offer lower latencies sacrificing throughput. This talk reports on Saturn[1] and Eunomia[2], two complementary systems that break this tradeoff by providing simultaneously high-throughput and low latency, even in face of partial replication. The key ingredient to the success of our approach is to decouple the metadata path from the data path and to serialize concurrent events (to reduce metadata), in the metadata path, in a way that minimizes the impact on the latency perceived by clients.
Cite as

Luís Rodrigues. Causality for the Masses: Offering Fresh Data, Low Latency, and High Throughput. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rodrigues:LIPIcs.OPODIS.2017.1,
  author =	{Rodrigues, Lu{\'\i}s},
  title =	{{Causality for the Masses: Offering Fresh Data, Low Latency, and High Throughput}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.1},
  URN =		{urn:nbn:de:0030-drops-86553},
  doi =		{10.4230/LIPIcs.OPODIS.2017.1},
  annote =	{Keywords: Distributed Systems, Causal Consistency}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.2
piChain: When a Blockchain meets Paxos

Authors: Conrad Burchert and Roger Wattenhofer

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We present a new fault-tolerant distributed state machine to inherit the best features of its “parents in spirit”: Paxos, providing strong consistency, and a blockchain, providing simplicity and availability. Our proposal is simple as it does not include any heavy weight distributed failure handling protocols such as leader election. In addition, our proposal has a few other valuable features, e.g., it is responsive, it scales well, and it does not send any overhead messages.
Cite as

Conrad Burchert and Roger Wattenhofer. piChain: When a Blockchain meets Paxos. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 2:1-2:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{burchert_et_al:LIPIcs.OPODIS.2017.2,
  author =	{Burchert, Conrad and Wattenhofer, Roger},
  title =	{{piChain: When a Blockchain meets Paxos}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.2},
  URN =		{urn:nbn:de:0030-drops-86543},
  doi =		{10.4230/LIPIcs.OPODIS.2017.2},
  annote =	{Keywords: Consensus, Crash Failures, Availability, Network Partition, Consistency}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.3
Broadcasting in an Unreliable SINR Model

Authors: Fabian Kuhn and Philipp Schneider

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We investigate distributed algorithms for broadcasting in unreliable wireless networks. Our basic setting is the signal to noise and interference ratio (SINR) model, which captures the physical key characteristics of wireless communication. We consider a dynamic variant of this model in which an adversary can adaptively control the model parameters for each individual transmission. Moreover, we assume that the network devices have no information about the geometry or the topology of the network and do neither know the exact model parameters nor do they have any control over them. Our model is intended to capture the inherently unstable and unreliable nature of real wireless transmission, where signal quality and reception depends on many different aspects that are often hard to measure or predict. We show that with moderate adaptations, the broadcast algorithm of Daum et al. [DISC 13] also works in such an adversarial, much more dynamic setting. The algorithm allows to broadcast a single message in a network of size n in time O(D·polylog(n+R)), where D is the diameter and R describes the granularity of the communication graph.
Cite as

Fabian Kuhn and Philipp Schneider. Broadcasting in an Unreliable SINR Model. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 3:1-3:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kuhn_et_al:LIPIcs.OPODIS.2017.3,
  author =	{Kuhn, Fabian and Schneider, Philipp},
  title =	{{Broadcasting in an Unreliable SINR Model}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.3},
  URN =		{urn:nbn:de:0030-drops-86247},
  doi =		{10.4230/LIPIcs.OPODIS.2017.3},
  annote =	{Keywords: radio networks, wireless networks, broadcast, SINR model, unreliable communication, dynamic networks}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.4
Deterministic Subgraph Detection in Broadcast CONGEST

Authors: Janne H. Korhonen and Joel Rybicki

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: - For any constant k, detecting k-paths and trees on k nodes can be done in O(1) rounds. - For any constant k, detecting k-cycles and pseudotrees on k nodes can be done in O(n) rounds. - On d-degenerate graphs, cliques and 4-cycles can be enumerated in O(d + log n) rounds, and 5-cycles in O(d2 + log n) rounds. In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for d-degenerate graphs can be improved to O(d/logn) and O(d2/logn), respect- ively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.
Cite as

Janne H. Korhonen and Joel Rybicki. Deterministic Subgraph Detection in Broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 4:1-4:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{korhonen_et_al:LIPIcs.OPODIS.2017.4,
  author =	{Korhonen, Janne H. and Rybicki, Joel},
  title =	{{Deterministic Subgraph Detection in Broadcast CONGEST}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.4},
  URN =		{urn:nbn:de:0030-drops-86252},
  doi =		{10.4230/LIPIcs.OPODIS.2017.4},
  annote =	{Keywords: distributed computing, subgraph detection, CONGEST model, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.5
Distributed Distance-Bounded Network Design Through Distributed Convex Programming

Authors: Michael Dinitz and Yasamin Nazari

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manner (Kuhn et al. 2006), this is essentially the only class of linear programs for which such an algorithm is known. In this work we provide a distributed algorithm for solving a different class of convex programs which we call “distance-bounded network design convex programs”. These can be thought of as relaxations of network design problems in which the connectivity requirement includes a distance constraint (most notably, graph spanners). Our algorithm runs in O((D/ε) log n) rounds in the LOCAL model and with high probability finds a (1+ε)-approximation to the optimal LP solution for any 0 < ε ≤ 1, where D is the largest distance constraint. While solving linear programs in a distributed setting is interesting in its own right, this class of convex programs is particularly important because solving them is often a crucial step when designing approximation algorithms. Hence we almost immediately obtain new and improved distributed approximation algorithms for a variety of network design problems, including Basic 3- and 4-Spanner, Directed k-Spanner, Lowest Degree k-Spanner, and Shallow-Light Steiner Network Design with a spanning demand graph. Our algorithms do not require any “heavy” computation and essentially match the best-known centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the best-known centralized bounds.
Cite as

Michael Dinitz and Yasamin Nazari. Distributed Distance-Bounded Network Design Through Distributed Convex Programming. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 5:1-5:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.OPODIS.2017.5,
  author =	{Dinitz, Michael and Nazari, Yasamin},
  title =	{{Distributed Distance-Bounded Network Design Through Distributed Convex Programming}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.5},
  URN =		{urn:nbn:de:0030-drops-86262},
  doi =		{10.4230/LIPIcs.OPODIS.2017.5},
  annote =	{Keywords: distributed algorithms, approximation algorithms, convex programming}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.6
Lower Bounds for Subgraph Detection in the CONGEST Model

Authors: Tzlil Gonen and Rotem Oshman

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
In the subgraph-freeness problem, we are given a constant-sized graph H, and wish to de- termine whether the network graph contains H as a subgraph or not. Until now, the only lower bounds on subgraph-freeness known for the CONGEST model were for cycles of length greater than 3; here we extend and generalize the cycle lower bound, and obtain polynomial lower bounds for subgraph-freeness in the CONGEST model for two classes of subgraphs. The first class contains any graph obtained by starting from a 2-connected graph H for which we already know a lower bound, and replacing the vertices of H by arbitrary connected graphs. We show that the lower bound on H carries over to the new graph. The second class is constructed by starting from a cycle Ck of length k ≥ 4, and constructing a graph H ̃ from Ck by replacing each edge {i, (i + 1) mod k} of the cycle with a connected graph Hi, subject to some constraints on the graphs H_{0}, . . . , H_{k−1}. In this case we obtain a polynomial lower bound for the new graph H ̃, depending on the size of the shortest cycle in H ̃ passing through the vertices of the original k-cycle.
Cite as

Tzlil Gonen and Rotem Oshman. Lower Bounds for Subgraph Detection in the CONGEST Model. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 6:1-6:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gonen_et_al:LIPIcs.OPODIS.2017.6,
  author =	{Gonen, Tzlil and Oshman, Rotem},
  title =	{{Lower Bounds for Subgraph Detection in the CONGEST Model}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.6},
  URN =		{urn:nbn:de:0030-drops-86445},
  doi =		{10.4230/LIPIcs.OPODIS.2017.6},
  annote =	{Keywords: subgraph freeness, CONGEST, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.7
Extending Transactional Memory with Atomic Deferral

Authors: Tingzhe Zhou, Victor Luchangco, and Michael Spear

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
This paper introduces atomic deferral, an extension to TM that allows programmers to move long-running or irrevocable operations out of a transaction while maintaining serializability: the transaction and its de- ferred operation appear to execute atomically from the perspective of other transactions. Thus, program- mers can adapt lock-based programs to exploit TM with relatively little effort and without sacrificing scalability by atomically deferring the problematic operations. We demonstrate this with several use cases for atomic deferral, as well as an in-depth analysis of its use on the PARSEC dedup benchmark, where we show that atomic deferral enables TM to be competitive with well-designed lock-based code.
Cite as

Tingzhe Zhou, Victor Luchangco, and Michael Spear. Extending Transactional Memory with Atomic Deferral. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 7:1-7:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.OPODIS.2017.7,
  author =	{Zhou, Tingzhe and Luchangco, Victor and Spear, Michael},
  title =	{{Extending Transactional Memory with Atomic Deferral}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.7},
  URN =		{urn:nbn:de:0030-drops-86275},
  doi =		{10.4230/LIPIcs.OPODIS.2017.7},
  annote =	{Keywords: Transactional Memory, Concurrency, Synchronization, I/O}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.8
Lock Oscillation: Boosting the Performance of Concurrent Data Structures

Authors: Panagiota Fatourou and Nikolaos D. Kallimanis

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
In combining-based synchronization, two main parameters that affect performance are the com- bining degree of the synchronization algorithm, i.e. the average number of requests that each com- biner serves, and the number of expensive synchronization primitives (like CAS, Swap, etc.) that it performs. The value of the first parameter must be high, whereas the second must be kept low. In this paper, we present Osci, a new combining technique that shows remarkable perform- ance when paired with cheap context switching. We experimentally show that Osci significantly outperforms all previous combining algorithms. Specifically, the throughput of Osci is higher than that of previously presented combining techniques by more than an order of magnitude. Notably, Osci’s throughput is much closer to the ideal than all previous algorithms, while keep- ing the average latency in serving each request low. We evaluated the performance of Osci in two different multiprocessor architectures, namely AMD and Intel. Based on Osci, we implement and experimentally evaluate implementations of concurrent queues and stacks. These implementations outperform by far all current state-of-the-art concur- rent queue and stack implementations. Although the current version of Osci has been evaluated in an environment supporting user-level threads, it would run correctly on any threading library, preemptive or not (including kernel threads).
Cite as

Panagiota Fatourou and Nikolaos D. Kallimanis. Lock Oscillation: Boosting the Performance of Concurrent Data Structures. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 8:1-8:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fatourou_et_al:LIPIcs.OPODIS.2017.8,
  author =	{Fatourou, Panagiota and Kallimanis, Nikolaos D.},
  title =	{{Lock Oscillation: Boosting the Performance of Concurrent Data Structures}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.8},
  URN =		{urn:nbn:de:0030-drops-86282},
  doi =		{10.4230/LIPIcs.OPODIS.2017.8},
  annote =	{Keywords: Synchronization, concurrent data structures, combining}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.9
Progress-Space Tradeoffs in Single-Writer Memory Implementations

Authors: Damien Imbs, Petr Kuznetsov, and Thibault Rieutord

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Many algorithms designed for shared-memory distributed systems assume the single-writer multi- reader (SWMR) setting where each process is provided with a unique register that can only be written by the process and read by all. In a system where computation is performed by a bounded number n of processes coming from a large (possibly unbounded) set of potential participants, the assumption of an SWMR memory is no longer reasonable. If only a bounded number of multi- writer multi-reader (MWMR) registers are provided, we cannot rely on an a priori assignment of processes to registers. In this setting, implementing an SWMR memory, or equivalently, ensuring stable writes (i.e., every written value persists in the memory), is desirable. In this paper, we propose an SWMR implementation that adapts the number of MWMR registers used to the desired progress condition. For any given k from 1 to n, we present an algorithm that uses n + k − 1 registers to implement a k-lock-free SWMR memory. In the special case of 2-lock-freedom, we also give a matching lower bound of n + 1 registers, which supports our conjecture that the algorithm is space-optimal. Our lower bound holds for the strictly weaker progress condition of 2-obstruction-freedom, which suggests that the space complexity for k-obstruction-free and k-lock-free SWMR implementations might coincide.
Cite as

Damien Imbs, Petr Kuznetsov, and Thibault Rieutord. Progress-Space Tradeoffs in Single-Writer Memory Implementations. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 9:1-9:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{imbs_et_al:LIPIcs.OPODIS.2017.9,
  author =	{Imbs, Damien and Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Progress-Space Tradeoffs in Single-Writer Memory Implementations}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.9},
  URN =		{urn:nbn:de:0030-drops-86290},
  doi =		{10.4230/LIPIcs.OPODIS.2017.9},
  annote =	{Keywords: Single-writer memory implementation, comparison-based algorithms, space complexity, progress conditions}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.10
The Teleportation Design Pattern for Hardware Transactional Memory

Authors: Nachshon Cohen, Maurice Herlihy, Erez Petrank, and Elias Wald

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We identify a design pattern for concurrent data structures, called teleportation, that uses best- effort hardware transactional memory to speed up certain kinds of legacy concurrent data struc- tures. Teleportation unifies and explains several existing data structure designs, and it serves as the basis for novel approaches to reducing the memory traffic associated with fine-grained locking, and with hazard pointer management for memory reclamation.
Cite as

Nachshon Cohen, Maurice Herlihy, Erez Petrank, and Elias Wald. The Teleportation Design Pattern for Hardware Transactional Memory. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 10:1-10:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2017.10,
  author =	{Cohen, Nachshon and Herlihy, Maurice and Petrank, Erez and Wald, Elias},
  title =	{{The Teleportation Design Pattern for Hardware Transactional Memory}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.10},
  URN =		{urn:nbn:de:0030-drops-86306},
  doi =		{10.4230/LIPIcs.OPODIS.2017.10},
  annote =	{Keywords: Hardware transactional memory, concurrent data structures}
}
  • Refine by Author
  • 5 Bessani, Alysson
  • 2 Aspnes, James
  • 2 Attiya, Hagit
  • 2 Felber, Pascal
  • 2 Leitão, João
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Evidence collection, storage and analysis
  • 1 Computer systems organization → Real-time systems
  • 1 Computer systems organization → Redundancy
  • 1 Computer systems organization → Reliability
  • 1 Computing methodologies → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 3 Distributed Systems
  • 2 Byzantine fault tolerance
  • 2 Reconfiguration
  • 2 Synchronization
  • 2 approximation algorithms
  • Show More...

  • Refine by Type
  • 37 document
  • 1 volume

  • Refine by Publication Year
  • 35 2018
  • 2 2021
  • 1 2017

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact