Publications related to Order-Optimal Consensus Through Randomized Path Averaging

Related publications (30)

Metastability of the Potts Ferromagnet on Random Regular Graphs

We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...

SPRINGER2023

Discovering Influencers in Opinion Formation Over Social Graphs

Ali H. Sayed, Mert Kayaalp, Valentina Shumovskaia

The adaptive social learning paradigm helps model how networked agents are able to form opinions on a state of nature and track its drifts in a changing environment. In this framework, the agents repeatedly update their beliefs based on private observation ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Colin Neil Jones, Yuning Jiang, Yingzhao Lian

This paper presents a novel distributed approach for solving AC power flow (PF) problems. The optimization problem is reformulated into a distributed form using a communication structure corresponding to a hypergraph, by which complex relationships between ...

IEEE2023

Quantization for Distributed Processing and Learning of Structured Data

Isabela Cunha Maia Nobre

In the domains of machine learning, data science and signal processing, graph or network data, is becoming increasingly popular. It represents a large portion of the data in computer, transportation systems, energy networks, social, biological, and other s ...

EPFL2022

Data-driven and Safe Networked Control with Applications to Microgrids

Mustafa Sahin Turan

Today, automatic control is integrated into a wide spectrum of real-world systems such as electrical grids and transportation networks. Many of these systems comprise numerous interconnected agents, perform safety-critical operations, or generate large amo ...

EPFL2022

Two-layer adaptive signal control framework for large-scale networks combining efficient Max-Pressure and Perimeter Control

Nikolaos Geroliminis, Anastasios Kouvelas, Dimitrios Tsitsokas

This work investigates the benefits of a two-layer adaptive signal control framework combining multi-region perimeter control (PC) with distributed Max Pressure (MP) control in selected network intersections. Motivated by MP’s questionable performance in o ...

2022

Motif Cut Sparsifiers

Mikhail Kapralov, Jakab Tardos, Mikhail Makarov

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Probabilistic and temporal failure detectors for solving distributed problems

Rachid Guerraoui

Failure detectors (FD)s are celebrated for their modularity in solving distributed problems. Algorithms are constructed using FD building blocks. Synchrony assumptions to implement FDs are studied separately and are typically expressed as eventual guarante ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2021

Dynamic Byzantine Reliable Broadcast

Rachid Guerraoui, Jovan Komatovic, Dragos-Adrian Seredinschi

Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a co ...

Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik2021

The Hidden Complexity of Distributed Systems

Karolos Antoniadis

The field of distributed computing has a long history, of more than fifty years. During that time, our understanding of the field has improved immensely and a certain body of folklore beliefs has formed. However, such folklore beliefs are not necessarily a ...

EPFL2020

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the f ...

EPFL2020

Online Distributed Learning Over Graphs With Multitask Graph-Filter Models

Ali H. Sayed, Roula Nassif

In this article, we are interested in adaptive and distributed estimation of graph filters from streaming data. We formulate this problem as a consensus estimation problem over graphs, which can be addressed with diffusion LMS strategies. Most popular grap ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Optimized Quantization in Distributed Graph Signal Filtering

Pascal Frossard, Isabela Cunha Maia Nobre

Distributed graph signal processing algorithms require the network nodes to communicate by exchanging messages in order to achieve a common objective. These messages have a finite precision in realistic networks, which may necessitate to implement message ...

2019

Extrapolating Paths with Graph Neural Networks

Andreas Loukas, Jean-Baptiste Francis Marie Juliette Cordonnier

We consider the problem of path inference: given a path prefix, i.e., a partially observed sequence of nodes in a graph, we want to predict which nodes are in the missing suffix. In particular, we focus on natural paths occurring as a by-product of the int ...

IJCAI, Inc.2019

On the Rainbow Turan number of paths

Abhishek Methuku

Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Learning of robust spectral graph dictionaries for distributed processing

Pascal Frossard, Ntorina Thanou

We consider the problem of distributed representation of signals in sensor networks, where sensors exchange quantized information with their neighbors. The signals of interest are assumed to have a sparse representation with spectral graph dictionaries. We ...

SPRINGEROPEN2018

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Graph Signal Processing : Sparse Representation and Applications

Ntorina Thanou

Over the past few decades we have been experiencing an explosion of information generated by large networks of sensors and other data sources. Much of this data is intrinsically structured, such as traffic evolution in a transportation network, temperature ...

EPFL2016

On the Difficulty of Selecting Ising Models with Approximate Recovery

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an approximate recovery criterion that allows for a number of missed edges ...

Ieee-Inst Electrical Electronics Engineers Inc2016