Titlebook: Structural Information and Communication Complexity; 11th International C Ratislav Královic̆,Ondrej Sýkora Conference proceedings 2004 Spri

FLASK

Armory

Long-Lived Rambo: Trading Knowledge for Communication,ining linearizability with efficiency in practical algorithms is difficult. A reconfigurable linearizable data service, called ., was developed by Lynch and Shvartsman. This service guarantees consistency under dynamic conditions involving asynchrony, message loss, node crashes, and new node arrival

Femish

使高兴

Tighter Bounds on Feedback Vertex Sets in Mesh-Based Networks,, whose removal makes a graph acyclic. The problem is .-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. We improve the upper bounds of [11] both for the two-dimensional mesh of trees, and for the pyramid networks. We also present upper

恶心

提炼

esthetician

Time Efficient Gossiping in Known Radio Networks,her values of . we propose a solution admitting gossiping in time ⌈log(. − 1)⌉ + 2. Finally we study asymptotically optimal .(.)-time gossiping (where . is a diameter of the network) in graphs with max-degree . for any integer constant .≥ 0 and . large enough.

Lignans

The Price of Anarchy in All-Optical Networks,t of paths to the requests so that no request can lower its cost by choosing a different path in the network. For such strategies, we bound the loss of performance of the network (price of anarchy) by comparing the number of wavelengths used by the worst pure Nash equilibrium with that of a centralized optimal solution.

合唱团

Axillary

Mobile Agents Rendezvous When Tokens Fail,agent rendezvous under symmetric conditions with different types of knowledge. Our results suggest that knowledge of . is better than knowledge of . in terms of achieving rendezvous as quickly as possible in the faulty token setting.