Concept

Circuit complexity

Related publications (189)

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficien ...

Springer Verlag2012

Fighting Back: Using Observability Tools to Improve the DBMS (Not Just Diagnose It)

Frederick Ryan Johnson

Observability tools increase the transparency of the system and help practitioners identify a wide variety of bugs and bottlenecks. In this paper we claim that such tools (DTrace, in our case) can play a much more active role: the same features which allow ...

ACM2012

How to Allocate Tasks Asynchronously

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Asynchronous task allocation is a fundamental problem in distributed computing, in which p asyn- chronous 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 bui ...

2012

Rethinking FPGAs: Elude the Flexibility Excess of LUTs with And-Inverter Cones

Paolo Ienne, David Novo Bruna, Hadi Parandeh Afshar, Hind Benbihi

Look-Up Tables (LUTs) are universally used in FPGAs as the elementary logic blocks. They can implement any logic function and thus covering a circuit is a relatively straightforward problem. Naturally, flexibility comes at a price, and increasing the numbe ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2012

Soft switching characterization of a 6.5kV IGBT for high power LLC resonant DC-DC converter

Drazen Dujic

Medium voltage (MV) high power applications are usually realized using high voltage semiconductors (3.3kV and above) operated in hard switching mode with low switching frequencies (several hundreds of Hz). However, for high power DC-DC converters employing ...

VDE2012

The complexity of robust atomic storage

Rachid Guerraoui, Marko Vukolic

We study the time-complexity of robust atomic read/write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures ( ...

ACM Press2011

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

André Schiper, Martin Hutle, Zarko Milosevic

We investigate the reduction of atomic broadcast to consensus in systems with Byzantine faults. Among the several definitions of Byzantine consensus that differ only by their validity property, we identify those equivalent to atomic broadcast. Finally, we ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2011

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

André Schiper, Martin Hutle, Zarko Milosevic

2011

Complexity of the critical node problem over trees

Marco Di Summa

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...

2011

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.