Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

TDC Seminar: Fault-Tolerant Labeling and Compact Routing Schemes
event speaker icon
Michal Dory, Haifa University
event date icon
Monday, 08.04.2024, 13:30
event location icon
Zisapel (ECE) 608
Assume that you have a huge graph, where edges and vertices may fail, and you want to answer questions about this graph quickly, without inspecting the whole graph. A fault-tolerant labeling scheme allows us to do just that. It is a distributed data structure, in which each vertex and edge is assigned a short label, such that given the labels of a pair of vertices s,t, and a set of failures F, you can answer questions about s and t in G\F. For example, determine if s and t are connected in G\F, just by looking at their labels.

I will discuss fault-tolerant connectivity labeling schemes for general graphs. I will also show applications for fault-tolerant routing. Here the goal is to provide each vertex a small routing table, such that given these tables we can efficiently route messages in the network, even in the presence of failures.

Based on a joint work with Merav Parter.