000180633 001__ 180633
000180633 005__ 20190509132424.0
000180633 0247_ $$2doi$$a10.5075/epfl-thesis-5447
000180633 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis5447-2
000180633 02471 $$2nebis$$a7336706
000180633 037__ $$aTHESIS
000180633 041__ $$aeng
000180633 088__ $$a5447
000180633 245__ $$aRandomized versus Deterministic Implementations of Concurrent Data Structures
000180633 269__ $$a2012
000180633 260__ $$bEPFL$$c2012$$aLausanne
000180633 300__ $$a129
000180633 336__ $$aTheses
000180633 520__ $$aOne of the key trends in computing over the past two  decades has been increased distribution, both at the  processor level, where multi-core architectures are now the  norm, and at the system level, where many key services are  currently distributed overmultiple machines. Thus,  understanding the power and limitations of computing in a  concurrent, distributed setting is one of the major  challenges in Computer Science. In this thesis, we analyze the complexity of implementing  concurrent data structures in asynchronous shared memory  systems. We focus on the complexity of a classic distributed  coordination task called renaming, in which a set of  processes need to pick distinct names from a small set of  identifiers. We present the first tight bounds for the time  complexity of this problem, both for deterministic and  randomized implementations, solving a long-standing open  problem in the field. For deterministic algorithms, we prove  a tight linear lower bound; for randomized solutions, we  provide logarithmic upper and lower bounds on time  complexity. Together, these results show an exponential  separation between deterministic and randomized renaming  solutions. Importantly, the lower bounds extend to  implementations of practical shared-memory data structures,  such as queues, stacks, and counters. From a technical perspective, this thesis highlights new  connections between the distributed renaming problem and  other fundamental objects, such as sorting networks, mutual  exclusion, and counters. In particular, we show that sorting  networks can be used to obtain optimal randomized solutions  to renaming, and that, in turn, the existence of these  solutions implies a linear lower bound on the complexity of  the problem. In sum, the results in this thesis suggest that  deterministic implementations of shared-memory data  structures do not scale well in terms of worst-case time  complexity. On the positive side, we emphasize randomization  as a natural alternative, which can circumvent the  deterministic lower bounds with high probability. Thus, a  promising direction for future work is to extend our  randomized renaming techniques to obtain efficient  implementations of concurrent data structures.
000180633 6531_ $$aconcurrent algorithms
000180633 6531_ $$ashared memory
000180633 6531_ $$adata structures
000180633 6531_ $$arenaming
000180633 6531_ $$arandomization
000180633 6531_ $$alower bounds
000180633 6531_ $$aalgorithmes concurrents
000180633 6531_ $$amémoire partagée
000180633 6531_ $$astructures de données
000180633 6531_ $$arenommage
000180633 6531_ $$améthodes probabilistes
000180633 6531_ $$abornes inférieures
000180633 700__ $$0242985$$g177872$$aAlistarh, Dan
000180633 720_2 $$aGuerraoui, Rachid$$edir.$$g105326$$0240335
000180633 8564_ $$uhttps://infoscience.epfl.ch/record/180633/files/EPFL_TH5447.pdf$$zTexte intégral / Full text$$s1259397$$yTexte intégral / Full text
000180633 909C0 $$xU10407$$0252114$$pDCL
000180633 909CO $$pthesis-bn2018$$pDOI$$pIC$$ooai:infoscience.tind.io:180633$$qDOI2$$qGLOBAL_SET$$pthesis
000180633 918__ $$dEDIC2005-2015$$cIIF$$aIC
000180633 919__ $$aLPD
000180633 920__ $$b2012
000180633 970__ $$a5447/THESES
000180633 973__ $$sPUBLISHED$$aEPFL
000180633 980__ $$aTHESIS