Arrow Research search

Author name cluster

Moti Medina

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

MFCS Conference 2023 Conference Paper

Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations

  • Noy Biton
  • Reut Levi
  • Moti Medina

We study the problem of finding a Hamiltonian cycle under the promise that the input graph has a minimum degree of at least n/2, where n denotes the number of vertices in the graph. The classical theorem of Dirac states that such graphs (a. k. a. Dirac graphs) are Hamiltonian, i. e. , contain a Hamiltonian cycle. Moreover, finding a Hamiltonian cycle in Dirac graphs can be done in polynomial time in the classical centralized model. This paper presents a randomized distributed CONGEST algorithm that finds w. h. p. a Hamiltonian cycle (as well as maximum matching) within O(log n) rounds under the promise that the input graph is a Dirac graph. This upper bound is in contrast to general graphs in which both the decision and search variants of Hamiltonicity require Ω̃(n²) rounds, as shown by Bachrach et al. [PODC'19]. In addition, we consider two generalizations of Dirac graphs: Ore graphs and Rahman-Kaykobad graphs [IPL'05]. In Ore graphs, the sum of the degrees of every pair of non-adjacent vertices is at least n, and in Rahman-Kaykobad graphs, the sum of the degrees of every pair of non-adjacent vertices plus their distance is at least n+1. We show how our algorithm for Dirac graphs can be adapted to work for these more general families of graphs.

Details

I&C Journal 2018 Journal Article

Best of two local models: Centralized local and distributed local algorithms

  • Guy Even
  • Moti Medina
  • Dana Ron

We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in log ⁎ ⁡ n, where n is the number of vertices of the input graph. The recursive centralized local improvement technique by Nguyen and Onak (FOCS 2008) is employed to obtain a distributed approximation scheme for maximum (weighted) matching.

Details DOI

TCS Journal 2013 Journal Article

Competitive and deterministic embeddings of virtual networks

  • Guy Even
  • Moti Medina
  • Gregor Schaffrath
  • Stefan Schmid

Network virtualization is an important concept to overcome the ossification of today’s Internet as it facilitates innovation also in the network core and as it promises a more efficient use of the given resources and infrastructure. Virtual networks (VNets) provide an abstraction of the physical network: multiple VNets may cohabit the same physical network, but can be based on completely different protocol stacks (also beyond IP). One of the main challenges in network virtualization is the efficient admission control and embedding of VNets. The demand for virtual networks (e. g. , for a video conference) can be hard to predict, and once the request is accepted, the specification/QoS guarantees must be ensured throughout the VNet’s lifetime. This requires an admission control algorithm which only selects high-benefit VNets in times of scarce resources, and an embedding algorithm which realizes the VNet in such a way that the likelihood that future requests can be embedded as well is maximized. This article describes a generic algorithm for the online VNet embedding problem which does not rely on any knowledge of the future VNet requests but whose performance is competitive to an optimal offline algorithm that has complete knowledge of the request sequence in advance: the so-called competitive ratio is, loosely speaking, logarithmic in the sum of the resources. Our algorithm is generic in the sense that it supports multiple traffic models, multiple routing models, and even allows for nonuniform benefits and durations of VNet requests.

Details DOI

TCS Journal 2012 Journal Article

Revisiting randomized parallel load balancing algorithms

  • Guy Even
  • Moti Medina

We deal with the well studied allocation problem of assigning n balls to n bins so that the maximum number of balls assigned to the same bin is minimized. We focus on randomized, constant-round, distributed, asynchronous algorithms for this problem. Adler et al. (1998) [1] presented lower bounds and upper bounds for this problem. A similar lower bound appears in Berenbrink et al. (1999) [2]. The general lower bound is based on a topological assumption. Our first contribution is the observation that the topological assumption does not hold for two algorithms presented by Adler etal. (1998) [1]. We amend this situation by presenting proofs of the lower bound for these two specific algorithms. We present an algorithm in which a ball that was not allocated in the first round retries with a new choice in the second round. We present tight bounds on the maximum load obtained by our algorithm. The analysis is based on analyzing the expectation and transforming it to a bound with high probability using martingale tail inequalities. Finally, we present a 3-round heuristic with a single synchronization point. We conducted experiments that demonstrate its advantage over parallel algorithms for 1 0 6 ≤ n ≤ 8 ⋅ 1 0 6 balls and bins. In fact, the obtained maximum load meets the best experimental results for sequential algorithms.

Details DOI

TCS Journal 2011 Journal Article

Parallel randomized load balancing: A lower bound for a more general model

  • Guy Even
  • Moti Medina

We extend the lower bound of Adler et al. (1998) [1] and Berenbrink et al. (1999) [2] for parallel randomized load balancing algorithms. The setting in these asynchronous and distributed algorithms is of n balls and n bins. The algorithms begin by each ball choosing d bins independently and uniformly at random. The balls and bins communicate to determine the assignment of each ball to a bin. The goal is to minimize the maximum load, i. e. , the number of balls that are assigned to the same bin. In Adler et al. (1998) [1] and Berenbrink et al. (1999) [2], a lower bound of Ω ( log n / log log n r ) is proved if the communication is limited to r rounds. Three assumptions appear in the proofs in Adler et al. (1998) [1] and Berenbrink et al. (1999) [2]: the topological assumption, random choices of confused balls, and symmetry. The topological assumption states that each ball’s decision is based only on collisions between choices of balls. The confused ball assumption states that if a ball obtains the same topological information from all its chosen bins, then the ball commits to one of the chosen bins by flipping a fair coin. The symmetry assumption states that all the balls run identical algorithms, the same assumption holds for the bins. We extend the proof of the lower bound so that it holds without these three assumptions. This lower bound applies to every parallel randomized load balancing algorithm we are aware of (Adler et al. , 1998 [1]; Berenbrink et al. , 1999 [2]; Stemann, 1996 [3]; Even and Medina, 2009 [4]).

Details DOI
v2026.09.13