Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
education [2022/02/25 11:00] fablpd |
education [2024/05/16 16:27] fablpd |
||
|---|---|---|---|
| Line 8: | Line 8: | ||
| \\ | \\ | ||
| - | * [[education/ca_2021|Concurrent Algorithms]] (theory & practice) | + | * [[education/ca_2023|Concurrent Algorithms]] (theory & practice) |
| - | * [[education/da|Distributed Algorithms]] (theory & practice) | + | * [[education/da_2023|Distributed Algorithms]] (theory & practice) |
| \\ | \\ | ||
| The lab taught in the past the following courses: | The lab taught in the past the following courses: | ||
| Line 28: | Line 28: | ||
| * **[[cryptocurrencies|Cryptocurrencies]]**: We have several project openings as part of our ongoing research on designing new cryptocurrency systems. Please contact [[rachid.guerraoui@epfl.ch|Prof. Rachid Guerraoui]]. | * **[[cryptocurrencies|Cryptocurrencies]]**: We have several project openings as part of our ongoing research on designing new cryptocurrency systems. Please contact [[rachid.guerraoui@epfl.ch|Prof. Rachid Guerraoui]]. | ||
| - | * **On the design and implementation of scalable and secure blockchain algorithms**: Consensus has recently gained in popularity with the advent of blockchain technologies. Unfortunately, most blockchains do not scale due, in part, to their centralized (leader-based) limitation. We recently designed a promising fully decentralised (leader-less) algorithm that promises to scale to large networks. The goal of this project is to implement it in rust and compare its performance on AWS instances against a traditional leader-based alternative like BFT-Smart whose code will be provided. Contact [[https://people.epfl.ch/vincent.gramoli|Vincent Gramoli]] for more information. | + | * **Tackling data heterogeneity in Byzantine-robust ML**: Context: Distributed ML is a very effective paradigm to learn collaboratively when all users correctly follow the protocol. However, some users may behave adversarially and measures should be taken to protect against such Byzantine behavior [ [[https://papers.nips.cc/paper/2017/hash/f4b9ec30ad9f68f89b29639786cb62ef-Abstract.html|1]], [[https://proceedings.mlr.press/v162/farhadkhani22a.html|2]] ]. In real-world settings, users have different datasets (i.e. non-iid), which makes defending against Byzantine behavior challenging, as was shown recently in [ [[https://proceedings.neurips.cc/paper/2021/hash/d2cd33e9c0236a8c2d8bd3fa91ad3acf-Abstract.html|3]], [[https://openreview.net/forum?id=jXKKDEi5vJt|4]] ]. Some defenses were proposed to tackle data heterogeneity, but their performance is suboptimal on simple learning tasks. Goal: Develop defenses with special emphasis on empirical performance and efficiency in the heterogeneous setting. Contact [[https://people.epfl.ch/youssef.allouah?lang=en|Youssef Allouah]] for more information. |
| - | * **Making Blockchain Accountable**: Abstract: One of the key drawback of blockchain is its lack of accountability. In fact, it does not hold participants responsible for their actions. This is easy to see as a malicious or Byzantine user typically double spends in a branch of blocks that disappears from the system, hence remaining undetected. Accountability is often thought to be communication costly: to detect a malicious participants who has sent deceitful messages to different honest participants for them to disagree, one may be tempted to force each honest participant to exchange all the messages they receive and cross-check them. However, we have recently designed an algorithm that shares the same communication complexity as the current consensus algorithms of existing blockchains. The goal of this project is to make blockchains accountable by implementing this accountable consensus algorithm and comparing it on a distributed set of machines against a baseline implementation. Contact [[https://people.epfl.ch/vincent.gramoli|Vincent Gramoli]] for more information. | + | * **Benchmark to certify Byzantine-robustness in ML**: Context: Multiple attacks have been proposed to instantiate a Byzantine adversary in distributed ML [ [[https://proceedings.neurips.cc/paper/2019/hash/ec1c59141046cd1866bbbcdfb6ae31d4-Abstract.html|1]], [[https://proceedings.mlr.press/v115/xie20a.html|2]] ]. While these attacks have been successful against known defenses, it remains unknown whether stronger attacks exist. As such, a strong benchmark is needed, to go beyond the cat-and-mouse game illustrating the existing research. Ideally, similar to other ML subfields such as privacy-preserving ML or adversarial examples, the desired benchmark should guarantee that no stronger attack exists. Goal: Develop a strong benchmark for attacks in Byzantine ML. Contact [[https://people.epfl.ch/youssef.allouah?lang=en|Youssef Allouah]] for more information. |
| - | * **Robust mean estimation**: In recent years, many algorithms have been proposed to perform robust mean estimation, which has been shown to be equivalent to robust gradient-based machine learning. A new concept has been proposed to define the performance of a robust mean estimator, called the [[https://arxiv.org/abs/2008.00742|averaging constant]] (along with the Byzantine resilience). This research project consists of computing the theoretical averaging constant of different proposed robust mean estimators, and to study their empirical performances on randomly generated vectors. Contact [[https://people.epfl.ch/sadegh.farhadkhani?lang=en|Sadegh Farhadkhani]] for more information. | ||
| - | * **Accelerate Byzantine collaborative learning**: [[https://arxiv.org/abs/2008.00742|Our recent NeurIPS paper]] proposed algorithms for collaborative machine learning in the presence of Byzantine nodes, which have been proved to be near optimal with respect to optimality at convergence. However, these algorithms require all-to-all communication at every round, which is suboptimal. This research consists of designing a practical solution to Byzantine collaborative learning, based on the idea of a random communication network at each round, with both theoretical guarantees and practical implementation. Contact [[https://people.epfl.ch/sadegh.farhadkhani?lang=en|Sadegh Farhadkhani]] for more information. | + | * **Evaluating Distributed Systems**: By nature, distributed systems are hard to evaluate. Deploying real world systems and orchestrating large scale experiments require dedicated software and expensive infrastructure. As a result, many widespread distributed systems are not properly evaluated, tested on uncomparable or irreproductible setups. Projects of this category aim to build efficient and scalable evaluation tools for distributed systems. Diablo-related projects involve building a test harness for evaluating blockchains (skills required: network programming, blockchain, Go, C++). Another set of projects focus on creating large networks simulators able to emulate hundreds of powerful machines from a single physical server (skills required: system programming, virtualization, C, C++). Contact [[https://people.epfl.ch/gauthier.voron/?lang=en|Gauthier Voron]] for more information. |
| - | * **Decentralize Tournesol’s learning algorithms**: The [[https://tournesol.app/|Tournesol platform]] leverages the contributions of its community of contributors to assign a « should be more recommended » score to YouTube videos rated by the contributors, using a learning algorithm. Currently, the computations are performed on a central server. But as Tournesol’s user base grows, and as more sophisticated learning algorithms are considered for deployment, there is a growing need to decentralize the computations of the learning algorithm. This project aims to build a framework, which will enable Tournesol users to run part of the computations of Tournesol’s scores directly in their browsers. Contact [[https://people.epfl.ch/le.hoang/?lang=en|Lê Nguyên Hoang]] for more information. | + | * **Smart Contracts and Decentralized Software**: Smart contracts are one of the key innovations brought by blockchains, enabling users to deploy codes that get executed transparently, autonomously and in a decentralized fashion. However, the applicability of smart contracts is hampered by their limited performance. Projects of this category aim to build runtime environments for fast and efficient execution of smart contracts. The first set of projects address the challenge of deterministic parallelism, or how to use several threads to execute a smart contract while guaranteeing a deterministic result (skills required: compiler principles, Rust). The second set of projects explores the concept of non-transactional smart contracts, a way to remove the notion of gas in smart contracts (skills required: system programming, C, Rust). The last set of projects focus on high-throughput cryptographic primitives: how to use hardware acceleration to speed up transaction authentication (skills required: cryptography principles, GPU programming, C, Assembly). Contact [[https://people.epfl.ch/gauthier.voron/?lang=en|Gauthier Voron]] for more information. |
| - | * **Listening to the silent majority**: Vanilla machine learning from user-generated data inevitably favors those who generated the most amounts of data. But this means that learning algorithms will be optimized for these users, rather than for the silent majority. This research aims to correct for this bias, by trying to infer what data the majority would have likely generated, and by inferring what the models would have learned if the silent majority’s data was included in the training of the models. It involves both designing algorithms, proving correctness and implementing them. This research is motivated by the [[https://tournesol.app/|Tournesol project]]. Contact [[https://people.epfl.ch/le.hoang/?lang=en|Lê Nguyên Hoang]] for more information. | + | * **Safe and Scalable Consensus**: Decentralized systems like cryptocurrencies rely on the concept of consensus. This component is critical as it dictates how performant, safe and scalable a distributed system is. Over the last years, the DCL has pushed the performance of consensus algorithms to unprecedented levels but the practical safety and scalability are yet to be addressed. Projects of this category focus on designing and implementing distributed consensus algorithms which are safer against cyberattacks or adverse environments and work with higher number of participants. On one side, some projects explore new consensus designs with good theoretical guarantees and practical behaviors (skills required: distributed algorithms, network programming, Go). On the other side, some projects focus on ensuring the correctness of existing consensus algorithms through model checking at various levels (skills required: distributed algorithms, Rust, TLA+). Contact [[https://people.epfl.ch/gauthier.voron/?lang=en|Gauthier Voron]] for more information. |
| - | * **Should experts be given more voting rights?**: This is a question that Condorcet tackled in 1785, through what is now known as the jury problem. However, his model was crude and does not apply to many critical problems, e.g. determining if a video on vaccines should be largely recommended. This research aims to better understand how voting rights should be allocated, based not only on how likely voters are to be correct, but also on the correlations between the voters’ judgments. So far, it involves mostly a theoretical analysis. This research is motivated by the [[https://tournesol.app/|Tournesol project]]. Contact [[https://people.epfl.ch/le.hoang/?lang=en|Lê Nguyên Hoang]] for more information. | ||
| - | * **Probabilistic Byzantine Resilience**: Development of high-performance, Byzantine-resilient distributed systems with provable probabilistic guarantees. Two options are currently available, both building on previous work on probabilistic Byzantine broadcast: (i) a theoretical project, focused the correctness of probabilistic Byzantine-tolerant distributed algorithms; (ii) a practical project, focused on numerically evaluating of our theoretical results. Please contact [[matteo.monti@epfl.ch|Matteo Monti]] to get more information. | + | * **Robust mean estimation**: In recent years, many algorithms have been proposed to perform robust mean estimation, which has been shown to be equivalent to robust gradient-based machine learning. A new concept has been proposed to define the performance of a robust mean estimator, called the [[https://arxiv.org/abs/2008.00742|averaging constant]] (along with the Byzantine resilience). This research project consists of computing the theoretical averaging constant of different proposed robust mean estimators, and to study their empirical performances on randomly generated vectors. Contact [[https://people.epfl.ch/sadegh.farhadkhani?lang=en|Sadegh Farhadkhani]] for more information. |
| - | * **Distributed coordination using RDMA.** RDMA (Remote Direct Memory Access) allows accessing a remote machine's memory without interrupting its CPU. This technology is gaining traction over the last couple of years, as it allows for the creation of real-time distributed systems. RDMA allows for communication to take place close to the μsec scale, which enables the design and implementation of systems that process requests in only tens of μsec. Current research focuses on achieving real-time failure detection through a combination of novel algorithm design, latest hardware and linux kernel customization. Fast failure detection over RDMA brings the notion of availability to a new level, essentially allowing modern systems to enter the era of 7 nines of availability. Contact [[https://people.epfl.ch/athanasios.xygkis|Athanasios Xygkis]] and [[https://people.epfl.ch/antoine.murat|Antoine Murat]] for more information. | ||
| + | * **Accelerate Byzantine collaborative learning**: [[https://arxiv.org/abs/2008.00742|Our recent NeurIPS paper]] proposed algorithms for collaborative machine learning in the presence of Byzantine nodes, which have been proved to be near optimal with respect to optimality at convergence. However, these algorithms require all-to-all communication at every round, which is suboptimal. This research consists of designing a practical solution to Byzantine collaborative learning, based on the idea of a random communication network at each round, with both theoretical guarantees and practical implementation. Contact [[https://people.epfl.ch/sadegh.farhadkhani?lang=en|Sadegh Farhadkhani]] for more information. | ||
| - | |||
| - | \\ | + | * **Probabilistic Byzantine Resilience**: Development of high-performance, Byzantine-resilient distributed systems with provable probabilistic guarantees. Two options are currently available, both building on previous work on probabilistic Byzantine broadcast: (i) a theoretical project, focused the correctness of probabilistic Byzantine-tolerant distributed algorithms; (ii) a practical project, focused on numerically evaluating of our theoretical results. Please contact [[matteo.monti@epfl.ch|Matteo Monti]] to get more information. |
| - | * **Byzantine-resilient heterogeneous GANs**: Byzantine-resilient federated learning has emerged as a major theme over the last couple of years, in grand part due to the need to distribute machine learning across many nodes, due to performance and privacy concerns. Until now it has focused on training a single model across many workers and many parameter serves. While this approach has brought on formidable results - including in GAN training, the topic of efficient, distributed and byzantine-resilient training of heterogeneous architectures remain relatively unexplored. In the context of Generative adversarial networks (GANs), such learning is critical to training light discriminators that can specialize in detecting specific featuers of generator-generated images. The goal of this project will be to investigate the potential for GAN training process poisonning by malicious discriminators and generators and investigate efficient protocols to ensure the training process robustness. You will need to have experience with scientific computing in Python, ideally with PyTorch experience, and notions of distributed computing. Contact [[https://people.epfl.ch/andrei.kucharavy|Andrei Kucharavy]] for more information. | + | * **Microsecond-scale dependable systems.** Modern networking technologies such as RDMA (Remote Direct Memory Access) allow for sub-microsecond communication latency. Combined with emerging data center architectures, such as disaggregated resources pools, they open the door to novel blazing-fast and resource-efficient systems. Our research focuses on designing such microsecond-scale systems that can also tolerate faults. Our vision is that tolerating network asynchrony as well as faults (crash and/or Byzantine) is a must, but that it shouldn't affect the overall performance of a system. We achieve this goal by devising and implementing novel algorithms tailored for new hardware and revisiting theoretical models to better reflect modern data centers. Previous work encompasses microsecond-scale (BFT) State Machine Replication, Group Membership Services and Key-Value Stores (OSDI'20, ATC'22 and ASPLOS'23). Overall, if you are interested in making data centers faster and safer, contact [[https://people.epfl.ch/athanasios.xygkis|Athanasios Xygkis]] and [[https://people.epfl.ch/antoine.murat|Antoine Murat]] for more information. |
| - | \\ | + | |
| - | * **Hijacking proof-of-work to make it useful: distributed gradient-free learning approach** | ||
| - | Proof-of-work blockchains - notably Bitcoin and Ethereum - reach a probabilistic consensus about the contents of the blockchain by a mechanism of probabilistic leader election. Every contributor to the consensus tries to solve a puzzle, and the first one to succeed is elected a leader, allowed to create the next block and publicly add information to it. The puzzle needs to be hard to solve and easy to verify, solvable only by random guessing and not allowing for any shortcuts and allow for its difficulty to be tuned so that nodes don't find answers to it simultaneously and take different leaderships forking the chain in two. Partial cryptographic hash reversal has traditionally been a perfect candidate for such puzzle, but it has no interest outside being a challenge for blockchain. And with 100-300 PetaFLOP/s (drawing 100 TWh/y) of general purpose computational power being tied into Ethereum blockchain alone as of early 2022, the waste of computational resources and energy is colossal. | + | |
| - | While the interest of blockchains and the suitability of proof-of-work as a mechanism to run them is widely debated, it's at this day the mechanism for the two largest ones. We try to at least use some of that challenge useful by injecting a "try" step of a (1,λ)-ES evolutionary search algorithm into the hash computation loop, slowing it down and making it do something useful in during the slowdown period. This class of evolutionary search algorithm achieves a good performance on black-bock optimization tasks (sometimes exceeding RL approaches in traditionally RL problems), is embarrassingly parallel, fits well the requirements for a proof-of-work function and can be empirically optimized to minimize the waste of computational resources during a training run. | ||
| - | However, in its current state the (1,λ)-ES-based useful proof-of-work has been proven to work in cases where the data used for the training tasks can be fully replicated among the nodes. For numerous applications, it is not an option. Finding ways to solve that problem, both from a theoretical and an experimental perspective will be the goal of this project. | + | \\ |
| - | You will need solid skills in Python (Rust and WebAssembly are a plus), basic understanding of distributed algorithms and of machine learning concepts. Some familiarity with blockchains and black box optimization is a plus, but is not a requirement. Contact Andrei Kucharavy (andrei.kucharavy@epfl.ch) for more information. | ||
| Line 73: | Line 66: | ||
| If the subject of a Master Project interests you as a Semester Project, please contact the supervisor of the Master Project to see if it can be considered for a Semester Project. | If the subject of a Master Project interests you as a Semester Project, please contact the supervisor of the Master Project to see if it can be considered for a Semester Project. | ||
| - | EPFL I&C duration, credits and workload information are available [[https://www.epfl.ch/schools/ic/education/|here]]. Don't hesitate to contact the project supervisor if you want to complete your Semester Project outside the regular semester period. | + | EPFL I&C duration, credits and workload information are available on [[https://www.epfl.ch/schools/ic/education/master/semester-project-msc/|https://www.epfl.ch/schools/ic/education/master/semester-project-msc/]]. |