Blockchain technologies enable the decentralized storage and verification of records, such as financial transactions.
Systems like Bitcoin and Ethereum see a considerable usage and have market values in the order of 10s of billions of dollars.
A recent evolution of blockchain consensus systems, which have traditionally been maintaining a chain of blocks of transactions, is the introduction of Directed Acyclic Graph (DAG)-based algorithms.
In these new systems, popularized by companies such as Sui and IOTA, transactions are positioned in rows of blocks that are connected in a DAG.
The participants of these systems add blocks to the DAG in parallel, which has been shown to result in higher throughput, lower latency and higher decentralization.

Some blockchains, including DAG-based ones, support smart contracts, which enable the execution of (almost) arbitrary code with correctness, verifiability, and consistency guarantees.
A natural usage of smart contracts is Decentralized Finance (DeFi).
DeFi implements services that are offered in traditional centralized finance, such as loans and currency exchanges, in a decentralized fashion.
For example, instead of a central authority possessing different currencies and fixing their exchange rates through supply and demand of their clients, a decentralized exchange (DeX) can match buyers and sellers and update the exchange rate on the fly based on the supply of the two tokens.

The promise of safely removing the need for a central authority and regulations is however undermined by current blockchain implementations.
Intuitively, the decentralized nature of DeFi should prevent malicious behavior, but in practice validators (i.e., the entities that maintain the blockchain) have the possibility to do so.
For example, in Ethereum, miners have full control over the content of blocks.
This means that they have the power to reorder and inject transactions.
The profit that is obtained this way is called Miner Extractable Value (MEV).
% Indeed, the output of arbitrary code, in particular of DeFi code, can heavily depend on the transaction execution order.
% For example, in a DeX, if the exchange rate between two tokens is computed on the fly, an adversary can manipulate the transaction order to extract a profit.

MEV is not desirable because it introduces hidden costs for correct users: higher fees, worse exchange rates and network congestion.
Different mitigation techniques have been proposed over the years.
The most commonly used in practice are systems that allow the re-distribution or an easier extraction of MEV.
These have significant ethical concerns, as they increase resource consumption while still maintaining the negative side effects of MEV on the average consumer.

It is also possible to anonymize the content of transactions until after their execution, making it more difficult for attackers to exploit their contents for profit.
While anonymizing transactions makes an attacker's task more difficult, it requires the use of expensive cryptographic primitives or the presence of a trusted third-party, and transaction metadata might still be exploited to enable MEV.

The most interesting concept from the academic community against MEV is Order Fairness, which promises that transactions will be executed in an order that accurately represents the actual order in which the transactions were made public.
These systems have been mainly studied as an extension of existing linear consensus systems, but have been scarcely applied to DAGs.
Indeed, DAGs have been thought to have some inherent resistance to MEV extraction, but recent work by Zhang et al. has shown otherwise.

To the best of our knowledge, the only system that combines DAG-based consensus and Order Fairness is FairDAG.
While this protocol provides strong theoretical guarantees, we will show that it lacks real-world applicability and contains some suboptimal design decisions.

In this work we propose Tilikum, the first DAG-based consensus protocol that upholds Order Fairness through Ordering linearizability without sacrificing usability and improving average throughput by about 15 times.

The Algorithm Selection Problem is a relevant question in computer science that would enable us to predict which algorithm would perform better on a given instance of a problem.
Different solutions have been proposed, either using Mixed Integer Programming or machine learning models, but both suffer from either poor scalability, no guarantees of optimality, or not interpretable models that could be used to gain insights into the nature of the problem.
In this work we propose a dynamic programming method to build Optimal Decision Trees to solve the Algorithm Selection Problem, giving us an interpretable model that is globally optimal over the training dataset. We also show that this method is orders of magnitude faster in training trees that are identical to the current state-of-the-art and propose possible improvements for future work.