93 Search Results for "M�ller-Schloer, Christian"


Document
Principles of Contract Languages (Dagstuhl Seminar 22451)

Authors: Dilian Gurov, Reiner Hähnle, Marieke Huisman, Giles Reger, and Christian Lidström

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22451 "Principles of Contract Languages". At the seminar, participants discussed the fundamental aspects of software contracts. Topics included the format and expressiveness of contracts, their use cases in software development and analysis, and contract composition and decomposition.

Cite as

Dilian Gurov, Reiner Hähnle, Marieke Huisman, Giles Reger, and Christian Lidström. Principles of Contract Languages (Dagstuhl Seminar 22451). In Dagstuhl Reports, Volume 12, Issue 11, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{gurov_et_al:DagRep.12.11.1,
  author =	{Gurov, Dilian and H\"{a}hnle, Reiner and Huisman, Marieke and Reger, Giles and Lidstr\"{o}m, Christian},
  title =	{{Principles of Contract Languages (Dagstuhl Seminar 22451)}},
  pages =	{1--27},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Gurov, Dilian and H\"{a}hnle, Reiner and Huisman, Marieke and Reger, Giles and Lidstr\"{o}m, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.11.1},
  URN =		{urn:nbn:de:0030-drops-178334},
  doi =		{10.4230/DagRep.12.11.1},
  annote =	{Keywords: software contracts, program specifications, software development, program analysis}
}
Document
An Optimal Algorithm for Sliding Window Order Statistics

Authors: Pavel Raykov

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)


Abstract
Assume there is a data stream of elements and a window of size m. Sliding window algorithms compute various statistic functions over the last m elements of the data stream seen so far. The time complexity of a sliding window algorithm is measured as the time required to output an updated statistic function value every time a new element is read. For example, it is well known that computing the sliding window maximum/minimum has time complexity O(1) while computing the sliding window median has time complexity O(log m). In this paper we close the gap between these two cases by (1) presenting an algorithm for computing the sliding window k-th smallest element in O(log k) time and (2) prove that this time complexity is optimal.

Cite as

Pavel Raykov. An Optimal Algorithm for Sliding Window Order Statistics. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{raykov:LIPIcs.ICDT.2023.5,
  author =	{Raykov, Pavel},
  title =	{{An Optimal Algorithm for Sliding Window Order Statistics}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.5},
  URN =		{urn:nbn:de:0030-drops-177479},
  doi =		{10.4230/LIPIcs.ICDT.2023.5},
  annote =	{Keywords: sliding window, order statistics, median, selection algorithms}
}
Document
Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices

Authors: Prayaag Venkat

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
In this paper, we initiate the study of the algorithmic problem of certifying lower bounds on the discrepancy of random matrices: given an input matrix A ∈ ℝ^{m × n}, output a value that is a lower bound on disc(A) = min_{x ∈ {± 1}ⁿ} ‖Ax‖_∞ for every A, but is close to the typical value of disc(A) with high probability over the choice of a random A. This problem is important because of its connections to conjecturally-hard average-case problems such as negatively-spiked PCA [Afonso S. Bandeira et al., 2020], the number-balancing problem [Gamarnik and Kızıldağ, 2021] and refuting random constraint satisfaction problems [Prasad Raghavendra et al., 2017]. We give the first polynomial-time algorithms with non-trivial guarantees for two main settings. First, when the entries of A are i.i.d. standard Gaussians, it is known that disc(A) = Θ (√n2^{-n/m}) with high probability [Karthekeyan Chandrasekaran and Santosh S. Vempala, 2014; Aubin et al., 2019; Paxton Turner et al., 2020] and that super-constant levels of the Sum-of-Squares SDP hierarchy fail to certify anything better than disc(A) ≥ 0 when m < n - o(n) [Mrinalkanti Ghosh et al., 2020]. In contrast, our algorithm certifies that disc(A) ≥ exp(-O(n²/m)) with high probability. As an application, this formally refutes a conjecture of Bandeira, Kunisky, and Wein [Afonso S. Bandeira et al., 2020] on the computational hardness of the detection problem in the negatively-spiked Wishart model. Second, we consider the integer partitioning problem: given n uniformly random b-bit integers a₁, …, a_n, certify the non-existence of a perfect partition, i.e. certify that disc(A) ≥ 1 for A = (a₁, …, a_n). Under the scaling b = α n, it is known that the probability of the existence of a perfect partition undergoes a phase transition from 1 to 0 at α = 1 [Christian Borgs et al., 2001]; our algorithm certifies the non-existence of perfect partitions for some α = O(n). We also give efficient non-deterministic algorithms with significantly improved guarantees, raising the possibility that the landscape of these certification problems closely resembles that of e.g. the problem of refuting random 3SAT formulas in the unsatisfiable regime. Our algorithms involve a reduction to the Shortest Vector Problem and employ the Lenstra-Lenstra-Lovász algorithm.

Cite as

Prayaag Venkat. Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 98:1-98:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{venkat:LIPIcs.ITCS.2023.98,
  author =	{Venkat, Prayaag},
  title =	{{Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{98:1--98:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.98},
  URN =		{urn:nbn:de:0030-drops-176015},
  doi =		{10.4230/LIPIcs.ITCS.2023.98},
  annote =	{Keywords: Average-case discrepancy theory, lattices, shortest vector problem}
}
Document
Invited Talk
Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk)

Authors: Jennifer L. Welch

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
Atomic shared objects, whose operations take place instantaneously, are a powerful technique for designing complex concurrent programs. Since they are not always available, they are typically substituted with software implementations. A prominent condition relating these implementations to their atomic specifications is linearizability, which preserves safety properties of programs using them. However linearizability does not preserve hyper-properties, which include probabilistic guarantees about randomized programs. A more restrictive property, strong linearizability, does preserve hyper-properties but it is impossible to achieve in many situations. In particular, we show that there are no strongly linearizable implementations of multi-writer registers or snapshot objects in message-passing systems. On the other hand, we show that a wide class of linearizable implementations, including well-known ones for registers and snapshots, can be modified to approximate the probabilistic guarantees of randomized programs when using atomic objects. This is joint work with Hagit Attiya and Constantin Enea.

Cite as

Jennifer L. Welch. Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{welch:LIPIcs.DISC.2022.3,
  author =	{Welch, Jennifer L.},
  title =	{{Using Linearizable Objects in Randomized Concurrent Programs}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.3},
  URN =		{urn:nbn:de:0030-drops-171946},
  doi =		{10.4230/LIPIcs.DISC.2022.3},
  annote =	{Keywords: Concurrent objects, strong linearizability, impossibility proofs, message-passing systems, randomized algorithms}
}
Document
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm

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

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
A singularly (near) optimal distributed algorithm is one that is (near) optimal in two criteria, namely, its time and message complexities. For synchronous CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general asynchronous CONGEST networks. In this paper, we present a randomized distributed MST algorithm that, with high probability, computes an MST in asynchronous CONGEST networks and takes Õ(D^{1+ε} + √n) time and Õ(m) messages, where n is the number of nodes, m the number of edges, D is the diameter of the network, and ε > 0 is an arbitrarily small constant (both time and message bounds hold with high probability). Since Ω̃(D+√n) and Ω(m) are respective time and message lower bounds for distributed MST construction in the standard KT₀ model, our algorithm is message optimal (up to a polylog(n) factor) and almost time optimal (except for a D^ε factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all D = O(n^{1-ε})) and uses Õ(m) messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the KT₁ CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth Õ(D^{1+ε}) (for an arbitrarily small constant ε > 0) in Õ(D^{1+ε}) time and Õ(m) messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting. This tree construction may be of independent interest as it can also be used for efficiently performing basic tasks such as verified broadcast and convergecast in asynchronous networks.

Cite as

Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.DISC.2022.19,
  author =	{Dufoulon, Fabien and Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
  title =	{{An Almost Singularly Optimal Asynchronous Distributed MST Algorithm}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.19},
  URN =		{urn:nbn:de:0030-drops-172107},
  doi =		{10.4230/LIPIcs.DISC.2022.19},
  annote =	{Keywords: Asynchronous networks, Minimum Spanning Tree, Distributed Algorithm, Singularly Optimal}
}
Document
Improved Deterministic Connectivity in Massively Parallel Computation

Authors: Manuela Fischer, Jeff Giliberti, and Christoph Grunau

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
A long line of research about connectivity in the Massively Parallel Computation model has culminated in the seminal works of Andoni et al. [FOCS'18] and Behnezhad et al. [FOCS'19]. They provide a randomized algorithm for low-space MPC with conjectured to be optimal round complexity O(log D + log log_{m/n} n) and O(m) space, for graphs on n vertices with m edges and diameter D. Surprisingly, a recent result of Coy and Czumaj [STOC'22] shows how to achieve the same deterministically. Unfortunately, however, their algorithm suffers from large local computation time. We present a deterministic connectivity algorithm that matches all the parameters of the randomized algorithm and, in addition, significantly reduces the local computation time to nearly linear. Our derandomization method is based on reducing the amount of randomness needed to allow for a simpler efficient search. While similar randomness reduction approaches have been used before, our result is not only strikingly simpler, but it is the first to have efficient local computation. This is why we believe it to serve as a starting point for the systematic development of computation-efficient derandomization approaches in low-memory MPC.

Cite as

Manuela Fischer, Jeff Giliberti, and Christoph Grunau. Improved Deterministic Connectivity in Massively Parallel Computation. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.DISC.2022.22,
  author =	{Fischer, Manuela and Giliberti, Jeff and Grunau, Christoph},
  title =	{{Improved Deterministic Connectivity in Massively Parallel Computation}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.22},
  URN =		{urn:nbn:de:0030-drops-172138},
  doi =		{10.4230/LIPIcs.DISC.2022.22},
  annote =	{Keywords: Massively Parallel Computation, MPC, MapReduce, Deterministic Algorithms, Connectivity, Hitting Set, Maximum Matching, Derandomization}
}
Document
Fast Distributed Vertex Splitting with Applications

Authors: Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general poly log log n-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized poly log log n-round CONGEST algorithm for (1+ε)Δ-edge coloring n-node graphs of sufficiently large constant maximum degree Δ, for any ε > 0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

Cite as

Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Fast Distributed Vertex Splitting with Applications. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.DISC.2022.26,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Maus, Yannic and Nolin, Alexandre},
  title =	{{Fast Distributed Vertex Splitting with Applications}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{26:1--26:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.26},
  URN =		{urn:nbn:de:0030-drops-172176},
  doi =		{10.4230/LIPIcs.DISC.2022.26},
  annote =	{Keywords: Graph problems, Edge coloring, List coloring, Lov\'{a}sz local lemma, LOCAL model, CONGEST model, Distributed computing}
}
Document
Broadcast CONGEST Algorithms Against Eavesdroppers

Authors: Yael Hitron, Merav Parter, and Eylon Yogev

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
An eavesdropper is a passive adversary that aims at extracting private information on the input and output values of the network’s participants, by listening to the traffic exchanged over a subset of edges in the graph. We consider secure congest algorithms for the basic broadcast task, in the presence of eavesdropper (edge) adversaries. For D-diameter n-vertex graphs with edge connectivity Θ(f), we present f-secure broadcast algorithms that run in Õ(D+√{f n}) rounds. These algorithms transmit some broadcast message m^* to all the vertices in the graph, in a way that is information-theoretically secure against an eavesdropper controlling any subset of at most f edges in the graph. While our algorithms are heavily based on network coding (secret sharing), we also show that this is essential. For the basic problem of secure unicast we demonstrate a network coding gap of Ω(n) rounds. In the presence of vertex adversaries, known as semi-honest, we introduce the Forbidden-Set Broadcast problem: In this problem, the vertices of the graph are partitioned into two sets, trusted and untrusted, denoted as R, F ⊆ V, respectively, such that G[R] is connected. It is then desired to exchange a secret message m^* between all the trusted vertices while leaking no information to the untrusted set F. Our algorithm works in Õ(D+√|R|) rounds and its security guarantees hold even when all the untrusted vertices F are controlled by a (centralized) adversary.

Cite as

Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST Algorithms Against Eavesdroppers. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hitron_et_al:LIPIcs.DISC.2022.27,
  author =	{Hitron, Yael and Parter, Merav and Yogev, Eylon},
  title =	{{Broadcast CONGEST Algorithms Against Eavesdroppers}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.27},
  URN =		{urn:nbn:de:0030-drops-172186},
  doi =		{10.4230/LIPIcs.DISC.2022.27},
  annote =	{Keywords: congest, edge-connectivity, secret sharing}
}
Document
The Weakest Failure Detector for Genuine Atomic Multicast

Authors: Pierre Sutra

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
Atomic broadcast is a group communication primitive to order messages across a set of distributed processes. Atomic multicast is its natural generalization where each message m is addressed to dst(m), a subset of the processes called its destination group. A solution to atomic multicast is genuine when a process takes steps only if a message is addressed to it. Genuine solutions are the ones used in practice because they have better performance. Let 𝒢 be all the destination groups and ℱ be the cyclic families in it, that is the subsets of 𝒢 whose intersection graph is hamiltonian. This paper establishes that the weakest failure detector to solve genuine atomic multicast is 𝜇 = (∧_{g,h ∈ 𝒢} Σ_{g ∩ h}) ∧ (∧_{g ∈ 𝒢} Ω_g) ∧ γ, where Σ_P and Ω_P are the quorum and leader failure detectors restricted to the processes in P, and γ is a new failure detector that informs the processes in a cyclic family f ∈ ℱ when f is faulty. We also study two classical variations of atomic multicast. The first variation requires that message delivery follows the real-time order. In this case, 𝜇 must be strengthened with 1^{g ∩ h}, the indicator failure detector that informs each process in g ∪ h when g ∩ h is faulty. The second variation requires a message to be delivered when the destination group runs in isolation. We prove that its weakest failure detector is at least 𝜇 ∧ (∧_{g, h ∈ 𝒢} Ω_{g ∩ h}). This value is attained when ℱ = ∅.

Cite as

Pierre Sutra. The Weakest Failure Detector for Genuine Atomic Multicast. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{sutra:LIPIcs.DISC.2022.35,
  author =	{Sutra, Pierre},
  title =	{{The Weakest Failure Detector for Genuine Atomic Multicast}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{35:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.35},
  URN =		{urn:nbn:de:0030-drops-172267},
  doi =		{10.4230/LIPIcs.DISC.2022.35},
  annote =	{Keywords: Failure Detector, State Machine Replication, Consensus}
}
Document
Brief Announcement
Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies

Authors: Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is 2-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of O(log m/ log log m) and a lower bound of Ω(log m/ log log m) for polynomial-time approximation algorithms, where m is the number of static links. Under splittable (resp., unsplittable) and non-segregated routing, even for demands of a single source (resp., destination), the problem cannot be approximated better than Ω(c_{max}/c_{min}) unless P=NP, where c_{max} (resp., c_{min}) denotes the maximum (resp., minimum) capacity. It is still NP-hard for uniform capacities, but can be solved efficiently for a single commodity and uniform capacities.

Cite as

Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid. Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dai_et_al:LIPIcs.DISC.2022.42,
  author =	{Dai, Wenkai and Dinitz, Michael and Foerster, Klaus-Tycho and Schmid, Stefan},
  title =	{{Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.42},
  URN =		{urn:nbn:de:0030-drops-172330},
  doi =		{10.4230/LIPIcs.DISC.2022.42},
  annote =	{Keywords: Congestion, Reconfigurable Networks, Algorithms, Complexity}
}
Document
RANDOM
A Sublinear Local Access Implementation for the Chinese Restaurant Process

Authors: Peter Mörters, Christian Sohler, and Stefan Walzer

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


Abstract
The Chinese restaurant process is a stochastic process closely related to the Dirichlet process that groups sequentially arriving objects into a variable number of classes, such that within each class objects are cyclically ordered. A popular description involves a restaurant, where customers arrive one by one and either sit down next to a randomly chosen customer at one of the existing tables or open a new table. The full state of the process after n steps is given by a permutation of the n objects and cannot be represented in sublinear space. In particular, if we only need specific information about a few objects or classes it would be preferable to obtain the answers without simulating the process completely. A recent line of research [Oded Goldreich et al., 2010; Moni Naor and Asaf Nussboim, 2007; Amartya Shankha Biswas et al., 2020; Guy Even et al., 2021] attempts to provide access to huge random objects without fully instantiating them. Such local access implementations provide answers to a sequence of queries about the random object, following the same distribution as if the object was fully generated. In this paper, we provide a local access implementation for a generalization of the Chinese restaurant process described above. Our implementation can be used to answer any sequence of adaptive queries about class affiliation of objects, number and sizes of classes at any time, position of elements within a class, or founding time of a class. The running time per query is polylogarithmic in the total size of the object, with high probability. Our approach relies on some ideas from the recent local access implementation for preferential attachment trees by Even et al. [Guy Even et al., 2021]. Such trees are related to the Chinese restaurant process in the sense that both involve a "rich-get-richer" phenomenon. A novel ingredient in our implementation is to embed the process in continuous time, in which the evolution of the different classes becomes stochastically independent [Joyce and Tavaré, 1987]. This independence is used to keep the probabilistic structure manageable even if many queries have already been answered. As similar embeddings are available for a wide range of urn processes [Krishna B. Athreya and Samuel Karlin, 1968], we believe that our approach may be applicable more generally. Moreover, local access implementations for birth and death processes that we encounter along the way may be of independent interest.

Cite as

Peter Mörters, Christian Sohler, and Stefan Walzer. A Sublinear Local Access Implementation for the Chinese Restaurant Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{morters_et_al:LIPIcs.APPROX/RANDOM.2022.28,
  author =	{M\"{o}rters, Peter and Sohler, Christian and Walzer, Stefan},
  title =	{{A Sublinear Local Access Implementation for the Chinese Restaurant Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  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.2022.28},
  URN =		{urn:nbn:de:0030-drops-171500},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.28},
  annote =	{Keywords: Chinese restaurant process, Dirichlet process, sublinear time algorithm, random recursive tree, random permutation, random partition, Ewens distribution, simulation, local access implementation, continuous time embedding}
}
Document
Online Metric Allocation and Time-Varying Regularization

Authors: Nikhil Bansal and Christian Coester

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
We introduce a general online allocation problem that connects several of the most fundamental problems in online optimization. Let M be an n-point metric space. Consider a resource that can be allocated in arbitrary fractions to the points of M. At each time t, a convex monotone cost function c_t: [0,1] → ℝ_+ appears at some point r_t ∈ M. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost c_t(x_{r_t}), where x_{r_t} is the fraction of the resource at r_t at the end of time t. For example, when the cost functions are c_t(x) = α x, this is equivalent to randomized MTS, and when the cost functions are c_t(x) = ∞⋅1_{x < 1/k}, this is equivalent to fractional k-server. Because of an inherent scale-freeness property of the problem, existing techniques for MTS and k-server fail to achieve similar guarantees for metric allocation. To handle this, we consider a generalization of the online multiplicative update method where we decouple the rate at which a variable is updated from its value, resulting in interesting new dynamics. We use this to give an O(log n)-competitive algorithm for weighted star metrics. We then show how this corresponds to an extension of the online mirror descent framework to a setting where the regularizer is time-varying. Using this perspective, we further refine the guarantees of our algorithm. We also consider the case of non-convex cost functions. Using a simple 𝓁₂²-regularizer, we give tight bounds of Θ(n) on tree metrics, which imply deterministic and randomized competitive ratios of O(n²) and O(nlog n) respectively on arbitrary metrics.

Cite as

Nikhil Bansal and Christian Coester. Online Metric Allocation and Time-Varying Regularization. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.ESA.2022.13,
  author =	{Bansal, Nikhil and Coester, Christian},
  title =	{{Online Metric Allocation and Time-Varying Regularization}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.13},
  URN =		{urn:nbn:de:0030-drops-169515},
  doi =		{10.4230/LIPIcs.ESA.2022.13},
  annote =	{Keywords: Online algorithms, competitive analysis, k-server, metrical task systems, mirror descent, regularization}
}
Document
Relating Real and Synthetic Social Networks Through Centrality Measures

Authors: Maria J. Blesa, Mihail Eduard Popa, and Maria Serna

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
We perform here a comparative study on the behaviour of real and synthetic social networks with respect to a selection of nine centrality measures. Some of them are topology based (degree, closeness, betweenness), while others consider the relevance of the actors within the network (Katz, PageRank) or their ability to spread influence through it (Independent Cascade rank, Linear Threshold Rank). We run different experiments on synthetic social networks, with 1K, 10K, and 100K nodes, generated according to the Gaussian Random partition model, the stochastic block model, the LFR benchmark graph model and hyperbolic geometric graphs model. Some real social networks are also considered, with the aim of discovering how do they relate to the synthetic models in terms of centrality. Apart from usual statistical measures, we perform a correlation analysis between all the nine measures. Our results indicate that, in general, the correlation matrices of the different models scale nicely with size. Moreover, the correlation plots distinguish four categories that classify most of the real networks studied here. Those categories have a clear correspondence with particular configurations of the models for synthetic networks.

Cite as

Maria J. Blesa, Mihail Eduard Popa, and Maria Serna. Relating Real and Synthetic Social Networks Through Centrality Measures. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{blesa_et_al:LIPIcs.SEA.2022.7,
  author =	{Blesa, Maria J. and Popa, Mihail Eduard and Serna, Maria},
  title =	{{Relating Real and Synthetic Social Networks Through Centrality Measures}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.7},
  URN =		{urn:nbn:de:0030-drops-165410},
  doi =		{10.4230/LIPIcs.SEA.2022.7},
  annote =	{Keywords: centrality measures, influence spread models, synthetic social networks}
}
Document
An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP

Authors: Akshay Gupte, Arie M. C. A. Koster, and Sascha Kuhnke

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
We present an iterative algorithm to compute feasible solutions in reasonable running time to quadratically constrained quadratic programs (QCQPs), which form a challenging class of nonconvex continuous optimization. This algorithm is based on a mixed-integer linear program (MILP) which is a restriction of the original QCQP obtained by discretizing all quadratic terms. In each iteration, this MILP restriction is solved to get a feasible QCQP solution. Since the quality of this solution heavily depends on the chosen discretization of the MILP, we iteratively adapt the discretization values based on the MILP solution of the previous iteration. To maintain a reasonable problem size in each iteration of the algorithm, the discretization sizes are fixed at predefined values. Although our algorithm did not always yield good feasible solutions on arbitrary QCQP instances, an extensive computational study on almost 1300 test instances of two different problem classes - box-constrained quadratic programs with complementarity constraints and disjoint bilinear programs, demonstrates the effectiveness of our approach. We compare the quality of our solutions against those from heuristics and local optimization algorithms in two state-of-the-art commercial solvers and observe that on one instance class we clearly outperform the other methods whereas on the other class we obtain competitive results.

Cite as

Akshay Gupte, Arie M. C. A. Koster, and Sascha Kuhnke. An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{gupte_et_al:LIPIcs.SEA.2022.24,
  author =	{Gupte, Akshay and Koster, Arie M. C. A. and Kuhnke, Sascha},
  title =	{{An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.24},
  URN =		{urn:nbn:de:0030-drops-165585},
  doi =		{10.4230/LIPIcs.SEA.2022.24},
  annote =	{Keywords: Quadratically Constrained Quadratic Programs, Mixed Integer Linear Programming, Heuristics, BoxQP, Disjoint Bilinear}
}
Document
Extended Abstract
Prisma: A Tierless Language for Enforcing Contract-Client Protocols in Decentralized Applications (Extended Abstract)

Authors: David Richter, David Kretzler, Pascal Weisenburger, Guido Salvaneschi, Sebastian Faust, and Mira Mezini

Published in: LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022)


Abstract
Decentralized applications (dApps) consist of smart contracts that run on blockchains and clients that model collaborating parties. dApps are used to model financial and legal business functionality. Today, contracts and clients are written as separate programs - in different programming languages - communicating via send and receive operations. This makes distributed program flow awkward to express and reason about, increasing the potential for mismatches in the client-contract interface, which can be exploited by malicious clients, potentially leading to huge financial losses. In this paper, we present Prisma, a language for tierless decentralized applications, where the contract and its clients are defined in one unit. Pairs of send and receive actions that "belong together" are encapsulated into a single direct-style operation, which is executed differently by sending and receiving parties. This enables expressing distributed program flow via standard control flow and renders mismatching communication impossible. We prove formally that our compiler preserves program behavior in presence of an attacker controlling the client code. We systematically compare Prisma with mainstream and advanced programming models for dApps and provide empirical evidence for its expressiveness and performance. The design space of dApp programming and other multi-party languages depends on one major choice: a local model versus a global model. In a local model, parties are defined in separate programs and their interactions are encoded via send and receive effects. In a global language, parties are defined within one shared program and interactions are encoded via combined send-and-receive operations with no effects visible to the outside world. The global model is followed by tierless [Christian Queinnec, 2000; Cooper et al., 2007; Choi and Chang, 2019; Fowler et al., 2019; Serrano et al., 2006; Serrano and Prunet, 2016; Radanne et al., 2016; Weisenburger et al., 2018] and choreographic [Kohei Honda et al., 2011; Fabrizio Montesi et al., 2014; Saverio Giallorenzo et al., 2020] languages. However, known approaches to dApp programming follow the local model, thus rely on explicitly specifying the client-contract interaction protocol. Moreover, the contract and clients are implemented in different languages, hence, developers have to master two technology stacks. The dominating approach in industry is Solidity [Mix, 2019] for the contract and JavaScript for clients. Solidity relies on expressing the protocol using assertions in the contract code, which are checked at run time [Solidity documentation - common patterns, 2020]. Failing to insert the correct assertions may give parties illegal access to monetary values to the detriment of others [Nikolić et al., 2018; Luu et al., 2016]. In research, contract languages [Ankush Das et al., 2019; Michael J. Coblenz, 2017; Franklin Schrans et al., 2018; Franklin Schrans et al., 2019; Michael J. Coblenz et al., 2019; Michael J. Coblenz et al., 2019; Reed Oei et al., 2020; Sam Blackshear et al., 2019] have been proposed that rely on advanced type systems such as session types, type states, and linear types. The global model has not been explored for dApp programming. This is unfortunate given the potential to get by with a standard typing discipline and to avoid intricacies and potential mismatches of a two-language stack. Our work fills this gap by proposing Prisma - the first language that features a global programming model for Ethereum dApps. While we focus on the Ethereum blockchain, we believe our techniques to be applicable to other smart contract platforms. Prisma enables interleaving contract and client logic within the same program and adopts a direct style (DS) notation for encoding send-and-receive operations (with our awaitCl language construct) akin to languages with async/await [Gavin M. Bierman et al., 2012; Scala async rfc]. DS addresses shortcomings with the currently dominant encoding of the protocol’s finite state machines (FSM) [Mix, 2019; Michael J. Coblenz, 2017; Franklin Schrans et al., 2018; Franklin Schrans et al., 2019; Michael J. Coblenz et al., 2019; Michael J. Coblenz et al., 2019]. We argue writing FSM style corresponds to a control-flow graph of basic blocks, which is low-level and more suited to be written by a compiler than by a human. With FSM style, the contract is a passive entity whose execution is driven by clients. whereas the DS encoding allows the contract to actively ask clients for input, fitting dApp execution where a dominant contract controls execution and diverts control to other parties when their input is needed. In the following Prisma snippet, the payout function is a function invoked by the contract when it is time to pay money to a client. In Prisma, variables, methods and classes are separated into two namespaces, one for the contract and one for the clients. The payout method is located on the contract via the annotation @co. The body of the method diverts the control to the client using awaitCl(...) { ... }, hence the contained readLine call is executed on the client. Note that no explicit send/receive operations are needed but the communication protocol is expressed through the program control flow. Only after the check client == toBePayed that the correct client replied, the current contact balance balance() is transferred to the client via transfer. @co def payout(toBePayed: Arr[Address]): Unit = { awaitCl(client => client == toBePayed) { readLine("Press enter for payout") } toBePayed.transfer(balance()) } Overall, Prisma relieves the developer from the responsibility of correctly managing distributed, asynchronous program flows and the heterogeneous technology stack. Instead, the burden is put on the compiler, which distributes the program flow by means of selective continuation-passing-style (CPS) translation and defunctionalisation and inserts guards against malicious client interactions. We needed to develop a CPS translation for the code that runs on the Ethereum Virtual Machine (EVM) since the EVM has no built-in support for concurrency primitives which could be used for asynchronous communication. While CPS translations are well-known, we cannot use them out-of-the-box because the control flow is interwoven with distribution in our case. A CPS translation that does not take distribution into account would allow malicious clients to force the contract to deviate from the intended control flow by sending a spoofed continuation. Thus, it was imperative to prove correctness of our distributed CPS translation to ensure control-flow integrity of the contract.

Cite as

David Richter, David Kretzler, Pascal Weisenburger, Guido Salvaneschi, Sebastian Faust, and Mira Mezini. Prisma: A Tierless Language for Enforcing Contract-Client Protocols in Decentralized Applications (Extended Abstract). In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 35:1-35:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{richter_et_al:LIPIcs.ECOOP.2022.35,
  author =	{Richter, David and Kretzler, David and Weisenburger, Pascal and Salvaneschi, Guido and Faust, Sebastian and Mezini, Mira},
  title =	{{Prisma: A Tierless Language for Enforcing Contract-Client Protocols in Decentralized Applications}},
  booktitle =	{36th European Conference on Object-Oriented Programming (ECOOP 2022)},
  pages =	{35:1--35:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-225-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{222},
  editor =	{Ali, Karim and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2022.35},
  URN =		{urn:nbn:de:0030-drops-162632},
  doi =		{10.4230/LIPIcs.ECOOP.2022.35},
  annote =	{Keywords: Domain Specific Languages, Smart Contracts, Scala}
}
  • Refine by Author
  • 6 Müller-Schloer, Christian
  • 4 Bellman, Kirstie
  • 4 Komusiewicz, Christian
  • 4 Konrad, Christian
  • 4 Schmeck, Hartmut
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Distributed algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 2 Networks → Network algorithms
  • 2 Theory of computation → Algebraic complexity theory
  • 2 Theory of computation → Dynamic graph algorithms
  • Show More...

  • Refine by Keyword
  • 4 self-organization
  • 3 approximation algorithms
  • 3 self-healing
  • 2 Approximation algorithms
  • 2 C Preprocessor
  • Show More...

  • Refine by Type
  • 93 document

  • Refine by Publication Year
  • 18 2017
  • 13 2006
  • 12 2022
  • 8 2008
  • 7 2016
  • 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