Publications related to Lower Bounds on Generic Broadcast Algorithms

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.

On the Construction of Polar Codes

Emre Telatar, Seyed Hamed Hassani, Ramtin Pedarsani

We consider the problem of efficiently constructing polar codes over binary memoryless symmetric (BMS) channels. The complexity of designing polar codes via an exact evaluation of the polarized channels to find which ones are "good" appears to be exponenti ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 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

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of

n

processes with step complexity $ ...

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

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

André Schiper, Martin Hutle, Zarko Milosevic

2011

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh, Hagit Albo Attiya, Andrei Giurgiu

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

2010

Distributed Agreement with Optimal Communication Complexity

Seth Gilbert

We consider the problem of fault-tolerant agreement in a crash-prone synchronous system. We present a new randomized consensus algorithm that achieves optimal communication efficiency, using only O(n) bits of communication, and terminates in (almost optima ...

Siam, 3600 Univ City Science Center, Philadelphia, Pa 19104-2688 Usa2010

Algebraic, AIDA/Cube and Side Channel Analysis of KATAN Family of Block Ciphers

Pouyan Sepehrdad, Jorge Nakahara

This paper presents the first results on AIDA/cube, algebraic and side-channel attacks on variable number of rounds of all members of the KATAN family of block ciphers. Our cube attacks reach 60, 40 and 30 rounds of KATAN32, KATAN48 and KATAN64, respective ...

Springer2010

Attacking the Knudsen-Preneel Compression Functions

Martijn Stam, Onur Özen

Knudsen and Preneel (Asiacrypt’96 and Crypto’97) introduced a hash function design in which a linear error-correcting code is used to build a wide-pipe compression function from underlying blockciphers operating in Davies-Meyer mode. In this paper, we (re) ...

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

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

n

processes with step complexity $ ...

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

Lower Bounds on Generic Broadcast Algorithms

Graph Chatbot

Chat with Graph Search

On the Construction of Polar Codes

Sub-Logarithmic Test-and-Set Against a Weak Adversary

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

Fast Randomized Test-and-Set and Renaming

Distributed Agreement with Optimal Communication Complexity

Algebraic, AIDA/Cube and Side Channel Analysis of KATAN Family of Block Ciphers

Attacking the Knudsen-Preneel Compression Functions

Algorithm/Architecture Co-Exploration of Visual Computing: Overview and Future Perspectives

Sub-Logarithmic Test-and-Set Against a Weak Adversary

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

On the Construction of Polar Codes

Distributed Agreement with Optimal Communication Complexity

Attacking the Knudsen-Preneel Compression Functions

Algebraic, AIDA/Cube and Side Channel Analysis of KATAN Family of Block Ciphers

Algorithm/Architecture Co-Exploration of Visual Computing: Overview and Future Perspectives

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

Fast Randomized Test-and-Set and Renaming