3 citations · 12 across the 19 of their papers we have counts for
29 papers
Metastability-Containing Turing Machines
Johannes Bund, Amir Leshem, Moti Medina
Metastability is a spurious mode of operation in digital signals, where an electrical signal fails to settle into a stable state within a specified time, leading to uncertainty and…
Codes for Metastability-Containing Addition
Johannes Bund, Christoph Lenzen, Moti Medina
We investigate the fundamental task of addition under uncertainty, namely, addends that are represented as intervals of numbers rather than single values. One potential source of s…
PALS: Distributed Gradient Clocking on Chip
Johannes Bund, Matthias Függer, Moti Medina
Consider an arbitrary network of communicating modules on a chip, each requiring a local signal telling it when to execute a computational step. There are three common solutions to…
Robust Routing Made Easy: Reinforcing Networks Against Non-Benign Faults
Christoph Lenzen, Moti Medina, Mehrdad Saberi +1
With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important…
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 , where denotes the number of vertices in the g…
Synchronizer-Free Digital Link Controller
Johannes Bund, Matthias Függer, Christoph Lenzen +1
This work presents a producer-consumer link between two independent clock domains. The link allows for metastability-free, low-latency, high-throughput communication by slight adju…
PALS: Plesiochronous and Locally Synchronous Systems
Johannes Bund, Matthias Függer, Christoph Lenzen +2
Consider an arbitrary network of communicating modules on a chip, each requiring a local signal telling it when to execute a computational step. There are three common solutions to…
Distributed Testing of Graph Isomorphism in the CONGEST model
Reut Levi, Moti Medina
In this paper we study the problem of testing graph isomorphism (GI) in the CONGEST distributed model. In this setting we test whether the distributive network, , is isomorphi…
Optimal Metastability-Containing Sorting via Parallel Prefix Computation
Johannes Bund, Christoph Lenzen, Moti Medina
Friedrichs et al. (TC 2018) showed that metastability can be contained when sorting inputs arising from time-to-digital converters, i.e., measurement values can be correctly sorted…
Small Hazard-free Transducers
Johannes Bund, Christoph Lenzen, Moti Medina
Ikenmeyer et al. (JACM'19) proved an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions. This raises th…
Property Testing of Planarity in the CONGEST model
Reut Levi, Moti Medina, Dana Ron
We give a distributed algorithm in the {\sf CONGEST} model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et a…
Graph Ranking and the Cost of Sybil Defense
Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg +5
Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, s…
Optimal Metastability-Containing Sorting Networks
Johannes Bund, Christoph Lenzen, Moti Medina
When setup/hold times of bistable elements are violated, they may become metastable, i.e., enter a transient state that is neither digital 0 nor 1. In general, metastability cannot…
Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model
Guy Even, Reut Levi, Moti Medina
In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided error testing algorithms in the g…
Robust Routing Made Easy
Christoph Lenzen, Moti Medina, Mehrdad Saberi +1
With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important…
Competitive Path Computation and Function Placement in SDNs
Guy Even, Moti Medina, Boaz Patt-Shamir
We consider a task of serving requests that arrive in an online fashion in Software-Defined Networks (SDNs) with network function virtualization (NFV). Each request specifies an ab…
A Constant Approximation Algorithm for Scheduling Packets on Line Networks
Guy Even, Moti Medina, Adi Rosén
In this paper we improve the approximation ratio for the problem of scheduling packets on line networks with bounded buffers, where the aim is that of maximizing the throughput. Ea…
Sublinear Random Access Generators for Preferential Attachment Graphs
Guy Even, Reut Levi, Moti Medina +1
We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space and random…
Non-Local Probes Do Not Help with Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi +2
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computi…
Better Online Deterministic Packet Routing on Grids
Guy Even, Moti Medina, Boaz Patt-Shamir
We consider the following fundamental routing problem. An adversary inputs packets arbitrarily at sources, each packet with an arbitrary destination. Traffic is constrained by link…
Online Packet-Routing in Grids with Bounded Buffers
Guy Even, Moti Medina
We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model \cite{AKOR}. In this model the netw…
Distributed Maximum Matching in Bounded Degree Graphs
Guy Even, Moti Medina, Dana Ron
We present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted c…
Best of Two Local Models: Local Centralized and Local Distributed 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 algo…
A Nonmonotone Analysis with the Primal-Dual Approach: online routing of virtual circuits with unknown durations
Guy Even, Moti Medina
We address the question of whether the primal-dual approach for the design and analysis of online algorithms can be applied to nonmonotone problems. We provide a positive answer by…