Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2008 | Buch

Mobile Entities Computing: Models and Problems Kapitel lesen Erstes Kapitel lesen

Structural Information and Communication Complexity

15th International Colloquium, SIROCCO 2008 Villars-sur-Ollon, Switzerland, June 17-20, 2008 Proceedings

herausgegeben von: Alexander A. Shvartsman, Pascal Felber

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The Colloquium on Structure, Information, Communication, and Complexity (SIROCCO) is an annual research meeting focused on the relationship between information and e?ciency in decentralized (distributed, parallel, and network) computing.Thisyear,SIROCCOcelebratedits15thanniversary.Overtheyears, the colloquium has become a widely recognized forum bringing together - searchers interested in the fundamental principles underlying the interplay - tween local structural knowledge and global communication and computation complexity. SIROCCO covers topics such as distributed algorithms, compact data structures, information dissemination, informative labeling schemes, c- binatorial optimization, and others, with potential applications to large-scale distributed systems including global computing platforms, peer-to-peer systems andapplications,socialnetworks,wirelessnetworks,andnetworkprotocols(such as routing, broadcasting, localization). SIROCCO 2008 was held in Villars-sur- Ollon, in the Swiss Alps, June 17–20, 2008. There were 52 contributions submitted to SIROCCO 2008. All papers - derwent a thorough refereeing process, where each submission was reviewed by at least 3, and on average 3.4, Program Committee members. After in-depth discussions, the Program Committee selected 22 high-quality contributions for presentation at the colloquium and publication in this volume. We thank the authors of all the submitted papers, the Program Committee members, and the external reviewers. Without their dedication, we could not have prepared a program of such quality. ThereweretwoinvitedspeakersatSIROCCO2008:NicolaSantoro(Carleton University) and Boaz Patt-Shamir (Tel-Aviv University). We express our gratitude to the SIROCCO Steering Committee, and in p- ticulartoPierreFraigniaudforhisenthusiasmandhisinvaluablehelpthroughout the preparation of this event.

Inhaltsverzeichnis

Frontmatter

Invited Talks

Mobile Entities Computing: Models and Problems
Abstract
By mobile entity computing (MEC) we refer to the study of the computational and complexity issues arising in systems of autonomous computational entities located in a spatial universe \({\cal U}\) in which they can move. The entities have computational capabilities (i.e., storage and processing), can move in \({\cal U}\) (their movement is constrained by the nature of \({\cal U}\)), exhibit the same behavior (i.e., execute the same protocol), and are autonomous in their actions (e.g., they are not directed by an external controller). Depending on the context, the entities are sometimes called agents, other times robots.
Depending on the nature of \({\cal U}\), two different settings are identified. The first setting, sometimes called a graph world or discrete universe or netscape, is when the \({\cal U}\) is a simple graph and the entities can move from node to neighbouring node. An instance of such setting is that of mobile software agents in a network. The other setting, called sometimes continuous universe, is when \({\cal U}\) is a geometric space which the entities, endowed with wireless sensorial/communication capabilities, can perceive and can move in. Instances of such settings are autonomous mobile robots, and autonomous vehicular networks.
These settings have been long the subject of separate intensive investigations in fields as diverse as AI, robotics, and software engineering, and only recently by the distributed computing community. Indeed, the use of mobile software agents is becoming increasingly popular when computing in networked environments, ranging from Internet to the Data Grid, both as a theoretical paradigm and as a system-supported programming platform but the theoretical research had focused mainly on the descriptive and semantic concerns. This situation has drastically changed in recent years, as an increasing number of algorithmic investigations have started to examine the setting. Similarly, in the last few years the problems related to the coordination and control of autonomous mobile robots have been investigated not only in the traditional fields of AI, robotics and control but also by researchers in distributed computing).
In both settings, the research concern is on determining what tasks can be performed by the entities, under what conditions, and at what cost. In particular, a central question is to determine what minimal hypotheses allow a given problem to be solved.
The purpose of this talk is to introduce the computational models and the fundamental problems in MEC; although the focus is on the discrete universe, several of the introduced concepts extend, mutata mutandis, to the continuous case.
Nicola Santoro
Reputation, Trust and Recommendation Systems in Peer-to-Peer Systems
Abstract
The Internet has brought about the notion of peer-to-peer computing, whose reliance on a central authority (let alone a central server) is minimal. It seems fair to say that one of the Great Promises of the Internet is that such unmoderated direct interaction between users will reduce much of the traditional overhead due to the “man in middle” taking his share: either financially (in the context of e-commerce) or conceptually (in the context of opinion shaping, say). The flip side of this prospect, of course, is the danger that the system will deteriorate into a lawless jungle: some users in a peer-to-peer system, possibly coordinated, might exploit honest users to their advantage, since it appears that there is no effective way to enforce rules in this game.
Boaz Patt-Shamir

Regular Papers

Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses
Abstract
Systems of autonomous mobile robots have been attracted as distributed systems. Minimal setting for robots to solve some class of problems has been studied with theoretical concerns. This paper contributes discussion on relationship between inaccuracy of compasses which give axes of coordinate systems of robots and the possibility of gathering robots. The gathering problem is to make all robots meet at a single point which is not predefined. The problem has been shown to be solvable for two robots with dynamically variable compasses within the difference of π/4 between two robots. This paper improves the limit of difference to π/3. This is shown with the fully asynchronous robot model CORDA. Configurations and executions of robot systems for CORDA with dynamic compasses are formalised. In order to deal with behaviors of robots a concept of relative configurations is also introduced.
Nobuhiro Inuzuka, Yuichi Tomida, Taisuke Izumi, Yoshiaki Katayama, Koichi Wada
Locating and Repairing Faults in a Network with Mobile Agents
Abstract
We consider a fixed, undirected, known network and a number of “mobile agents” which can traverse the network in synchronized steps. Some nodes in the network may be faulty and the agents are to find the faults and repair them. The agents could be software agents, if the underlying network represents a computer network, or robots, if the underlying network represents some potentially hazardous physical terrain. Assuming that the first agent encountering a faulty node can immediately repair it, it is easy to see that the number of steps necessary and sufficient to complete this task is Θ(n/k + D), where n is the number of nodes in the network, D is the diameter of the network, and k is the number of agents. We consider the case where one agent can repair only one faulty node. After repairing the fault, the agent dies. We show that a simple deterministic algorithm for this problem terminates within O(n/k + Dlogf/loglogf) steps, where f =  min {n/k, n/D}, assuming that the number of faulty nodes is at most k/2. We also demonstrate the worst-case asymptotic optimality of this algorithm by showing a network such that for any deterministic algorithm, there is a placement of k/2 faults forcing the algorithm to work for Ω(n/k + Dlogf/loglogf) steps.
Colin Cooper, Ralf Klasing, Tomasz Radzik
Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots
Abstract
In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles.
We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task.
We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that there are n-node trees where Ω(n) robots are necessary; this holds even if the maximum degree is 4. On the other hand, we show that if the maximum degree is 3, it is possible to explore with only \(O(\frac{\log n} {\log\log n})\) robots. The proof of the result is constructive. Finally, we prove that the size of the team is asymptotically optimal: we show that there are trees of degree 3 whose exploration requires \(\Omega(\frac{\log n}{\log\log n})\) robots.
Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro
Average Binary Long-Lived Consensus: Quantifying the Stabilizing Role Played by Memory
Abstract
Consider a system composed of n sensors operating in synchronous rounds. In each round an input vector of sensor readings x is produced, where the i-th entry of x is a binary value produced by the i-th sensor. The sequence of input vectors is assumed to be smooth: exactly one entry of the vector changes from one round to the next one. The system implements a fault-tolerant averaging consensus function f. This function returns, in each round, a representative output value v of the sensor readings x. Assuming that at most t entries of the vector can be erroneous, f is required to return a value that appears at least t + 1 times in x. The instability of the system is the number of output changes over a random sequence of input vectors.
Our first result is to design optimal instability consensus systems with and without memory. Roughly, in the memoryless case, we show that an optimal system is D 0, that outputs 1 unless it is forced by the fault-tolerance requirement to output 0 (on vectors with t or less 1’s). For the case of systems with memory, we show that an optimal system is D 1, that initially outputs the most common value in the input vector, and then stays with this output unless forced by the fault-tolerance requirement to change (i.e., a single bit of memory suffices).
Our second result is to quantify the gain factor due to memory by computing c n (t), the number of decision changes performed by D 0 per each decision change performed by D 1. If \(t=\frac{n}{2}\) the system is always forced to decide the simple majority and, in that case, memory becomes useless. We show that the same type of phenomenon occurs when \(\frac{n}{2}-t\) is constant. Nevertheless, as soon as \(\frac{n}{2}-t \sim \sqrt{n}\), memory plays an important stabilizing role because the ratio c n (t) grows like \(\Theta(\sqrt{n})\). We also show that this is an upper bound: \(c_n(t)=O(\sqrt{n})\) for every t.
Our results are average case versions of previous works where the sequence of input vectors was assumed to be, in addition to smooth, geodesic: the i-th entry of the input vector was allowed to change at most once over the sequence. It thus eliminates some anomalies that ocurred in the worst case, geodesic instability setting.
Florent Becker, Sergio Rajsbaum, Ivan Rapaport, Éric Rémila
Distributed Approximation Algorithm for Resource Clustering
Abstract
In this paper, we consider the clustering of resources on large scale platforms. More precisely, we target parallel applications consisting of independant tasks, where each task is to be processed on a different cluster. In this context, each cluster should be large enough so as to hold and process a task, and the maximal distance between two hosts belonging to the same cluster should be small in order to minimize latencies of intra-cluster communications. This corresponds to maximum bin covering with an extra distance constraint. We describe a distributed approximation algorithm that computes resource clustering with coordinates in ℚ in O(log2 n) steps and O(nlogn) messages, where n is the overall number of hosts. We prove that this algorithm provides an approximation ratio of \(\frac{1}{3}\).
Olivier Beaumont, Nicolas Bonichon, Philippe Duchon, Hubert Larchevêque
Sharpness: A Tight Condition for Scalability
Abstract
A distributed system is scalable if the rate at which it completes its computation and communication tasks does not depend on its size. As an example, the scalability of a peer-to-peer application that transmits data among a large group depends on the topology and the synchronization implemented between the peers. This work describes a model designed to shed light on the conditions that enable scalability. Formally, we model here a collection of tasks, each requiring a random amount of time, which are related by precedence constraints. We assume that the tasks are organized along an euclidean lattice of dimension d. Our main assumption is that the precedence relation between these tasks is invariant by translation along any of these dimensions, so that the evolution of the system follows Uniform Recurrence Equations (UREs). Our main result is that scalability may be shown under two general conditions: (1) a criterion called “sharpness” satisfied by the precedence relation and (2) a condition on the distribution of each task completion time, which only depends on the dimension d. These conditions are shown to be tight. This result offers a universal technique to prove scalability which can be useful to design new systems deployed among an unlimited number of collaborative nodes.
Augustin Chaintreau
Discovery of Network Properties with All-Shortest-Paths Queries
Abstract
We consider the problem of discovering properties (such as the diameter) of an unknown network G(V,E) with a minimum number of queries. Initially, only the vertex set V of the network is known. Information about the edges and non-edges of the network can be obtained by querying nodes of the network. A query at a node q ∈ V returns the union of all shortest paths from q to all other nodes in V. We study the problem as an online problem – an algorithm does not initially know the edge set of the network, and has to decide where to make the next query based on the information that was gathered by previous queries. We study how many queries are needed to discover the diameter, a minimal dominating set, a maximal independent set, the minimum degree, and the maximum degree of the network. We also study the problem of deciding with a minimum number of queries whether the network is 2-edge or 2-vertex connected. We use the usual competitive analysis to evaluate the quality of online algorithms, i.e., we compare online algorithms with optimum offline algorithms. For all properties except maximal independent set and 2-vertex connectivity we present and analyze online algorithms. Furthermore we show, for all the aforementioned properties, that “many” queries are needed in the worst case. As our query model delivers more information about the network than the measurement heuristics that are currently used in practise, these negative results suggest that a similar behavior can be expected in realistic settings, or in more realistic models derived from the all-shortest-paths query model.
Davide Bilò, Thomas Erlebach, Matúš Mihalák, Peter Widmayer
Recovering the Long-Range Links in Augmented Graphs
Abstract
The augmented graph model, as introduced by Kleinberg (STOC 2000), is an appealing model for analyzing navigability in social networks. Informally, this model is defined by a pair (H,ϕ), where H is a graph in which inter-node distances are supposed to be easy to compute or at least easy to estimate. This graph is ”augmented” by links, called long-range links, which are selected according to the probability distribution ϕ. The augmented graph model enables the analysis of greedy routing in augmented graphs G ∈ (H,ϕ). In greedy routing, each intermediate node handling a message for a target t selects among all its neighbors in G the one that is the closest to t in H and forwards the message to it.
This paper addresses the problem of checking whether a given graph G is an augmented graph. It answers part of the questions raised by Kleinberg in his Problem 9 (Int. Congress of Math. 2006). More precisely, given G ∈ (H,ϕ), we aim at extracting the base graph H and the long-range links R out of G. We prove that if H has high clustering coefficient and H has bounded doubling dimension, then a simple local maximum likelihood algorithm enables to partition the edges of G into two sets H′ and R′ such that E(H) ⊆ H′ and the edges in H′ ∖ E(H) are of small stretch, i.e., the map H is not perturbed too greatly by undetected long-range links remaining in H′. The perturbation is actually so small that we can prove that the expected performances of greedy routing in G using the distances in H′ are close to the expected performances of greedy routing using the distances in H. Although this latter result may appear intuitively straightforward, since H′ ⊇ E(H), it is not, as we also show that routing with a map more precise than H may actually damage greedy routing significantly. Finally, we show that in absence of a hypothesis regarding the high clustering coefficient, any local maximum likelihood algorithm extracting the long-range links can miss the detection of at least Ω(n 5ε /logn) long-range links of stretch at least Ω(n 1/5 − ε ) for any 0 < ε< 1/5, and thus the map H cannot be recovered with good accuracy.
Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker
Computing Frequent Elements Using Gossip
Abstract
We present algorithms for identifying frequently occurring elements in a large distributed data set using gossip. Our algorithms do not rely on any central control, or on an underlying network structure, such as a spanning tree. Instead, nodes repeatedly select a random partner and exchange data with the partner – if this process continues for a (short) period of time, the desired results are computed, with probabilistic guarantees on the accuracy. Our algorithm for frequent elements is built by layering a novel small space “sketch” of data over a gossip-based data dissemination mechanism. We prove that the algorithm converges to the approximate frequent elements with high probability, and provide bounds on the time till convergence. To our knowledge, this is the first work on computing frequent elements using gossip.
Bibudh Lahiri, Srikanta Tirthapura
Maintaining Consistent Transactional States without a Global Clock
Abstract
A crucial property required from software transactional memory systems (STMs) is that transactions, even ones that will eventually abort, will operate on consistent states. The only known technique for providing this property is through the introduction of a globally shared version clock whose values are used to tag memory locations. Unfortunately, the need for a shared clock moves STM designs from being completely decentralized back to using centralized global information.
This paper presents TLC, the first thread-local clock mechanism for allowing transactions to operate on consistent states. TLC is the proof that one can devise coherent-state STM systems without a global clock.
A set of early benchmarks presented here within the context of the TL2 STM algorithm, shows that TLC’s thread-local clocks perform as well as a global clock on small scale machines. Of course, the big promise of the TLC approach is in providing a decentralized solution for future large scale machines, ones with hundreds of cores. On such machines, a globally coherent clock based solution is most likely infeasible, and TLC promises a way for transactions to operate consistently in a distributed fashion.
Hillel Avni, Nir Shavit
Equal-Area Locus-Based Convex Polygon Decomposition
Abstract
This paper presents an algorithm for convex polygon decomposition around a given set of locations. Given an n-vertex convex polygon P and a set X of k points positioned arbitrarily inside P, the task is to divide P into k equal area convex parts, each containing exactly one point of X. The problem is motivated by a terrain covering task for a swarm of autonomous mobile robots. The algorithm runs in time O(k n + k 2logk).
David Adjiashvili, David Peleg
On the Power of Local Orientations
Abstract
We consider a network represented by a simple connected undirected graph with N anonymous nodes that have local orientations, i.e. incident edges of each vertex have locally-unique labels – port names.
We define a pre-processing phase that enables a right-hand rule using agent (RH-agent) to traverse the entire graph. For this phase we design an algorithm for an agent that performs the precomputation. The agent will alter the network by modifying the local orientations using a simple operation of exchanging two local labels in each step. We show a polynomial-time algorithm for this precomputation that needs only one pebble and O(logN) memory in the agent.
Furthermore we design a similar algorithm where the memory that the agent uses for the precomputation is decreased to O(1). In this case, the agent is not able to perform some operations by itself due to the lack of memory and needs support from the environment.
Monika Steinová
Best Effort and Priority Queuing Policies for Buffered Crossbar Switches
Abstract
The buffered crossbar switch architecture has recently gained considerable research attention. In such a switch, besides normal input and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crossbar buffers, output and input contention is eliminated, and the scheduling process is greatly simplified. We analyze the performance of switch policies by means of competitive analysis, where a uniform guarantee is provided for all traffic patterns. The goal of the switch policy is to maximize the weighted throughput of the switch, that is the total value of packets sent out of the switch. For the case of unit value packets (Best Effort), we present a simple greedy switch policy that is 4-competitive. For the case of variable value packets, we consider the Priority Queueing (PQ) mechanism, which provides better Quality of Service (QoS) guarantees by decreasing the delay of real-time traffic. We propose a preemptive greedy switch policy that achieves a competitve ratio of 18. Our results hold for any value of the switch fabric speedup. Moreover, the presented policies incur low overhead and are amenable to efficient hardware implementation at wire speed. To the best of our knowledge, this is the first work on competitive analysis for the buffered crossbar switch architecture.
Alex Kesselman, Kirill Kogan, Michael Segal
Word of Mouth: Rumor Dissemination in Social Networks
Abstract
In this paper we examine the diffusion of competing rumors in social networks. Two players select a disjoint subset of nodes as initiators of the rumor propagation, seeking to maximize the number of persuaded nodes. We use concepts of game theory and location theory and model the selection of starting nodes for the rumors as a strategic game. We show that computing the optimal strategy for both the first and the second player is NP-complete, even in a most restricted model. Moreover we prove that determining an approximate solution for the first player is NP-complete as well. We analyze several heuristics and show that—counter-intuitively—being the first to decide is not always an advantage, namely there exist networks where the second player can convince more nodes than the first, regardless of the first player’s decision.
Jan Kostka, Yvonne Anne Oswald, Roger Wattenhofer
Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games
Abstract
We study coordination mechanisms for scheduling n selfish tasks on m identical parallel machines and we focus on the price of anarchy of non-preemptive coordination mechanisms, i.e., mechanisms whose local policies do not delay or preempt tasks. We prove that the price of anarchy of every non-preemptive coordination mechanism for m > 2 is \(\Omega(\frac{\log \log m}{\log \log \log m})\), while for m = 2, we prove a \(\frac{7}{6}\) lower bound. Our lower bounds indicate that it is impossible to produce a non-preemptive coordination mechanism that improves on the currently best known price of anarchy for identical machine scheduling, which is \(\frac{4}{3}-\frac{1}{3m}\).
Konstantinos Kollias
Computing Approximate Nash Equilibria in Network Congestion Games
Abstract
We consider the problem of computing ε-approximate Nash equilibria in network congestion games. The general problem is known to be PLS-complete for every ε> 0, but the reductions are based on artificial and steep delay functions with the property that already two players using the same resource cause a delay that is significantly larger than the delay for a single player.
We consider network congestion games with delay functions such as polynomials, exponential functions, and functions from queuing theory. We analyse which approximation guarantees can be achieved for such congestion games by the method of randomised rounding. Our results show that the success of this method depends on different criteria depending on the class of functions considered. For example, queuing theoretical functions admit good approximations if the equilibrium load of every resource is bounded away appropriately from its capacity.
Andreas Emil Feldmann, Heiko Röglin, Berthold Vöcking
On the Performance of Beauquier and Debas’ Self-stabilizing Algorithm for Mutual Exclusion
Abstract
In [Dij74] Dijkstra introduced the notion of self-stabilizing algorithms and presented an algorithm with three states for the problem of mutual exclusion on a ring of processors. In [BD95] a similar three state algorithm with an upper bound of \(5\frac{3}{4}n^2+O(n)\) and a lower bound of \(\frac{1}{8}n^2-O(n)\) were presented for its stabilization time. For this later algorithm we prove an upper bound of \(1\frac{1}{2}n^2 + O(n)\), and show a lower bound of n 2 − O(n).
Viacheslav Chernoy, Mordechai Shalom, Shmuel Zaks
Self-stabilizing Cuts in Synchronous Networks
Abstract
Consider a synchronized distributed system where each node can only observe the state of its neighbors. Such a system is called self-stabilizing if it reaches a stable global state in a finite number of rounds. Allowing two different states for each node induces a cut in the network graph. In each round, every node decides whether it is (locally) satisfied with the current cut. Afterwards all unsatisfied nodes change sides independently with a fixed probability p. Using different notions of satisfaction enables the computation of maximal and minimal cuts, respectively. We analyze the expected time until such cuts are reached on several graph classes and consider the impact of the parameter p and the initial cut.
Thomas Sauerwald, Dirk Sudholt
Quiescence of Self-stabilizing Gossiping among Mobile Agents in Graphs
Abstract
This paper considers gossiping among mobile agents in graphs: agents move on the graph and have to disseminate their initial information to every other agent. We focus on self-stabilizing solutions for the gossip problem, where agents may start from arbitrary locations in arbitrary states. Self-stabilization requires (some of the) participating agents to keep moving forever, hinting at maximizing the number of agents that could be allowed to stop moving eventually.
This paper formalizes the self-stabilizing agent gossip problem, introduces the quiescence number (i.e., the maximum number of eventually stopping agents) of self-stabilizing solutions and investigates the quiescence number with respect to several assumptions related to agent anonymity, synchrony, link duplex capacity, and whiteboard capacity.
Toshimitsu Masuzawa, Sébastien Tixeuil
Gathering with Minimum Delay in Tree Sensor Networks
Abstract
Data gathering is a fundamental operation in wireless sensor networks in which data packets generated at sensor nodes are to be collected at a base station. In this paper we suppose that each sensor is equipped with an half–duplex interface; hence, a node cannot receive and transmit at the same time. Moreover, each node is equipped with omnidirectional antennas allowing the transmission over distance R. The network is a multi-hop wireless network and the time is slotted so that one–hop transmission of one data item consumes one time slot. We model the network with a graph where the vertices represent the nodes and two nodes are connected if they are in the transmission/interference range of each other. Due to interferences a collision happens at a node if two or more of its neighbors try to transmit at the same time. Furthermore we suppose that an intermediate node should forward a message as soon as it receives it. We give an optimal collision free gathering schedule for tree networks whenever each node has at least one data packet to send.
Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno
Centralized Communication in Radio Networks with Strong Interference
Abstract
We study communication in known topology radio networks with the presence of interference constraints. We consider a real-world situation, when a transmission of a node produces an interference in the area that is larger than the area, where the transmitted message can be received. For each node, there is an area, where a signal of its transmission is too low to be decoded by a receiver, but is strong enough to interfere with other incoming simultaneous transmissions. Such a setting is modelled by a newly proposed interference reachability graph that extends the standard graph model based on reachability graphs. Further, focusing on the information dissemination problem in bipartite interference reachability graphs, we introduce interference ad-hoc selective families as an useful combinatorial tool. They are a natural generalization of ad-hoc selective families. Adopting known algorithms and techniques, we show how to construct small interference ad-hoc selective families in the case when, for each node, the ratio of the only-interfering neighbors to the other neighbors is bounded. Finally, taking into account the maximum degree in an underlying interference reachability graph, we study the broadcasting problem in general radio networks.
František Galčík
Fast Radio Broadcasting with Advice
Abstract
We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: O(n) bits of advice are sufficient but o(n) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
David Ilcinkas, Dariusz R. Kowalski, Andrzej Pelc
Backmatter
Metadaten
Titel
Structural Information and Communication Complexity
herausgegeben von
Alexander A. Shvartsman
Pascal Felber
Copyright-Jahr
2008
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-69355-0
Print ISBN
978-3-540-69326-0
DOI
https://doi.org/10.1007/978-3-540-69355-0

Premium Partner

    Bildnachweise