We introduce a distributed algorithm for clock synchronization in sensor networks. Our algorithm assumes that nodes in the network only know their immediate neighborhoods and an upper bound on the network's diamet...
详细信息
We introduce a distributed algorithm for clock synchronization in sensor networks. Our algorithm assumes that nodes in the network only know their immediate neighborhoods and an upper bound on the network's diameter. Clock-synchronization messages are only sent as part of the communication-assumed to be reasonably frequent-that already takes place among nodes. The algorithm has the gradient property of [R. Fan, N. Lynch, Gradient clock synchronization, distributedcomputing 18 (2006) 255-266], achieving an O(1) worst-case skew between the logical clocks of neighbors. The algorithm's actions are such that no constant lower bound exists on the rate at which logical clocks progress in time, and for this reason the lower bound of [R. Fan, N. Lynch, Gradient clock synchronization, distributedcomputing 18 (2006) 255-266;L Meier, L Thiele, Brief announcement: Gradient clock synchronization in sensor networks, in: proceedings of the twenty-Fourth annualacmsymposium on principles of distributedcomputing, 2005, p. 238] that forbids a constant clock skew between neighbors does not apply. (C) 2008 Elsevier Inc. All rights reserved.
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system that implements a di...
详细信息
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system that implements a distributed hash table abstraction, and study the process by which Chord maintains its distributed state as nodes join and leave the system. We argue that traditional performance measures based on run-time are uniformative for a continually running P2P network, and that the rate at which nodes in the network need to participate to maintain system state is a more useful metric. We give a general lower bound on this rate for a network to remain connected, and prove that an appropriately modified version of Chord's maintenance rate is within a logarithmic factor of the optimum rate.
A two-level model of distributed computation based on actors is presented. This model is the basis for developing a semantic framework supporting dynamic customizability and separation of concerns in designing and rea...
详细信息
ISBN:
(纸本)9780897917100
A two-level model of distributed computation based on actors is presented. This model is the basis for developing a semantic framework supporting dynamic customizability and separation of concerns in designing and reasoning with respect to the components of open distributed systems (ODS). This paper focuses on remote creation, migration, and reachability as well as their specification at different levels of abstraction and their composition.
The proceedings contains 30 papers from the 17th annualacmsymposium on principles of distributedcomputing. Topics discussed include: compact routing schemes;reconsidering fragmentation;dynamic bandwidth allocations...
详细信息
The proceedings contains 30 papers from the 17th annualacmsymposium on principles of distributedcomputing. Topics discussed include: compact routing schemes;reconsidering fragmentation;dynamic bandwidth allocations;balancing networks resolved;asynchronous group mutual exclusions;SCRAMNet systems;private multiparty computations;database private information retrievals;fast-track multiparty computations;threshold cryptography;optimistic contract signing;asynchronous message-passing models;round-by-round fault detectors;message classification models;fault-tolerant concurrent programs;universal constructions;randomized synchronous consensus;and dynamic view-oriented group communication services.
The symposium materials contain 25 papers. The topics covered include distributed priority algorithms, connection-based communication in dynamic networks, adaptive packet routing, computing with faulty shared memory, ...
详细信息
ISBN:
(纸本)0897914953
The symposium materials contain 25 papers. The topics covered include distributed priority algorithms, connection-based communication in dynamic networks, adaptive packet routing, computing with faulty shared memory, fault-tolerant coordination, self-stabilization, shared-memory multiprocessors, fast mutual exclusion, fast network decomposition, the weakest failure detector for solving consensus, leader election in complete networks, randomized coordinated attack protocols, distributed edge coloring, and proving probabilistic correctness statements.
暂无评论