Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with MultiplicityDistributed Computing -  Tập 36  - Trang 89-106 - 2022
Armando Castañeda, Sergio Rajsbaum, Michel Raynal
This work consideres asynchronous shared memory systems in which any number of processes may crash. It identifies relaxations of fetch & increment, queues, sets and stacks that can be non-blocking or wait-free implemented using only Read/Write operations, without Read-After-Write synchronization patterns. Set-linearizability, a generalization of linearizability designed to specify concurrent behav......  hiện toàn bộ
 On deadlocks of exclusive AND-requests for resourcesDistributed Computing -  Tập 9  - Trang 77-94 - 1995
Y. C. Tay, W. Tim Loke
Although there are numerous concurrency control algorithms and they use a variety of techniques, there is an underlying serializability theory that serves both as a basis for analyzing their correctness and as a guide for designing new protocols. Following this paradigm, this paper proposes a uniform framework for characterizing and developing distributed deadlock-related algorithms. The system co......  hiện toàn bộ
 Low-congestion shortcut and graph parametersDistributed Computing -  Tập 34  - Trang 349-365 - 2021
Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi
Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of 
                
                  
                
                $${\tilde{\Omega }}(\sqrt{n} + D)$$
                
               rounds for several global problems, where n denotes the number of nodes and D the diameter of the input graph. Because such a lower bound is derived from ......  hiện toàn bộ
 An improved lower bound for the time complexity of mutual exclusionDistributed Computing -  Tập 15  - Trang 221-253 - 2002
James H. Anderson, Yong-Jik Kim
We establish a lower bound of 
                  $\Omega(\log N/\log\log N)$
                 remote memory references for N-process mutual exclusion algorithms based on reads, writes, or comparison primitives such as test-and-set and compare-and-swap. Our bound improves an earlier lower bound of 
                  $\Omega(\log\log N/\log\log\log N)$
                 established by Cypher. Our lo......  hiện toàn bộ
 A resource-competitive jamming defenseDistributed Computing -  Tập 31  - Trang 419-439 - 2017
Valerie King, Seth Pettie, Jared Saia, Maxwell Young
Consider a scenario where Alice wishes to send a message m to Bob in a time-slotted wireless network. However, there exists an adversary, Carol, who aims to prevent the transmission of m by jamming the communication channel. There is a per-slot cost of 1 to send, receive or jam m on the channel, and we are interested in how much Alice and Bob need to spend relative to Carol in order to guarantee c......  hiện toàn bộ
 Compiling path expressions into VLSI circuitsDistributed Computing -  Tập 1  - Trang 150-166 - 1986
T. S. Anantharaman, E. M. Clarke, M. J. Foster, B. Mishra
Path expressions were originally proposed by Campbell and Habermann [2] as a mechanism for process synchronization at the monitor level in software. Not surprisingly, they also provide a useful notation for specifying the behavior of asynchronous circuits. Motivated by these potential applications we investigate how to directly translate path expressions into hardware. Our implementation is compli......  hiện toàn bộ
 Distributed data clustering in sensor networksDistributed Computing -  Tập 24  - Trang 207-222 - 2011
Ittay Eyal, Idit Keidar, Raphael Rom
Low overhead analysis of large distributed data sets is necessary for current data centers and for future sensor networks. In such systems, each node holds some data value, e.g., a local sensor read, and a concise picture of the global system state needs to be obtained. In resource-constrained environments like sensor networks, this needs to be done without collecting all the data at any location,......  hiện toàn bộ
 Bộ nhớ đệm lười trong TLA Dịch bởi AI Distributed Computing -  Tập 12  - Trang 151-174 - 1999
Peter Ladkin, Leslie Lamport, Bryan Olivier, Denis Roegel
Chúng tôi giải quyết vấn đề do Gerth đề xuất, đó là xác minh rằng một phiên bản đơn giản hóa của thuật toán lưu trữ lười của Afek, Brown và Merritt là nhất quán theo thứ tự. Chúng tôi xác định thuật toán và tính nhất quán theo thứ tự trong TLA$^+$, một ngôn ngữ biên soạn chính thức dựa trên TLA (Logic Thời gian của Các hành động). Sau đó, chúng tôi mô tả cách xây dựng và kiểm tra một bằng chứng tí......  hiện toàn bộ