RH Logo

All
My Hubs

Distributed Computing

Trending
Today
All
Papers
Posts
Hypotheses

Sign in to discover all of the research papers you care about, live as they're published.

6
Date Added: Oct 31, 2020
Date Added: Oct 31, 2020
Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove that the worst-case amortized cost of the operations on our linked lists is linear in the length of the list plus the contention, which is better than in previous lock-free implementations of this data structure. Our implementation uses backlinks that are set when a node is deleted so that concurrent operations visiting the deleted node can recover. To avoid performance problems that would arise from traversing long chains of backlink pointers, we introduce flag bits, which indicate that a deletion of the next node is underway. We then give a lock-free implementation of a skip list dictionary data structure that uses the new linked list algorithms to implement individual levels. Our algorithms use the single-word C&S synchronization primitive.
3
Date Added: May 25, 2021
Date Added: May 25, 2021
In the recent past, the emergence of IPv6 capable low-power mesh networks has put the visions of the Industrial Internet of Things (IIoT) right at the doorstep. In particular, 6LoWPAN has shown to be a promising foundation for a general purpose, IPv6 capable, low-power network stack, and has since seen broad adoption. While several aspects of the underlying technologies are steadily advancing, adequate multicast routing has been an ongoing issue. A steady stream of potential improvements has been proposed, most of which trying to alleviate shortcomings in Routing Protocol for Low-Power and Lossy Networks (RPL), the predominantly used routing protocol. In this paper, we summarize the current state of (multicast) routing in 6LoWPAN, known issues and recent proposals for improvements, and argue for alternatives/extensions and their drawbacks and potential benefits.
24
Date Added: Dec 2, 2020
Date Added: Dec 2, 2020
The advent of stablecoins offers new and innovative ways to improve financial inclusion, reduce transaction costs, and increase the efficiency of the global financial system. The following paper explores the assets and process necessary for creating a central bank digital currency (CBDC) on the Celo platform, as well as the potential impact on the financial system. Perhaps most importantly, the paper also introduces the idea that current technological advancements allow for a better understanding of the velocity of money, and may afford central banks the ability to influence money velocity, thus potentially creating a new transmission channel for monetary policy.
12
Date Added: Oct 29, 2020
Date Added: Oct 29, 2020
Linearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model[16]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel[14]. As a building block, our algorithm uses a lock-free strongly linearizable ABA-detecting register. We obtain this object by modifying the wait-free linearizable ABA-detecting register of Aghazadeh and Woelfel [5], which, as we show, is not strongly linearizable. Aspnes and Herlihy[8] identified a wide class of types that have wait-free linearizable implementations. These types require that any pair of operations either commute, or one overwrites the other. Aspnes and Herlihy gave a general wait-free linearizable implementation of such types, employing an atomic snapshot object. We show that this implementation is strongly linearizable, proving that all types in this class have a lock-free strongly linearizable implementation from atomic registers.