Amos Korman

AAMAS Conference 2026 Conference Paper

Fast and Robust Information Spreading in the Noisy PULL Model

• Niccolò D'archivio
• Amos Korman
• Emanuele Natale
• Robin Vacus

Efficient information spreading in stochastic multi-agent systems is a core challenge when communication is noisy, bandwidth-limited, and agents lack global coordination. Yet biological systems—such as antcoloniesandfishschools—routinelyovercometheseconstraints: a small number of informed individuals can reliably guide large, uncoordinated populations using minimal, noisy signals. Motivated by these observations, we investigate how reliable information dissemination can be achieved in bio-inspired stochastic settings with limited communication and no global control. We analyze the noisy PULL(ℎ) model, covering a general setting that spans from rumor spreading to majority consensus: a subset of source agents hold initial preferences, and the goal is to converge to the majority preference. Agents passively observe noisy messages from ℎ randomly sampled peers per round. Prior work shows that convergence requires Ω(𝑛/ℎ) rounds even under favorable conditions. We ask: how far can one push simplicity—no synchronization and minimal message size—without compromising convergence speed? We present a quasi self-stabilizing protocol using only 2-bit messages that converges from arbitrary initial states despite severe noise and asynchrony. It achieves optimal convergence time 𝑂((𝑛/ℎ) log𝑛) with high probability, and𝑂(log𝑛) time in the fully connected case ℎ = 𝑛. A key subroutine is an even simpler 1-bit protocolassumingsimultaneousstart, basedonanaturaltwo-phase “listen-then-amplify” mechanism reminiscent of biological strategies. Together, our results connect biologically inspired heuristics with provable guarantees for robust, efficient information dissemination in highly unreliable and uncoordinated systems.

IJCAI Conference 2023 Conference Paper

On the Role of Memory in Robust Opinion Dynamics

• Luca Becchetti
• Andrea Clementi
• Amos Korman
• Francesco Pasquale
• Luca Trevisan
• Robin Vacus

We investigate opinion dynamics in a fully-connected system, consisting of n agents, where one of the opinions, called correct, represents a piece of information to disseminate. One source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal of the remaining agents is to quickly agree on this correct opinion. At each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of l random agents and then updates its opinion according to some rule. We consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample. This setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules. Qualitatively speaking, we show that lack of memory prevents efficient convergence. Specifically, we prove that any dynamics requires Omega(n^2) expected time, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i. e. , the case l=n. Conversely, we prove that the simple voter model (in which l=1) correctly solves the problem, while almost matching the aforementioned lower bound. These results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may require the use of memory.

TCS Journal 2017 Journal Article

Fast rendezvous on a cycle by agents with different speeds

• Ofer Feinerman
• Amos Korman
• Shay Kutten
• Yoav Rodeh

The difference between the speed of the actions of different processes is typically considered as an obstacle that makes the achievement of cooperative goals more difficult. In this work, we aim to highlight potential benefits of such asynchrony phenomena to tasks involving symmetry breaking. Specifically, in this paper, identical (except for their speeds) mobile agents are placed at arbitrary locations on a (continuous) cycle of length n and use their speed difference in order to rendezvous fast. We normalize the speed of the slower agent to be 1, and fix the speed of the faster agent to be some c > 1. (An agent does not know whether it is the slower agent or the faster one.) The straightforward distributed-race (DR) algorithm is the one in which both agents simply start walking until rendezvous is achieved. It is easy to show that, in the worst case, the rendezvous time of DR is n / ( c − 1 ). Note that in the interesting case, where c is very close to 1 (e. g. , c = 1 + 1 / n k ), this bound becomes huge. Our first result is a lower bound showing that, up to a multiplicative factor of 2, this bound is unavoidable, even in a model that allows agents to leave arbitrary marks (the white board model), even assuming sense of direction, and even assuming n and c are known to agents. That is, we show that under such assumptions, the rendezvous time of any algorithm is at least n 2 ( c − 1 ) if c ⩽ 3 and slightly larger (specifically, n c + 1 ) if c > 3. We then manage to construct an algorithm that precisely matches the lower bound for the case c ⩽ 2, and almost matches it when c > 2. Moreover, our algorithm performs under weaker assumptions than those stated above, as it does not assume sense of direction, and it allows agents to leave only a single mark (a pebble) and only at the place where they start the execution. Finally, we investigate the setting in which no marks can be used at all, and show tight bounds for c ⩽ 2, and almost tight bounds for c > 2.

SODA Conference 2017 Conference Paper

Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

• Lucas Boczkowski
• Amos Korman
• Emanuele Natale

This paper considers the basic PULL model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of n agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast (also termed Rumor Spreading). We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. In particular, the specification of who is a source and what is its initial input bit may be set by an adversary. We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property (called “the bitwise-independence property” ) that uses ℓ-bits messages to one that uses only log ¿-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer T, within Õ(log n log T ) rounds w. h. p. , and using messages that contain 3 bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing Majority Bit Dissemination protocol which converges in Õ(log n ) time, w. h. p. , on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.

STOC Conference 2016 Conference Paper

Parallel exhaustive search without coordination

• Pierre Fraigniaud
• Amos Korman
• Yoav Rodeh

We analyse parallel algorithms in the context of exhaustive search over totally ordered sets. Imagine an infinite list of “boxes”, with a “treasure” hidden in one of them, where the boxes’ order reflects the importance of finding the treasure in a given box. At each time step, a search protocol executed by a searcher has the ability to peek into one box, and see whether the treasure is present or not. Clearly, the best strategy of a single searcher would be to open the boxes one by one, in increasing order. Moreover, by equally dividing the workload between them, k searchers can trivially find the treasure k times faster than one searcher. However, this straightforward strategy is very sensitive to failures ( e.g., crashes of processors), and overcoming this issue seems to require a large amount of communication. We therefore address the question of designing parallel search algorithms maximizing their speed-up and maintaining high levels of robustness , while minimizing the amount of resources for coordination. Based on the observation that algorithms that avoid communication are inherently robust, we focus our attention on identifying the best running time performance of non-coordinating algorithms. Specifically, we devise non-coordinating algorithms that achieve a speed-up of 9/8 for two searchers, a speed-up of 4/3 for three searchers, and in general, a speed-up of k /4(1+1/ k ) 2 for any k ≥ 1 searchers. Thus, asymptotically, the speed-up is only four times worse compared to the case of full coordination. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm can achieve better speed-ups. Our algorithms are surprisingly simple and hence applicable. However they are memory intensive and so we suggest a practical, memory efficient version, with a speed-up of ( k 2 − 1)/4 k . That is, it is only a factor of ( k +1)/( k −1) slower than the optimal algorithm. Overall, we highlight that, in faulty contexts in which coordination between the searchers is technically difficult to implement, intrusive with respect to privacy, and/or costly in term of resources, it might well be worth giving up on coordination, and simply run our non-coordinating exhaustive search algorithms.

I&C Journal 2013 Journal Article

Controller and estimator for dynamic networks

• Amos Korman
• Shay Kutten

Afek, Awerbuch, Plotkin, and Saks identified an important fundamental problem inherent to distributed networks, which they called the Resource Controller problem. Consider, first, the problem in which one node (called the ‘root’) is required to estimate the number of events that occurred all over the network. This counting problem can be viewed as a useful variant of the heavily studied and used task of topology update (that deals with collecting all remote information). The Resource Controller problem generalizes the counting problem: such remote events are considered as requests, and the counting node, i. e. , the ‘root’, also issues permits for the requests. That way, the number of requests granted can be controlled (bounded). An efficient Resource Controller was constructed in the paper by Afek et al. , and it can operate on a dynamic network assuming that the network is spanned by a tree that may only grow, and only by allowing leaves to join the tree. In contrast, the Resource Controller presented here can operate under a more general dynamic model, allowing the spanning tree of the network to undergo both insertions and deletions of both leaves and internal nodes. Despite the more dynamic network model we allow, the message complexity of our controller is never more than the message complexity of the more restricted controller. All the applications for the controller of Afek et al. can be used also with our controller. Moreover, with the same message complexity, our controller can handle these applications under the more general dynamic model mentioned above. In particular, the new controller can be transformed into an efficient size-estimation protocol, i. e. , a protocol allowing all nodes to maintain a constant factor estimation of the number of nodes in the dynamically changing network. Informally, the resulting new size-estimation protocol uses O ( log 2 n ) amortized message complexity per topological change (assuming that the number of changes in the network size is “not too small”), where n is the current number of nodes in the network. An application of the size estimation of Afek et al. was to solve agreement in the case of initial faults (Fischer, Lynch, and Paterson) and leader election under initial faults (Bar-Yehuda and Kutten). Hence, the controllers in this paper can be useful for these applications too.

SODA Conference 2011 Conference Paper

Approximating the Statistics of various Properties in Randomly Weighted Graphs

• Yuval Emek
• Amos Korman
• Yuval Shavitt

STOC Conference 2011 Conference Paper

Distributed verification and hardness of distributed approximation

• Atish Das Sarma
• Stephan Holzer
• Liah Kor
• Amos Korman
• Danupon Nanongkai
• Gopal Pandurangan
• David Peleg
• Roger Wattenhofer

We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected (every node knows in the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication.

FOCS Conference 2011 Conference Paper

Local Distributed Decision

• Pierre Fraigniaud
• Amos Korman
• David Peleg

A central theme in distributed network algorithms concerns understanding and coping with the issue of {\em locality}. Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for \emph{distributed decision problems}. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard $\cal{LOCAL}$ model of computation and define $LD(t)$ (for {\em local decision}) as the class of decision problems that can be solved in $t$ communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class $BPLD(t, p, q)$, containing all languages for which there exists a randomized algorithm that runs in $t$ rounds, accepts correct instances with probability at least $p$ and rejects incorrect ones with probability at least $q$. We show that $p^2+q = 1$ is a threshold for the containment of $LD(t)$ in $BPLD(t, p, q)$. More precisely, we show that there exists a language that does not belong to $LD(t)$ for any $t=o(n)$ but does belong to $BPLD(0, p, q)$ for any $p, q\in (0, 1]$ such that $p^2+q\leq 1$. On the other hand, we show that, restricted to hereditary languages, $BPLD(t, p, q) = LD(O(t))$, for any function $t$ and any $p, q\in (0, 1]$ such that $p^2+q&gt, 1$. In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide \emph{all} languages \emph{in constant time}. Finally, we introduce the notion of local reduction, and establish some completeness results.

TCS Journal 2011 Journal Article

Online computation with advice

• Yuval Emek
• Pierre Fraigniaud
• Amos Korman
• Adi Rosén

We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice is a function, defined by the online algorithm, of the whole request sequence. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b = 0 corresponds to the classical online model, and b = ⌈ log ∣ A ∣ ⌉, where A is the algorithm’s action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones. In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k -server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1 ≤ b ≤ Θ ( log n ), where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio Ω ( log ( n ) / b ) and we present a deterministic online algorithm for MTS with competitive ratio O ( log ( n ) / b ). For the k -server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k O ( 1 / b ) for any choice of Θ ( 1 ) ≤ b ≤ log k.

STOC Conference 2010 Conference Paper

An optimal ancestry scheme and small universal posets

• Pierre Fraigniaud
• Amos Korman

In this paper, we solve the ancestry problem, which was introduced more than twenty years ago by Kannan et al. [STOC '88], and is among the most well-studied problems in the field of informative labeling schemes. Specifically, we construct an ancestry labeling scheme for n-node trees with label size log 2 n + O(log log n) bits, thus matching the log 2 n + Ω(log log n) bits lower bound given by Alstrup et al. [SODA '03]. Besides its optimal label size, our scheme assigns the labels in linear time, and guarantees that any ancestry query can be answered in constant time. In addition to its potential impact in terms of improving the performances of XML search engines, our ancestry scheme is also useful in the context of partially ordered sets. Specifically, for any fixed integer k, our scheme enables the construction of a universal poset of size O(n k log 4k n) for the family of n-element posets with tree-dimension at most k. This bound is almost tight thanks to a lower bound of n k-o(1) due to Alon and Scheinerman [Order '88].

SODA Conference 2010 Conference Paper

Compact Ancestry Labeling Schemes for XML Trees

• Pierre Fraigniaud
• Amos Korman

TCS Journal 2009 Journal Article

A note on models for graph representations

• Amos Korman
• Shay Kutten

This paper is intended more to ask questions than give answers. Specifically, we consider models for labeling schemes, and discuss issues regarding the number of labels consulted vs. the sizes of the labels. Recently, quite a few papers studied methods for representing network properties by assigning informative labels to the vertices of a network. Consider a graph function f on pairs of vertices (for example, f can be the distance function). In an f -labeling scheme, the labels are constructed in such a way so that given the labels of any two vertices u and v, one can compute the function f ( u, v ) (e. g. the graph distance between u and v ) just by looking at these two labels. Some very involved lower bounds for the sizes of the labels were proven. Also, some highly sophisticated labeling schemes were developed to ensure short labels. In this paper, we demonstrate that such lower bounds are very sensitive to the number of vertices consulted. That is, we show several constructions of such labeling schemes that beat the lower bounds by large margins. Moreover, as opposed to the strong technical skills that were needed to develop the traditional labeling schemes, most of our schemes are almost trivial. The catch is that in our model, one needs to consult the labels of three vertices instead of two. That is, a query about vertices u and v can access also the label of some third vertex w ( w is determined by the labels of u and v ). More generally, we address the model in which a query about vertices u and v can access also the labels of c other vertices. We term our generalized model labeling schemes with queries. The main importance of this model is theoretical. Specifically, this paper may serve as a first step towards investigating different tradeoffs between the amount of labels consulted and the amount of information stored at each vertex. As we show, if all vertices can be consulted then the problem almost reduces to the corresponding sequential problem. On the other hand, consulting just the labels of u and v (or even just the label of u ) reduces the problem to a purely distributed one. Therefore, in a sense, our model spans a range of intermediate notions between the sequential and the distributed settings. In addition to the theoretical interest, we also show cases that schemes constructed for our model can be translated to the traditional model or to the sequential model, thus, simplifying the construction for those models as well. For implementing query labeling schemes in a distributed environment directly, we point at a potential usage for some new paradigms that became common recently, such as P2P and overlay networks.

I&C Journal 2007 Journal Article

Labeling schemes for weighted dynamic trees

• Amos Korman
• David Peleg

A Distance labeling scheme is a type of localized network representation in which short labels are assigned to the vertices, allowing one to infer the distance between any two vertices directly from their labels, without using any additional information sources. As most applications for network representations in general, and distance labeling schemes in particular, concern large and dynamically changing networks, it is of interest to focus on distributed dynamic labeling schemes. The paper considers dynamic weighted trees where the vertices of the trees are fixed but the (positive integral) weights of the edges may change. The two models considered are the edge-dynamic model, where from time to time some edge changes its weight by a fixed quanta, and the increasing-dynamic model in which edge weights can only grow. The paper presents distributed approximate distance labeling schemes for the two dynamic models, which are efficient in terms of the required label size and communication complexity involved in updating the labels following the weight changes.

SODA Conference 2002 Conference Paper

Labeling schemes for flow and connectivity

• Michal Katz
• Nir A. Katz
• Amos Korman
• David Peleg