The Experts below are selected from a list of 145203 Experts worldwide ranked by ideXlab platform
Prasad Jayanti - One of the best experts on this subject based on the ideXlab platform.
-
Dartmouth Computer Science Technical Report TR2004-523 Efcient Wait-Free Implementation of Multiword LL/SC Variables
2004Co-Authors: Prasad Jayanti, Srdjan PetrovicAbstract:Since the design of lock-Free data structures often poses a formidable intellectual challenge, researchers are constantly in search of abstractions and primitives that simplify this design. The multiword LL/SC object is such a primitive: many existing algorithms are based on this primitive, including the nonblocking and wait-Free universal constructions [1], the closed objects construction [4] and the snapshot algorithms [12, 13]. In this paper, we consider the problem of implementing a W -word LL/SC object shared by N processes. The previous best algorithm, due to Anderson and Moir [1], is time optimal (LL and SC operations run in O.W/ time), but has a space complexity of O.N 2 W/. We present an algorithm that uses novel buffer management ideas to cut down the space complexity by a factor of N to O.N W/, while still being time optimal.
-
PODC - f -arrays: Implementation and applications
Proceedings of the twenty-first annual symposium on Principles of distributed computing - PODC '02, 2002Co-Authors: Prasad JayantiAbstract:We introduce f-array, a new type of shared object that generalizes the multiwriter snapshot object, and design efficient (linearizable and wait-Free) algorithms for implementing it. f-arrays have made possible improved solutions to some important problems, as listed below:• A wait-Free Implementation of multiwriter snapshot, where the time complexity of scan and update operations is independent of the number of processes accessing the Implementation.• A wait-Free Implementation of counter object whose time complexity has the dual advantage that it is adaptive and guarantees a small worst-case bound: the time complexity is O(1) for read and O(min(k, log n)) for increment, where k is point contention and n is the maximum number of processes that the Implementation is designed to handle.• A wait-Free Implementation of a restricted version of a priority queue with similar time complexity as the counter Implementation.• A local spinning mutual exclusion algorithm that admits processes into Critical Section (CS) according to their priorities; processes with the same priority enter the CS in first-come-first-served order. In both cache coherent and NUMA multiprocessors, a process makes at most O(min(k, log n)) remote references to complete the entry and exit sections once. To the best of our knowledge, this is the first mutual exclusion algorithm that supports process priorities and has sublinear worst-case time complexity.All algorithms in this paper require support for LL/SC instructions.
-
DISC - A Complete and Constant Time Wait-Free Implementation of CAS from LL/SC and Vice Versa
Lecture Notes in Computer Science, 1998Co-Authors: Prasad JayantiAbstract:We consider three popular types of shared memory that support one of the following sets of operations: {CAS, read, write}, {LL, SC, VL, read, write}, or {RLL, RSC, read, write}. We present algorithms that, together with Moir's [Moi97], efficiently implement each shared memory above from any of the other two. Our Implementations are wait-Free and have constant time and space complexity. Thus, concurrent programs developed for one of the above memories can be ported to any other without incurring any increase in time complexity. Further, since our Implementations are wait-Free, a wait-Free concurrent program remains wait-Free even after porting.
-
ICDCS - Efficient Wait-Free Implementation of Multiword LL/SC Variables
25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), 1Co-Authors: Prasad Jayanti, Srdjan PetrovicAbstract:Since the design of lock-Free data structures often poses a formidable intellectual challenge, researchers are constantly in search of abstractions and primitives that simplify this design. The multiword LL/SC object is such a primitive: many existing algorithms are based on this primitive, including the nonblocking and wait-Free universal constructions (Anderson et. al., 1995), the closed objects construction (Chandra et. al., 1998) and the snap-shot algorithms (Jayanti, 2005, 2002). In this paper, the authors considered the problem of implementing a W-word LL/SC object shared by N processes. The previous best algorithm, due to Anderson and Moir, is time optimal (LL and SC operations run in O(W) time), but has a space complexity of O(N2 W). An algorithm that uses novel buffer management ideas to cut down the space complexity by a factor of N to O(NW), while still being time optimal was presented
Thomas Roche - One of the best experts on this subject based on the ideXlab platform.
-
Higher-order glitch Free Implementation of the AES using Secure Multi-Party Computation protocols
Journal of Cryptographic Engineering, 2012Co-Authors: Thomas Roche, Emmanuel ProuffAbstract:Higher-order side channel analysis (HO-SCA) is a powerful technique against cryptographic Implementations and the design of appropriate countermeasures is nowadays an important topic. In parallel, another class of attacks, called glitches attacks, have been investigated which exploit the hardware glitches phenomena occurring during the physical execution of algorithms. Some solutions have been proposed to counteract HO-SCA at any order or to defeat glitches attacks, but no work has until now focused on the definition of a sound countermeasure thwarting both attacks. We introduce in this paper a circuit model in which side-channel resistance in the presence of glitches effects can be characterized. This allows us to construct the first glitch Free HO-SCA countermeasure. The new construction can be built from any Secure Multi-Party Computation protocol and, as an illustration, we propose to apply the protocol introduced by Ben-Or et al at STOC in 1988. The adaptation of the latter protocol to the context of side-channel analysis results in a completely new higher-order masking scheme, particularly interesting when addressing resistance in the presence of glitches. An application of our scheme to the AES block cipher is detailed, as well as an information theoretic evaluation of the new masking function that we call polynomial masking.
-
higher order glitches Free Implementation of the aes using secure multi party computation protocols
Cryptographic Hardware and Embedded Systems, 2011Co-Authors: Emmanuel Prouff, Thomas RocheAbstract:Higher-order side channel attacks (HO-SCA) is a powerful technique against cryptographic Implementations and the design of appropriate countermeasures is nowadays an important topic. In parallel, another class of attacks, called glitches attacks, have been investigated which exploit the hardware glitches phenomena occurring during the physical execution of algorithms. We introduce in this paper a circuit model that encompasses sufficient conditions to resist glitches effects. This allows us to construct the first countermeasure thwarting both glitches and HO-SCA attacks. Our new construction requires Secure Multi-Party Computation protocols and we propose to apply the one introduced by Ben'Or et al. at STOC in 1988. The adaptation of the latter protocol to the context of side channel analysis results in a completely new higher-order masking scheme, particularly interesting when addressing resistance in the presence of glitches. An application of our scheme to the AES block cipher is detailed.
-
CHES - Higher-order glitches Free Implementation of the AES using secure multi-party computation protocols
Cryptographic Hardware and Embedded Systems – CHES 2011, 2011Co-Authors: Emmanuel Prouff, Thomas RocheAbstract:Higher-order side channel attacks (HO-SCA) is a powerful technique against cryptographic Implementations and the design of appropriate countermeasures is nowadays an important topic. In parallel, another class of attacks, called glitches attacks, have been investigated which exploit the hardware glitches phenomena occurring during the physical execution of algorithms. We introduce in this paper a circuit model that encompasses sufficient conditions to resist glitches effects. This allows us to construct the first countermeasure thwarting both glitches and HO-SCA attacks. Our new construction requires Secure Multi-Party Computation protocols and we propose to apply the one introduced by Ben'Or et al. at STOC in 1988. The adaptation of the latter protocol to the context of side channel analysis results in a completely new higher-order masking scheme, particularly interesting when addressing resistance in the presence of glitches. An application of our scheme to the AES block cipher is detailed.
Emmanuel Prouff - One of the best experts on this subject based on the ideXlab platform.
-
Higher-order glitch Free Implementation of the AES using Secure Multi-Party Computation protocols
Journal of Cryptographic Engineering, 2012Co-Authors: Thomas Roche, Emmanuel ProuffAbstract:Higher-order side channel analysis (HO-SCA) is a powerful technique against cryptographic Implementations and the design of appropriate countermeasures is nowadays an important topic. In parallel, another class of attacks, called glitches attacks, have been investigated which exploit the hardware glitches phenomena occurring during the physical execution of algorithms. Some solutions have been proposed to counteract HO-SCA at any order or to defeat glitches attacks, but no work has until now focused on the definition of a sound countermeasure thwarting both attacks. We introduce in this paper a circuit model in which side-channel resistance in the presence of glitches effects can be characterized. This allows us to construct the first glitch Free HO-SCA countermeasure. The new construction can be built from any Secure Multi-Party Computation protocol and, as an illustration, we propose to apply the protocol introduced by Ben-Or et al at STOC in 1988. The adaptation of the latter protocol to the context of side-channel analysis results in a completely new higher-order masking scheme, particularly interesting when addressing resistance in the presence of glitches. An application of our scheme to the AES block cipher is detailed, as well as an information theoretic evaluation of the new masking function that we call polynomial masking.
-
higher order glitches Free Implementation of the aes using secure multi party computation protocols
Cryptographic Hardware and Embedded Systems, 2011Co-Authors: Emmanuel Prouff, Thomas RocheAbstract:Higher-order side channel attacks (HO-SCA) is a powerful technique against cryptographic Implementations and the design of appropriate countermeasures is nowadays an important topic. In parallel, another class of attacks, called glitches attacks, have been investigated which exploit the hardware glitches phenomena occurring during the physical execution of algorithms. We introduce in this paper a circuit model that encompasses sufficient conditions to resist glitches effects. This allows us to construct the first countermeasure thwarting both glitches and HO-SCA attacks. Our new construction requires Secure Multi-Party Computation protocols and we propose to apply the one introduced by Ben'Or et al. at STOC in 1988. The adaptation of the latter protocol to the context of side channel analysis results in a completely new higher-order masking scheme, particularly interesting when addressing resistance in the presence of glitches. An application of our scheme to the AES block cipher is detailed.
-
CHES - Higher-order glitches Free Implementation of the AES using secure multi-party computation protocols
Cryptographic Hardware and Embedded Systems – CHES 2011, 2011Co-Authors: Emmanuel Prouff, Thomas RocheAbstract:Higher-order side channel attacks (HO-SCA) is a powerful technique against cryptographic Implementations and the design of appropriate countermeasures is nowadays an important topic. In parallel, another class of attacks, called glitches attacks, have been investigated which exploit the hardware glitches phenomena occurring during the physical execution of algorithms. We introduce in this paper a circuit model that encompasses sufficient conditions to resist glitches effects. This allows us to construct the first countermeasure thwarting both glitches and HO-SCA attacks. Our new construction requires Secure Multi-Party Computation protocols and we propose to apply the one introduced by Ben'Or et al. at STOC in 1988. The adaptation of the latter protocol to the context of side channel analysis results in a completely new higher-order masking scheme, particularly interesting when addressing resistance in the presence of glitches. An application of our scheme to the AES block cipher is detailed.
Rida A. Bazzi - One of the best experts on this subject based on the ideXlab platform.
-
PODC - Bounded wait-Free Implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions
Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing - PODC '07, 2007Co-Authors: Amitanand S. Aiyer, Lorenzo Alvisi, Rida A. BazziAbstract:We present the first optimally resilient, bounded, wait-Free Implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active readers and not on the total number of readers in the system. With a novel use of secret sharing techniques combined with write back throttling we present the first solution to tolerate Byzantine readers information theoretically, without the use of cryptographic techniques based on unproven number-theoretic assumptions.
-
DISC - Bounded wait-Free Implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions
Lecture Notes in Computer Science, 1Co-Authors: Amitanand S. Aiyer, Lorenzo Alvisi, Rida A. BazziAbstract:We present the first optimally resilient, bounded, wait-Free Implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active readers and not on the total number of readers in the system. With a novel use of secret sharing techniques combined with write back throttling we present the first solution to tolerate Byzantine readers information theoretically, without the use of cryptographic techniques based on unproven numbertheoretic assumptions.
Hagit Attiya - One of the best experts on this subject based on the ideXlab platform.
-
PODC - Separating Lock-Freedom from Wait-Freedom
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018Co-Authors: Hagit Attiya, Armando Castañeda, Danny Hendler, Matthieu PerrinAbstract:A long-standing open question has been whether lock-Freedom and wait-Freedom are fundamentally different progress conditions, namely, can the former be provided in situations where the latter cannot? This paper answers the question in the affirmative, by proving that there are objects with lock-Free Implementations, but without wait-Free Implementations-using objects of any finite power. We precisely define an object called n-process long-lived approximate agreement (n-LLAA), in which two sets of processes associated with two sides, 0 or 1, need to decide on a sequence of increasingly closer outputs. We prove that 2-LLAA has a lock-Free Implementation using reads and writes only, while n-LLAA has a lock-Free Implementation using reads, writes and (n - 1)-process consensus objects. In contrast, we prove that there is no wait-Free Implementation of the n-LLAA object using reads, writes and specific (n - 1)-process consensus objects, called (n - 1)-window registers.
-
Separating Lock-Freedom from Wait-Freedom
2018Co-Authors: Hagit Attiya, Armando Castañeda, Danny Hendler, Matthieu PerrinAbstract:A long-standing open question has been whether lock-Freedom and wait-Freedom are fundamentally different progress conditions, namely, can the former be provided in situations where the latter cannot? This paper answers the question in the affirmative, by proving that there are objects with lock-Free Implementations, but without wait-Free Implementations-using objects of any finite power. We precisely define an object called n-process long-lived approximate agreement (n-LLAA), in which two sets of processes associated with two sides, 0 or 1, need to decide on a sequence of increasingly closer outputs. We prove that 2-LLAA has a lock-Free Implementation using reads and writes only, while n-LLAA has a lock-Free Implementation using reads, writes and (n − 1)-process consensus objects. In contrast, we prove that there is no wait-Free Implementation of the n-LLAA object using reads, writes and specific (n − 1)-process consensus objects, called (n − 1)-window registers.
-
Nontrivial and universal helping for wait-Free queues and stacks
Journal of Parallel and Distributed Computing, 2018Co-Authors: Hagit Attiya, Armando Castañeda, Danny HendlerAbstract:Abstract This paper studies two approaches to formalize helping in wait-Free Implementations of shared objects. The first approach is based on operation valency, and it allows us to make an important distinction between trivial and nontrivial helping. We show that any wait-Free Implementation of a queue from Test&Set requires nontrivial helping. We also define a weaker type of nontrivial helping and show that any wait-Free queue Implementation from a set of arbitrary base objects requires it. In contrast, there is a wait-Free Implementation of a stack from Test&Set with only trivial helping. These results shed light on the well-known open question of whether there exists a wait-Free Implementation of a queue in Common2 , and indicate why it seems to be more difficult than implementing a stack. The other approach formalizes the helping mechanism employed by Herlihy’s universal wait-Free construction and is based on having an operation by one process restrict the possible linearizations of operations by other processes. We show that queue and stack Implementations possessing such universal helping can be used to solve consensus. This result can be used to show that a strongly linearizable (Golab et al., 2011) Implementation of a queue or a stack for n processes must use objects that allow to solve consensus among n or more processes.
-
OPODIS - Nontrivial and Universal Helping for Wait-Free Queues and Stacks
2016Co-Authors: Hagit Attiya, Armando Castañeda, Danny HendlerAbstract:This paper studies two approaches to formalize helping in wait-Free Implementations of shared objects. The first approach is based on operation valency, and it allows us to make the important distinction between trivial and nontrivial helping. We show that a wait-Free Implementation of a queue from common2 objects (e.g., Test&Set) requires nontrivial helping. In contrast, there is a wait-Free Implementation of a stack from Common2 objects with only trivial helping. This separation might shed light on the difficulty of implementing a queue from Common2 objects. The other approach formalizes the helping mechanism employed by Herlihy's universal wait-Free construction and is based on having an operation by one process restrict the possible linearizations of operations by other processes. We show that objects possessing such universal helping can be used to solve consensus.
