Studies for distributed applications have demonstrated that application quality in distributedcomputing is strongly dependent on the quality of the underlying communication system. Besides performance characteristics...
详细信息
ISBN:
(纸本)9780897919524
Studies for distributed applications have demonstrated that application quality in distributedcomputing is strongly dependent on the quality of the underlying communication system. Besides performance characteristics the reliability properties of a communication system are playing a predominant role with regard to the quality achievable from applications' point of view. In this paper we study distributed applications with video communication via lossy communication systems. We develop analytical models reflecting transmission of MPEG coded video streams both without and with forward error correction (FEC). These models allow us to determine the optimum amount of redundancy to be used for FEC when communicating via constant bit rate connections. We conclude that FEC algorithms offer the potential for high quality-of-service even in the case of using a communication system with low quality.
When evaluated to true, a stable property remains true forever. Such a stable property may characterize important states of a computation. This is the case of deadlocked or terminated computations. In this paper we ex...
The proceedings contain 54 papers. The topics discussed include: distributedcomputing theory for wireless networks and mobile systems;pragmatic primitives for non-blocking data structures;the SkipTrie: low-depth conc...
ISBN:
(纸本)9781450320658
The proceedings contain 54 papers. The topics discussed include: distributedcomputing theory for wireless networks and mobile systems;pragmatic primitives for non-blocking data structures;the SkipTrie: low-depth concurrent search without rebalancing;optimal deterministic routing and sorting on the congested clique;Byzantine vector consensus in complete graphs;fast Byzantine agreement in dynamic networks;synchronous Byzantine agreement with nearly a cubic number of communication bits;how to meet asynchronously at polynomial cost;on the complexity of universal leader election;on the complexity of universal leader election;on minimum interaction time for continuous distributed interactive computing;scalable anonymous communication with Byzantine adversary;brokerage and closure in a strategic model of social capital;and feedback from nature: an optimal distributed algorithm for maximal independent set selection.
This paper presents a fast distributed algorithm to compute a small k-dominating set D (for any fixed k) and its induced graph partition (breaking the graph into radius k clusters centered around the vertices of D). T...
详细信息
ISBN:
(纸本)9780897917100
This paper presents a fast distributed algorithm to compute a small k-dominating set D (for any fixed k) and its induced graph partition (breaking the graph into radius k clusters centered around the vertices of D). The time complexity of the algorithm is O(k log* n). Small k-dominating sets have applications in a number of areas, including routing with sparse routing tables via the scheme of [PU], the design of distributed data structures [P2], and center selection in a distributed network (cf. [BKP]). The main application described in this paper concerns a fast distributed algorithm for constructing a minimum weight spanning tree (MST). On an n-vertex network of diameter d, the new algorithm constructs an MST in time O(√n log* n + d), improving on the results of [GKP]. The new MST algorithm is conceptually simpler than the three-phase algorithm of [GKP]. In addition to exploiting small k-dominating sets, it uses a very simple convergecast protocol to inform a center about graph edges, that avoids forwarding messages about edges that close cycles. This convergecast protocol is similar to the one used in the third phase of the algorithm of [GKP], and most of the novelty lies in a new careful analysis proving that the convergecast process is fully pipelined, and no waiting occurs at intermediate nodes. This enables the new algorithm to skip the complicated second phase of the algorithm of [GKP].
The proceedings contain 65 papers. The topics discussed include: coordinated consensus in dynamic networks;error-free multi-valued consensus with Byzantine failures;Byzantine agreement with homonyms;distributed graph ...
ISBN:
(纸本)9781450307192
The proceedings contain 65 papers. The topics discussed include: coordinated consensus in dynamic networks;error-free multi-valued consensus with Byzantine failures;Byzantine agreement with homonyms;distributed graph coloring in a few rounds;toward more localized local algorithms: removing assumptions concerning global knowledge;the complexity of robust atomic storage;resilience of mutual exclusion algorithms to transient memory faults;structuring unreliable radio networks;the impact of memory models on software reliability in multiprocessors;on the power of hardware transactional memory to simplify memory management;a complexity separation between the cache-coherent and distributed shared memory models;from bounded to unbounded concurrency objects and back;distributed deterministic edge coloring using bounded neighborhood independence;and the space complexity of long-lived and one-shot timestamp implementations.
The proceedings contain 30 papers. The topics discussed include: dynamic systems and their distributed termination;UIDs as internal names in a distributed file system;testing incomplete specifications of distributed s...
ISBN:
(纸本)0897910818
The proceedings contain 30 papers. The topics discussed include: dynamic systems and their distributed termination;UIDs as internal names in a distributed file system;testing incomplete specifications of distributed systems;distributed communication via global buffer;language constructs and support systems for distributedcomputing;efficient schemes for parallel communication;distributed multi-destination routing: the constraints of local information;randomized parallel communication;language concepts for distributed processing of large arrays;four combinators for concurrency;bounds on information exchange for byzantine agreement;a refinement of Kahn's semantics to handle nondeterminism and communication refinement of Kaiin's semantics to handle non-determinism and communication;understanding and using asynchronous message passing;on the distribution of an assertion;real time resource allocation in distributed systems;finding safe paths in a faulty environment;on-the-fly deadlock prevention;edge locks and deadlock avoidance in distributed systems;and a distributed algorithm for detecting resource deadlocks in distributed systems.
This paper presents a new algorithm to answer top-k queries (e.g. "find the k objects with the highest aggregate values") in a distributed network. Existing algorithms such as the Threshold Algorithm [10] co...
详细信息
ISBN:
(纸本)9781581138023
This paper presents a new algorithm to answer top-k queries (e.g. "find the k objects with the highest aggregate values") in a distributed network. Existing algorithms such as the Threshold Algorithm [10] consume an excessive amount of bandwidth when the number of nodes, m, is high. We propose a new algorithm called "Three-Phase Uniform Threshold" (TPUT). TPUT reduces network bandwidth consumption by pruning away ineligible objects, and terminates in three round-trips regardless of data input. The paper presents two sets of results about TPUT. First, trace-driven simulations show that, depending on the size of the network, TPUT reduces network traffic by one to two orders of magnitude compared to existing algorithms. Second, TPUT is proven to be instance-optimal on common data series. In particular, analysis shows that by using a pruning parameter α
A wait-free universal construction is attractive because, no matter what type of wait-free objects are needed by applications, they can be implemented simply by instantiating the universal construction with the approp...
详细信息
A wait-free universal construction is attractive because, no matter what type of wait-free objects are needed by applications, they can be implemented simply by instantiating the universal construction with the appropriate types. However, the worst-case time complexity of every existing n-process universal construction is Ω(n): that is, in any implementation obtained by instantiating a universal construction, in the worst-case a process performs Ω(n) computation in order to complete a single operation on the implemented object. In fact, a lower bound of Ω(n) has been proved for the worst-case local time complexity of any oblivious universal construction.
The proceedings contain 21 papers. The topics discussed include: viewstamped replication: a new primary copy method to support highly-available distributed systems;DCF: distributed communication with fault tolerance;o...
ISBN:
(纸本)0897912772
The proceedings contain 21 papers. The topics discussed include: viewstamped replication: a new primary copy method to support highly-available distributed systems;DCF: distributed communication with fault tolerance;one-bit algorithms;the power of multimedia: combining point-to-point and multiaccess networks;recovery in distributed systems using optimistic message logging and checkpointing;the data link layer: two impossibility results;improved algorithms for distributed resource allocation;end-to-end communication in unreliable networks;the cost of messages;a lattice-structured proof technique applied to a minimum spanning tree algorithm;computing on anonymous networks;understanding and verifying distributed algorithms using stratified decomposition;detecting stable properties of networks in concurrent logic programming languages;concurrent common knowledge: a new definition of agreement for asynchronous systems;secure and verifiable schemes for election and general distributedcomputing problems;process semantics: global axioms, compositional rules, and applications;the global time assumption and semantics for concurrent systems;and a combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor.
暂无评论