This paper studies the problem of making distributed decisions with the goal of maximizing a given utility function. The focus is entirely on the design and performance of the voting strategy and complete abstract fro...
详细信息
ISBN:
(纸本)9780897918008
This paper studies the problem of making distributed decisions with the goal of maximizing a given utility function. The focus is entirely on the design and performance of the voting strategy and complete abstract from implementational details, such as how ballots are collected from the voters and how the results of the election is communicated to the voters. The main interest is in giving a tight estimate of the cumulative profit achievable in a worst-case setting.
Recently, a new paradigm was proposed in which synchronization is accomplished by linking independent read and write operations separated by an arbitrary computation. The linking is such that the write operation will ...
详细信息
ISBN:
(纸本)9780897918008
Recently, a new paradigm was proposed in which synchronization is accomplished by linking independent read and write operations separated by an arbitrary computation. The linking is such that the write operation will succeed only if the shared memory has not been modified since the read. This is called transactional synchronization. With transactional synchronization, any RMW primitive using optimal time and space can be simulated.
In my presentation I will propose a new link-layer model for distributedcomputing based on so-called relays that promises to be useful for the design of robust and secure distributed systems based on overlay networks...
详细信息
An adaptive algorithm for mutual exclusion is presented using only read and write operations. The algorithm has O(k) remote step complexity and O(log k) system response time. The space complexity of the algorithm is O...
详细信息
An adaptive algorithm for mutual exclusion is presented using only read and write operations. The algorithm has O(k) remote step complexity and O(log k) system response time. The space complexity of the algorithm is O(nN), where N is the range of processes' names.
This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simula...
详细信息
ISBN:
(纸本)0897914953
This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simulate reliable shared-memory objects, despite the fact that the available memory objects (e.g. read/write registers, test-and-set registers, read-modify-write registers) may be faulty.
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time...
详细信息
ISBN:
(纸本)9781595936165
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give an algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion. For weighted dynamic graphs we give a constant-factor approximation algorithm that runs in constant time for each insertion or deletion.
暂无评论