Browsing by Author "Giakkoupis, George"

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    Analysis of Asynchronous and Synchronous Rumor Spreading Protocols
    (2016) Nazari, Yasamin; Woelfel, Philipp; Giakkoupis, George
    This thesis focuses on a class of randomized broadcasting algorithms known as rumor spreading algorithms. In these algorithms, initially one node in a network has a rumor, and nodes exchange the rumor with one of their randomly chosen neighbors. In the originally proposed rumor spreading algorithms, nodes take steps in synchronous rounds. More recently, an arguably more realistic asynchronous model was proposed in which nodes take steps independently of each other. In this thesis, we first provide formal definitions for the basic concepts used in the literature. We then formally prove that several known models are equivalent. Next, we present several upper bounds on the running time of the push protocol on general graphs that improve the currently known upper bounds. Finally, we show that in the asynchronous model, the push protocol has twice the running time of the push-pull protocol on regular graphs.
  • Thumbnail Image
    ItemOpen Access
    Faster Randomized Repeated Choice and DCAS
    (ACM, 2024) Bencivenga, Dante; Giakkoupis, George; Woelfel, Philipp
    At STOC 2021, Giakkoupis, Giv, and Woelfel, presented an efficient randomized implementation of Double Compare-And-Swap (DCAS) from Compare-And-Swap (CAS) objects. DCAS is a useful and fundamental synchronization primitive for shared memory systems, which, contrary to CAS, is not available in hardware. The DCAS algorithm has O(logn) expected amortized step complexity against an oblivious adversary, where nn is the number of processes in the system. The bottleneck of this algorithm is a building block, introduced in the same paper: A repeated choice (RC) object, which allows processes to propose values, and later agree on (and “lock in”) one of the proposed values, which is roughly uniformly distributed among the “recently” proposed ones. The object can then be unlocked, and the process be repeated. The RC implementation introduced by Giakkoupis et al. has step complexity O(logn). In this paper, we present a more efficient RC algorithm, with similar probabilistic guarantees, but expected step complexity O(loglogn). We then show how this improved RC object can be used to achieve an exponential improvement in the expected amortized step complexity of DCAS.
  • Thumbnail Image
    ItemOpen Access
    The Space Complexity of Distributed Tasks in the Shared Memory Model
    (2016) Helmi Khomeirani, Maryam; Woelfel, Philipp; Higham, Lisa; Jacobson, Michael J. Jr; Giakkoupis, George; Rajsbaum, Sergio; Krishnamurthy, Diwakar
    In this thesis, I study the space complexity of the implementation of test-and-set and renaming problems from atomic multi-reader/multi-writer registers in distributed synchronous systems with n processes. Previously, Giakkoupis and Woelfel as well as Styer and Peterson showed that at least Omega(log n) registers are required to implement one-shot test-and-set objects. First, I show a deterministic obstruction-free test-and-set algorithm using O(sqrt n) unbounded registers. Next, I present a deterministic obstruction-free implementation of a one-shot test-and-set object from Theta(log n) registers of size Theta(log n) bits, which closes the gap between the upper and lower bound. The problem of assigning unique names to processes from a set of size f(k) is called f-adaptive renaming, where k is the number of participating processes. Long-lived f-adaptive renaming allows each process to acquire and then release a name any number of times. One-shot adaptive renaming allows each process to get a name at most once. Let f: {1, ... ,n} -> N be a non-decreasing function satisfying f(1) <= n-1 and let d = max{x | f(x) <= n-1}. I show a lower bound of d + 1 registers for any non-deterministic solo-terminating long-lived f-adaptive renaming task. Furthermore, I observe that, this is a tight lower bound for long-lived (k+c)-adaptive renaming. However, for any non-deterministic solo-terminating one-shot (k+c)-adaptive renaming, I prove a lower bound of floor{2(n - c)/(c+2)} registers. I also provide two one-shot renaming algorithms: a wait-free one-shot (3k^2/2)-adaptive renaming algorithm from ceil{sqrt n} + 1 registers, and an obstruction-free one-shot f-adaptive renaming algorithm from min{n, x | f(x) >= 2n} + 1 registers.