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

Sem Borst

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

ResearcherUnclaimed source record
math.PRNetworking and Internet ArchitecturePerformanceDiscrete MathematicsDistributed, Parallel, and Cluster ComputingInformation Theorymath.COmath.IT

Catalog footprint

What is connected

15works
8topics
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

15 published item(s)

preprint2022arXiv

Crossover times in bipartite networks with activity constraints and time-varying switching rates

In this paper we study the performance of a bipartite network in which customers arrive at the nodes of the network, but not all nodes are able to serve their customers at all times. Each node can be either active or inactive, and two nodes connected by a bond cannot be active simultaneously. This situation arises in wireless random-access networks where, due to destructive interference, stations that are close to each other cannot use the same frequency band. We consider a model where the network is bipartite, the active nodes switch themselves off at rate 1, and the inactive nodes switch themselves on at a rate that depends on time and on which half of the bipartite network they are in. An inactive node cannot become active when one of the nodes it is connected to by a bond is active. The switching protocol allows the nodes to share activity among each other. In the limit as the activation rate becomes large, we compute the crossover time between the two states where one half of the network is active and the other half is inactive. This allows us to assess the overall activity of the network depending on the switching protocol. Our results make use of the metastability analysis for hard-core interacting particle models on finite bipartite graphs derived in an earlier paper. They are valid for a large class of bipartite networks, subject to certain assumptions. Proofs rely on a comparison with switching protocols that are not time-varying, through coupling techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Heavy-Traffic Universality of Redundancy Systems with Assignment Constraints

Service systems often face task-server assignment-constraints due to skill-based routing or geographical conditions. Redundancy scheduling responds to this limited flexibility by replicating tasks to specific servers in agreement with these assignment constraints. We gain insight from product-form stationary distributions and weak local stability conditions to establish a state space collapse in heavy traffic. In this limiting regime, the parallel-server system with redundancy scheduling operates as a multi-class single-server system, achieving full resource pooling and exhibiting strong insensitivity to the underlying assignment constraints. In particular, the performance of a fully flexible (unconstrained) system can be matched even with rather strict assignment constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Power-of-two sampling in redundancy systems: the impact of assignment constraints

A classical sampling strategy for load balancing policies is power-of-two, where any server pair is sampled with equal probability. This does not cover practical settings with assignment constraints which force non-uniform sampling. While intuition suggests that non-uniform sampling adversely impacts performance, this was only supported through simulations, and rigorous statements have remained elusive. Building on product-form distributions for redundancy systems, we prove the stochastic dominance of uniform sampling for a four-server system as well as arbitrary-size systems in light traffic.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Transition time asymptotics of queue-based activation protocols in random-access networks

We consider networks where each node represents a server with a queue. An active node deactivates at unit rate. An inactive node activates at a rate that depends on its queue length, provided none of its neighbors is active. For complete bipartite networks, in the limit as the queues become large, we compute the average transition time between the two states where one half of the network is active and the other half is inactive. We show that the law of the transition time divided by its mean exhibits a trichotomy, depending on the activation rate functions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Achievable Stability in Redundancy Systems

We consider a system with $N$ parallel servers where incoming jobs are immediately replicated to, say, $d$ servers. Each of the $N$ servers has its own queue and follows a FCFS discipline. As soon as the first job replica is completed, the remaining replicas are abandoned. We investigate the achievable stability region for a quite general workload model with different job types and heterogeneous servers, reflecting job-server affinity relations which may arise from data locality issues and soft compatibility constraints. Under the assumption that job types are known beforehand we show for New-Better-than-Used (NBU) distributed speed variations that no replication $(d=1)$ gives a strictly larger stability region than replication $(d>1)$. Strikingly, this does not depend on the underlying distribution of the intrinsic job sizes, but observing the job types is essential for this statement to hold. In case of non-observable job types we show that for New-Worse-than-Used (NWU) distributed speed variations full replication ($d=N$) gives a larger stability region than no replication $(d=1)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stability of Redundancy Systems with Processor Sharing

We investigate the stability condition for redundancy-d systems where each of the servers follows a processor-sharing (PS) discipline. We allow for generally distributed job sizes, with possible dependence among the d replica sizes being governed by an arbitrary joint distribution. We establish that the stability condition is characterized by the expectation of the minimum of d replica sizes being less than the mean interarrival time per server. In the special case of identical replicas, the stability condition is insensitive to the job size distribution given its mean, and the stability condition is inversely proportional to the number of replicas. In the special case of i.i.d. replicas, the stability threshold decreases (increases) in the number of replicas for job size distributions that are NBU (NWU). We also discuss extensions to scenarios with heterogeneous servers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Threshold-based rerouting and replication for resolving job-server affinity relations

We consider a system with several job types and two parallel server pools. Within the pools the servers are homogeneous, but across pools possibly not in the sense that the service speed of a job may depend on its type as well as the server pool. Immediately upon arrival, jobs are assigned to a server pool. This could be based on (partial) knowledge of their type, but such knowledge might not be available. Information about the job type can however be obtained while the job is in service; as the service progresses, the likelihood that the service speed of this job type is low increases, creating an incentive to execute the job on different, possibly faster, server(s). Two policies are considered: reroute the job to the other server pool, or replicate it there. We determine the effective load per server under both the rerouting and replication policy for completely unknown as well as partly known job types. We also examine the impact of these policies on the stability bound, and find that the uncertainty in job types may significantly degrade the performance. For (highly) unbalanced service speeds full replication achieves the largest stability bound while for (nearly) balanced service speeds no replication maximizes the stability bound. Finally, we discuss how the use of threshold-based policies can help improve the expected latency for completely or partly unknown job types.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Scaling Laws for Maximum Coloring of Random Geometric Graphs

We examine maximum vertex coloring of random geometric graphs, in an arbitrary but fixed dimension, with a constant number of colors. Since this problem is neither scale-invariant nor smooth, the usual methodology to obtain limit laws cannot be applied. We therefore leverage different concepts based on subadditivity to establish convergence laws for the maximum number of vertices that can be colored. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A stochastic network with mobile users in heavy traffic

We consider a stochastic network with mobile users in a heavy-traffic regime. We derive the scaling limit of the multi-dimensional queue length process and prove a form of spatial state space collapse. The proof exploits a recent result by Lambert and Simatos which provides a general principle to establish scaling limits of regenerative processes based on the convergence of their excursions. We also prove weak convergence of the sequences of stationary joint queue length distributions and stationary sojourn times.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Delay Performance and Mixing Times in Random-Access Networks

We explore the achievable delay performance in wireless random-access networks. While relatively simple and inherently distributed in nature, suitably designed queue-based random-access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. The specific type of activation rules for which throughput optimality has been established, may however yield excessive queues and delays. Motivated by that issue, we examine whether the poor delay performance is inherent to the basic operation of these schemes, or caused by the specific kind of activation rules. We derive delay lower bounds for queue-based activation rules, which offer fundamental insight in the cause of the excessive delays. For fixed activation rates we obtain lower bounds indicating that delays and mixing times can grow dramatically with the load in certain topologies as well.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lingering Issues in Distributed Scheduling

Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-r), with r the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-r) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact. In addition extensive simulation experiments are conducted to illustrate and validate the various analytical results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Queue-Based Random-Access Algorithms: Fluid Limits and Stability Issues

We use fluid limits to explore the (in)stability properties of wireless networks with queue-based random-access algorithms. Queue-based random-access schemes are simple and inherently distributed in nature, yet provide the capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of activation rules for which throughput optimality has been established, may result in excessive queue lengths and delays. The use of more aggressive/persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees. In order to gain qualitative insight and investigate the (in)stability properties of more aggressive/persistent activation rules, we examine fluid limits where the dynamics are scaled in space and time. In some situations, the fluid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exhibit random oscillatory characteristics, giving rise to major technical challenges. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may cause instability in others. Simulation experiments are conducted to illustrate and validate the analytical results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Stability of Random Admissible-Set Scheduling in Spatially Continuous Wireless Systems

We examine the stability of wireless networks whose users are distributed over a compact space. A subset of users is called {\it admissible} when their simultaneous activity obeys the prevailing interference constraints and, in each time slot, an admissible subset of users is selected uniformly at random to transmit one packet. We show that, under a mild condition, this random admissible-set scheduling mechanism achieves maximum stability in a broad set of scenarios, and in particular in symmetric cases. The proof relies on a description of the system as a measure-valued process and the identification of a Lyapunov function.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stability of parallel queueing systems with coupled service rates

This paper considers a parallel system of queues fed by independent arrival streams, where the service rate of each queue depends on the number of customers in all of the queues. Necessary and sufficient conditions for the stability of the system are derived, based on stochastic monotonicity and marginal drift properties of multiclass birth and death processes. These conditions yield a sharp characterization of stability for systems, where the service rate of each queue is decreasing in the number of customers in other queues, and has uniform limits as the queue lengths tend to infinity. The results are illustrated with applications where the stability region may be nonconvex.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Exact asymptotics for fluid queues fed by multiple heavy-tailed on-off flows

We consider a fluid queue fed by multiple On-Off flows with heavy-tailed (regularly varying) On periods. Under fairly mild assumptions, we prove that the workload distribution is asymptotically equivalent to that in a reduced system. The reduced system consists of a ``dominant'' subset of the flows, with the original service rate subtracted by the mean rate of the other flows. We describe how a dominant set may be determined from a simple knapsack formulation. The dominant set consists of a ``minimally critical'' set of On-Off flows with regularly varying On periods. In case the dominant set contains just a single On-Off flow, the exact asymptotics for the reduced system follow from known results. For the case of several On-Off flows, we exploit a powerful intuitive argument to obtain the exact asymptotics. Combined with the reduced-load equivalence, the results for the reduced system provide a characterization of the tail of the workload distribution for a wide range of traffic scenarios.

0 citations0 reviewsNo code linkedOpen access