Publications related to Queue (abstract data type)

A Theory of Traffic Regulators for Deterministic Networks With Application to Interleaved Regulators

We introduce Pi-regulation, a new definition of traffic regulation which extends both the arrival curves of network calculus and Chang's max-plus g-regulation, and also includes new types of regulation, such as packet rate limitations. We provide a new exa ...

2018

Elastic transactions

Rachid Guerraoui, Vincent Gramoli, Pascal Felber

This paper presents elastic transactions, an appealing alternative to traditional transactions, in particular to implement search structures in shared memory multicore architectures. Upon conflict detection, an elastic transaction might drop what it did so ...

Academic Press Inc Elsevier Science2017

Contract-Based Resource Verification for Higher-Order Functions with Memoization

Viktor Kuncak, Ravichandhran Kandhadai Madhavan, Sumith Kulal

We present a new approach for specifying and verifying resource utilization of higher-order functional programs that use lazy evaluation and memoization. In our approach, users can specify the desired resource bound as templates with numerical holes e.g. a ...

Assoc Computing Machinery2017

Improved Utility-based Congestion Control for Low-Delay Communication

Pascal Frossard, Laura Toni, Sergio Mena, Stefano D'Aronco

Due to the presence of buffers in the inner network nodes, each congestion event leads to buffer queueing and thus to an increasing end-to-end delay. In the case of delay sensitive applications, a large delay might not be acceptable and a solution to prope ...

Ieee-Inst Electrical Electronics Engineers Inc2017

Algorithmic Resource Verification

Ravichandhran Kandhadai Madhavan

Static estimation of resource utilisation of programs is a challenging and important problem with numerous applications. In this thesis, I present new algorithms that enable users to specify and verify their desired bounds on resource usage of functional p ...

EPFL2017

The roles of coupling and the deviation matrix in determining the value of capacity in M/M/1/C queues

Sophie Myriam Hautphenne

In an M/M/1/C queue, customers are lost when they arrive to find C customers already present. Assuming that each arriving customer brings a certain amount of revenue, we are interested in calculating the value of an extra waiting place in terms of the expe ...

Springer Verlag2016

Design of Optimal Traffic Flow Control at Intersection with Regard for Queue Length Constraints

Jack Haddad

Consideration was given to a well-known problem of traffic control at an individual intersection with minimal total delay. The constraints on control (duration of green light in the main direction) and phase variables (queue lengths along each direction) w ...

2011

Decision Procedures for Algebraic Data Types with Abstractions

Viktor Kuncak, Philippe Paul Henri Suter, Mirco Dotta

We describe a family of decision procedures that extend the decision procedure for quantifier-free constraints on recursive algebraic data types (term algebras) to support recursive abstraction functions. Our abstraction functions are catamorphisms (term a ...

2010

Stability and bounds in aggregate scheduling networks

Gianluca Rizzo

We study networks of FIFO nodes, where flows are constrained by arrival curves. A crucial question with these networks is: Can we derive a bound to the maximum delay that a packet can experience when traversing the network, and to the maximum queue size at ...

EPFL2008

Full Functional Verification of Linked Data Structures

Viktor Kuncak

We present the first verification of full functional correctness for a range of linked data structure implementations, including mutable lists, trees, graphs, and hash tables. Specifically, we present the use of the Jahob verification system to verify form ...

2008

On Optimal Replication Group Splits in P2P Data Stores Based on the Hypercube

P2P data stores excel if availability of inserted data items must be guaranteed. Their inherent mechanisms to counter peer pop- ulation dynamics make them suitable for a wide range of application domains. This paper presents and analyzes the split maintena ...

GI2007