I was unsuccessful trying to reproduce this on M58. My steps are:

1. Install M58 Chrome onto Android device.
2. Sign into google account, enable sync for all types.
3. Perform a google search for "foo".
4. Close the tab with the search for "foo". (This one is important, otherwise a reload of that page will re-write to history)
5. Open History page, see 'foo - Google Search'
6. Switch to Android's Settings > More > toggle on Airplane mode
7. Switch back to Chrome, open History page, 'CLEAR BROWSING DATA...' button > 'CLEAR DATA' button (Leaving all the check boxes checked and the time range being since the 'beginning of time')
8. Verify History page is empty.
9. Switch to Android's Settings > More > toggle off Airplane mode.
10. Switch back to Chrome, close and reopen History page, verify there are still no entries.

If you're doing things differently than this and you think it will repro with adjusted steps, please let me know how to test things differently.

My understanding of the way this should work is that there are two data sources we need to modify when we delete all your history, and that's the local history db and sync's history data. The local history db is easy, it doesn't need network connectivity. But sync does, because not all your data is simply on your device. So when you delete history from the beginning of time, we create a HISTORY_DELETE_DIRECTIVES object that is then stored in your local sync db. When you connect your device to the internet at a later point, that directive gets sent out and propagates this deletion.

Here you said the case of one search history "foo". If there are more search history in a particular tab  and you are deleting the search history when you are offline without deleting the tab.As you said because the tab is still there reloading of previous page should be take place when you are connected to internet and it will overwrite the history.(it should be only for the case of last history).But all the history of the tab will be overwritten.

Thank you for providing more feedback. Adding requester "skym@chromium.org" to the cc list and removing "Needs-Feedback" label.

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

Perform this steps.
1.make a new tab on chrome
2.search "ABC"
3.then search "cde"
4.then check the history which showing these search labels 
5.then delete the current tab when you are 'ONLINE'
6.then go to airplane mode
7.then again open history and delete the history corresponding to "ABC" and "cde"
8.go online 
9.open search history
10."ABC" and "cde" search labels will still there....

This contradicts what you said.is,even after the deletion of tab the problem exists....
In this case How can be history overwritten without the presence of corresponding tab???...

I have a suggestion for this problem.
Maintain 2 local history db .When online operations takes place both will have same content.when offline deletion takes place make only one of them to get modified. Then when we connect to internet ,before synchronization we need to check whether these 2 are of same content.if both are same synchronization can be done without any problem.Otherwise the synchronization db should be updated with the changes done on local db and then only it can do synchronization without any problem.

Its only a suggestion.I don't know weather it is possible or not :-)

Sorry for the slow responses here. Still investigating. Progress so far:

I was able to reproduce this problem by following steps from #5. The difference is that deleting single history entries while offline does not work correctly, while using the 'CLEAR BROWSING DATA' button (as in #2) does work.

Bizarrely though, this doesn't seem to happen on desktop (Linux). I've only reproduced this issue on Android so far. While the timestamps in the directives are in microseconds, it seems on Android the last 3 digits get zeroed out. I've been trying to explain how this discrepancy could cause this behavior but have been unsuccessful so far.

It looks like handling deletions while offline for the current device was a primary design goal when sync history was added. So this is definitely something we want to understand and fix. It seems that upon a history page deletion of history entries (not time range), we do two things

1) Create a deletion directive in sync. This always get sent out when re-connecting to the internet.
2) Send a deletion request to the WebHistory service, see https://cs.chromium.org/chromium/src/components/history/core/browser/web_history_service.cc?l=422 . This piece doesn't happen if you're offline, and I'm a bit confused exactly why we even bother with this step. Perhaps it's to better handle deletes across multiple clients (which we only aim to do best effort on).

Working theory is that the deletion directives through sync are broken for Android because of the zeroed out timestmaps, and solely relies on the WebHistory request. Need to verify.

I have another suggestion.Take a copy of sync data before you go offline named it as sync_copy. Then ,when a deletion takesplace at offline on local device corresponding request to sync_copy is sent and perform deletions on sync_copy.
(then perform the steps as you said with slight modifications)
1) Create a deletion directive in sync(in original data). This always get sent out to sync_copy when re-connecting to the internet.
2) Send a deletion request to the WebHistory service if it needs deletion.
3)then perform deletion on sync

The theory proposed in #8 seems to be panning out. Adding print statements to https://cs.chromium.org/chromium/src/chrome/browser/android/history/browsing_history_bridge.cc?l=112 I can see that the numbers when in 'java time' have 3 less digits of resolution. If we can simply avoid dropping those 3 digits, everything should work again. Unclear how difficult this will be to do.

The reason the WebHistory requests still work on Android (when online), is that they do not use a 'global_id' timestamp, but pass the URL and a large time range.

Alternatively we could make the async logic that converts deletion directives to WebHistory deletes be more permissive, but I think this approach has a slew of downsides. Potential for false/incorrect deletions, and the multi device deletions story becomes worse. We have microsecond granularity on these "ids" for a reason.

It seems desktop platforms use Javascript time as opposed to Java time, see conversion definitions at https://cs.chromium.org/chromium/src/base/time/time.h?l=497

Both Javascript and Java are using ms, but Javascript stores this in a double instead of int64, and so we have decimal values. And it converts back without loss.

For example, 13141440986109460 (C++) <--> 1496967386109.459961 (Javascript)

Looks like native UI was actually added to the History page quite recently, the handler in question was created in https://codereview.chromium.org/2542203002 and base/time.h's FromJavaTime() was created in https://codereview.chromium.org/2548213005/

I'm still not sure how to change the Java side, +twellington who might have a suggestion. I'm thinking of trying to just pass both timestamps, and only pass C++ timestamp back. Might be a little ugly.

We should probably also add a note ToJavaTime()/FromJavaTime() that round-tripping is lossy.

I'm fine with passing an extra value back for the Java timestamp and C++ timestamp. JNI has a jdouble that could be used to pass a double to/from Java if that preserves precision.  We could distinguish them as "javaTimestamps" and "nativeTimestamps" or something like that and document why both are needed.

The int64 timestamp is used on the Java side to create a Timestamp (which is used for bucketing); Timestamp object creation requires a millisecond value, so I'd like to keep that.

Any progress??

 Issue 730943  has been merged into this issue.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/209633050f6d05fff54e8dcd2195743858b33125

commit 209633050f6d05fff54e8dcd2195743858b33125
Author: skym <skym@chromium.org>
Date: Mon Jun 12 20:55:04 2017

Send microsecond resolution timestamps to Java history page so they can be sent back.

When an entry on the history page is deleted, we create history
deletion directives that are sent through sync. These are required to
support offline history deletions, and make sure these are properly
propagated. However, these deletion directives rely on exact matches in
timestamps, which are in microseconds since the epoch.

The History page on Android converted microsecond timestamps to
millisecond timestamps for Java compatibility, but when these
timestamps were handed to the logic that created history deletion
directives, they were now slightly off. This change simply plumbs
through microsecond timestamps through the java code and back.

BUG= 729020 

Review-Url: https://codereview.chromium.org/2935783002
Cr-Commit-Position: refs/heads/master@{#478756}

[modify] https://crrev.com/209633050f6d05fff54e8dcd2195743858b33125/chrome/android/java/src/org/chromium/chrome/browser/history/BrowsingHistoryBridge.java
[modify] https://crrev.com/209633050f6d05fff54e8dcd2195743858b33125/chrome/android/java/src/org/chromium/chrome/browser/history/HistoryItem.java
[modify] https://crrev.com/209633050f6d05fff54e8dcd2195743858b33125/chrome/android/javatests/src/org/chromium/chrome/browser/history/HistoryActivityTest.java
[modify] https://crrev.com/209633050f6d05fff54e8dcd2195743858b33125/chrome/android/javatests/src/org/chromium/chrome/browser/history/HistoryAdapterTest.java
[modify] https://crrev.com/209633050f6d05fff54e8dcd2195743858b33125/chrome/android/javatests/src/org/chromium/chrome/browser/history/StubbedHistoryProvider.java
[modify] https://crrev.com/209633050f6d05fff54e8dcd2195743858b33125/chrome/browser/android/history/browsing_history_bridge.cc
[modify] https://crrev.com/209633050f6d05fff54e8dcd2195743858b33125/chrome/browser/android/history/browsing_history_bridge.h

To answer comment #14, fix is checked in. Should be picked up by the next Canary build. Closing as such.

This bug requires manual review: M60 has already been promoted to the beta branch, so this requires manual review
Please contact the milestone owner if you have questions.
Owners: amineer@(Android), cmasso@(iOS), josafat@(ChromeOS), bustamante@(Desktop)

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

What to do next?is it rewardable?

To give some justification for the merge, here the user has given us an explicit command to delete a piece of their history. If this doesn't work, it feels very bad from a Privacy perspective. It is important that we do everything we can to respect a user's privacy, and I think merging this back to M60 falls into this bucket.

While it only affects users that are offline, on Android (mobile) it is common to have intermittent internet which would cause this bug to surface.

The risk of the patch is isolated to the chrome://history page on Android. Worst case we show incorrect history or no history at all on the Android history page, or leak memory. This CL is mainly changing how timestamps are passed, which means displaying wrong timestamp, or breaking deletions more/differently.

A lot of what adds to the number of lines in the CL are name changes and test changes. The thrust of it is just that instead of passing a list of millisecond timestamps, we pass 1 millisecond timestamp and a list of microsecond timestamps to Java land. The microsecond timestamps come back, while the millisecond timestamp is used for the logic as before.

Merge approved for M60 branch 3112.  Please merge by 5 PM PT.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb

commit ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb
Author: Sky Malice <skym@chromium.org>
Date: Wed Jun 21 22:22:56 2017

Send microsecond resolution timestamps to Java history page so they can be sent back.

When an entry on the history page is deleted, we create history
deletion directives that are sent through sync. These are required to
support offline history deletions, and make sure these are properly
propagated. However, these deletion directives rely on exact matches in
timestamps, which are in microseconds since the epoch.

The History page on Android converted microsecond timestamps to
millisecond timestamps for Java compatibility, but when these
timestamps were handed to the logic that created history deletion
directives, they were now slightly off. This change simply plumbs
through microsecond timestamps through the java code and back.

BUG= 729020 

Review-Url: https://codereview.chromium.org/2935783002
Cr-Original-Commit-Position: refs/heads/master@{#478756}
Review-Url: https://codereview.chromium.org/2953673002 .
Cr-Commit-Position: refs/branch-heads/3112@{#429}
Cr-Branched-From: b6460e24cf59f429d69de255538d0fc7a425ccf9-refs/heads/master@{#474897}

[modify] https://crrev.com/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb/chrome/android/java/src/org/chromium/chrome/browser/history/BrowsingHistoryBridge.java
[modify] https://crrev.com/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb/chrome/android/java/src/org/chromium/chrome/browser/history/HistoryItem.java
[modify] https://crrev.com/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb/chrome/android/javatests/src/org/chromium/chrome/browser/history/HistoryActivityTest.java
[modify] https://crrev.com/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb/chrome/android/javatests/src/org/chromium/chrome/browser/history/HistoryAdapterTest.java
[modify] https://crrev.com/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb/chrome/android/javatests/src/org/chromium/chrome/browser/history/StubbedHistoryProvider.java
[modify] https://crrev.com/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb/chrome/browser/android/history/browsing_history_bridge.cc
[modify] https://crrev.com/ec2a6b24c7b356aa35cbe950a49bf4cd7f1909bb/chrome/browser/android/history/browsing_history_bridge.h

What is the next action?

I don't think this is a next action. This bug has been fixed, and merged into M60. Thanks for reporting this bug, btw, I'm glad you caught this and we were able to fix this.

In regards to comment #21, I don't believe there are rewards/bounties for anything other than security issues. See https://www.google.com/about/appsecurity/chrome-rewards/index.html

I think it is also a kind of security issue. If a person deletes his browsing history(while offline) or browsed tabs(while offline or online) it is not supposed to exist again on the history page.
The problem here is ,the person wants to hide his data(history). But the browser reveals it..
Since Google account shares all these history informations one who has access to a particular account can also see these histories(deleted).so,don't you think it is also a security issue?

Can I hope any legal appreciation from Google like certificate or other rather than reward?

I visited the Google chrome reward program page through the link you sent.there I could find a FAQ and answer .I show that.

"Q: Will Google reward for bugs that are not specifically listed in the table above?

A: Yes - we're interested in rewarding any information that enables us to better protect our users. All of our reward amounts are based on the quality of the report and the security impact of the bug."

Is there any chance for hopping?