Troyan Monastery

If you are in northern Bulgarian, I recommend stopping by Troyan Monastery.  It is definitely worth a couple of hours of your time.

Walking up to it, the entrance is fairly simplistic, which is to be expected from a monastery.

The entrance to Troyan Monastery; very simple, as expected. However, your attention diverts to the mosaic to the left.
The entrance to Troyan Monastery; very simple, as expected. However, your attention diverts to the mosaic to the left.

The mosaic on top of the left entrance doorway is a new modern day recreation of a roman style mosaic of virgin Mary with baby Christ.

Continue reading “Troyan Monastery”

Hitar Petar

Hitar Pitar is a quaint little restaurant and hotel in the village of Beli Osam in Bulgaria (close to the Troyan Monastery). It has a neat collection of decorative artifacts that make for an interesting collection of photos.

The restaurant is located on the banks of the Beli Osam river.

Hitar Petar restaurant as seen from across the river
Hitar Petar restaurant as seen from across the river

Continue reading “Hitar Petar”

Tsarevets: a photo essay

Tsarevets fortress was a medieval stronghold of the erstwhile Second Bulgarian Empire located near the city of Veliko Tarnovo (which was also the capital city of that empire). While the fortress is in ruins, the recent reconstructions and restorations make it worth visiting.

View of the fortress from the city.
View of the fortress from the city.

The fortress itself is situated on top of a hill of the same name. The stronghold consisted of two forts, one on each hill. You can see the ruins of the second fort on the hill in the left hand side of the photograph above. The second fort is not reconstructed well enough to attract tourists.

Let’s step inside.

Continue reading “Tsarevets: a photo essay”

Airfare booking and pricing, demystified!

I work on Google’s air travel infrastructure team, which powers Google Flight Search. Last month, I did a #HangoutOnAir with university students in India. The main focus of that talk was to introduce the students to the sort of challenges that we face. The talk is up on Google Plus, and has since been split into two parts.

In the first part (which is targeted for a general audience), I cover the fundamentals of flight booking, tackling issues like routing (10,000+ routes for SFO-JFK!?), seat availability, fare codes, pricing and more. It answers questions such as, “why did you pay $50 more than the person sitting next you in the plane for the same ticket?”, and “why  are tickets on this flight from SFO to JFK available when flying SFO to BOS via JFK, but not available for a non-stop flight from SFO to JFK?”

You can check out part 1 [here].

In the second part, I get into the computer sciency details of the complexity of airfare search (even the simplest versions of this problem are NP-hard), and provide a (over)simplified description of QPX — the engine that Google uses to search and price airfare tickets. This talk is targeted at computer science students and professional.

Check out part 2 [here].

Solvability-based comparison of failure detectors

New paper in NCA 2014, with Josef Widder.

Abstract: Failure detectors are oracles that have been introduced to provide processes in asynchronous systems with information about faults. This information can then be used to solve problems otherwise unsolvable in asynchronous systems. A natural question is on the “minimum amount of information” a failure detector has to provide for a given problem. This question is classically addressed using a relation that states that a failure detector D is stronger (that is, provides “more, or better, information”) than a failure detector D’ if D can be used to implement D’. It has recently been shown that this classic implementability relation has some drawbacks. To overcome this, different relations have been defined, one of which states that a failure detector D is stronger than D’ if D can solve all the time-free problems solvable by D’. In this paper we compare the implementability-based hierarchy of failure detectors to the hierarchy based on solvability. This is done by introducing a new proof technique for establishing the solvability relation. We apply this technique to known failure detectors from the literature and demonstrate significant differences between the hierarchies.

A preprint is available on ArXiv; click here to access it.