Search
Now showing items 891-900 of 976
Efficient gossip and robust distributed computation
(2005)
This paper presents an efficient deterministic gossip algorithm for p synchronous, crash-prone, message-passing processors. The algorithm has time complexity T=O(log2p) and message complexity M=O(p1+ε), for any ε>0. This ...
Performing dynamically injected tasks on processes prone to crashes and restarts
(2011)
To identify the tradeoffs between efficiency and fault-tolerance in dynamic cooperative computing, we initiate the study of a task performing problem under dynamic processes' crashes/restarts and task injections. The system ...
Automated implementation of complex distributed algorithms specified in the IOA language
(2009)
IOA is a formal language for describing Input/Output automata that serves both as a formal specification language and as a programming language (Garland et al. in http://theory.lcs.mit.edu/tds/ioa/manual.ps, 2004). The IOA ...
Efficient gossip and robust distributed computation
(2003)
This paper presents an efficient deterministic gossip algorithm for p synchronous, crash-prone, message-passing processors. The algorithm has time complexity T = O(log2 p) and message complexity M = O(p1+ε), for any ε > ...
Failure-sensitive analysis of parallel algorithms with controlled memory access concurrency
(2007)
The abstract problem of using P failure-prone processors to cooperatively update all locations of an N-element shared array is called Write-All. Solutions to Write-All can be used iteratively to construct efficient simulations ...
Selfish routing in the presence of network uncertainty
(2009)
We study the problem of selfish routing in the presence of incomplete network information. Our model consists of a number of users who wish to route their traffic on a network of m parallel links with the objective of ...
On the robustness of (semi) fast quorum-based implementations of atomic shared memory
(2008)
This paper studies a trade-off between fault-tolerance and latency in implementations of atomic read/write objects in message-passing systems. In particular, considering fast or semifast quorum-based implementations, that ...
The complexity of synchronous iterative do-all with crashes
(2001)
Do-All is the problem of performing N tasks in a distributed system of P failure-prone processors [8]. Many distributed and parallel algorithms have been developed for this problem and several algorithm simulations have ...
Cooperative computing with fragmentable and mergeable groups
(2003)
This work considers the problem of performing a set of N tasks on a set of P cooperating message-passing processors (P ≤ N). The processors use a group communication service (GCS) to coordinate their activity in the setting ...