21 Search Results for "Gilbert, David"

Document
DOI: 10.4230/LIPIcs.DISC.2021.3
Frugal Byzantine Computing

Authors: Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi

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

Abstract
Traditional techniques for handling Byzantine failures are expensive: digital signatures are too costly, while using 3f+1 replicas is uneconomical (f denotes the maximum number of Byzantine processes). We seek algorithms that reduce the number of replicas to 2f+1 and minimize the number of signatures. While the first goal can be achieved in the message-and-memory model, accomplishing the second goal simultaneously is challenging. We first address this challenge for the problem of broadcasting messages reliably. We study two variants of this problem, Consistent Broadcast and Reliable Broadcast, typically considered very close. Perhaps surprisingly, we establish a separation between them in terms of signatures required. In particular, we show that Consistent Broadcast requires at least 1 signature in some execution, while Reliable Broadcast requires O(n) signatures in some execution. We present matching upper bounds for both primitives within constant factors. We then turn to the problem of consensus and argue that this separation matters for solving consensus with Byzantine failures: we present a practical consensus algorithm that uses Consistent Broadcast as its main communication primitive. This algorithm works for n = 2f+1 and avoids signatures in the common case - properties that have not been simultaneously achieved previously. Overall, our work approaches Byzantine computing in a frugal manner and motivates the use of Consistent Broadcast - rather than Reliable Broadcast - as a key primitive for reaching agreement.
Cite as

Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi. Frugal Byzantine Computing. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aguilera_et_al:LIPIcs.DISC.2021.3,
  author =	{Aguilera, Marcos K. and Ben-David, Naama and Guerraoui, Rachid and Papuc, Dalia and Xygkis, Athanasios and Zablotchi, Igor},
  title =	{{Frugal Byzantine Computing}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{3:1--3:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.3},
  URN =		{urn:nbn:de:0030-drops-148051},
  doi =		{10.4230/LIPIcs.DISC.2021.3},
  annote =	{Keywords: Reliable Broadcast, Consistent Broadcast, Consensus, Byzantine Failure, Message-and-memory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.12
Space and Time Bounded Multiversion Garbage Collection

Authors: Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei

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

Abstract
We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only O(1) time on average to reclaim each version and maintains only a constant factor more versions than needed (plus an additive term). It is designed for multiversion schemes using version lists, which are the most common. Our approach uses two components that are of independent interest. First, we define a novel range-tracking data structure which stores a set of old versions and efficiently finds those that are no longer needed. We provide a wait-free implementation in which all operations take amortized constant time. Second, we represent version lists using a new lock-free doubly-linked list algorithm that supports efficient (amortized constant time) removals given a pointer to any node in the list. These two components naturally fit together to solve the multiversion garbage collection problem - the range-tracker identifies which versions to remove and our list algorithm can then be used to remove them from their version lists. We apply our garbage collection technique to generate end-to-end time and space bounds for the multiversioning system of Wei et al. (PPoPP 2021).
Cite as

Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, Yihan Sun, and Yuanhao Wei. Space and Time Bounded Multiversion Garbage Collection. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.DISC.2021.12,
  author =	{Ben-David, Naama and Blelloch, Guy E. and Fatourou, Panagiota and Ruppert, Eric and Sun, Yihan and Wei, Yuanhao},
  title =	{{Space and Time Bounded Multiversion Garbage Collection}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{12:1--12:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.12},
  URN =		{urn:nbn:de:0030-drops-148143},
  doi =		{10.4230/LIPIcs.DISC.2021.12},
  annote =	{Keywords: Lock-free, data structures, memory management, snapshot, version lists}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.23
Broadcast CONGEST Algorithms against Adversarial Edges

Authors: Yael Hitron and Merav Parter

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

Abstract
We consider the corner-stone broadcast task with an adaptive adversary that controls a fixed number of t edges in the input communication graph. In this model, the adversary sees the entire communication in the network and the random coins of the nodes, while maliciously manipulating the messages sent through a set of t edges (unknown to the nodes). Since the influential work of [Pease, Shostak and Lamport, JACM'80], broadcast algorithms against plentiful adversarial models have been studied in both theory and practice for over more than four decades. Despite this extensive research, there is no round efficient broadcast algorithm for general graphs in the CONGEST model of distributed computing. Even for a single adversarial edge (i.e., t = 1), the state-of-the-art round complexity is polynomial in the number of nodes. We provide the first round-efficient broadcast algorithms against adaptive edge adversaries. Our two key results for n-node graphs of diameter D are as follows: - For t = 1, there is a deterministic algorithm that solves the problem within Õ(D²) rounds, provided that the graph is 3 edge-connected. This round complexity beats the natural barrier of O(D³) rounds, the existential lower bound on the maximal length of 3 edge-disjoint paths between a given pair of nodes in G. This algorithm can be extended to a Õ((tD)^{O(t)})-round algorithm against t adversarial edges in (2t+1) edge-connected graphs. - For expander graphs with edge connectivity of Ω(t²log n), there is a considerably improved broadcast algorithm with O(t log ² n) rounds against t adversarial edges. This algorithm exploits the connectivity and conductance properties of G-subgraphs obtained by employing the Karger’s edge sampling technique. Our algorithms mark a new connection between the areas of fault-tolerant network design and reliable distributed communication.
Cite as

Yael Hitron and Merav Parter. Broadcast CONGEST Algorithms against Adversarial Edges. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hitron_et_al:LIPIcs.DISC.2021.23,
  author =	{Hitron, Yael and Parter, Merav},
  title =	{{Broadcast CONGEST Algorithms against Adversarial Edges}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{23:1--23:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.23},
  URN =		{urn:nbn:de:0030-drops-148256},
  doi =		{10.4230/LIPIcs.DISC.2021.23},
  annote =	{Keywords: CONGEST, Fault-Tolerant Network Design, Edge Connectivity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.24
General CONGEST Compilers against Adversarial Edges

Authors: Yael Hitron and Merav Parter

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

Abstract
We consider the adversarial CONGEST model of distributed computing in which a fixed number of edges (or nodes) in the graph are controlled by a computationally unbounded adversary that corrupts the computation by sending malicious messages over these (a-priori unknown) controlled edges. As in the standard CONGEST model, communication is synchronous, where per round each processor can send O(log n) bits to each of its neighbors. This paper is concerned with distributed algorithms that are both time efficient (in terms of the number of rounds), as well as, robust against a fixed number of adversarial edges. Unfortunately, the existing algorithms in this setting usually assume that the communication graph is complete (n-clique), and very little is known for graphs with arbitrary topologies. We fill in this gap by extending the methodology of [Parter and Yogev, SODA 2019] and provide a compiler that simulates any CONGEST algorithm 𝒜 (in the reliable setting) into an equivalent algorithm 𝒜' in the adversarial CONGEST model. Specifically, we show the following for every (2f+1) edge-connected graph of diameter D: - For f = 1, there is a general compiler against a single adversarial edge with a compilation overhead of Ô(D³) rounds. This improves upon the Ô(D⁵) round overhead of [Parter and Yogev, SODA 2019] and omits their assumption regarding a fault-free preprocessing phase. - For any constant f, there is a general compiler against f adversarial edges with a compilation overhead of Ô(D^{O(f)}) rounds. The prior compilers of [Parter and Yogev, SODA 2019] were limited to a single adversarial edge. Our compilers are based on a new notion of fault-tolerant cycle covers. The computation of these cycles in the adversarial CONGEST model constitutes the key technical contribution of the paper.
Cite as

Yael Hitron and Merav Parter. General CONGEST Compilers against Adversarial Edges. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hitron_et_al:LIPIcs.DISC.2021.24,
  author =	{Hitron, Yael and Parter, Merav},
  title =	{{General CONGEST Compilers against Adversarial Edges}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{24:1--24:18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.24},
  URN =		{urn:nbn:de:0030-drops-148266},
  doi =		{10.4230/LIPIcs.DISC.2021.24},
  annote =	{Keywords: CONGEST, Cycle Covers, Byzantine Adversaries}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.27
Singularly Near Optimal Leader Election in Asynchronous Networks

Authors: Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg

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

Abstract
This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in asynchronous networks. Kutten et al. (JACM 2015) presented a singularly near optimal randomized leader election algorithm for general synchronous networks that ran in O(D) time and used O(m log n) messages (where D, m, and n are the network’s diameter, number of edges and number of nodes, respectively) with high probability. Both bounds are near optimal (up to a logarithmic factor), since Ω(D) and Ω(m) are the respective lower bounds for time and messages for leader election even for synchronous networks and even for (Monte-Carlo) randomized algorithms. On the other hand, for general asynchronous networks, leader election algorithms are only known that are either time or message optimal, but not both. Kutten et al. (DISC 2020) presented a randomized asynchronous leader election algorithm that is singularly near optimal for complete networks, but left open the problem for general networks. This paper shows that singularly near optimal (up to polylogarithmic factors) bounds can be achieved for general asynchronous networks. We present a randomized singularly near optimal leader election algorithm that runs in O(D + log² n) time and O(m log² n) messages with high probability. Our result is the first known distributed leader election algorithm for asynchronous networks that is near optimal with respect to both time and message complexity and improves over a long line of results including the classical results of Gallager et al. (ACM TOPLAS, 1983), Peleg (JPDC, 1989), and Awerbuch (STOC, 89).
Cite as

Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Near Optimal Leader Election in Asynchronous Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kutten_et_al:LIPIcs.DISC.2021.27,
  author =	{Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
  title =	{{Singularly Near Optimal Leader Election in Asynchronous Networks}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{27:1--27:18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.27},
  URN =		{urn:nbn:de:0030-drops-148294},
  doi =		{10.4230/LIPIcs.DISC.2021.27},
  annote =	{Keywords: Leader election, Singular optimality, Randomized algorithms, Asynchronous networks, Arbitrary graphs}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.46
Brief Announcement: Twins – BFT Systems Made Robust

Authors: Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi

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

Abstract
Twins is an effective strategy for generating test scenarios with Byzantine [Lamport et al., 1982] nodes in order to find flaws in Byzantine Fault Tolerant (BFT) systems. Twins finds flaws in the design or implementation of BFT protocols that may cause correctness issues. The main idea of Twins is the following: running twin instances of a node that use correct, unmodified code and share the same network identity and credentials allows to emulate most interesting Byzantine behaviors. Because a twin executes normal, unmodified node code, building Twins only requires a thin wrapper over an existing distributed system designed for Byzantine tolerance. To emulate material, interesting scenarios with Byzantine nodes, it instantiates one or more twin copies of the node, giving the twins the same identities and network credentials as the original node. To the rest of the system, the node and all its twins appear indistinguishable from a single node behaving in a "questionable" manner. This approach generates many interesting Byzantine behaviors, including equivocation, double voting, and losing internal state, while forgoing uninteresting behavior scenarios that can be filtered at the transport layer, such as producing semantically invalid messages. Building on configurations with twin nodes, Twins systematically generates scenarios with Byzantine nodes via enumeration over protocol rounds and communication patterns among nodes. Despite this being inherently exponential, one new flaw and several known flaws were materialized by Twins in the arena of BFT consensus protocols. In all cases, protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems. In two of these cases, it took the community more than a decade to discover protocol flaws that Twins would have surfaced within minutes. Additionally, Twins has been incorporated into the continuous release testing process of a production setting (DiemBFT) in which it can execute 44M Twins-generated scenarios daily.
Cite as

Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi. Brief Announcement: Twins – BFT Systems Made Robust. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 46:1-46:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bano_et_al:LIPIcs.DISC.2021.46,
  author =	{Bano, Shehar and Sonnino, Alberto and Chursin, Andrey and Perelman, Dmitri and Li, Zekun and Ching, Avery and Malkhi, Dahlia},
  title =	{{Brief Announcement: Twins – BFT Systems Made Robust}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{46:1--46: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.46},
  URN =		{urn:nbn:de:0030-drops-148485},
  doi =		{10.4230/LIPIcs.DISC.2021.46},
  annote =	{Keywords: Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.7
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Cite as

Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
  author =	{Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
  title =	{{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7},
  URN =		{urn:nbn:de:0030-drops-127681},
  doi =		{10.4230/LIPIcs.FUN.2021.7},
  annote =	{Keywords: puzzles, sliding blocks, PSPACE-hardness}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.16
On Deterministic Linearizable Set Agreement Objects

Authors: Felipe de Azevedo Piovezan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
A recent work showed that, for all n and k, there is a linearizable (n,k)-set agreement object O_L that is equivalent to the (n,k)-set agreement task [David Yu Cheng Chan et al., 2017]: given O_L, it is possible to solve the (n,k)-set agreement task, and given any algorithm that solves the (n,k)-set agreement task (and registers), it is possible to implement O_L. This linearizable object O_L, however, is not deterministic. It turns out that there is also a deterministic (n,k)-set agreement object O_D that is equivalent to the (n,k)-set agreement task, but this deterministic object O_D is not linearizable. This raises the question whether there exists a deterministic and linearizable (n,k)-set agreement object that is equivalent to the (n,k)-set agreement task. Here we show that in general the answer is no: specifically, we prove that for all n ≥ 4, every deterministic linearizable (n,2)-set agreement object is strictly stronger than the (n,2)-set agreement task. We prove this by showing that, for all n ≥ 4, every deterministic and linearizable (n,2)-set agreement object (together with registers) can be used to solve 2-consensus, whereas it is known that the (n,2)-set agreement task cannot do so. For a natural subset of (n,2)-set agreement objects, we prove that this result holds even for n = 3.
Cite as

Felipe de Azevedo Piovezan, Vassos Hadzilacos, and Sam Toueg. On Deterministic Linearizable Set Agreement Objects. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{deazevedopiovezan_et_al:LIPIcs.OPODIS.2019.16,
  author =	{de Azevedo Piovezan, Felipe and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{On Deterministic Linearizable Set Agreement Objects}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.16},
  URN =		{urn:nbn:de:0030-drops-118026},
  doi =		{10.4230/LIPIcs.OPODIS.2019.16},
  annote =	{Keywords: Asynchronous shared-memory systems, consensus, set agreement, deterministic objects}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.19
On Low-Risk Heavy Hitters and Sparse Recovery Schemes

Authors: Yi Li, Vasileios Nakos, and David P. Woodruff

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We study the heavy hitters and related sparse recovery problems in the low failure probability regime. This regime is not well-understood, and the main previous work on this is by Gilbert et al. (ICALP'13). We recognize an error in their analysis, improve their results, and contribute new sparse recovery algorithms, as well as provide upper and lower bounds for the heavy hitters problem with low failure probability. Our results are summarized as follows: 1) (Heavy Hitters) We study three natural variants for finding heavy hitters in the strict turnstile model, where the variant depends on the quality of the desired output. For the weakest variant, we give a randomized algorithm improving the failure probability analysis of the ubiquitous Count-Min data structure. We also give a new lower bound for deterministic schemes, resolving a question about this variant posed in Question 4 in the IITK Workshop on Algorithms for Data Streams (2006). Under the strongest and well-studied l_{infty}/ l_2 variant, we show that the classical Count-Sketch data structure is optimal for very low failure probabilities, which was previously unknown. 2) (Sparse Recovery Algorithms) For non-adaptive sparse-recovery, we give sublinear-time algorithms with low-failure probability, which improve upon Gilbert et al. (ICALP'13). In the adaptive case, we improve the failure probability from a constant by Indyk et al. (FOCS '11) to e^{-k^{0.99}}, where k is the sparsity parameter. 3) (Optimal Average-Case Sparse Recovery Bounds) We give matching upper and lower bounds in all parameters, including the failure probability, for the measurement complexity of the l_2/l_2 sparse recovery problem in the spiked-covariance model, completely settling its complexity in this model.
Cite as

Yi Li, Vasileios Nakos, and David P. Woodruff. On Low-Risk Heavy Hitters and Sparse Recovery Schemes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2018.19,
  author =	{Li, Yi and Nakos, Vasileios and Woodruff, David P.},
  title =	{{On Low-Risk Heavy Hitters and Sparse Recovery Schemes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.19},
  URN =		{urn:nbn:de:0030-drops-94237},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.19},
  annote =	{Keywords: heavy hitters, sparse recovery, turnstile model, spike covariance model, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.25
SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms

Authors: Lingxiao Huang, Yifei Jin, and Jian Li

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We study two important SVM variants: hard-margin SVM (for linearly separable cases) and nu-SVM (for linearly non-separable cases). We propose new algorithms from the perspective of saddle point optimization. Our algorithms achieve (1-epsilon)-approximations with running time O~(nd+n sqrt{d / epsilon}) for both variants, where n is the number of points and d is the dimensionality. To the best of our knowledge, the current best algorithm for nu-SVM is based on quadratic programming approach which requires Omega(n^2 d) time in worst case [Joachims, 1998; Platt, 1999]. In the paper, we provide the first nearly linear time algorithm for nu-SVM. The current best algorithm for hard margin SVM achieved by Gilbert algorithm [Gärtner and Jaggi, 2009] requires O(nd / epsilon) time. Our algorithm improves the running time by a factor of sqrt{d}/sqrt{epsilon}. Moreover, our algorithms can be implemented in the distributed settings naturally. We prove that our algorithms require O~(k(d +sqrt{d/epsilon})) communication cost, where k is the number of clients, which almost matches the theoretical lower bound. Numerical experiments support our theory and show that our algorithms converge faster on high dimensional, large and dense data sets, as compared to previous methods.
Cite as

Lingxiao Huang, Yifei Jin, and Jian Li. SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.SWAT.2018.25,
  author =	{Huang, Lingxiao and Jin, Yifei and Li, Jian},
  title =	{{SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.25},
  URN =		{urn:nbn:de:0030-drops-88515},
  doi =		{10.4230/LIPIcs.SWAT.2018.25},
  annote =	{Keywords: nu-SVM, hard-margin SVM, saddle point optimization, distributed algorithm}
}
Document
DOI: 10.4230/DagRep.4.11.138
Multiscale Spatial Computational Systems Biology (Dagstuhl Seminar 14481)

Authors: David Gilbert, Monika Heiner, Koichi Takahashi, and Adelinde M. Uhrmacher

Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14481 "Multiscale Spatial Computational Systems Biology". This seminar explored challenges arising from the need to model and analyse complex biological systems at multiple scales (spatial and temporal), which falls within the general remit of Computational Systems Biology. A distinguishing factor of the seminar was the modelling exercise -- where teams explored different modelling paradigms, in order to better understand the details of the approaches, their challenges, potential applications, and their pros and cons. This activity was carried out in a collaborative and self-directed manner using the Open Space Technology approach as evidenced by a high degree of communication both within and between the teams. Eight teams were formed, and reports from five of them are included in this document.
Cite as

David Gilbert, Monika Heiner, Koichi Takahashi, and Adelinde M. Uhrmacher. Multiscale Spatial Computational Systems Biology (Dagstuhl Seminar 14481). In Dagstuhl Reports, Volume 4, Issue 11, pp. 138-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{gilbert_et_al:DagRep.4.11.138,
  author =	{Gilbert, David and Heiner, Monika and Takahashi, Koichi and Uhrmacher, Adelinde M.},
  title =	{{Multiscale Spatial Computational Systems Biology (Dagstuhl Seminar 14481)}},
  pages =	{138--226},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{11},
  editor =	{Gilbert, David and Heiner, Monika and Takahashi, Koichi and Uhrmacher, Adelinde M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.11.138},
  URN =		{urn:nbn:de:0030-drops-49723},
  doi =		{10.4230/DagRep.4.11.138},
  annote =	{Keywords: Multiscale, multidimensional, computational modelling, space, time, systems biology, synthetic biology}
}
Document
DOI: 10.4230/DagSemProc.09091.1
09091 Abstracts Collection – Formal Methods in Molecular Biology

Authors: Rainer Breitling, David Roger Gilbert, Monika Heiner, and Corrado Priami

Published in: Dagstuhl Seminar Proceedings, Volume 9091, Formal Methods in Molecular Biology (2009)

Abstract
From 23. February to 27. February 2009, the Dagstuhl Seminar 09091 ``Formal Methods in Molecular Biology '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Rainer Breitling, David Roger Gilbert, Monika Heiner, and Corrado Priami. 09091 Abstracts Collection – Formal Methods in Molecular Biology. In Formal Methods in Molecular Biology. Dagstuhl Seminar Proceedings, Volume 9091, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:DagSemProc.09091.1,
  author =	{Breitling, Rainer and Gilbert, David Roger and Heiner, Monika and Priami, Corrado},
  title =	{{09091 Abstracts Collection – Formal Methods in Molecular Biology }},
  booktitle =	{Formal Methods in Molecular Biology},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9091},
  editor =	{Rainer Breitling and David Roger Gilbert and Monika Heiner and Corrado Priami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09091.1},
  URN =		{urn:nbn:de:0030-drops-19972},
  doi =		{10.4230/DagSemProc.09091.1},
  annote =	{Keywords: Formal models, systems biology, biological processes}
}
Document
DOI: 10.4230/DagSemProc.09091.2
09091 Executive Summary – Formal Methods in Molecular Biology

Authors: Rainer Breitling, David Roger Gilbert, Monika Heiner, and Corrado Priami

Published in: Dagstuhl Seminar Proceedings, Volume 9091, Formal Methods in Molecular Biology (2009)

Abstract
Formal logical models play an increasing role in the newly emerging field of Systems Biology. Compared to the classical, well-established approach of modeling biological processes using continuous and stochastic differential equations, formal logical models offer a number of important advantages. Many different formal modeling paradigms have been applied to molecular biology, each with its own community, formalisms and tools. In this seminar we brought together modelers from various backgrounds to stimulate closer interaction within the field and to create a common platform for discussion. A central feature of the seminar was a modeling competition (with a highly collaborative flavor) of various modeling paradigms.
Cite as

Rainer Breitling, David Roger Gilbert, Monika Heiner, and Corrado Priami. 09091 Executive Summary – Formal Methods in Molecular Biology. In Formal Methods in Molecular Biology. Dagstuhl Seminar Proceedings, Volume 9091, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:DagSemProc.09091.2,
  author =	{Breitling, Rainer and Gilbert, David Roger and Heiner, Monika and Priami, Corrado},
  title =	{{09091 Executive Summary – Formal Methods in Molecular Biology}},
  booktitle =	{Formal Methods in Molecular Biology},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9091},
  editor =	{Rainer Breitling and David Roger Gilbert and Monika Heiner and Corrado Priami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09091.2},
  URN =		{urn:nbn:de:0030-drops-19964},
  doi =		{10.4230/DagSemProc.09091.2},
  annote =	{Keywords: Formal models, systems biology, biological processes.}
}
Document
DOI: 10.4230/DagSemProc.09091.3
Analyzing various models of Circadian Clock and Cell Cycle coupling

Authors: Attila Csikász-Nagy, Adrien Faure, Roberto Larcher, Paola Lecca, Ivan Mura, Ferenc Jordan, Alida Palmisano, Alessandro Romanel, Sean Sedwards, Heike Siebert, Sylvain Soliman, Denis Thieffry, Judit Zámborszky, Tommaso Mazza, and Paolo Ballarini

Published in: Dagstuhl Seminar Proceedings, Volume 9091, Formal Methods in Molecular Biology (2009)

Abstract
The daily rhythm can influence the proliferation rate of many cell types. In the mammalian system the transcription of the cell cycle regulatory protein Wee1 is controlled by the circadian clock. Zamborszky et al. (2007) present a computational model coupling the cell cycle and circadian rhythm, showing that this coupling can lead to multimodal cell cycle time distributions. Biological data points to additional couplings, including a link back from the cell cycle to the circadian clock. Proper modelling of this coupling requires a more detailed description of both parts of the model. Hence, we aim at further extending and analysing earlier models using a combination of modelling techniques and computer software, including CoSBI lab, BIOCHAM, and GINsim.
Cite as

Attila Csikász-Nagy, Adrien Faure, Roberto Larcher, Paola Lecca, Ivan Mura, Ferenc Jordan, Alida Palmisano, Alessandro Romanel, Sean Sedwards, Heike Siebert, Sylvain Soliman, Denis Thieffry, Judit Zámborszky, Tommaso Mazza, and Paolo Ballarini. Analyzing various models of Circadian Clock and Cell Cycle coupling. In Formal Methods in Molecular Biology. Dagstuhl Seminar Proceedings, Volume 9091, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{csikasznagy_et_al:DagSemProc.09091.3,
  author =	{Csik\'{a}sz-Nagy, Attila and Faure, Adrien and Larcher, Roberto and Lecca, Paola and Mura, Ivan and Jordan, Ferenc and Palmisano, Alida and Romanel, Alessandro and Sedwards, Sean and Siebert, Heike and Soliman, Sylvain and Thieffry, Denis and Z\'{a}mborszky, Judit and Mazza, Tommaso and Ballarini, Paolo},
  title =	{{Analyzing various models of Circadian Clock and Cell Cycle coupling}},
  booktitle =	{Formal Methods in Molecular Biology},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9091},
  editor =	{Rainer Breitling and David Roger Gilbert and Monika Heiner and Corrado Priami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09091.3},
  URN =		{urn:nbn:de:0030-drops-19944},
  doi =		{10.4230/DagSemProc.09091.3},
  annote =	{Keywords: Cell cycle, circadian clock, computational modelling}
}
Document
DOI: 10.4230/DagSemProc.09091.4
BioModel Engineering: Its role in Systems Biology and Synthetic Biology

Authors: David Roger Gilbert, Rainer Breitling, and Monika Heiner

Published in: Dagstuhl Seminar Proceedings, Volume 9091, Formal Methods in Molecular Biology (2009)

Abstract
BioModel Engineering takes place at the interface of computing science, mathematics, engineering and biology, and provides a systematic approach for designing, constructing and analyzing computational models of biological systems. Some of its central concepts are inspired by efficient software engineering strategies. BioModel Engineering does not aim at engineering biological systems per se, but rather aims at describing their structure and behavior, in particular at the level of intracellular molecular processes, using computational tools and techniques in a principled way. The two major application areas of BioModel Engineering are systems biology and synthetic biology. In the former, the aim is the design and construction of models of existing biological systems, which explain observed properties and predict the response to experimental interventions; in the latter, BioModel Engineering is used as part of a general strategy for designing and constructing synthetic biological systems with novel functionalities. The overall steps in building computational models in a BioModel Engineering framework are: Problem Identification, Model Construction, Static and Dynamic Analysis, Simulation, and Model management and development. A major theme in BioModel Engineering is that of constructing a (qualitative) model means (1) finding the structure, (2) obtaining an initial state and (3) parameter fitting. In an approach that we have taken, the structure is obtained by piecewise construction of models from modular parts, the initial state which describes concentrations of species or numbers of molecules is obtained by analysis of the structure, and parameter fitting comprises determining the rate parameters of the kinetic equations by reference to trusted data. Model checking can play a key role in BioModel Engineering – for example in recent work we have shown how parameter estimation can be achieved by characterising the desired behaviour of a model with a temporal logic property and altering the model to make it conform to the property as determined through model checking.
Cite as

David Roger Gilbert, Rainer Breitling, and Monika Heiner. BioModel Engineering: Its role in Systems Biology and Synthetic Biology. In Formal Methods in Molecular Biology. Dagstuhl Seminar Proceedings, Volume 9091, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gilbert_et_al:DagSemProc.09091.4,
  author =	{Gilbert, David Roger and Breitling, Rainer and Heiner, Monika},
  title =	{{BioModel Engineering: Its role in Systems Biology and Synthetic Biology}},
  booktitle =	{Formal Methods in Molecular Biology},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9091},
  editor =	{Rainer Breitling and David Roger Gilbert and Monika Heiner and Corrado Priami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09091.4},
  URN =		{urn:nbn:de:0030-drops-19929},
  doi =		{10.4230/DagSemProc.09091.4},
  annote =	{Keywords: Biochemical systems, models, design, construction, systems biology, synthetic biology, model checking.}
}
  • Refine by Author
  • 4 Heiner, Monika
  • 3 Breitling, Rainer
  • 3 Gilbert, David Roger
  • 2 Ben-David, Naama
  • 2 Gilbert, David
  • Show More...

  • Refine by Classification
  • 2 Networks → Network algorithms
  • 2 Theory of computation → Concurrent algorithms
  • 2 Theory of computation → Distributed algorithms
  • 1 Computing methodologies → Support vector machines
  • 1 Mathematics of computing → Continuous optimization
  • Show More...

  • Refine by Keyword
  • 4 systems biology
  • 2 CONGEST
  • 2 Formal models
  • 2 computational modelling
  • 2 synthetic biology
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 8 2009
  • 6 2021
  • 2 2018
  • 2 2020
  • 1 2003
  • Show More...

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