Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper extends the definitions of lock-freedom and wait-freedom to encompass group computations, introducing the concepts of gl-freedom and gw-freedom. By ensuring that the new definitions maintain logical consistency with the original while accommodating multi-threaded collaboration, the authors provide a framework that enhances the characterization of distributed systems and other complex computational environments. The findings illustrate that this extension allows for a more nuanced understanding of concurrency in programming, particularly in contexts such as NUMA systems and private data handling among threads.
Expanding lock-freedom and wait-freedom to group computations reveals new insights into concurrency in distributed systems and enhances program characterization.
A domain extension of a definition refers to broadening the scope of a definition so that it applies to a larger set of cases than originally specified. The notion of lock-free and wait-free computation is designed for the domain of tasks that are completed by a single thread (in competition with other threads). The goal of this paper is to extend the definition of lock-freedom and wait-freedom to group-computations (denoted by gl-freedom and gw-freedom) that require that the task at hand must be completed by a collaboration between multiple threads. When extending a definition, certain constraints must be respected: the new domain must remain logically consistent with the original meaning, the extension should not introduce contradictions or ambiguities, and it must preserve the essential properties that make the definition valid and useful. We demonstrate this by showing that our extended definition is consistent with the original definition when the group consists of a single thread. We note that extension allows us to characterize programs in a new domain (distributed computing, NUMA computation systems, systems with private data for different threads, etc.) instead of relegating them to be in the same category (deadlock/livelock-free) without regard to the actual properties of that program. We also illustrate this definition with various examples.