BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Quentin Bramas

Quentin Bramas appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Networking and Internet ArchitectureDistributed, Parallel, and Cluster ComputingData Structures and AlgorithmsComputational ComplexityCryptography and SecurityMultiagent SystemsRobotics

Catalog footprint

What is connected

9works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2024arXiv

Stand-Up Indulgent Gathering on Lines for Myopic Luminous Robots

We consider a strong variant of the crash fault-tolerant gathering problem called stand-up indulgent gathering (SUIG), by robots endowed with limited visibility sensors and lights on line-shaped networks. In this problem, a group of mobile robots must eventually gather at a single location, not known beforehand, regardless of the occurrence of crashes. Differently from previous work that considered unlimited visibility, we assume that robots can observe nodes only within a certain fixed distance (that is, they are myopic), and emit a visible color from a fixed set (that is, they are luminous), without multiplicity detection. We consider algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots. Then, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, SUIG can be solved in the fully synchronous model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Deploying Near-Optimal Delay-Constrained Paths with Segment Routing in Massive-Scale Networks

With a growing demand for quasi-instantaneous communication services such as real-time video streaming, cloud gaming, and industry 4.0 applications, multi-constraint Traffic Engineering (TE) becomes increasingly important. While legacy TE management planes have proven laborious to deploy, Segment Routing (SR) drastically eases the deployment of TE paths and is thus increasingly adopted by Internet Service Providers (ISP). There is a clear need in computing and deploying Delay-Constrained Least-Cost paths (DCLC) with SR for real-time interactive services. However, most current DCLC solutions are not tailored for SR. They also often lack efficiency or guarantees. Similarly to approximation schemes, we argue that the challenge is to design an algorithm providing both performances and guarantees. However, conversely to most of these schemes, we also consider operational constraints to provide a practical, high-performance implementation. We leverage the inherent limitations of delay measurements and account for the operational constraint added by SR to design a new algorithm, best2cop, providing guarantees and performance in all cases. Best2cop outperforms a state-of-the-art algorithm on both random and real networks of up to 1000 nodes. Relying on commodity hardware with a single thread, our algorithm retrieves all non-superfluous 3-dimensional routes in only 250ms and 100ms respectively. This execution time is further reduced using multiple threads, as the design of best2cop enables a speedup almost linear in the number of cores. Finally, we extend best2cop to deal with massive scale ISP by leveraging the multi-area partitioning of these deployments. Thanks to our new topology generator specifically designed to model the realistic patterns of such massive IP networks, we show that best2cop solves DCLC-SR in approximately 1 second even for ISP having more than 100000 routers.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Fast-Convergence Routing of the Hot-Potato

Interactions between the intra- and inter-domain routing protocols received little attention despite playing an important role in forwarding transit traffic. More precisely, by default, IGP distances are taken into account by BGP to select the closest exit gateway for the transit traffic (hot-potato routing). Upon an IGP update, the new best gateway may change and should be updated through the (full) re-convergence of BGP, causing superfluous BGP processing and updates in many cases. We propose OPTIC (Optimal Protection Technique for Inter-intra domain Convergence), an efficient way to assemble both protocols without losing the hot-potato property. OPTIC pre-computes sets of gateways (BGP next-hops) shared by groups of prefixes. Such sets are guaranteed to contain the post-convergence gateway after any single IGP event for the grouped prefixes. The new optimal exits can be found through a single walk-through of each set, allowing the transit traffic to benefit from optimal BGP routes almost as soon as the IGP converges. Compared to vanilla BGP, OPTIC's structures allow it to consider a reduced number of entries: this number can be reduced by 99\% for stub networks. The update of OPTIC's structures, which is not required as long as border routers remain at least bi-connected, scales linearly in time with its number of groups.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the improvement of the in-place merge algorithm parallelization

In this paper, we present several improvements in the parallelization of the in-place merge algorithm, which merges two contiguous sorted arrays into one with an O(T) space complexity (where T is the number of threads). The approach divides the two arrays into as many pairs of partitions as there are threads available; such that each thread can later merge a pair of partitions independently of the others. We extend the existing method by proposing a new algorithm to find the median of two partitions. Additionally, we provide a new strategy to divide the input arrays where we minimize the data movement, but at the cost of making this stage sequential. Finally, we provide the so-called linear shifting algorithm that swaps two partitions in-place with contiguous data access. We emphasize that our approach is straightforward to implement and that it can also be used for external (out of place) merging. The results demonstrate that it provides a significant speedup compared to sequential executions, when the size of the arrays is greater than a thousand elements.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stateless Distributed Ledgers

In public distributed ledger technologies (DLTs), such as Blockchains, nodes can join and leave the network at any time. A major challenge occurs when a new node joining the network wants to retrieve the current state of the ledger. Indeed, that node may receive conflicting information from honest and Byzantine nodes, making it difficult to identify the current state. In this paper, we are interested in protocols that are stateless, i.e., a new joining node should be able to retrieve the current state of the ledger just using a fixed amount of data that characterizes the ledger (such as the genesis block in Bitcoin). We define three variants of stateless DLTs: weak, strong, and probabilistic. Then, we analyze this property for DLTs using different types of consensus.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distributed Online Data Aggregation in Dynamic Graphs

We consider the problem of aggregating data in a dynamic graph, that is, aggregating the data that originates from all nodes in the graph to a specific node, the sink. We are interested in giving lower bounds for this problem, under different kinds of adversaries. In our model, nodes are endowed with unlimited memory and unlimited computational power. Yet, we assume that communications between nodes are carried out with pairwise interactions, where nodes can exchange control information before deciding whether they transmit their data or not, given that each node is allowed to transmit its data at most once. When a node receives a data from a neighbor, the node may aggregate it with its own data. We consider three possible adversaries: the online adaptive adversary, the oblivious adversary , and the randomized adversary that chooses the pairwise interactions uniformly at random. For the online adaptive and the oblivious adversary, we give impossibility results when nodes have no knowledge about the graph and are not aware of the future. Also, we give several tight bounds depending on the knowledge (be it topology related or time related) of the nodes. For the randomized adversary, we show that the Gathering algorithm, which always commands a node to transmit, is optimal if nodes have no knowledge at all. Also, we propose an algorithm called Waiting Greedy, where a node either waits or transmits depending on some parameter, that is optimal when each node knows its future pairwise interactions with the sink.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Packet Efficient Implementation of the Omega Failure Detector

We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an implementation of the Omega Failure Detector under such an assumption.To motivate the study, we prove that the existence and sustainability of a leader is exponentially more probable in a multi-hop Omega implementation than in a single-hop one.An implementation is: \emph{message efficient} if all but finitely many messages are sent by a single process; \emph{packet efficient} if the number of packets used to transmit a message in all but finitely many messages is linear w.r.t the number of processes, packets of different messages may potentially use different channels, thus the number of used channels is not limited; \emph{super packet efficient} if the number of channels used by packets to transmit all but finitely many messages is linear.We present the following results for deterministic algorithms. If reliability and timeliness of one message does not correlate with another, i.e., there are no channel reliability properties, then a packet efficient implementation of Omega is impossible. If eventuallytimely and fair-lossy channels are considered, we establish necessary and sufficient conditions for the existence of a message and packet efficient implementation of Omega. We also prove that the eventuality of timeliness of channels makes a super packet efficientimplementation of Omega impossible. On the constructive side, we present and prove correct a deterministic packet efficient implementation of Omega that matches the necessary conditions we established.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Random Bit Complexity of Mobile Robots Scattering

We consider the problem of scattering $n$ robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner, all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering. We first prove that $n \log n$ random bits are necessary to scatter $n$ robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem. Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in $o(\log \log n)$ rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific protocol of this family that is random bit optimal ($n \log n$ random bits are used) and time optimal ($\log \log n$ rounds are used). This improves the time complexity of previous results in the same setting by a $\log n$ factor. Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes its time complexity gap with and without strong multiplicity detection (that is, $O(1)$ time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach it as needed otherwise).

0 citations0 reviewsNo code linkedOpen access