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