Patrick Eugster

Prof. Patrick Eugster


Research Focus & Metrics

Academic Career Length

21Years (2006-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 October 2021 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MVMalte Viering
Malte Viering
RHRaymond Hu
Raymond Hu
PEPatrick Eugster
Patrick Eugster
LZLukasz Ziarek
Lukasz Ziarek
This paper presents a formulation of multiparty session types (MPSTs) for practical fault-tolerant distributed programming. We tackle the challenges faced by session types in the context of distributed systems involving asynchronous and concurrent partial failures – such as supporting dynamic replacement of failed parties and retrying failed protocol segments in an ongoing multiparty session – in the presence of unreliable failure detection. Key to our approach is that we develop a novel model of event-driven concurrency for multiparty sessions. Inspired by real-world practices, it enables us to unify the session-typed handling of regular I/O events with failure handling and the combination of features needed to express practical fault-tolerant protocols. Moreover, the characteristics of our model allow us to prove a global progress property for well-typed processes engaged in multiple concurrent sessions, which does not hold in traditional MPST systems. To demonstrate its practicality, we implement our framework as a toolchain and runtime for Scala, and use it to specify and implement a session-typed version of the cluster management system of the industrial-strength Apache Spark data analytics framework. Our session-typed cluster manager composes with other vanilla Spark components to give a functioning Spark runtime; e.g., it can execute existing third-party Spark applications without code modification. A performance evaluation using the TPC-H benchmark shows our prototype implementation incurs an average overhead below 10%.

17 April 2021
Verified
Conference Paper
Open access
MBMarcel Blöcher
Marcel Blöcher
LWLin Wang
Lin Wang
PEPatrick Eugster
Patrick Eugster
MSMax Schmidt
Max Schmidt
The recent trend towards more programmable switching hardware in data centers opens up new possibilities for distributed applications to leverage in-network computing (INC). Literature so far has largely focused on individual application scenarios of INC, leaving aside the problem of coordinating usage of potentially scarce and heterogeneous switch resources among multiple INC scenarios, applications, and users. The traditional model of resource pools of isolated compute containers does not fit an INC-enabled data center. This paper describes HIRE, a Holistic INC-aware Resource managEr which allows for server-local and INC resources to be coordinated in a unified manner. HIRE introduces a novel flexible resource (meta-)model to address heterogeneity, resource interchangeability, and non-linear resource requirements, and integrates dependencies between resources and locations in a unified cost model, cast as a min-cost max-flow problem. In absence of prior work, we compare HIRE against variants of state-of-the-art schedulers retrofitted to handle INC requests. Experiments with a workload trace of a 4000 machine cluster show that HIRE makes better use of INC resources by serving 8-30% more INC requests, while at the same time reducing network detours by 20%, and reducing tail placement latency by 50%.

13 March 2023 in ACM Transactions on Privacy and Security
Verified
Journal Article
Open access
RORodrigo Otoni
Rodrigo Otoni
MMMatteo Marescotti
Matteo Marescotti
LALeonardo Alt
Leonardo Alt
PEPatrick Eugster
Patrick Eugster
AHAntti E. J. Hyvärinen
Antti E. J. Hyvärinen
NSNatasha Sharygina
Natasha Sharygina
Smart contracts are tempting targets of attacks, as they often hold and manipulate significant financial assets, are immutable after deployment, and have publicly available source code, with assets estimated in the order of millions of dollars being lost in the past due to vulnerabilities. Formal verification is thus a necessity, but smart contracts challenge the existing highly efficient techniques routinely applied in the symbolic verification of software, due to specificities not present in general programming languages. A common feature of existing works in this area is the attempt to reuse off-the-shelf verification tools designed for general programming languages. This reuse can lead to inefficiency and potentially unsound results, as domain translation is required. In this article, we describe a carefully crafted approach that directly models the central aspects of smart contracts natively, going from the contract to its logical representation without intermediary steps. We use the expressive and highly automatable logic of constrained Horn clauses for modeling and instantiate our approach to the Solidity language. A tool implementing our approach, called Solicitous , was developed and integrated into the SMTChecker module of the Solidity compiler solc. We evaluated our approach on an extensive benchmark set containing 22,446 real-world smart contracts deployed on the Ethereum blockchain over a 27-month period. The results show that our approach is able to establish safety of significantly more contracts than comparable, publicly available verification tools, with an order of magnitude increase in the percentage of formally verified contracts.

16 August 2013
Verified
Conference Paper
Open access
PDF file
KKKirill Kogan
Kirill Kogan
SNSergey Nikolenko
Sergey Nikolenko
WCWilliam Culhane
William Culhane
PEPatrick Eugster
Patrick Eugster
EREddie Ruan
Eddie Ruan
Traffic classification is a core problem underlying efficient implementation of network services. In this work we draw from our experience in classifier design for commercial systems to address this problem in SDN and OpenFlow. We identify methods from other fields of computer science and show research directions that can be applied for efficient design of packet classifiers. Proposed abstractions and design patterns can significantly reduce requirements on network elements and enable deployment of functionality that would be infeasible in a traditional way.

1 January 2009
Verified
Book Chapter
Open access
PDF file
HYHao Yuan
Hao Yuan
PEPatrick Eugster
Patrick Eugster
The context-free language (CFL) reachability problem is well known and studied in computer science, as a fundamental problem underlying many important static analyses such as points-to-analysis. Solving the CFL reachability problem in the general case is very hard. Popular solutions resorting to a graph traversal exhibit a time complexity of O(k3n3) for a grammar of size k. For Dyck CFLs, a particular class of CFLs, this complexity can be reduced to O(kn3). Only recently the first subcubic algorithm was proposed by Chaudhuri, dividing the complexity of predating solutions by a factor of logn. In this paper we propose an effective algorithm for solving the CFL reachability problem for Dyck languages when the considered graph is a bidirected tree with specific constraints. Our solution pre-processes the graph in O(n logn logk) time in a space of O(n logn), after which any Dyck-CFL reachability query can be answered in O(1) time, while a naïve online algorithm will require O(n) time to answer a query or require O(n2) to store the pre-computed results for all pairs of nodes.

27 March 2023 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Open access
DMDanushka Menikkumbura
Danushka Menikkumbura
PTParvin Taheri
Parvin Taheri
EVErico Vanini
Erico Vanini
SFSonia Fahmy
Sonia Fahmy
PEPatrick Eugster
Patrick Eugster
TETom Edsall
Tom Edsall
In this article, we present RoCC , a robust congestion control approach for datacenter networks based on RDMA. RoCC leverages switch queue size as an input to a PI controller, which computes the fair data rate of flows in the queue. The PI parameters are self-tuning to guarantee stability, rapid convergence, and fair and near-optimal throughput in a wide range of congestion scenarios. Our simulation and DPDK implementation results show that RoCC can achieve up to $7\times$ reduction in PFC frames generated under high load levels, compared to DCQCN. At the same time, RoCC can achieve $1.7-4.5\times$ and $1.4-3.9\times$ lower tail latency for long flows and $2.1-7\times$ and $3.5-8.2\times$ lower tail latency for short flows, compared to DCQCN and HPCC, respectively. We also find that RoCC does not require PFC. The functional components of RoCC can be efficiently implemented in P4 and FPGA-based switch hardware.