Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSynchronous Concurrent Broadcasts for Intermittent Channels with Bounded Capacities
154
0
0.0
(
0
)
Added by
Volker Turau
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Volker Turau
Ask ChatGPT about the research
No Arabic abstract
In this work we extend the recently proposed synchronous broadcast algorithm amnesiac flooding to the case of intermittent communication channels. In amnesiac flooding a node forwards a received message in the subsequent round. There are several reasons that render an immediate forward of a message impossible: Higher priority traffic, overloaded channels, etc. We show that postponing the forwarding for one or more rounds prevents termination. Our extension overcomes this shortcoming while retaining the advantages of the algorithm: Nodes dont need to memorize the reception of a message to guarantee termination and messages are sent at most twice per edge. This extension allows to solve more general broadcast tasks such as multi-source broadcasts and concurrent broadcasts for systems with bounded channel capacities.
rate research
Read More
In this paper we suggest a method by which reference broadcast synchronization (RBS), and other methods of estimating clock values, can be incorporated in standard clock synchronization algorithms to improve synchronization quality. We advocate a logical separation of the task of estimating the clock values of other nodes in the network from the task of using these estimates to output a logical clock value. The separation is achieved by means of a virtual estimate graph, overlaid on top of the real network graph, which represents the information various nodes can obtain about each other. RBS estimates are represented in the estimate graph as edges between nodes at distance 2 from each other in the original network graph. A clock synchronization algorithm then operates on the estimate graph as though it were the original network. To illustrate the merits of this approach, we modify a recent optimal gradient clock synchronization algorithm to work in this setting. The modified algorithm transparently takes advantage of RBS estimates and any other means by which nodes can estimate each others clock values.
This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are $k$ identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol GNN that solves the DSMS problem on overlay trees. We prove that GNN is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze GNN for one-shot executions, i.e., all requests are invoked simultaneously. We prove that when running GNN on top of a special family of tree topologies---known as hierarchically well-separated trees (HSTs)---we obtain a randomized distributed protocol with an expected competitive ratio of $O(log n)$ on general network topologies with $n$ processors. From a technical point of view, our main result is that GNN optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of $Omega(max{k, log n/loglog n})$ on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.
This work introduces the particle-intensity channel (PIC) as a model for molecular communication systems and characterizes the capacity limits as well as properties of the optimal (capacity-achieving) input distributions for such channels. In the PIC, the transmitter encodes information, in symbols of a given duration, based on the probability of particle release, and the receiver detects and decodes the message based on the number of particles detected during the symbol interval. In this channel, the transmitter may be unable to control precisely the probability of particle release, and the receiver may not detect all the particles that arrive. We model this channel using a generalization of the binomial channel and show that the capacity-achieving input distribution for this channel always has mass points at probabilities of particle release of zero and one. To find the capacity-achieving input distributions, we develop an efficient algorithm we call dynamic assignment Blahut-Arimoto (DAB). For diffusive particle transport, we also derive the conditions under which the input with two mass points is capacity-achieving.
We present a fully lock-free variant of the recent Montage system for persistent data structures. Our variant, nbMontage, adds persistence to almost any nonblocking concurrent structure without introducing significant overhead or blocking of any kind. Like its predecessor, nbMontage is buffered durably linearizable: it guarantees that the state recovered in the wake of a crash will represent a consistent prefix of pre-crash execution. Unlike its predecessor, nbMontage ensures wait-free progress of the persistence frontier, thereby bounding the number of recent updates that may be lost on a crash, and allowing a thread to force an update of the frontier (i.e., to perform a sync operation) without the risk of blocking. As an extra benefit, the helping mechanism employed by our wait-free sync significantly reduces its latency. Performance results for nonblocking queues, skip lists, trees, and hash tables rival custom data structures in the literature -- dramatically faster than achieved with prior general-purpose systems, and generally within 50% of equivalent non-persistent structures placed in DRAM.
The theory of distributed computing, lagging in its development behind practice, has been biased in its modelling by employing mechanisms within the model mimicking reality. Reality means, processors can fail. But theory is about predicting consequences of reality, hence if we capture reality by artificial models, but those nevertheless make analysis simpler, we should pursue the artificial models. Recently the idea was advocated to analyze distributed systems and view processors as infallible. It is the message delivery substrate that causes problems. This view not only can effectively emulate reality, but above all seems to allow to view any past models as emph{synchronous} models. Synchronous models are easier to analyze than asynchronous ones. Furthermore, it gives rise to models we havent contemplated in the past. One such model, presented here, is the Hybrid Message-Adversary. We motivate this model through the need to analyze Byzantine faults. The Hybrid model exhibits a phenomenon not seen in the past.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
