Simulating a Shared Queue on Top of Eventually Synchronous Message-Passing Distributed Systems
Abstract
Distributed computer systems are comprised of multiple processing nodes that communicate and coordinate actions in order to achieve a common goal. They are often used to handle tasks that are too large to be handled by a single processor or are inherently distributed. Distributed systems can be either a message-passing system, where nodes pass messages between each other to coordinate actions, or a shared-memory system, where nodes have access to a shared data object between all of the nodes. These shared objects provide a higher level of abstraction to the programmer than a message-passing system but may not be available to use. Instead, algorithms have been developed in the past that allow the nodes to keep a local copy of the shared data object and send messages between each other to coordinate modifications to the object. This way, concurrent operations on the implemented object are guaranteed to be linearizable, or give the illusion that the operations are executed sequentially and in a legal order. This thesis will examine one of these algorithms which was originally developed for a synchronous system, where there is an upper bound on message delays. We will instead examine the algorithm's behavior in a system that starts with arbitrarily long message delays, including messages that are lost and never delivered, but eventually stabilizes and has bounded message delays at a time unknown to the nodes. We will be measuring the length of time needed for the execution to become linearizable after the system stabilizes, called the grace period. We will focus on the case where the shared object is a first-in-first-out Queue. We have simulated this algorithm using a discrete event simulator so that the timing elements can be precisely controlled.
Citation
Ziesmer, Emma Anne (2022). Simulating a Shared Queue on Top of Eventually Synchronous Message-Passing Distributed Systems. Undergraduate Research Scholars Program. Available electronically from https : / /hdl .handle .net /1969 .1 /196537.