Fabien Dufoulon

Fabien Dufoulon

Auto-generated profile, based on publicly available information

Fabien Dufoulon

Lancaster University, Lancaster, United Kingdom

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

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

Representative Publications

View All Publications
16 June 2023
Verified
Conference Paper
Open access
FDFabien Dufoulon
Fabien Dufoulon
WMWilliam K. Moses
William K. Moses
GPGopal Pandurangan
Gopal Pandurangan
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have O(log n) round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best known lower bound is [EQUATION] [Kuhn, Moscibroda, Wattenhofer, JACM 2016]. Breaking past the O(log n) round complexity upper bound or showing stronger lower bounds have been longstanding open problems. Energy is a premium resource in various settings such as battery-powered wireless networks and sensor networks. The bulk of the energy is used by nodes when they are awake, i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping, it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake, also called the (worst-case) awake complexity. An intriguing open question is whether one can design a distributed MIS algorithm that has significantly smaller awake complexity compared to existing algorithms. In particular, the question of obtaining a distributed MIS algorithm with o(log n) awake complexity was left open in [Chatterjee, Gmyr, Pandurangan, PODC 2020]. Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of O(log n) and also bypassing its fundamental [EQUATION] round complexity lower bound exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in O(log log n) awake complexity with high probability.1 However, this algorithm has a round complexity that is O(poly(n)). We then show how to drastically improve the round complexity at the cost of a slight increase in awake complexity by presenting a randomized distributed (Monte Carlo) algorithm for MIS that, with high probability computes an MIS in O((log log n) log* n) awake complexity and O((log3 n)(log log n) log* n) round complexity. Our algorithms work in the CONGEST model where messages of size O(log n) bits can be sent per edge per round.

1 June 2017
Verified
Conference Paper
Closed access
ADAlexandre Dambreville
Alexandre Dambreville
JTJoanna Tomasik
Joanna Tomasik
JCJohanne Cohen
Johanne Cohen
FDFabien Dufoulon
Fabien Dufoulon
We address online scheduling for servers of Cloud service providers. Each server is composed of several variable-speed processors whose power function is convex. The servers may be busy, idle or switched off. The objective of our scheduling is to minimize the energy consumed by a Cloud computing platform. To achieve this goal, we try to anticipate computing demands by predicting a workload, then we modify the set of available servers to fit this prediction and finally we schedule our jobs on the available servers. To schedule jobs we have developed the POD (Predict Optimize Dispatch) algorithm. We evaluate its performance for real-life traces in the presence of different types of prediction. The analysis shows that our scheduling reduces energy consumption considerably.

13 June 2025
Verified
Conference Paper
Open access
FDFabien Dufoulon
Fabien Dufoulon
FMFrédéric Magniez
Frédéric Magniez
GPGopal Pandurangan
Gopal Pandurangan

13 June 2025
Verified
Conference Paper
Open access
FDFabien Dufoulon
Fabien Dufoulon
GPGopal Pandurangan
Gopal Pandurangan

9 October 2025 in arXiv
Verified
Preprint
Open access
PDF file
DBDominick Banasik
Dominick Banasik
VDVarsha Dani
Varsha Dani
FDFabien Dufoulon
Fabien Dufoulon
AGAayush Gupta
Aayush Gupta
THThomas P. Hayes
Thomas P. Hayes
GPGopal Pandurangan
Gopal Pandurangan
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the Radio Network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model -- with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1. CD model: We present a randomized distributed MIS algorithm with energy complexity $O(\log n)$, round complexity $O(\log^2 n)$, and failure probability $1 / poly(n)$, where $n$ is the network size. We show that our energy complexity is optimal by showing a matching $Ω(\log n)$ lower bound. 2. no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity $O(\log^2n \log \log n)$, round complexity $O(\log^3 n \log Δ)$, and failure probability $1 / poly(n)$. The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of $O(\log^3 n)$ of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.

30 April 2025 in arXiv
Verified
Preprint
Open access
PDF file
FDFabien Dufoulon
Fabien Dufoulon
SPShreyas Pai
Shreyas Pai
GPGopal Pandurangan
Gopal Pandurangan
SPSriram Pemmaraju
Sriram Pemmaraju
PRPeter Robinson
Peter Robinson
Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the \emph{message complexity} of distributed computing problems and its relationship (if any) with round complexity is still quite limited. To illustrate, for many fundamental distributed graph optimization problems such as (exact) diameter computation, All-Pairs Shortest Paths (APSP), Maximum Matching etc., while (near) round-optimal algorithms are known, message-optimal algorithms are hitherto unknown. More importantly, the existing round-optimal algorithms are not message-optimal. This raises two important questions: (1) Can we design message-optimal algorithms for these problems? (2) Can we give message-time tradeoffs for these problems in case the message-optimal algorithms are not round-optimal? In this work, we focus on a fundamental graph optimization problem, \emph{All Pairs Shortest Path (APSP)}, whose message complexity is still unresolved. We present two main results in the CONGEST model: (1) We give a message-optimal (up to logarithmic factors) algorithm that solves weighted APSP, using $\tilde{O}(n^2)$ messages. This algorithm takes $\tilde{O}(n^2)$ rounds. (2) For any $0 \leq \varepsilon \le 1$, we show how to solve unweighted APSP in $\tilde{O}(n^{2-\varepsilon })$ rounds and $\tilde{O}(n^{2+\varepsilon })$ messages. At one end of this smooth trade-off, we obtain a (nearly) message-optimal algorithm using $\tilde{O}(n^2)$ messages (for $\varepsilon = 0$), whereas at the other end we get a (nearly) round-optimal algorithm using $\tilde{O}(n)$ rounds (for $\varepsilon = 1$). This is the first such message-time trade-off result known.