In order to formalize Distributed Ledger Technologies and their interconnections, recent research has introduced the concept of a Distributed Ledger Object (denoted $$\mathcal {O}^L$$ ), a concurrent abstraction that maintains a totally ordered sequence of records, capturing the essence of blockchains and distributed ledgers. In this work, we introduce the Distributed Grow-only Set object (denoted $$\mathcal {O}^{GS}$$ ), a novel abstraction that, unlike the $$\mathcal {O}^L$$ , maintains an immutable set of records by supporting only Add and Get operations. This object is inspired by the Grow-only Set (G-Set) a well-known Conflict-free Replicated Data Type (CRDT). We formally define the $$\mathcal {O}^{GS}$$ and present a Byzantine-tolerant, consensus-free implementation (denoted as $$\mathcal {O}^{GS}_B$$ ) that ensures eventual consistency. Building on this implementation, we propose consensus-free algorithmic solutions to two fundamental problems: the Atomic Appends problem, which concerns atomically appending multiple records to distinct ledgers, and the Atomic Adds problem, its counterpart in the context of G-Sets. Additionally, we show how the $$\mathcal {O}^{GS}_B$$ can be leveraged to construct a consensus-free, Single-Writer Byzantine-tolerant $$\mathcal {O}^L$$ . We argue that the applicability of the $$\mathcal {O}^{GS}_B$$ extends well beyond these specific use cases, offering a lightweight and efficient foundation for a variety of distributed applications.

In this paper, we consider a relay-enabled wireless network and optimize the weighted proportional fair (wPF) bandwidth allocation by means of exact algorithms with linear complexity on the number of users and relays. Complex architectures typical of relay-enabled systems pose the need of developing efficient techniques that account for the intertwined nature of all the network agents, as resources must be split not only between users, but also between relays and relay-served users, altogether constrained by backhaul capacities and the traffic bottleneck present at the wired base stations. Here, traditional schemes for bandwidth allocation cannot be applied, as resources from one point of the network cannot be allocated regardless the allocation performed at other entities of the same network. Hence, we develop a compact weighted proportional fair resource management with very lightweight complexity, able to jointly allocate access and backhaul resources optimally in real time. We benchmark the results on network capacity and fairness with state-of-art proposals and show that the wPF exact algorithms proposed yield the best trade-off between capacity and fairness in relay networks.

Aiding the ground cellular network with aerial base stations carried by drones has experienced an intensive raise of interest in the past years. Reconfigurable air-to-ground channels enable aerial stations to enhance users’ access links by means of seeking good line-of-sight connectivity while hovering in the air. In this article, we propose an analytical framework for the 3D placement of a fleet of coordinated drone relays. This framework optimizes network performance in terms of user throughput fairness, expressed through the α-fairness metric. The optimization problem is formulated as a mixed-integer non-convex program, which is intractable. Hence, we propose an extremal-optimization-based algorithm, Parallelized Alpha-fair Drone Deployment (PADD), which solves the problem online, in low-degree polynomial time. We evaluate our proposal by means of numerical simulations over the real topology of a dense city. We discuss the advantages of integrating drone relay stations in current networks and test several resource scheduling approaches in both static and dynamic scenarios, including with progressively larger and denser crowds.

With the current advances in unmanned aerial vehicle (UAV) technologies, aerial vehicles are becoming very attractive for many purposes. However, currently the bottleneck in their adoption is no longer due to architectural and protocol challenges and constraints, but rather to the limited energy that they can rely on. In this article, we design two power resupply schemes under the assumption of a fleet of homogeneous UAVs. Such schemes are designed to minimize the size of the fleet to be devoted to apersistentservice (i.e., carried out at all times) of a set of aerial locations. First, we consider the case where the aerial locations to be served are equidistant from an energy supply station. In that scenario, we design a simple scheduling scheme, that we name homogeneous rotating resupply (HoRR), which we prove to be feasible and exact in the sense that it uses the minimum possible number of UAVs to guarantee the permanent coverage of the aerial service locations. Then, we extend that work for the case of nonevenly distributed aerial locations. In this new scenario, we demonstrate that the problem becomes NP-hard, and design a lightweight scheduling scheme, partitioned heterogeneous rotating resupply (PHeRR), which extends the operation ofHoRRto the heterogeneous case. Through numerical analysis, we show thatPHeRRprovides near-exact resupply schedules.

Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. In this paper we introduce a number of routing scheduling algorithms which, making use of certain knowledge about the network's structure, guarantee stability for certain injection rates. First, we introduce two new families of combinatorial structures, which we call universally strong selectors and generalized universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, we propose two local-knowledge packet-oblivious routing scheduling algorithms. The first proposed routing scheduling algorithm only needs to know some upper bounds on the number of links and on the network's degree, and is asymptotically optimal regarding the injection rate for which stability is guaranteed. The second proposed routing scheduling algorithm is close to be asymptotically optimal, but it only needs to know an upper bound on the number of links. For such algorithms, we also provide some results regarding both the maximum latencies and queue lengths. Furthermore, we also evaluate how the lack of global knowledge about the system topology affects the performance of the routing scheduling algorithms.

The adoption and integration of drones in commu-nication networks is becoming reality thanks to the deployment of advanced solutions for IoT and cellular communication relay schemes. However, using drones introduces new energy con-straints and scheduling issues in the dynamic management of the network topology, due to the need to call back and recharge, or substitute, drones that run out of energy. In this paper, we describe the design of a drone recharging scheme for realisti-cally limited flight time of drones, and leverage the presence of recharging stations. Indeed, drones need to be recharged periodically, and maximizing the operational time of drones is paramount to minimize the size of the fleet of drones to be devoted to a drone mission, hence its cost. We design Homogeneous Rotating Recharge (HRR), an optimal drone recharging scheduling that extends the coverage of a cellular network. HRR minimizes the number of back-up drones needed to guarantee a fixed number of operational drones, so as to support the operation of an underlying cellular network. Results show that operating a network of drones with our scheme provides reliable and stable performance over time.

The integration of aerial base stations carried by drones in cellular networks offers promising opportunities to enhance the connectivity enjoyed by ground users. In this paper, we propose an optimization framework for the 3-D placement and repositioning of a fleet of drones with a realistic inter-drone interference model and drone connectivity constraints. We show how to maximize network coverage by means of an extremal-optimization algorithm. The design of our algorithm is based on a mixed-integer non-convex program formulation for a coverage problem that is NP-Complete, as we prove in the paper. We not only optimize drone positions in a 3-D space in polynomial time, but also assign flight routes solving an assignment problem and using a strong geometrical tool, namely Bézier curves, which are extremely useful for non-uniform and realistic topologies. Specifically, we propose to fly drones following Bézier curves to seek the chance of approaching to clusters of ground users. This enhances coverage over time while users and drones move. We assess the performance of our proposal for synthetic scenarios as well as realistic maps extracted from the topology of a capital city. We demonstrate that our framework is near-optimal and using Bézier curves increases coverage up to 47 percent while drones move.

This work provides a proper formalization for Distributed Ledger Objects (as first defined in [Antonio Fernández Anta et al., 2018]), when processes may be Byzantine. The formal definitions are accompanied by algorithms to implement Byzantine Distributed Ledgers by utilizing a Byzantine Atomic Broadcast service.

We consider the impact of scheduling disciplines on performance of routing in the framework of adversarial queuing. We propose an adversarial model which reflects stalling of packets due to transient failures and explicitly incorporates feedback produced by a network when packets are stalled. This adversarial model provides a methodology to study stability of routing protocols when flow-control and congestion-control mechanisms affect the volume of traffic. We show that any scheduling policy that is universally stable, in the regular model of routing that additionally allows packets to have two priorities, remains stable in the proposed adversarial model. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 88–97 2015

In this paper, we propose a set of heuristics to be used within greedy algorithms to build connected dominating sets (CDSs). These algorithms depends on a heuristic and we show that the selection of such heuristic is fundamental to optimizing system operation, both in terms of energy consumption and data transmission. Based on some parameters such as the node's degree, the distances between nodes and the already explored nodes, we propose two different heuristics, denoted HIand HT. Using the network simulator ns-2, we perform a number of experiments in different scenarios and analyzed the performance of our proposed algorithms. We show that our algorithms provide CDSs with lower connection duration at a lower energy cost than previous proposals.

Abstract Random walks have been proven useful in several applications in networks. Some variants of the basic random walk have been devised pursuing a suitable trade‐off between better performance and limited cost. A self‐avoiding random walk (SAW) is one that tries not to revisit nodes, therefore covering the network faster than a random walk. Suggested as a network search mechanism, the performance of the SAW has been analyzed using essentially empirical studies. A strict analytical approach is hard since, unlike the random walk, the SAW is not a Markovian stochastic process. We propose an analytical model to estimate the average search length of a SAW when used to locate a resource in a network. The model considers single or multiple instances of the resource sought and the possible availability of one‐hop replication in the network (nodes know about resources held by their neighbors). The model characterizes networks by their size and degree distribution, without assuming a particular topology. It is, therefore, a mean‐field model, whose applicability to real networks is validated by simulation. Experiments with sets of randomly built regular networks, Erdős–Rényi networks, and scale‐free networks of several sizes and degree averages, with and without one‐hop replication, show that model predictions are very close to simulation results, and allow us to draw conclusions about the applicability of SAWs to network search. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

The paper proposes a simple protocol that ensures sequential consistency. The protocol assumes that the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. Unlike other sequential consistency protocols, the one proposed here does not rely on a strong synchronization mechanism, such as an atomic broadcast primitive or a central node managing a copy of every shared object. From a methodological point of view, the protocol is built incrementally starting from the very definition of sequential consistency. It has the noteworthy property that a process that issues a write operation never has to wait for other processes. Depending on the current local state, most read operations issued also have the same property.

In this paper we analyze a novel paradigm of reliable communications which is not based on the traditional timeout-and-retransmit mechanism of TCP. Our approach, which we call FBP (fountain based protocol), consists on using a digital fountain encoding which guarantees that duplicate packets are not possible. Using game theory, we analyze the behavior of TCP and FBP in the presence of congestion. We show that hosts using TCP have an incentive to switch to an FBP approach obtaining a higher throughput. Furthermore, we also show that a Nash equilibrium takes place when all hosts use FBP. At this equilibrium, the performance of the network is similar to the performance obtained when all hosts comply with TCP.

Most of congestion control schemes require users to behave in a cooperative way, so that they respect some "social responsible" rules. However, without forcing end users to adopt a centralized mandated algorithm controlling their behavior (which is not advisable), it is not possible to guarantee that they will not act in a selfish manner. Consequently, a fundamental issue is to evaluate the impact of having users that act in such a manner. In such a scenario, having a Nash equilibrium guarantees that no selfish user has incentive to unilaterally deviate from its current state (i.e., it guarantees that we are in a stable state in the presence of selfish users). However, here we formally prove that an efficient Nash equilibrium can not be reached in practice for any oblivious control policy.

A concurrent object is an object that can be concurrently accessed by several processes. Sequential consistency is a consistency criterion for such objects. Informally, it states that a multiprocess program executes correctly if its results could have been produced by executing that program on a single processor system. (Sequential consistency is weaker than atomic consistency -the usual consistency criterion- as it does not refer to real-time.) The paper proposes a simple protocol that ensures sequential consistency when the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. Differently from other sequential consistency protocols, the proposed protocol does not rely on a strong synchronization mechanism such as an atomic broadcast primitive or a central node managing a copy of every shared object. From a methodological point of view, the protocol is built incrementally starting from the very definition of sequential consistency. It lies the noteworthy property of providing fast writes operations (i.e., a process has never to wait when it writes a new value in a shared object). According to the current local state, some read operations can also be fast. An experimental evaluation of the protocol is also presented. The proposed protocol could be used to manage Web page caching.

No abstract available.

We study how to distribute storage capacity along a hierarchical system with cache-servers located at each node. This system is intended to deliver stored video streams in a video-on-demand way, ensuring that, once started, a transmission is completed without any delay or loss of quality. We perform a detailed analysis of the start-up time delay for some storage distributions, showing that an "intelligent" storage distribution can increase performance from 22% to 29% with respect to a uniform one and from 44% to 78% with respect to one in which all the storage is attached to the gateway router that connects the final users. We also analyze bandwidth usage, comparing the behavior of these storage distributions.

A large amount of work has been invested in devising algorithms to implement distributed shared memory (DSM) systems under different consistency models. However, to our knowledge, the possibility of interconnecting DSM systems with simple protocols and the consistency of the resulting system has never been studied. With this paper, we start a series of works on the properties of the interconnection of DSM systems, which tries to fill this void.