EE Seminar: Efficient Verification in Distributed Systems

12 בדצמבר 2018, 15:00 
חדר 011, בניין כיתות-חשמל 

Speaker: Mor Perry

Ph.D. student under the supervision of Prof. Boaz Patt-Shamir

 

Wednesday, December 12th, 2018 at 15:00
Room 011, Kitot Bldg., Faculty of Engineering

Efficient Verification in Distributed Systems

 

Abstract

 

In every complex system, faults can occur. Detecting faults, in many cases, is the first step in dealing with them. In this work, we focus on efficient detection of faults in distributed systems. A distributed system is a set of interconnected processors. We consider a standard message-passing model of distributed computation, where there is no central control or shared memory, and processors communicate only by sending messages on communication links in synchronous rounds. Distributed verification has received much attention over the years due to its applications to various domains. For example, checking the results obtained from the execution of a distributed program, constructing self-stabilizing algorithms, establishing lower bounds on the time required for distributed approximation, and developing a distributed complexity theory inspired by the sequential complexity theory.

 

In this work, we address the problem of locally verifying global properties of the network, and we study the effect of different network resources and relaxations on the complexity of verification. In particular, we first show that using randomization reduces the communication complexity exponentially. Also, approximations can significantly reduce space and communication complexity. The ability to send a different message on each link is a crucial factor which can greatly reduce the communication complexity of verification as well. Finally, we show that using multiple communication rounds can sometimes reduce space complexity even more than linearly in the number of rounds.

אוניברסיטת תל אביב עושה כל מאמץ לכבד זכויות יוצרים. אם בבעלותך זכויות יוצרים בתכנים שנמצאים פה ו/או השימוש
שנעשה בתכנים אלה לדעתך מפר זכויות, נא לפנות בהקדם לכתובת שכאן >>