Distributed Computing
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with Multiplicity
Distributed Computing - Tập 36 - Trang 89-106 - 2022
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......
On deadlocks of exclusive AND-requests for resources
Distributed Computing - Tập 9 - Trang 77-94 - 1995
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......
Low-congestion shortcut and graph parameters
Distributed Computing - Tập 34 - Trang 349-365 - 2021
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 ......
An improved lower bound for the time complexity of mutual exclusion
Distributed Computing - Tập 15 - Trang 221-253 - 2002
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......
A resource-competitive jamming defense
Distributed Computing - Tập 31 - Trang 419-439 - 2017
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......
Compiling path expressions into VLSI circuits
Distributed Computing - Tập 1 - Trang 150-166 - 1986
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......
Distributed data clustering in sensor networks
Distributed Computing - Tập 24 - Trang 207-222 - 2011
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,......
Bộ nhớ đệm lười trong TLA Dịch bởi AI
Distributed Computing - Tập 12 - Trang 151-174 - 1999
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í......
Upper and lower bounds for deterministic broadcast in powerline communication networks
Distributed Computing - - 2016
Tổng số: 554
- 1
- 2
- 3
- 4
- 5
- 6
- 10