The proceedings contain 39 papers from the proceedings of the 23rd annual acm symposium on principles of distributed computing. The topics discussed include: completely fair SFE and coalition-safe cheap talk;mechanism...
详细信息
The proceedings contain 39 papers from the proceedings of the 23rd annual acm symposium on principles of distributed computing. The topics discussed include: completely fair SFE and coalition-safe cheap talk;mechanism design for policy routing;selfish caching in distributed systems: a game-theoretic analysis;bringing practical lock-free synchronization to 64-bit applications;an almost non-blocking stack and lock-free linked lists and skip lists.
The proceedings contain 23 papers. The topics discussed include: concurrent programming for the masses;symmetry and similarity in distributed systems;on the analysis of cooperation and antagonism in networks of commun...
ISBN:
(纸本)0897911989
The proceedings contain 23 papers. The topics discussed include: concurrent programming for the masses;symmetry and similarity in distributed systems;on the analysis of cooperation and antagonism in networks of communicating processes;on characterization of safety and liveness properties in temporal logic;a model and proof system for asynchronous networks;easy impossibility proofs for distributed consensus problems;optimal clock synchronization;comparing how atomicity mechanisms support replication;site optimal termination protocols for a distributed database under network partitioning;distributed version management for read-only actions;a provably secure polynomial approximation scheme for the distributed lottery problem;and simple constant-time consensus protocols in realistic failure models.
The proceedings contain 62 papers. The topics discussed include: determining recoverable consensus numbers;history-independent concurrent objects;MemSnap: a fast adaptive snapshot algorithm for RMWable shared-memory;b...
ISBN:
(纸本)9798400706684
The proceedings contain 62 papers. The topics discussed include: determining recoverable consensus numbers;history-independent concurrent objects;MemSnap: a fast adaptive snapshot algorithm for RMWable shared-memory;brief announcement: randomized consensus: common coins are not the holy grail!;game dynamics and equilibrium computation in the population protocol model;brief announcement: optimally encoding information in chemical reaction networks;polylogarithmic time algorithms for shortest path forests in programmable matter;majority consensus thresholds in competitive Lotka-Volterra populations;brief announcement: self-stabilizing mis computation in the beeping model;brief announcement: on the limits of information spread by memory-less agents;and system optimizations for enabling training of extreme long sequence transformer models.
The proceedings contain 456 papers. The topics discussed include: agent-based simulation of electronic market places with decision support;emerging cooperation in a public good game with competition;a vehicular waitin...
ISBN:
(纸本)9781595937537
The proceedings contain 456 papers. The topics discussed include: agent-based simulation of electronic market places with decision support;emerging cooperation in a public good game with competition;a vehicular waiting time heuristic for dynamic vehicle routing problem;a framework for execution and 3D visualization of situated cellular agent based crowd simulations;a statistical approach for prediction of projects based on simulation;electricity market simulation: multiagent system approach;a validation methodology for agent-based simulations;coordination schemes in distributed simulation of relativistic particle transport;RePart: a reputation-based simulation tool for partnership formation;generation of continuous random networks by simulated annealing;and contextualizing normative open multi-agent systems.
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementati...
详细信息
ISBN:
(纸本)9781581138023
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that w...
详细信息
ISBN:
(纸本)9781581138023
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by f...
详细信息
ISBN:
(纸本)9781581138023
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Ω(nc/k2,/k) and Ω(Δ1/k/k) for some constant c, where n and Δ denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Ω(√log n/ log log n) and Ω(log Δ/ log log Δ). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.
We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources...
详细信息
We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources or cost for access to a remote replica. We show the existence of pure strategy Nash equilibria and investigate the price of anarchy, which is the relative cost of the lack of coordination. The price of anarchy can be high due to undersupply problems, but with certain network topologies it has better bounds. With a payment scheme the game can always implement the social optimum in the best case by giving servers incentive to replicate.
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 α
暂无评论