Publications related to Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Dynamic Byzantine Reliable Broadcast

Rachid Guerraoui, Dragos-Adrian Seredinschi, Jovan Komatovic, Andrei Tonkikh

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

Asynchronous distributed coordination and consensus with threshold logical clocks

Bryan Alexander Ford

Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. The invention proposes an approach to simplify asynchronous consensus by building it atop a novel threshold logic ...

2021

Low-Power Design of Digital VLSI Circuits around the Point of First Failure

Andrea Bonetti

As an increase of intelligent and self-powered devices is forecasted for our future everyday life, the implementation of energy-autonomous devices that can wirelessly communicate data from sensors is crucial. Even though techniques such as voltage scaling ...

EPFL2019

Exact Diffusion for Distributed Optimization and Learning-Part II: Convergence Analysis

Ali H. Sayed, Bicheng Ying, Kun Yuan

Part I of this paper developed the exact diffusion algorithm to remove the bias that is characteristic of distributed solutions for deterministic optimization problems. The algorithm was shown to be applicable to the larger set of locally balanced left-sto ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

Near-Optimal Noisy Group Testing via Separate Decoding of Items

Volkan Cevher, Jonathan Mark Scarlett

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. In this pa ...

2018

Theory and Practice of Coroutines with Snapshots

Aleksandar Prokopec, Fengyun Liu

While event-driven programming is a widespread model for asynchronous computing, its inherent control flow fragmentation makes event-driven programs notoriously difficult to understand and maintain. Coroutines are a general control flow construct that can ...

2018

Labeled PSI from Fully Homomorphic Encryption with Malicious Security

Zhicong Huang

Private Set Intersection (PSI) allows two parties, the sender and the receiver, to compute the intersection of their private sets without revealing extra information to each other. We are interested in the unbalanced PSI setting, where (1) the receiver's s ...

ASSOC COMPUTING MACHINERY2018

How little does non-exact recovery help in group testing?

Volkan Cevher, Jonathan Mark Scarlett

We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of tests. We characterize the information-theoretic performance limits in the presence of list decoding, in whi ...

Ieee2017

Automated Integration of Dual-Edge Clocking for Low-Power Operation in Nanometer Nodes

Andreas Peter Burg, Nicholas Alexander Preyss, Andrea Bonetti, Adam Shmuel Teman

Clocking power, including both clock distribution and registers, has long been one of the primary factors in the total power consumption of many digital systems. One straightforward approach to reduce this power consumption is to apply dual-edge-triggered ...

Association for Computing Machinery2017

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017

Axo: Tolerating Delay Faults in Real-Time Systems

Jean-Yves Le Boudec, Simon Bliudze, Maaz Mashood Mohiuddin, Wajeb Saab

We address delay faults: faults that cause a software component to take more time for completing an action than a given deadline. Such faults are particularly of interest in real- time mission-critical control applications that use general-purpose computin ...

2016

Incremental Syllable-Context Phonetic Vocoding

Petr Motlicek, Philip Neil Garner, Milos Cernak

Current very low bit rate speech coders are, due to complexity limitations, designed to work off-line. This paper investigates incremental speech coding that operates real-time and incrementally (i.e., encoded speech depends only on already-uttered speech ...

2015

Comparative Study of Trust Modeling For Automatic Landmark Tagging

Touradj Ebrahimi, Ivan Ivanov, Péter Vajda

Many images uploaded to social networks are related to travel, since people consider traveling to be an important event in their life. However, a signiﬁcant amount of travel images on the Internet lack proper geographical annotations or tags. In many cases ...

Ieee-Inst Electrical Electronics Engineers Inc2013

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal ...

2012

Consensus in the presence of mortal Byzantine faulty processes

Martin Biely

We consider the problem of reaching agreement in distributed systems in which some processes may deviate from their prescribed behavior before they eventually crash. We call this failure model "mortal Byzantine". After discussing some application examples ...

Springer Verlag2012

How to Allocate Tasks Asynchronously

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key buildi ...

IEEE2012

Model Checking of Distributed Algorithm Implementations

Maysam Yabandeh

It is notoriously difficult to develop reliable, high-performance distributed systems that run over asynchronous networks. Even if a distributed system is based on a well-understood distributed algorithm, its implementation can contain errors arising from ...

EPFL2011

The Exact Hausdorff Measure of the Zero Set of Fractional Brownian Motion

Driss Baraka, Thomas Mountford

Let {X(t), t is an element of R-N} be a fractional Brownian motion in R-d of index H. If L(0,I) is the local time of X at 0 on the interval I subset of R-N, then there exists a positive finite constant c(=c(N,d,H)) such that ...

Springer US2011